Foundations of Computer Science

Presentation on theme: "Foundations of Computer Science"— Presentation transcript:

1 Foundations of Computer Science
Chapter 7 作業系統 計算機概論 第三版 Foundations of Computer Science

2 Chap.5 計算機組織 Chap.4 資料運算 Chap.3 資料的儲存 Chap.2 數目系統 二元樣式 (binary pattern)

3 Machine cycle 機器語言 (machine languages) Chap.7 OS (作業系統) Program (binary pattern) OS (作業系統) Application (應用程式)

4 7.1 簡介 電腦是由兩個主要部分：硬體(hardware)和軟體(software)所構成的系統。
7.1 簡介 電腦是由兩個主要部分：硬體(hardware)和軟體(software)所構成的系統。 電腦軟體（software）又可分成兩大類：作業系統(OS)和應用程式。 應用程式藉著電腦硬體來解決使用者的問題；作業系統則提供了使用者存取硬體的介面。 Program(程式) Data(資料) 圖 7.1 電腦系統 p.186

5 7.1.1 作業系統（operating system）
作業系統是電腦硬體和使用者（可能是應用程式或人類）之間的介面 作業系統是一個程式（program）或一套程式，有助於其他 程式的執行。 作業系統會檢查硬體和軟體的資源是否能有效地被使用，且當資源使用發生衝突時，作業系統也會居間協調解決。 作業系統的兩個主要設計目標是： 提高硬體的使用效能。 讓資源的使用更容易。 p.186

6 7.1.2 啟動程式(Bootstrap process)
作業系統是電腦硬體和使用者（可能是應用程式或是人類）之間的介面，有助於其他程式的執行，並且提供硬體和軟體資源的使用管理。 作業系統是如何被載入的呢？今日解決的方法採用兩階段處理。 RAM kernel 圖 7.2 啟動程式 p.186

7 7.2 演化 作業系統有一段很長的演化歷史，概述如下。 批次作業系統（batch operating systems）
7.2 演化 作業系統有一段很長的演化歷史，概述如下。 批次作業系統（batch operating systems） 分時系統 (time-sharing System) 個人系統 平行系統（parallel systems） 分散式系統（distributed systems） 即時系統（real-time system） p.187

8 批次系統 批次作業系統（batch operating systems）是用來控制大型電腦。每一個要執行的程式都被稱為工作（job）。 在這個年代的作業系統都很簡單，所扮演的角色僅僅是確保所有的電腦資源都會從上個工作順利轉移到下個工作。 讀卡機讀卡 印表機 p.187

9 7.2.2 分時系統(time-sharing System)
為了要有效使用電腦系統的資源， 故導入了多重(元)程式（multiprogramming）。它的想法是一次在記憶體內儲存好幾個工作（job），每個可用的資源只分配給一個有需求的工作使用。 多重程式帶來了分時（time sharing）的概念：資源可以被不同的工作分享使用，每一個工作都分配了一段時間去使用資源。 p.188

10 行程排程(班) 多重(元)程式（multiprogramming）或分時作業大大地改善了電腦系統的效率。
這樣的作業系統必須具備排程(班)（scheduling）的能力：不但要能把資源配置給不同的程式，還要能決定哪個程式在哪個時候可以使用哪個資源。 使用者毋須透過操作員就能與電腦系統直接互動， 因而創造出一個新的術語：行程（process）。 Program(程式) Process (行程) p.188

11 7.2.3 個人系統 當個人電腦進入市場時，這類型電腦的作業系統通常有個別的需求。
個人系統 當個人電腦進入市場時，這類型電腦的作業系統通常有個別的需求。 在這個年代，出現了單一使用者作業系統（single-user operating systems），例如： DOS（磁碟作業系統）。 p.188

12 7.2.4 平行系統（parallel systems）
由於對速度和效率上的需求愈來愈高， 帶動了平行系統（parallel systems）的設計：在同一部電腦上有多個 CPU，每個 CPU 可以單獨執行一個程式或者各自執行一個大程式的某個部分。 這樣的作業系統會比只有單一 CPU 的作業系統來得更複雜。 進化 p.188

13 多核心(multiCore)技術 多核心CPU是目前CPU的主流，它是由平行處理概念而來，可提高CPU的產量。
回頭看平行系統的架構圖，每一個CPU都擁有屬於自己的本地端記憶體，而在多核心CPU中，每一個核心(Core)也有屬於自己專用的Cache記憶體。 而將多個核心放置於單一個晶片中，稱之為CMP(Chip MultiProcessor)技術，其架構如圖。 補充

14 多執行緒(multithreaded) 多核心目前的作業系統大多為多執行緒(multithreaded)作業系統。
所謂執行緒(thread)，即CPU執行程式的單位，同一個程式可能包含眾多執行緒，這些執行緒使用相同的程式，因此只需要記錄每一個執行緒的堆疊及程式計數器(Program Counter)，就可於暫停後再度執行該執行緒，而完成多執行緒作業系統之功能。 補充

15 並行與平行 並行(Concurrency): 當系統內只有一個單核心CPU時，多執行緒作業系統是透過不斷地切換執行緒來達到多執行緒的功能，因為CPU一次只能執行一個執行緒。 平行(Parallelism):但當系統內不只一個單核心CPU時（如平行系統），它就可以一次執行很多個執行緒，因為每一個CPU都可以執行一個執行緒，因此較多CPU的系統得以提升產量。 補充

16 7.2.5 分散式系統 網路和互聯網路的興起，在作業系統中創造了新的研究方向。
分散式系統 網路和互聯網路的興起，在作業系統中創造了新的研究方向。 分散式系統（distributed systems）合併了前幾代作業系統的特色，並也帶來了新的責任，例如安全控管。 p.188

17 即時系統 即時系統（real-time system）是被認定為可在指定時限內完成任務的作業系統，應用於像監督、即時回應或者需要控制的外部處理或環境等即時應用上。 p.189

18 7.3 組成單元 今日的作業系統相當複雜，它需要管理電腦系統中各種不同的資源。一個現代的作業系統至少需要完成四個任務：記憶體管理、行程管理、設備管理和檔案管理。 作業系統中不屬於以上四項的組成單元，通常稱作使用者介面或介面程式（shell）。使用者介面是作業系統中負責對外通訊的單元。 圖 7.3 作業系統的組成單元 p.189

19 使用者介面 每個作業系統都有使用者介面（user interface），它接受使用者（行程）發出的要求，翻譯後交給作業系統的其他組成單元。 某些作業系統中的使用者介面，例如 UNIX，被稱為介面程式（shell）。 另外也有因為是選單方式驅動而被稱為視窗（window）的圖形使用者介面（graphical user interface；GUI）組成單元。 p.189

20 使用者介面 命令列介面 (CLI, Command-Line Interface) 並不需花時間在視窗呈現的運算上, 因此會有較佳的執行效能
缺點則為操作介面較不友善, 需要記憶指令的用法才能上手 圖形使用者介面 (GUI, Graphical User Interface) 優點是能讓使用者較方便地執行程式. 缺點則為效能較差 補充

21 記憶體管理者 現代電腦系統的任務之一就是記憶體管理（memory management），關於作業系統的記憶體管理大約可分成兩大類： 單一程式（monoprogramming） 多重(元)程式（multiprogramming） Program(程式) Process (行程) OS決定放在主記憶體何處? p.190

22 單一程式（monoprogramming)
這個技術有幾個問題： 記憶體的大小必須足夠放得下整個程式。如果記憶體的容量比程式的所需容量小，那麼程式就不能執行。 當一個程式開始執行後，就不能再執行其他的程式。 圖 7.4 單一程式 p.190

23 多重(元)程式（multiprogramming）
在多重(元)程式（multiprogramming）中，同時會有超過一個以上的程式儲存在記憶體中，並行(Concurrency)地被執行，而CPU 就在這些程式間快速地切換。 圖 7.5 多重程式 p.190

24 多重程式架構 自從1960 年代以來， 多重程式的分類經過了多次的改變， 如圖7.6。在下面幾節中，我們會很簡要地討論每種架構。
其中有兩種技術是屬於非置換類（nonswapping），這意味著在執行的期間，程式全部都會保留在記憶體中。 另外兩種技術就屬於置換類（swapping），意味著在執行的期間，每一個程式部分儲存在記憶體中，程式可能在記憶體和磁碟間至少置換一次或更多次。 Program(程式) Process (行程) 圖 7.6 多重程式的分類 p.191

25 分割（partitioning） 用於多重程式的第一個技術叫做分割（partitioning）。
固定分割法 (fixed partitioning) 可變分割法 (Variable-partition) 在這個機制中，記憶體被切割成可變長度的區域，每個區域或分割都存放了一個程式，CPU 就在這些程式之間切換。 以這個技術而言，每一個程式全都儲存在記憶體中，並使用連續的記憶體位置。 圖 7.7 分割 p.191

26 分割問題 記憶體分割技術雖然改善了CPU 的效能，但仍然存在一些問題： 記憶體管理者必須事先決定分割的大小。
如果分割尺寸過小，那麼就會有一些程式不能載入記憶體； 如果分割尺寸過大，就會在記憶體中形成「洞(Hole)」（沒有使用的位置）。 即使在開始時電腦記憶體的分割相當完美，但在新程式取代舊程式後，就可能會形成一些新的洞。 當許多洞形成後，記憶體管理者可以利用聚集(compaction)來移動這些洞，變成可用的分割區域，但這對系統而言會造成額外的負擔。 p.191

27 固定分割法 (fixed partitioning)
是把記憶體劃分成多個大小固定的分割區，而且作業系統會使用表格記錄分割區的起始位址及長度。 補充

28 可變分割法 (Variable-partition)
是根據程式的大小劃分一塊大小剛好的分割區來儲存程式，而且作業系統同樣會使用表格記錄分割區的起始位址及長度。 補充

29 可變分割的範例 記憶體管理系統依行程的需求，給定記憶體的容量。
以64 MB記憶體為例，(b) 、(c) 、(d)載入3個Process(行程)。 (d) 剩下4 MB，不足以載入Process 4 (8 MB) 。 (e)process 2 移出記憶體，剩餘14 MB。 (f)process 4 載入至process 2 的位置，剩下6 MB。 (g)process 1 閒置並被移出，，剩餘20 MB。 (h) process 2 載入至process 1 的位置，剩下6 MB。 記憶體的聚集(compaction) 的需要：加重工作負擔。 補充

30 記憶體的動態配置(allocation)策略
最先合適(First-Fit) 遇到第一個夠大的「坑洞」就把行程載入 最佳合適(Best-Fit) 把每一個夠大的「坑洞」都拿來看看，然後選其中最小的一個來載入行程 最差合適(Worst-Fit) 也是把每個夠大的「坑洞」都拿來看看，然後選最大的可用空間來載入行程 補充

31 效能比較 最先合適和最佳合適在時間和記憶體空間的使用率上優於最差合適 在記憶體空間使用率上，最先合適與最佳合適很接近
最先合適的執行時間通常會比較短 補充

32 範例(補充) Assume that we have the following free block list.
We first need a memory space of 540K , then 230K, then 50K, and then 109K. With the Best-Fit policy ,we will find the spaces in blocks (a) , (b) , (c) , and (d)in sequence. Note that a , b , c , d are all in [1,8].What is the value of a2+(b+3c)d ? (A) (B) 68 (C) (D) (E) 30 (1) (2) (3) (4) (5) (6) (7) (8) 300K 270K 450K 630K 14K 310K 980K 120K 補充

33 分頁（paging） 分頁（paging）改善了分割的效率。
在分頁法中，記憶體被切割成相同大小的區域，叫做框（frames）。同樣地，程式也被切割成大小相同的尺寸，稱為頁（pages）。 在記憶體中，一個框裡會儲存一頁程式。分頁法較分割法為佳的原因是 ：當兩個程式都使用了三個非連續的框，在執行完後，記憶體可以讓另 一個需要六個框的程式使用，而不需要等待有六個連續框後才能載入記 憶體。 A1 C2 A2 C1 圖 7.8 分頁 p.192

34 行程的分頁對應至框的範例 記憶體管理系統依行程的需求，給定記憶體的框（frames）。
行程的分頁表(page table)資料結構 (在f之時間) 補充

35 頁的設計 頁的大小設定為2的次方。 相對的記憶體位址可表示為： 頁碼(Page No.) 位移(Offset)
16位元的位址，頁的大小設為210 = 1024位元組。 位址1502 = ( )2。 Page # = (000001)2。 Offset = ( )2。 補充

36 實際位址的轉換 補充

37 需求分頁（demand paging） 在需求分頁（demand paging）中，程式被切割成許多頁，這些頁逐一的被載入記憶體中、執行，再以另一頁取代後執行。 此外，同一個程式的連續頁，不必一定要載入到相同的記憶體框內，僅需載入到任何沒有在使用的框裡即可。 A1 進化 A1 C2 C2 B1 A2 A2 C1 圖 7.8 分頁 圖 7.9 需求分頁 p.193

38 需求分段（demand segmentation）
圖 需求分段 p.193

39 需求分頁與分段（demand paging and segmentation）
把記憶體分成很多框，再把一個分段（模組）分成若干頁，那麼就能將同一分段內的頁一個個載入到可用的記憶體框中執行。 p.193

40 虛擬記憶體（virtual memory）
圖 虛擬記憶體 p.194

41 7.3.3行程管理者 程式、工作與行程 現代的作業系統稱呼一群指令集合，多半使用下列三個術語：程式、工作和行程。
程式（program）是一群靜止的指令集合，通常儲存在磁碟（或磁帶）上。 程式一旦被選擇要執行時就變成了工作（job），直到它執行完成後，又再次變回一個程式。 行程（process）就是正在執行的程式。 p.194

42 狀態流程圖（state diagram） 當我們思考一個程式如何變成一個工作，以及一個工作如何變為一個行程時，程式、工作與行程之間的關係就變得愈來愈清楚，可用狀態流程圖（state diagram）來說明。 圖 區分程式、工作和行程範圍的狀態流程圖 p.195

43 狀態流程 p.195 當作業系統選擇了一個程式，此時程式就變成一個工作，並且進入保留狀態（hold state）。
當可用的記憶體空間可以完全或部分地儲存這個程式時，這個工作就移入就緒狀態（ready state）。 直到 CPU 能夠執行它，此時它就移入了執行狀態（running state）。 行程持續執行直到它需要輸入∕輸出（I/O）。 行程用完所分配的 CPU 時間片段。 行程執行結束。 在第一個情況，行程進入等待狀態（waiting state），直到 I/O 動作完成。 在第二個情況，則直接進入就緒狀態。 在第三個情況，它進入終止狀態（terminated state），並且也不再是一個行程。 p.195

44 排程器（schedulers） 排程器(又稱排班程式)
工作排程器（Job scheduler） 行程排程器(又稱CPU排班程式 , CPU scheduler) p.196

45 工作排程器（job scheduler） 工作排程器（job scheduler）將工作由保留狀態移到就緒狀態或由執行狀態移到終止狀態。
圖 工作排程器 p.196

46 行程排程器（process scheduler）
行程排程器（process scheduler, 又稱CPU排班程式 , CPU scheduler) 會將行程由一個狀態移動到另一個狀態。 圖 行程排程器 p.197

47 佇列（queues） 工作或行程從一種狀態移到另一種狀態，行程管理者通常會利用佇列（queues）（等待串列）來完成。
有很多不同的策略(演算法)供行程管理者從佇列中選出下一個工作或行程；它可能是先進先出（FIFO）、最短的工作先做，或佇列中擁有最高優先權的行程先做等。 圖 行程管理中所使用的佇列 p.197

48 行程排程器（process scheduler）
CPU 排程(CPU scheduling)演算法 的目的是找出下一個可以取得CPU 使用權的行程，常見的CPU 排程演算法如下： 先來先做 (FCFS，first-come first-served) ：依照行程抵達的先後順序來執行，先來的先做，做完再輪到下一個。 最短的工作先做 (SJF，shortest job first) ：先檢查 一遍在就緒狀態下的所有行程，將它們所需的執行時間由小到大排序，然後從時間最短的行程開始執行。 優先權 (priority) ：依照事先決定的優先權定義，計算出每個行程的優先順序，然後依照優先順序給予CPU 使用權。 依序循環 (round robin) ：每個行程輪流分配一個時間配額，如果不夠讓行程執行完畢，下一次就再分配一個時間配額給它，而行程在時間配額用完後，就立刻交出CPU 的使用權，讓下一個行程使用，重複這個過程直到行程結束為止。 補充

49 先來先做 (FCFS，first-come first-served)演算法
行程 所需時間單位 P1 40 P2 75 P3 20 P4 80 P5 25 以行程(Process)到達的先後順序來執行，先來的先做 甘特圖：用來表示每個程序的執行次序和時間軸 平均等待時間 (Waiting Time ) = ( ) / 5=101 平均回復時間(Turnaround time) = 平均等待時間 +平均CPU執行時間+平均I/O等待時間 (忽略) = /5=101+48=149 補充

50 最短的工作先做 (SJF，shortest job first)演算法
先看一遍在就緒狀態下的所有程序，將它們的所需執行時間從小排到大，然後從時間最短的開始執行 執行順序：P3、P5、P1、P2 、 P4 甘特圖： 平均的等待時間 (Waiting Time ) = ( ) / 5 = 62 平均的回復時間(Turnaround time) =平均等待時間+平均CPU執行時間=62+240/5=62+48 =110 行程 所需時間單位 P1 40 P2 75 P3 20 P4 80 P5 25 補充

51 優先權 (priority)演算法 依照事先決定好的優先權定義，計算出每個程序的優先順序，然後照著優先順序的先後給予CPU使用權
行程 所需時間單位 優先順序 P1 40 3 P2 75 1 P3 20 4 P4 80 5 P5 25 2 依照事先決定好的優先權定義，計算出每個程序的優先順序，然後照著優先順序的先後給予CPU使用權 執行順序：P2、P5、P1、P3 、 P4 甘特圖： 平均的等待時間 (Waiting Time ) = ( ) / 5 = 95 平均的回復時間(Turnaround time) =平均等待時間+平均CPU執行時間=95+240/5=95+48 =143 補充

52 依序循環 (round robin)演算法 行程 所需時間單位 P1 40 P2 75 P3 20 P4 80 P5 25 事先定義好固定的時間配額，讓每個程序輪流分配一個時間配額。假如不夠讓程序執行完成，下一次就再分配一個時間配額給它 甘特圖： 平均的等待時間 (Waiting Time ) = ( ) / 5 = 113 平均的回復時間(Turnaround time) =平均等待時間+平均CPU執行時間= /5= =161 補充

53 範例(補充) 1. 若有三個程序P1, P2, P3 都在時間0 到達。假設P1, P2, P3 之執行時間分別為24, 4, 2 個時間單位。則在最短工作優先（Shortest-Job-First, SJF）排程演算法（scheduling algorithm）下，三程序的平均等待時間為何？（四捨五入到整數）註：一行程的等待時間為該行程到達至其執行結束的過程中，花費在等待其它行程的時間。(A)2 (B)3 (C)5 (D) 年公務人員普通考試試題 2. 假設有五個程序（甲、乙、丙、丁、戊）同時送入電腦執行，它們的執行時間分別是5、4、3、2、1分鐘，如果該電腦是以甲、乙、丙、丁、戊的順序來循序且不經打斷地執行，請問該五個程序的平均回轉時間（Turnaround Time）是多少分鐘？(A)3分鐘 (B)5分鐘 (C)8分鐘 (D) 11分鐘 101 年公務人員普通考試試題 補充

54 7.3.4 設備管理者（device manager）
設備管理者應具備的功能如下： 設備管理者持續的監控每個輸入∕輸出設備，確保設備的功能正常。 設備管理者對每個輸入∕輸出設備各設置一個佇列或共同設置一個或多個佇列。 管理者對存取輸入∕輸出設備提供不同的使用策略。 p.200

55 7.3.5 檔案管理者 作業系統利用檔案管理者（file manager）來控制檔案的存取。 檔案管理者應具備的功能如下：
檔案管理者 作業系統利用檔案管理者（file manager）來控制檔案的存取。 檔案管理者應具備的功能如下： 檔案管理者控制了檔案的存取。 檔案管理者監督檔案的產生、刪除和修改。 檔案管理者能夠控制檔案的命名。 檔案管理者監督檔案的儲存：它們如何被儲存及被儲存在哪裡等。 檔案管理者負責歸檔和備份。 p.201

56 7.4 作業系統現況 7.4.1 UNIX 屬於中大型電腦的作業系統。
7.4 作業系統現況 UNIX 屬於中大型電腦的作業系統。 UNIX 已歷經了許多版本演變，而非常受到程式設計師與電腦科學家的歡迎，是具有三項突出特性的強大作業系統。 可攜式的作業系統，主要是用C 語言（用以取代使用每個系統都不一樣的機器語言）撰寫的。 UNIX有一組功能強大的公用程式（命令），可用以組合（一個稱為腳本的可執行檔）解決許多問題，這在其他的作業系統中就需要特別寫一個程式才能解決。 它與設備是無關的，因為所有的設備驅動程式都被包含在作業系統中，這意味著很容易就可以安裝任何想要使用的設備。 UNIX 是一個多使用者、多重(元)行程、可攜式的作業系統，被設計來協助程式設計、文字處理、通訊與其他預期作業系統能完成的任務。 p.201

57 UNIX 結構 UNIX 含有四個主要單元：核心、介面程式、一組公用程式與應用程式。 圖 UNIX 作業系統的組成單元 p.202

58 UNIX 結構 核心（kernel） : 是UNIX 系統的心臟，包含了作業系統最基本部分：記憶體管理、行程管理、設備管理與檔案管理。
公用程式（utility）: 是標準的UNIX 程式用以支援使用者行程，三個常見公用程式是文字編輯器、搜尋程式與排序程式。 應用程式: UNIX 的應用程式並非作業系統安裝套件的標準配備，而是由系統的管理者、專職程式設計師，或使用者所撰寫。 p.203

59 Sun Solaris作業系統的圖形化介面
UNIX命令列介面 Sun Solaris作業系統的圖形化介面 補充

60 Linux 屬於個人電腦的作業系統。 現今的Linux 是在1991 年由芬蘭Helsinki 大學學生Linus Torvalds 所開發的新作業系統。最初的核心是非常類似UNIX(Unix-like) 的小系統，經過許多演變而成為現在全功能的作業系統。 在1997 年發行的Linux 2.0 核心成為商用作業系統安裝套件核心：它具備了所有傳統UNIX 的全部特性。 p.203

61 Windows 在1980 年代後期，微軟在Dave Cutler 的領導下，開始發展新的單一使用者作業系統，用以取代MS-DOS〔Microsoft Disk Operating System（微軟磁碟機作業系統）〕，Windows 於是被發展出來，經過多次版本的演變，我們統一以 Windows 代表所提及的這些版本。 p.204

62 Windows嵌入式作業系統 微軟為了嵌入式系統所設計的作業系統 共計有Windows CE、Windows Mobile、 Windows phone、Windows 7 for Embedded Systems、Windows 7、 Windows 8，其適用場合整理如 表。 Acer ICONIA W5平板電腦 （搭載作業系統為Windows 8） 補充

63 iOS作業系統 Apple 推出的智慧型手機iPhone 採用其專屬的iOS，初期只支援單工，但隨即在新版的iOS 4就支援了多工處理的功能。 爾後Apple又推出iPad 平板電腦，也搭載iOS作業系統，由於其他Apple 的隨身裝置（例如iPod touch）也採用iOS作業系統，因此Apple的智慧型手機與平板電腦也將採用iOS 做為作業系統。 Apple iPad平板電腦 （作業系統為iOS） 補充

64 Android作業系統 Android是Google 推出的作業系統，Android作業系統是以Linux核心為基礎，並採取開放原始碼策略，因此不同的廠商可自行修改程式碼以發展其特色，Android最早採用在智慧型手機之上，當時所有安裝Android 2.0作業系統的手機都稱之為GPhone手機。 隨著iPad的熱賣，非蘋陣營也 積極著力在平板電腦的設計，而 Google 也在當下推出了適合安 裝於平板電腦的Android 3.0， 相較於Windows 7 在平板電腦 的表現，Android 3.0在非蘋陣 營中較受到青睞。而Google在 Android 4.0時，也採取整合策 略，使得Android 4.0可安裝於 智慧型手機與平板電腦。 Asus變形金剛平板電腦（搭載作業系統為Android） 補充