計算機概論-作業系統(排班演算法)

名詞解釋

• 護衛效應(convoy effect)：很多processes在等待一個需很長時間才能完成的process
• CPU scheduling是公平的：對每一個process的配置都很平均
• 飢餓(starvation)：長期無法取得足夠CPU來完成工作，造成自身無窮停滯的情況，可採aging technique解決
• 老化技術(aging technique)：每隔一段時間，將長時間未完成的工作，逐步提高其priority value
• preemptive：可插隊、可搶奪；當一個process取得CPU在執行時，有可能被迫放棄CPU
• 平均等待時間(average waiting time)：各process從到達ready queue至獲取CPU之平均時間
• 平均處理時間(average turnaround time)：各process從到達ready queue至process完成之平均時間
• 到達時間(arrival time)：process到達ready queue的時間
• burst time：指一個進程執行其所需的時間

排班目標

• CPU使用率(CPU utilization)↑
  CPU使用率 = CPU工作時間 / ( CPU工作時間 + CPU閒置時間 )
• 產能(throughput)↑
  單位時間能完成的process數
• 等待時間(waiting time)↓
  Process在ready queue等待獲取CPU的時間總合
• 處理時間(turnaround time)↓
  自process進入系統到完成工作的時間
• 反應時間(response time)↓
  自使用者下命令到系統產生第一個回應的時間
• 資源使用率(resource utilization)↑
• 公平(fair)
• 不會發生飢餓(no starvation)

Fisrst Come First Served(FCFS) Scheduling

說明：先到先做排程，arrival time越小(到達時間越早)優先處理

根據定義，可得到

• Turnaround time = Exit time – Arrival time
• Waiting time = Turnaround time – Burst time

Average turnaround time = ( 3 + 7 + 9 + 12 + 12 ) / 5 = 8.6
Average waiting time = ( 0 + 1 + 5 + 7 + 10 ) / 5 = 4.6
特點：

• 簡單易於設計
• 有護衛效應
• 平均等待時間最長
• 平均處理時間最長
• CPU scheduling是公平的
• No starvation
• Non-preemptive

Shortest Job First(SJF) Scheduling

說明：最短工作優先排程

根據定義，可得到

• Turnaround time = Exit time – Arrival time
• Waiting time = Turnaround time – Burst time

Average turnaround time = ( 3 + 7 + 11 + 14 + 3 ) / 5 = 7.6
Average waiting time = ( 0 + 1 + 7 + 9 + 1 ) / 5 = 3.6
特點：

• Average waiting time短
• Average turnaround time最短
• Response time不確定，計算密集型工作會被放到最後執行
• CPU scheduling是不公平的
• Starvation
• Non-preemptive(可插隊的SJF被歸類為SRTF)
• 不適合用於short-term scheduler，會來不及計算預估時間
• 可用於long-term scheduler
• 利用前幾次CPU bursts所測得的數值，預估下一個CPU burst長度
  τ_n+1 = α t_n + (1-α) τ_n,  0 ≤ α ≤ 1

Shortest Remaining Time First(SRTF) Scheduling

說明：最短剩餘時間優先排程

根據定義，可得到

• Turnaround time = Exit time – Arrival time
• Waiting time = Turnaround time – Burst time

Average turnaround time = ( 3 + 13 + 4 + 14 + 2 ) / 5 = 7.2
Average waiting time = ( 0 + 7 + 0 + 9 + 0 ) / 5 = 3.2
特點：

• Average waiting time最短
• Context switch次數較SJF頻繁
• 比SJF提供較好的response time性能
• CPU scheduling是不公平的
• Starvation
• Preemptive

Priority Scheduling

說明：優先權排程，優先權較高的process優先處理
若遇到相同優先權的部分，電腦實際排程要看演算法怎麼寫，一般會以FCFS來排序

根據定義，可得到

• Turnaround time = Exit time – Arrival time
• Waiting time = Turnaround time – Burst time

Average turnaround time = ( 11 + 6 + 15 + 20 + 8 ) / 5 = 12
Average waiting time = ( 8 + 0 + 11 + 15 + 6 ) / 5 = 8
特點：

• CPU scheduling是不公平的
• Starvation，可採aging technique，解決低優先權process配無限擱置問題
• 根據優先權的定義，可能是preemptive或non-preemptive
• 優先權可由系統內部或外部定義
  內部：使用一些可量化數值定義priority。如時間限制、記憶體需求、平均I/O burst與CPU burst的比例
  外部：由系統外部的標準所決定。如process的重要性
• 優先權是否可更改
  Static：優先權設定給process後，就不能再更改
  Dynamic：優先權設定給process後，可依需求再更改

Round-Robin Scheduling

說明：循環分時排程。當process未能在time quantum(或稱CPU time slice)內完成，則此process會被迫放棄CPU，並等待下一輪再使用

根據定義，可得到

• Turnaround time = Exit time – Arrival time
• Waiting time = Turnaround time – Burst time

Average turnaround time = ( 3 + 17 + 7 + 14 + 9 ) / 5 = 10
Average waiting time = ( 0 + 11 + 3 + 9 + 7 ) / 5 = 6
特點：

• 排班效益取決於time quantum
  time quantum太小，內文切換太頻繁
  time quantum太大，退化為FCFS
• 適用於time sharing system
• CPU scheduling是公平的
• No starvation
• Preemptive

Multilevel Queue Scheduling

說明：多層佇列排程。根據process的不同特性，將ready queue分成不同優先等級的ready queue，每個queue都有各自的排程演算法，各queue之間採固定的queue priority排序或分配各queue一個固定時間，process不得在各queue之間移動

特點：

• 排班設計/調整之靈活性高
• CPU scheduling是不公平的
• Starvation
• preemptive

Multilevel Feedback Queue Scheduling

說明：多層回授佇列排程與多層佇列排程類似，但允許process在各queue之間移動。
特點：

• 採aging technique，將未完成的process，每隔一段時間提升至上層queue
• 亦可配合降級之動作，上層queue的process未能於time quantum內完成，則此process放棄CPU後，被移至下層queue
• 排班設計/調整之靈活性高
• CPU scheduling是不公平的
• No starvation
• preemptive

排班演算法總結

死結(deadlock)

定義：系統中的所有process均在等候其他process所擁有的資源，使得系統無法繼續運作的現象
必要條件：

• 互斥(Mutual exclusion)：
  系統中至少有一項資源是不可共用的
• 持有和等待(hold and wait)：
  Process可以在等待時持有資源
• 不能搶奪(no preemptive)：
  當process擁有某一項資源的使用權時，除非process自動釋放資源，否則其他程序不可強佔此項資源
• 迴圈等待(circular wait)：
  系統中所有process均在等候其他process所持有的資源，且形成循環狀態

預防死結：打破上述其中一個條件，就可保證死結不會發生