Heptabase 筆記

核心問題：要如何制定 Scheduleing 的規則呢？

前面幾個章節我們知道了 Process，也知道作業系統可以透過 timer interrupt 的機制下有機會選擇是否要換去執行其他 Process 。

所以我們這章會開始討論一下作業系統是如何決定下一個執行的 Process 。

這章裡面提到的 Job 我們都可以理解成是一個 Process 。

簡化問題 #

為了簡化問題，我們先做幾個重要的假設，然後慢慢地移除這些假設，來更接近現實的狀況。

1. 每個 Job 都有相同的執行時間
2. 所有的 Job 都會同時出現
3. 只要 Job 開始執行就要執行到結束
4. 所有的 Job 只會使用 CPU 不會有其他 IO 的相關操作
5. 我們可以知道所有 Job 的執行時間

觀察數據 #

在我們開始討論如何設計 Scheduler 之前，我們可以先思考一下我們要用什麼標準來評斷一個設計好不好。

Turnaound time #

turnaround time 指的是在特定情境下，完成 Job 所需要的時間。

Response time #

response time 指的是 Job 抵達後多久會被執行。

實現 Scheduler 的幾種方法 #

FIFO #

這是最簡單的做法，不管任何情況，直接去執行 Jobs 。

Turnaournd time = (10+20+30) / 3

一旦我們拿掉第一個限制的話，FIFO 會出現一個問題

如果第一個執行的 Job 時間很長的話，這樣會大大增加我們的 Turnaround time 。

Turnaround time = (100+110+120) / 3

Shortest Job First (SJF) #

為了解決 FIFO 的小問題，我們可以選擇先把執行時間短的 Job 先執行完再執行長的。(我知道這個不現實，但還記得我們的限制嗎？)

Turnaround time = (10+20+120) / 3

讓我們讓事情變得更有趣一點，如果我們在 SJF 的基礎上拿掉了第二個限制(Jobs 同時抵達)

因為 Job 沒有同時抵達，並且我們第三個限制是只要開始執行 Job 就一定要執行到結束。

於是我們的 Turnaround time 就變成 = (100 + (110-10) + (120-10)) / 3

Shortest Time-to-Completion First (STCF) #

我們可以解除第三個限制(Job 一旦開始執行就要執行到結束)，就可以解決 SJF 遇到的問題，來提昇 Turnaround time 。

這樣我們就變成當有一個新的 Job 進來時，如果他的執行時間比當前執行的 Job 所剩時間還要短的話，就去執行新 Job 。

Turnaround time = ((120-0)+(20-10)+(30-10)) / 3

Round-Robin #

以上幾個做法都能夠有效的提高 Turnaround time 但卻不利於 response time 。

Round-Robin 的概念很簡單，我們可以執行每個 Job 一段時段時間，假設為 1s (這個時間段必須為 timer-interrupt 的倍數)。

如果你想要提高你的 response time 你就可以調整成每 500 ms 就切換一個 Job 。

但也要注意，每次的切換都是會有一些成本的(還記得前幾章說的 context switch 作業系統要做的一些事嗎？)

舉例來說，你設定每 10ms 切換 Job ，context-switch 的成本為 1ms 。這樣大概就有 10% 的時間被浪費在 context-switch 上了。

I/O 操作 #

Job 難免會有 I/O 操作，我們解放了第四個限制。因為我們已經解放了第三個限制，所以這個工作變得容易許多。

作業系統會把等待 I/O Job 先暫停，換去執行其他的 Job 來提高 CPU 的效率。

最後的問題 #

到了這邊你會發現，我們還有一個限制還沒有被解除，以上的討論都是基於，我們可以知道 Job 的執行時間，但在現實生活中，我們幾乎無法做到這件事情。

我們會在下一個章節裡討論這個問題。