# Process Scheduling

[TOC]

## Process Scheduling

>* Multiprogramming （多元程式規劃）
> 定義：
1. 系統載入多個 process 到 memory 中
2. 以並行或是平行方式同時執行
3. 當一 process 需要 I/O，CPU 將交給另一個 process 使用 → 使 CPU 的使用率最大化
>* Time Sharing（分時系統）
> * 定義：
多個 process 可輪流使用 CPU 一段固定時間（time slice），當給予的時間一結束就另一個 process 執行
> * 效果：
各 process 皆以為擁有專屬的系統
> * 特色：
注重公平、反應時間、互動性
>
>[name=YJ][color=#e2416a]

### Process Scheduling Queues

* Job Queue (New State)
早期電腦 memory 有限，誰能夠從 program 狀態 load 到 new state(launch)，什麼時候允許 program load 到 memory 成為 process
* Ready Queue (Ready State)
load 到 memory 後，會被放進 ready queue，等 OS Scheduler 決定誰可以去使用 CPU
* Device Queue (Wait State)
每一個 device 會有自己的 queue，可以知道 process 在做哪一個 device 的 I/O，例如自己 call sleep() 或是有其他的 interrupt，那會有其他 waiting queue 的存在

Queue 的管理如圖所示

說明：
* 會有一個 ready queue for CPU，很多個 I/O 的 waiting queue，看是哪個 device 或 disk，會有自己獨立的 queue，利用 PCB 中的 pointer 串起來
* ready queue 可能會有 level 1、level 2、level 3，取決於 Scheduling Algorithm 自身管理方式
* queue 之間的 tail 和 head 都有串起來，比較容易做 reordering，不同的 Scheduling Algorithm，可能會 dynamically 決定 ordering (run time做調整)，需要其他 pointer 串起來，變成雙向或把前、後記起來

### Process Scheduling Diagram


說明：

* Ready queue 中的 process 會等待被 load 進 CPU
* Waiting queue 發生的原因有很多種，OS 會有專門的 queue 去處理這些 event 的發生：
* I/O request
* 若自己發出 I/O request，這時候會被放到 I/O queue，等到做完 I/O，會 throw 一個 interrupt 回來，OS就會把它放回 ready queue
* ex: call printf()，會被放到 monitor queue

* time slice expired
* timer的 alarm 被 fire，會從 CPU(running state) 直接回到 ready queue
* 這是為了確保主控權可以回到OS的手上
* fork a child
* process 可以自己 create process
* 程式內為什麼會有這麼多 process，是因為有一個 parent 和 children 的關係，有一個 tree
* 在Linux中，create process的動作叫做"fork"
有兩種實做方式
(1)可能自己繼續執行讓children等Parent執行完在執行
(2)先讓children先執行，原來的Parent process會被放在waiting queue，等到Children執行完，才可以再回到ready queue執行

* wait for an interrupt
* ex: call sleep() 的 system call
* sleep 100ms → 告訴 OS，100 ms 之後，幫我 fire 一個 interrupt，把我自己給 wake up 起來
* call sleep() 的 process 會被放在 waiting queue 裡，等著 interrupt 的發生，才可以回到 ready queue 裡面

### Scheduler
把下圖跟前面講的 [state](https://hackmd.io/4pxdfl71SBSnGHHqMOZIgg#Process-%E7%9A%84-Cycle) 串在在一起：

說明：
* CPU 中的 process 是 running state
* 搶 CPU 需要 CPU Scheduling 來排程
* CPU Scheduling 又稱為 Short-term（很頻繁），因為 time sharing，每幾個 ms 就有一個 alarm 產生，打斷執行的程式，把 OS 的 CPU Scheduling 叫起來，重新排程，頻率非常高，非常快就要做 rescheduling 的動作
* memory 中的 processes 是 ready state，等待著 OS 把它排程到 CPU 中執行
* 如果 process 在 memory 中但還不能立刻被執行，就算 CPU 空了也無法執行 process 的話，就是在 waiting queue 中
* 進入 waiting queue 有幾個可能：
1. 因為自己，自己要等別人
ex：自己call I/O、sleep() 的 system call
2. 因為別人，被別人 interrupt 而要被迫做 Context Switch
* 還在 disk 中的 program，有機會成為 process 的話，就會變成 new state，只是被create and initiate，但還沒有準備好放到 CPU 中還在 disk 上，等著搶位置進到 memory
>疑問：create and initiate 是包在 new state 裡，還沒變成 process 之前怎麼會被 create 和 initiate？
>這個部份是對你修改的筆記提出疑問：）
>[name=YJ][color=#e2416a]
* 搶 memory 需要 Job Scheduling
* Job Scheduling 又稱為 Long-term，相較於 CPU 排程，可能幾秒或幾分鐘才要做一次排程，因為是由使用者（人在幾秒鐘後才會 create 一個 process）launch process，才會需要排程進到memory，時間相較於 ms 較長
* 所以使用者的 Program 能否 load 到 memory 中是由 Long-term scheduler決定
* 圖裡還有一個 Job Swapping：
* swap: 把 memory content 踢回 disk 去
* Medium-term scheduler：因為 memory 有限，會把 disk 的一塊空間拿來當 memory 使用，當 memory 不夠時，Medium-term scheduler 要把一些 process，從 memory 踢回 disk
* 當 ready 的 process 從 memory swap 回 disk 時，進入 waiting state（但是以 memory content 形式，不是檔案形式），當 memory 有空，或是 process 要被執行時，OS 再把 process 的 memory content 搬回 memory 等著被執行（回到ready state）

Scheduler 種類：
* **Short-term scheduler (短期 Scheduler)**
CPU Scheduler，memory 中的 process 等著被排程而進入 CPU 被執行
> 又稱 Process Scheduler、CPU Scheduler
> 目的：從 ready queue 中挑出 highest-priority process，並分派 CPU 給這個 process
> [name=YJ][color=#e2416a]


特色：
1. 執行頻率：最高
2. 注重 wait time
* 很多 process 在 ready queue 裡面，要等著使用CPU，我們定義效能的方式就是用「平均大家等了多少時間」
* ex：大家都不喜歡等很久，買食物、用餐上，平均來講希望越短越好
* 不同的 Scheduling Algorithm 在相同的人進來的情況下（同樣的順序、不同排程的演算法），平均得到的等待時間會不一樣，如果演算法設計得好，定義下的 wait time 效能會變得更好
3. 注重 fairness
* 有 priority 或者是 round-robin（循環制）的 Scheduling Algorithm，為了確保 fairness，就會希望每個 process 等待的時間能夠盡量一樣，有時候平均很低不代表大家都高興
* ex：經濟上，國家收入好不代表國民很均富
* 以圖裡中間那段文字來說明：
:::info
→ if 10 ms for picking a job, 100 ms for such a pick,
→ overhead = 10/100 = 10%
* 假如 100ms 就要做一次 Scheduling，每一次 Algorithm 只 run 10 個ms，那 overhead 就是 10%，CPU 有 10% 的時間根本沒在幫使用者做事情
* 如果 100ms 就要做一次 Scheduling，而 Algorithm 要 run100ms，原本希望 CPU 要 run 100% 的使用率，結果一半的時間都不在做使用者要它做的事情，那當然會覺得這台電腦很慢
:::
* 所以 Short-Term Scheduler 很重要，Short-Term Scheduler 的決定會直接影響到程式執行的效能和使用者看到的 response time（interactive 的速度），計算時間也不能太長，processes很多時，掃一遍所需要花的時間會非常驚人
4. 無法調控 Multiprogramming degree
5. 無法調控 I/O-Bounded 與 CPU-Bounded 之混合比例
6. 所有 system 皆有此 scheduler

* **Long-term scheduler (長期 Scheduler)**
Job Scheduling，有新的程式被產生，要排程進入 memory
> 又稱 Job Scheduling，目的是從 Job Queue 中挑出一些 Jobs，要排程進入 memory，ready for execution
> [name=YJ][color=#e2416a]


特色：
1. 控制電腦的 "degree of multiprogramming"
* 什麼是 degree of multiprogramming？
這台電腦上，目前有多少個程式在 memory 裡面，這會控制電腦的 memory 內部要有幾個 process，這個值不能太高也不能太低
* degree 太少時，CPU 會 idle，早期 batch 的 degree always=1，CPU 一直等I/O，Utilization 很低
* degree 太高時，會產生 Trashing 的問題，太多 process 在爭搶很有限的 memory，結果大家就在 disk 和 memory 之間一直做 swapping，所以電腦基本上還是在做I/O
* 所以 Long-term Scheduler 要控制 new 的 program 到底能不能被放到 memory，其實就是在控制 degree of multiprogramming

2. 執行的頻率：三種 Scheduling 中最低
* Long-term 是由使用者來 driven，若沒有新的 process 被 create，Long-term Scheduler 就沒有事情需要做

3. 調控 CPU-Bound 和 I/O-Bound 的混合比例
* memory 的目的是希望程式執行 CPU 和 I/O 的時間可以 Overlap，CPU 執行的時間要差不多跟 I/O 執行的時間一樣，這樣 CPU 跟 I/O 才都會有事情可以做
* 如果 load 進來的程式都是 CPU-bound（只需要執行CPU的instruction，只是加減這些純計算的操作），就算 load 很多在 memory 裡面，CPU 還是會非常忙碌，而 I/O device 還是放在那裡沒有做事，CPU 跟 I/O沒有overlap。只有使用到 CPU，I/O 的 bandwidth 就浪費掉了
* 反過來說，如果 load 進來的程式都是 I/O-bound（沒有人要做 CPU，每個都在 call printf()、scanf()），所有的程式都在等 I/O 的事情，因為 I/O 很慢，而 CPU 執行很快，卻一直都在 idle，這樣也不行
* 因為是使用者 create 的程式，有機會一次來的全部都是 CPU-bound 的程式或突然間來很多 I/O-bound 的程式，所以 Long-term Scheduler 要讓選進來的 process 在做 CPU 跟 I/O 的時間上，盡量可以 balance，讓 CPU 跟 I/O 都可以忙碌地做事，兩邊都不會 idle，使用率才可以增加

4. Long-term Scheduler 的角色已經慢慢淡化
* 因為 memory 足夠，只要使用者說要執行 Program，利用 memory 加上 virtual memory 的概念，process 都能直接 load 到 memory 再說，所以對於新的電腦來說，已經不太需要 Long-term Scheduler，可以把需要執行的 program，全部 new 到 memory 中，這個角色就會變成 Medium-term Scheduler 要做的事情

5. Batch System 可採用，但 real-time 及 time-sharing system 不採用

> 補充：
>
>
>| | I/O Bounded Job| CPU Bounded Job |
>| :--------: | :--------: | :--------: |
>| 定義 | 須大量 I/O 操作，少量 CPU 計算 | 須大量 CPU 操作，少量 I/O 計算 |
>| 速度限制 | 受限於 I/O device 的效能 | 受限於 CPU 的效能 |
>| Buffering | input：CPU 常面對空的 Buff<br>output：CPU 常面對滿的 Buff | input：I/O 常面對滿的 Buff<br>output：I/O 常面對空的 Buff |
>
> I/O Bounded Job (CPU Bounded Job)
> Def：此類型工作需要大量的 I/O operation<font color="green">（CPU operation）</font>，但對於 CPU computation<font color="green">（I/O 之 operation）</font>time 之需求量相對很少，所以其工作取決於 I/O device <font color="green">（CPU）</font> 之 speed
> 例：成績單列印、薪資處理及列印
> <font color="green">例：氣象預估、科學計算模擬</font>
>[name=YJ][color=#e2416a]

* **Medium-term scheduler (中期 Scheduler)**
swap memory 的 process 到 disk 上，或者把 disk 上的 program 放到 memory

> 定義：常用於 time-sharing system，當 memory space 不足時，且又有其他 process 需要更多 memory 空間時，則 medium-term scheduler 挑選部分 process（waiting state 者、lower-priority 者），將它們 swap out 到 disk 中，等到 memory 有多餘空間時，再 swap in 到 memory 中
> [name=YJ][color=#e2416a]

- swap out 是把process從memory再把它搬回到disk上(記得這邊是memory content的型式)，為什麼要搬是因為要控制degree of multiprogramming
- swap in: 讓等在disk的process可以回到memory，重新等著被排程給CPU做執行
因為有swap out，有時候memory的空間會空出來，這時候要把某些程序給切換回來

特色：
1. 調控 CPU-Bound 和 I/O-Bound 的混合比例
* CPU 跟 I/O 全部 load 到 memory，可是可以再去挑哪些 process 應該留在 memory，而哪些應該離開進到 disk 中，可以去控制 ratio 的部分
* 現在的電腦沒有 Long-Term Scheduler，所以使用者要 new 的 process 都不會刻意去拒絕，會全部放到 memory 中，但進來之後如果要再做進一步的管理，就要靠 Medium-Term Scheduler
* 實際上的 memory 空間還是很小，只是 disk 很大而已
2. 控制電腦的 "degree of multiprogramming"
* 當太多人去搶 memory 時，degree of multiprogramming 太高，可以用這個方式來減少 degree，把 memory 讓出來，給真的在等著被 CPU 執行的 process 使用，而不是讓memory 的空間被在 waiting state 的 process 所佔有

###### tags: `OS` `共筆`