第二章 行程管理 朱肇明 資管系 講師 大華技術學院.

Presentation on theme: "第二章 行程管理 朱肇明 資管系 講師 大華技術學院."— Presentation transcript:

1 第二章 行程管理 朱肇明 資管系 講師 大華技術學院

2 行程(process) 行程就是一個執行中的程式。 行程包括了 程式區段 資料區段 堆疊區段
CPU 中各暫存器的值(行程執行時所需控制資訊)

3 行程(process)與程式(program)
程式是放在外部的儲存裝置如硬碟上，而行程則放在記憶體中。 程式在儲存裝置中是靜態的，而行程在記憶體中是動態的，它會隨著一些事件的發生而產生相對的改變。 行程，簡單來說，就是一個執行中的程式。

4 行程的狀態 一個行程在執行過程中，會改變很多狀態。 一個行程的狀態通常有下列幾種： 建立 執行 懸置 就緒 終止

5 行程狀態轉換圖 建立 允許進入 離開 中斷 終止 就緒 執行 分派 事件發生 等待事件 懸置

6 行程控制區塊 行程控制區塊（PCB)，儲存行程在執行時相關的資訊。 PCB 中通常包括了
行程狀態 CPU 暫存器 排程資訊 I/O 狀態 當行程進行切換時，需要將目前行程的相關資訊記錄在該行程的 PCB 中，並將另一個行程的 PCB 載入至系統中，這個動作稱為內文切換。

7 行程控制區塊 行程狀態 鍵結 識別碼 記憶體管理資訊 程式計數器與其他暫存器 已開啟檔案串列 ：

8 行程的佇列 一個行程在執行期間會在各種不同的佇列中進出。 一個系統中通常有 工作佇列 就緒佇列 等待佇列 裝置佇列

9 就緒佇列與裝置佇列 ….. head tail 暫存器 … 就緒佇列 磁碟裝置佇列 行程等待佇列 行程控制區塊b 行程控制區塊l
行程控制區塊n 行程控制區塊P 行程控制區塊a

10 行程的切換 行程A 作業系統 行程B 中斷或系統呼叫 將狀態儲存至PCB A 執行中 閒置 由 PCB B 載入狀態 將狀態儲存至PCB B

11 內文切換 當 CPU 的使用權由一個行程轉到另一個行程時需進行內文切換。 內文切換動作所花的時間對系統而言是額外的負擔 。
執行緒降低內文切換所花的時間。

12 行程排程 為了增加 CPU 的使用效率而提出多個行程的觀念。 一個單 CPU 的系統來說，隨時只能有一個行程在執行。
當行程不只一個的時候，如何選擇最適當行程來執行就是行程排程。 如何排程是影響作業系統效能最重要的因素。

13 排程效能的衡量 使用率 產量 回覆時間 等待時間 反應時間 可預測性 公平性

14 先到先做排程法 First Come, First Served FCFS Scheduling 不可搶先排程法 先進入的行程先執行。

15 先到先做排程法 - 範例 行程 CPU 暴衝時間（毫秒） P1 20 P2 5 P3 5 P1 P2 P3 20 25 30
20 25 30 平均等待時間：( ）/ 3 = 15 毫秒 P2 P3 P1 5 10 30 平均等待時間：( ）/ 3 = 5 毫秒

16 最短工作優先排程 Shortest Job First 不可搶先排程法 需要的時間最短者先執行。 如果不只一個行程有相同最短時間則以
SJF Scheduling 不可搶先排程法 需要的時間最短者先執行。 如果不只一個行程有相同最短時間則以 FCFS決定

17 最短工作優先排程– 範例圖示 行程 CPU 暴衝時間（毫秒） P1 15 P2 4 P3 3 P3 P2 P1 3 7 22
3 7 22 平均等待時間：（ ）/ 3 = 3.3 毫秒 時間 若使用 FCFS 排程法，行程到達的順序為 P1、P2、P3 則平均等待時間：（ ）/ 3 = 11.3 毫秒 FCFS 的平均等待時間大約為 SJF 的 3.4 倍。

18 最短剩餘優先排程 SJF 也可以是可搶先的。 可搶先的 SJF 排程又稱為最短剩餘時間優先的排程法(SRT)

19 最短剩餘優先排程– 範例 行程 CPU 暴衝時間（毫秒） 到達時間 P1 6 0 P2 3 1 P3 7 2 P4 4 3 P1 P2 P4
時間　０ １ ４ ８ １３ ２０ 平均等待時間：（ ）/ 4 = 4.75 毫秒

20 優先權排程 Priority Scheduling 可為不可搶先排程法或不可搶先排程法 最高優先權的行程先執行
Highest Priority First

21 優先權排程 – 範例 使用不可搶先的優先權排程 優先權數值愈小代表優先權愈高 行程 CPU 暴衝時間（毫秒） 優先權 P1 6 2
時間　０ ５ ９ １５ １８ ２５ 平均等待時間：（ ）/ 5 = 9.4毫秒

22 循環分時排程 Round-Robin Scheduling
將時間等切成一小片一小片的時間切片，每一個時間切片則為每個行程每次得到 CPU 使用權後可執行的時間。 特別為分時系統所設計，為可搶先的。

23 循環分時排程 – 範例 行程 CPU 暴衝時間（毫秒） P1 6 P2 5 P3 7 (時間切片為 5 毫秒) P1 P2 P3 P1 P1
5 9 13 18 25 平均等待時間：（ ）/ 3 = 7.33 毫秒

24 多層佇列排程Multilevel Feedback Queue Scheduling
方法： 將行程分類，相同類型的行程分在同一佇列，而每一佇列都有自己的排程方法。 最常見的分類將行程分成 前景（互動）行程 - RR 排程法 背景（批次）行程 - FCFS 排程法 佇列與佇列之間還有優先權的關係，且佇列之間還需要另一個整體排程方法 可搶先的固定優先權排程法 可能會產生飢餓的現象。

25 多層佇列排程法 – 圖示 高優先權 系統行程 伺服精靈行程 使用者行程 批次行程 低優先權

26 多層反饋佇列排程 多層反饋佇列排程法允許行程在各個佇列間移動。 CPU 暴衝時間愈長的行程就移到優先權比較低佇列中。 能避免飢餓的現象發生。

27 多層反饋佇列排程 – 圖示 A: 時間切片 = 5 ms B: 時間切片 = 20 ms C: FCFS