# Process Scheduling
- Multiprogramming 多工處理：
CPU runs process at all times to <span style="color:orange">maximize CPU utilization</span>

- Time sharing 分時系統:
switch CPU frequently such that <span style="color:orange">users can interact</span> with each program while it's running

- <span style="color:orange">Process will have to wait until the CPU is free/context-switch happens then can be re-scheduled</span>
- Process執行的先後順序會由Process Scheduling的演算法去決定

---
## Process Scheduling Queues
- Process switch among states (migrate between different queues)
- <span style="color:orange">Job queue</span> (New state): set of all processes in the system

- <span style="color:orange">Ready queue</span> (Ready state): set of all processes residing in <span style="color:orange">main memory, ready and waiting to execute</span>
- <span style="color:orange">Device queue</span> (Wait state): set of processes waiting for an I/O device


---
## Process Scheduling Diagram

---
## Schedulers

### CPU Scheduler
- 因為time sharing的關係會頻繁發生，所以被稱為short-term scheduler
- CPU Scheduler會選擇要執行的process，載入CPU中，並從<font style="color: orange">**ready state 切換成 run state**</font>

### Job Scheduler
- Long-term scheduler
- <font style="color: orange">**new state 切換成 ready state**</font>

### Medium-term Scheduler
- 當記憶體不夠時會把一些process從memory踢回disk **(Job swapping)**
- 等要執行的時候再把它swap進記憶體裡面等待
- <font style="color: orange">**ready state 切換成 wait state**</font>


---
## Long-Term Scheduler
- Control <font style="color: orange">**degree of multiprogramming**</font> (目前有幾個process正在memory裡面)
- degree太低，會造成CPU閒置
- degree太高，會造成Thrashing，也就是太多process在爭搶有限的memory，造成很多process在memory/disk之前一直swap
- **最好的狀況就是CPU執行的時間要跟I/O執行的時間差不多，也就是要維持一個良好的CPU-bound & I/O-bound process比例**

- UNIX/NT: no long-term scheduler
- 現在的電腦因為memory夠大，基本上都會直接把process全部放到memory裡面(變成medium-term scheduler的工作)
- Multiprogramming degree is bounded by hardware limitation (e.g., # of terminals) or on the self-adjusting nature of users

---
## Short-Term Scheduler
- 執行頻率很高，大約 100ms 執行一次
- 由演算法來縮短每個 Process 的等待時間
- 因為效率要高，演算法也不能太過複雜，避免 CPU overhead 過高
* overhead = (time of pick) / (time of execution + time of pick)


---
### Medium-Term Scheduler
* swap out : 將 Process 由 memory 搬到 disk 中
* swap in : 將 Process 由 disk 搬到 memory 中
* propose : 改善 Process mix(改善CPU與I/O的平衡) / 減少記憶體中的 Process 數量，降低 degree釋放記憶體空間