Tetsuhiko的筆記

排程管理

2020-10-18 20:12:42
1177
作業系統
Tetsuhiko

CPU 排程（CPU Scheduling）
- 作業系統用「多元程式技術（Multiprogramming）」得到 CPU 最大使用率。
- 行程（Process）一開始都是 CPU Burst，交由 CPU 去處理該行程，接著是 I/O Burst ，做 I/O 資料的傳送。行程就在這兩個狀態間一直循環，最後會呼叫一個終止行程執行的「系統呼叫（System call）」作為行程的結束。
- CPU 排程從在「就緒佇列（Ready queue）」的行程中挑選行程進入 CPU 執行。
CPU 排程選擇的行程會在以下情況改變：
- 從「執行狀態（Running state）」切換至「等待狀態（Waiting state）」。
- 從「執行狀態（Running state）」切換至「就緒狀態（Ready state）」。
- 從「等待狀態（Waiting state）」切換至「就緒狀態（Ready state）」。
- 終止（Terminate）。
排程演算法
- 先來先到排程法：FCFS (First-come, First-served)
- 最短工作優先排程法：SJF (Shortest-Job First)
- 高響應比優先演算法：HRRN (Highest Response Ratio Next)
- 知更鳥式排程法／循環排程法：RR (Round Robin)
- 多階層佇列排程法 (Multi-level queue)：劃分為單獨的佇列，每個佇列都有自己的排程演算法。
- 多級反饋佇列排程法（Multi-level feedback queue）：行程可以在各個佇列之間移動。
- 優先等級排程法 (Priority scheduling)：分為「可搶先 (Preemptive) 」與「不可搶先 (Non-preemptive) 」兩種。
  ※ 優先權低的程式就可能永遠執行不到？
  　Ans:增加沒有被執行程式的優先權。
先來先到排程法（FCFS）
- 優點：
  - 有利於 CPU 作業較繁忙的程式，而不利於 I/O 較繁忙的程式。
  - 用於批次系統，不適用於分時系統 (Time-sharing system)。
- 缺點：低 CPU 利用度。
  - 均在等待一個很長的 CPU 時間來完成工作，造成平均等待時間大幅增加的不良現象。
  - 會造成低 I/O 利用度。
最短工作優先排程法（SJF）
- 優點：等待時間短。
  - 非搶先（SJF）：突發事件都準備就緒為0。
  - 搶先（SRTF）：作業的到達時間是任意的。
- 缺點：不公平（低優先級流程可能永遠不會執行）。
  ※ 解決方案：老化 – 隨著時間的流逝，流程的優先級增加。
高響應比優先演算法（HRRN）
- FCFS 及 SJF 的結合。
- 如果作業的等待時間相同、要求服務的時間越短，則優先權越大，此時類似於 SJF 演算法。
- 當要求服務的時間相同時，作業的優先權又取決於其等待時間，此時類似於 FCFS 演算法。
- 對於長作業的優先權，可以隨等待時間的增加而提高。當其等待時間足夠長時，也可以獲得處理，以避免出現飢餓現象（Starvation）。
循環排程法（RR）：分時系統所使用的排程法。
即時排程（Real-time scheduling）
- 最近期限優先排程演算法（Earliest deadline first scheduling, EDF）
  - 根據任務的截止時間確定任務的優先順序，任務的截止時間越早，其優先順序越高，具有最高優先順序的排在隊首。
  - EDF 既可以用於「搶先式 (Preemptive)」也可以用於「不可搶先式 (Non-preemptive)」。
- 最低鬆弛度優先排程演算法（Least slack time scheduling, LLF）
  - 在確定任務的優先順序時，根據的是任務的緊急（或鬆弛）程度。任務緊急程度愈高，賦予該任務的優先順序就愈高，以使之優先執行。
  - 此方式主要用於「搶先式 (Preemptive)」排程。

Homework

Process	Arrival time	CPU burst time
P0(0)	03	25
P1(2)	00	10
P2(1)	10	20
P3(3)	26	08
P4(4)	18	05

Numerical priority, while a higher number indicating a higher priority. CPU burst time is in milliseconds. Arrival time is the time the process became ready.

Assume that execution starts immediately at time 0 and there is no context switch overhead.

For the following scheduling disciplines, draw time diagram/Gantt Chart showing when each of the five processes executes. What is the waiting time for each process?

Which of the algorithms results in the minimum average waiting time? (over all processes)