cpu scheduling algorithm

FCFS(FIFS)(FIFO)

First-come First-service / First-In First-service / First-In First-out

新的process會接在ready queue的rear段， 當有cpu有空閒時會從ready queue的head拿出process來執行。
缺點:
Burst Time
\( P_1 \) 24
\( P_2 \) 3
\( P_3 \) 3

如果順序為\( 1\rightarrow 2\rightarrow 3 \)
avg. waiting time:
(0+24+27)/3 = 17 如果順序為\( 3\rightarrow 2\rightarrow 1 \)
avg. waiting time:
(6+3+0)/3 = 3

SJF(Shortest Job First)

選擇最小 CPU Burst Time的Process先執行
為在平均waiting time / turnaround time 有最好的排法(時間少)
SJF適用於Job Scheduler, 可預測各個Job的Time Limit。
由於Process 的下一個 CPU Burst Time 較難預測, 因此難被利用在 CPU Scheduler。

如果CPU動作相同，則會使用FIFO

SJF在batch process 的 Long-Term工作的排程來說， 可以使用(Process Time Limit)的方法來評估 process 運作的時間限制。
就SJF而言
(burst time愈長, 優先權越低)

Priority scheduler

會將CPU指定給具有最高優先權的Process，
若有優先權相等的要使用CPU，則採FCFS。
(burst time愈長, 優先權越低)
Burst time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2

Scheduler: \( P2 \rightarrow P5 \rightarrow P1 \rightarrow P3 \rightarrow P4 \)
優先權的設定方式
內部定義:
使用某些可以測量值來計算process的優先權。
ex. 時間限制、記憶體的需求、開啟檔案的數量、 平均I/O動作、平均CPU動作等。

外部定義:
則是作業系統外的因素決定。ex. 主要用途、金費等

Priority Scheduling 問題(Starvation)

問題是可能會讓較低優先權的process陷入無限期的等待CPU的地步。
稱為無限停滯(Block)或叫飢餓現象(Starvation)。

solution: Aging Techique (老化技術)

將在os中等候久的process的優先權逐漸提高。

Round-Robin Scheduling

O.S會定義CPU時間配額(Time Quantum)或時間分割(Time Slice)。
當process使用CPU超過time quantum or time slice時， 則Timer會產生中斷，讓process 從 running state 回到 ready state。
如果process在CPU執行時間小於time slice，則會自動釋放CPU。
反之，定時器會向os發出中斷，然後執行context switching。
如果 time quantum 過小，會造成context switching負擔過大。
turnaround time 同樣也取決於time slice配額的大小。
如果將處理context switch時間加進去，小的time slice需多次context switch，所以平均turnaround time也要增加。

Multi-processor scheduler

如果每個CPU有獨立的queue，
可能會造成有CPU忙綠, 有的可能starvation。
為了避免這種狀況，可以共用一個ready queue，
所有process都必須先進來這個queue等候，哪個CPU有空閒，
就安排那個process到空閒的CPU處理。
為了防止多個CPU選擇同一個process，或CPU選擇到的process遺失了，
利用master-slave處理器的結構(asymmetric mulitprocessing)， 一個特定的處理器充當cpu排班程式。

master processor

排班決定、I/O處理以及其他系統的動作都交由一個單一的cpu處理。
其他cpu只是負責執行user的程式碼。
這樣只有一個cpu會存取系統中的資料結構，
減輕資料共用帶來的麻煩。
但對I/O傾向的process可能會造成cpu上的瓶頸(只有master cpu才能動資料)。

Real-time system scheduling

hard real-time system

必須在一定量的時間內完成task， 通常要執行的process要到cpu時會附帶描述需要計算的或執行的 I/O時間量。
排班程式可能會接受這個process，並準時完成;或拒絕這個process。 稱為資源預約(resource reservation)。
此系統必須保證結果的確定性，專為執行某個重要process而設計。

Soft real-time system

要求重要process優先權高於其他process。
如果將他加到time-sharing system中，
可能造成資源分配不公平。產生starvation。

實現softr real-time system需要:

Thread Management