# OS-Chap5 - CPU scheduling
###### tags: `作業系統 Operating System note`, `110-1`, `2021`
###### nice link: [作業系統概念學習筆記 10 CPU排程](https://www.itread01.com/content/1550575293.html)

# Content
[TOC]

---

# 0. BackGround
- purpose : 為了在 multiprogramming 中能夠提高 CPU 的使用率，將 CPU 在各個 program/program(?) 之間切換
- for 單一處理器 (single processor)
- 每次只允許一個 process 執行，其餘 process 需等待原 process 完成、CPU idle 時，才能被 scheduled
- for multi-processor
- target : 在任何時候都有 process 在執行，使得 CPU 的使用率最大化。
- 當一個 process 必須等待時，作業系統(kernel) 會從該 process 拿走 CPU 的使用權，而將 CPU 交給其他可以執行的 process。

>>>>>>>>>>>>>>>>>> ---
- CPU - I/O 的區間週期(burst cycle)
- ### Process 的執行是由 **CPU execution** 和 **I/O wait** 組成。
- Processes 會在這兩個狀態之間 switch。(CPU burst -- I/O burst)
> - CPU burst = CPU 執行週期 (CPU execution)
> - I/O burst = I/O 等待週期 (I/O wait)

>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ---
- example :
- 普遍而言，有**大量的 short CPU bursts** 和 **少量的 long CPU bursts**
1. 大量的 short CPU bursts ⇨ **I/O-bound** program
2. 少量的 long CPU bursts ⇨ **CPU bound** program

> $ 補充 ~這裡有作業 ~HW 5.6 $

# 1. CPU scheduler (排程管理員)

# 2. Dispatcher
> (真正在做 context switch 的部分、真正把 CPU 控制權 交給 scheduler 選定的 process )
- dispatcher 負責將 CPU 控制權交給經由 Short-term scheduler 所挑選出的 process。

- 下列情況 Dispatcher 須執行：
- switching context : 內容交換/轉換
- register 和 program counter 內容的交換
- = 把 process 搬上搬下
- **switching to user mode**
- ex. 開機。從 kernel mode 轉換到 user mode
- **jumping** to the proper location in the user program to restart that program
> - :-1: 待補 :-1:

- Dispatcher Latency(延遲)
- 把 process 停掉(stop)，儲存(store)，控制權交給另一個process，再把原資料load回去，才開始執行，中間的過程所需要的時間。

# 3. Scheduling Criteria
> ### (衡量 scheduler 效能的準則)
- **CPU utilization(CPU使用率) :arrow_up: → 讓CPU盡量保持忙碌**
- def. CPU 花在 process 執行的時間
- def. CPU process exec. / CPU total time
- exec. = CPU 在執行 process 的時間
- idle = CPU 花在非執行 process 的時間
- total time = exec. + idle
- **Throughput(產能)** :arrow_up:
- def. 單位時間內完成的工作(process) 數目
- **Turnaround time** :arrow_down:
- def. **進去 process 到 出來 花的時間**
- = 完成時間 (完成-到達)
- = finish - enter ready queue
- **Waiting time** :arrow_down:
- **在 ready queue 等待得到 CPU** 的所有時間
- **Response time :arrow_down: ( = turnaround time - brust time/ exec. time)**
- 從 **user 下命令進入系統，到產生第一個回應所需的時間**。
- (= process進入 ~ 要被執行前的time slot)
- time-sharing system, user-interactive App 特別重視

> ### 排程的目標 : :arrow_up: :arrow_down:
- Resource utilization(資源使用率) :arrow_up:
- Fair(公平)
- No starvation

# 4. Classification of CPU scheduler Algorithm
> ### CPU 排程演算法大致的分類
## Preemptive vs Non-Preemptive :heavy_exclamation_mark: 必考 :heavy_exclamation_mark:
### preemptive
> 可以被中斷/可搶奪型/可以被插隊
- 若有一新 process 需先使用 CPU，**不論正在執行的 process 是否完成工作，可以立即被新 process 中斷**、並馬上執行新的process。
- 使用時機:
- process state = running → waiting
- e.g. I/O 請求、呼叫 wait 等待一個 sub process 的 terminate
- process state = running → terminate
- process state = running → ready
- e.g. time sharing 因 timeout 回到 ready、interrupt 發生
- process state = waiting → ready
- e.g. I/O 完成
- 適用於real-time system, time sharing system

### Non-preemptive = cooperative scheduling
> 不可被中斷/不可搶奪型
- 當一個 process 在使用 CPU 時，除非該 process 自行放棄 CPU 的使用權，否則**其他 process 不可奪取其 process 使用權**。
- 使用時機:
- process state = running → waiting
- process state = running → terminate

:star: 都自願要放棄了會甚麼還要打斷他放棄呢~~~

# 5. Algorithm with scheduling
## a) FCFS_______(First Come First Serve)
- def. Arrival Time (到達時間) 愈早 (小) 的Process，愈優先取得CPU控制權
> - 先進入 ready queue 的 process，會先被抓進 CPU runn，直到執行完畢。退出後，才會再從 ready queue 抓入下個 process。
- non-preemptive
- Convey Effect (護衛效用): short process behind long process
> - 當長作業先執行時，不利於後方短作業的執行。
> - 很多 Processes 均在等待一個需要很長 CPU Time 來完成工作的 Process，造成平均等待時間 (Avg. Waiting Time) 大幅增加
- 適用 CPU 繁忙的 OS，不利 I/O 繁忙的 OS。
- I/O execute 時間太長
- Example
- process table:
- Q1 & A1
- Q2 & A2

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ------------------
## b) SJF_______(Shortest Job First)
- ready queue 中，burst time 越短的 process 越早被抓入 CPU run。
- 分成 preemptive 和 non-preemptive

- preemptive:
- 若 ready queue 有更短的 process 可以被選擇，正在執行的 process 將立刻被暫停(run→ready)，換新的 process 進入執行
- t = 2 時
-- P1 尚未作完(remain burst time = 5)
-- 但同時間 P2 進入 ready queue，且 P2 的 burst time = 4 < P1 burst time = 5
➨ 所以 P1 中止 (dispatcher做事！)，讓 P2 先執行

- non-preemptive:
- 即便 ready queue 有更短的 process 可以被選擇，正在執行的 process 仍會先執行完自己的 job，做完後才在 ready queue 中找最短的 task 執行。
⇨⇨⇨ 在完成之前都不會被打斷
- t = 7 時
-- P1 已經完成
➨ 所以在 ready queue 中找最符合的 process (P3)，load 入 schedule(dispatcher做事！)

- Table

| | preemptive | non-preemptive |
|:-----------------------:|:-----------------:|:--------------------------:|
| Definition | 可以被中斷 | 不可被中斷 |
| Avg. waiting time | :arrow_down: 較佳 | :arrow_up: 較差(∵護衛效應) |
| Context switch 頻率 | :arrow_up: 多 | :arrow_down: 少 |
| Convey effect(護衛效應) | :x: | :o: |

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ------------------

## c) PQ_(Priority)
- Process 優先權最高，越優先取得 CPU 的控制權。
- **Starvation**
- **def. process 長期或無限期無法獲得系統的資源.**
- 優先權越低的 process 永遠無法執行。
- solution
- **Aging**
- 過一段時間就將 queue 中 priority 小的 process 的優先權+1(優先權降低、數字增大)。
- 讓長時間待在系統內，卻未完成工作的 process 提高 priority。


>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ------------------

## d) RR_(Round-Robin)
- OS會規定一個 CPU Time Slice 'q' (=Time Quantum，時間片段)，讓每個 process 進入 CPU 時，至多只能使用 CPU 執行 q 的長度
> - 若未能在 'q' 時間內完成，則此 process 會被迫放棄CPU (process state = Running → Ready)，並等待下一輪迴再使用CPU。
- Performance
- 取決於 'q' 的大小
- q large (≌⋈) → 退化成 FCFS
- q small (≌0) → Context switch太頻繁，CPU Time未真正用在 process exec.
• ∴Throughput (產能) 低。
- 'q' 該如何抉擇？
• 通常80%的工作可以在Time Slice內完成，效果較好。
- 通常使用在 Time-Sharing System 居多
- 實作方法:
- 需 Hardware 的支援 – Timer
> - Process 取得 CPU 後，Timer 的 initialize 為 Time Slice 的值，隨著Process的執行，Timer的值逐次遞減，直到 Timer 的值為 0，會發出 **“Time out” 中斷** 通知OS，OS會強迫目前的Process放棄CPU。
>

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ------------------
## e) MLQ_(Multilevel Queue)
-
-
-

>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> ------------------
## f) MLFBQ(Multilevel Feedback Queue)

---

# Multiple-Processor Scheduler (多處理器的排程)

# Real-time CPU scheduling (即時系統 CPU 排程)

---

## HomeWork
> ppt 5.3, 5.4, 5.6, 5.7, 5.8, 5.10, 5.22
> TA 5.3, 5.4, 5.5, 5.6, 5.7, 5.8, 5.10, 5.14, 5.15, 5.22

### 5.3
- Lottery Scheduling
- 利用給予 processes lottery tickets 的方式，當作進入 CPU 執行的門票
- 而是否能進入 CPU 執行，則是用抽籤 (random select) 的方式選擇。
- 執行的方式
- 一張票可以每ms 執行 50 次
- 贏了 lottery 後，該 process 可以執行 20 ms (( 50次 * 20 ms = 1s
- Ｑ：要如何改變執行的方式，保證 high-priority 的 threads 相較於 low-priority 有較高的機會能執行？
- Ａ：給予 high-priority 較多的 lottery tickets，low-priority 給予較少的 tickets，又因用 random choose 的方式選擇 processes，所以 high-priority 被抽重的機會會大大提升，而 low-priority 的也不至於產生 starvation(餓死)。

### 5.4
1. 每個 processor 有自己的 run queue
在多核系統的情況下，若每個 processor 有自己的 run queue，因為不同的 process 彼此間本來就有進行的先後順序，一旦將這些 process 被放進不同 processor 的 queue 時，需要在不同的 processor 之間做「同步」的行為。
- advantages
- 若需要同時 run 兩個以上的 processes 時，每個 processes 都可以被分配到各自的 processor。
- disadvantages
- 若不同 processor 在執行 process 時，動到 global variable (shared memory)，則須要使用 lock 和 context switch 來解決 race condition 狀況的發生。

2. 所有的 processor 用同一個 run queue
- advantages
- 會自動幫你排好 processes 的執行順序
- disadvantages
- 傳入同一 run queue 時要排隊。


> 補：run queue 是什麼？
> - 能夠在處理器(processor) 上執行的 process
> - 

### 5.6
- 題意：
- 每次 process 得到 CPU 的執行時間(time quantum)，並完全使用整個時間量程，不會做到一半要進行 I/O 的事(不阻塞 I/O），該 process 得到的 time quantum 就將增加 10 ms ( q 的上限是 100ms )
- 當一個 process 在使用其 time quantum 前阻塞(執行 I/O )時，其 time quantum 將減少 5 ms，但它的優先級保持不變
- Ａ：此 RR 較適合做 CPU-bound，而非 I/O bound。
- 因 CPU-bound 一直在 CPU 內部做計算或執行其他功能，不會和外界互動，所以每次都將增加 10ms ，直到達到 q 的上限。
- 非 I/O bound 的原因是 : 某 process 可能沒有辦法做完 time quantum 就得執行 I/O 的事，將導致自己的執行時間被減少 5ms ，但 priority 不變，到最後就只會被呼叫，context switch 進來後，就得馬上被 switch 出去，完全沒執行到(?)

> I/O bound vs CPU bound
> - I/O bound
> - 大多時間在做 I/O
> - ex. disk 和 CPU 的資料傳輸、和使用者互動、和硬體(資料輸入到印表機)互動
> - CPU bound
> - 大多時間在做 CPU 內部的事(做 CPU 內的 clock cycle)，沒有和使用者互動
> - ex. code 中的 count++
>
>- 

### 5.7

### 5.8

### 5.10
- ### A: B 和 D

### 5.22