# 作業系統 Ch5 Process Scheduling
###### tags: `作業系統 Operating System`
相關資料：[mit6.s081 Lab: Multithreading](https://hackmd.io/@Chang-Chia-Chi/BkoQi26kq)
## Basic Concepts
- Multiprogramming
- keep 多個 process 在 memory 中
- 一次只有一個 process 在 CPU 執行，其他的 process 處於 waiting 狀態
- 當執行狀態的行程必須等待資源才能往下執行（I/O request），作業系統拿回CPU的控制權交給等待的行程
- Process Scheduling 的目的是讓 CPU 在每個時刻都有工作可以做，增加使用效率
- Process 基本上不是在執行 instruction，就是在執行 I/O，執行一連串的 instructions 又稱為 burst(CPU burst & I/O burst)
- 一般來說，多數的 CPU burst 時間很短，少部份的 CPU burst 時間很長
- 一個 I/O Bound(I/O 密集) 的 Program 通常有很多短的 CPU burst (若沒有很長的 CPU burst，則通常是 I/O Bound)
- 一個 CPU Bound(計算密集) 的 Program 可能有一些很長的 CPU burst (如很長的 for loop)

### CPU Scheduler
- 從 Ready Queue 選擇誰可以被執行 (也就是將 Process 讀到 CPU 當中)

### Preemptive vs. Non-preemptive
- CPU scheduling 的決定時機主要有以下幾個
1. 從 running 換到 waiting state
2. 從 running 換到 ready state (CPU burst 被打斷，time sharing)
3. 從 waiting 到 ready state
4. 終止狀態
- Non-preemptive scheduling: 若一個 process 可以繼續執行(在 CPU burst)，則不會被打斷
- 因此只會在上面 1. 跟 4. 的情況下作 re-scheduling
- 例如 Window 3.X
- Preemptive scheduling
- 在所有情況都有可能 re-sheduling
- 如 Windows 95 及之後的版本, Mac OS X

### Preemptive Issues
- Preemptive 最大的缺點是 synchronization 的問題
- 需要同步化
- 導致存取 shared data 的問題與對應的 cost
- 對 OS kernel 設計的影響
- 在 kernel 中做 lock & unlock 的設計
- Unix 的解決方法是: 當在 run OS kernel 的 instruction 時，會把 timer disable，從 preemptive 變成 non-preemptive

### Dispatcher
- 由 scheduler 決定誰被執行，dispatcher 執行換人的動作，其負責
- switching context
- 從 kernel mode 轉換到 user mode
- process 換了之後，page table 的 pointer、program counter(load 到新的 state)
- Dispatch latency: dispatcher 執行換人動作，停止一個 process，啟動另一個 process 所需的時間
- Scheduling time
- Interrupt re-enabling time
- Context switch time

## Scheduling Algorithms
### Scheduling Criteria
- CPU utilization
- 理論上是 0% ~ 100%
- 實際上是 40% ~ 90%
- Throughput(從系統的角度)
- 單位時間完成的 processes 量
- Turnaround time(從 single job 的角度)
- submission ~ completion（從ready ~ terminate的時間）
- Waiting time
- Process 執行期間在 ready queue 中等待的時間
- 所以 I/O Burst 不算在 waiting time
- Response time
- submission ~ 第一個 response 產生(第一個 CPU burst 開始執行)

### Algorithms
#### FCFS Scheduling
- 依 (Burst time) 抵達順序執行(先來的先執行)
- P1(24), P2(3), P3(3)
 
- Waiting time: P1=0, P2=24, P3=27
- Average Waiting Time (AWT): (0 + 24 + 27)/3 = 17
- Non-preemptive
- Convoy effect: 很多 process 在等待一個很長 CPU Time 的 process，造成平均等待時間大幅增加的不良現象

#### Shortest-Job-First (SJF) Scheduling
- 時間最短的 process 先處理
- 運用行程下一個 CPU burst 的長度，而非 CPU burst total 長度
- SJF 的 average waiting time 一定是最短的
- Schemes
- Non-Preemptive SJF: 當一個行程拿到 CPU，不會被搶佔直到他完成
- Preemptive SJF: 當有新的行程且他的 CPU burst 的長度比較小，搶佔發生
#### Approximate Shortest-Job-First (SJF)
- SJF 的難處是在執行下一個 CPU burst 之前，無法得知實際的執行長度
- Approximate SJF: 下一個 burst 可預測為過去 CPU burst 長度的 exponential average

#### Priority Scheduling
- 每一個 process 有一個 priority number
- CPU 被分配給高優先度的行程
- Preemptive
- Non-preemptive
- SJF 可視為優先度的排程，其優先度是下一個預測的行程 CPU burst time
- 問題：Starvation -- 優先度低的 process 可能不會被執行
- 解法：aging -- 隨時間增加，若 process 還沒被執行到，則增加優先度
- ex: 每 15 分鐘增加優先度 1

#### Round-Robin(RR) Scheduling
- process 執行時，可在 CPU 執行的時間(time quantum)有限制，通常是 10~100 ms
- 達規定的執行時間後，程式被 preempted 並加到 ready queue 的尾端
- Performance
- TQ Large --> 類似 FCFS
- TQ small --> (context switch) overhead 增加

#### Multilevel Queue Scheduling
- Ready queue 切成分開的 queue
- 同一個 queue 通常放類似功能的 process
- 每一個 queue 有自己的排程演算法
- 因為還是只有一個 queue 的程式可以執行，所以 queue 之間也有排程，常見的作法是用權重的方式隨機挑選一個出來
- Fixed priority scheduling：有 starvation 問題，若最上層的 queue 先做，下層的 process 可能一直做不到
- Time slice：每個 queue 分配一定的 CPU time

#### Multilevel Feedback queue Scheduling
- process 執行的狀況在 run time 才能得知，如過去 CPU burst 多少、呼叫了哪些 system call 等等，系統會在 run time 接收這些資訊並分類放到合適的 queue 中
- process 可以在不同的 queue 中移動，因為也是一種 priority queue，也會有 starvation 的問題，通常搭配 aging 實作
- 一定先執行上層的 queue
- 依照 process CPU burst 的特性分類
- I/O-bound 及 interactive 的 process 在較高層的 queue --> short CPU burst
- CPU-bound 的 process 在較低層的 queue --> long CPU burst

- 當新的 job 抵達 Q0，以 FCFS (First Come First Serve) 演算法排程，若沒辦法在 8ms 內完成，則將 job 移到 Q1
- 同樣地 Q1 也是 FCFS ，若 job 在 16ms 內還是沒執行完，則被 preempted 並丟到 Q2
- 只有當 Q0 ~ Qi-1 是空的時候， Qi 中的 job 才會被執行
- 下一次回來 ready queue 時，系統會依照 feedback 判斷放在哪個 queue 中 (feedback 資訊會放在 PCB 中)
- 通常 scheduling 演算法由以下參數決定
- queues 數量
- 每個 queue 的排程演算法
- 提昇/降級一個行程的方法

### Evaluation Methods
- Deterministic modeling
- 以預定義的 workload 及演算法表現的好壞，缺點是難以通用化
- Queueing model
- 數學分析
- Simulation
- 以隨機數字產生器或 trace tapes 產生 workload
- Implementation
- 最準確的方式就是直接實作並觀察

## Multi-Processor Scheduling Multi-Core Processor Scheduling Real-Time Scheduling
### Multi-Processor Scheduling
- Asymmetric multiprocessing
- 所有系統的執行會由一個 master processor 掌控
- 其他 processors 只執行 user code (由 master 配置)
- 遠比 SMP 簡單
- Symmetric multiprocessing (SMP)
- 每一個 processor 都是 self-scheduling
- 所有 processors 共用 ready queue，或是每一個 processor 有自己的 ready queue
- 需要同步機制
### Processor affinity
- Processor affinity: process 與執行它的 processor 之間有 affinity 關係
- process 會將最近常使用的資料放在執行它的 processor 的快取中
- 快取的無效及資料重新放入是高成本的行為
- Solution
- soft affinity: 允許 process 在不同 processor 執行
- hard affinity: 只能在同一個 processor 執行
### NUMA and CPU Scheduling
- NUMA (non-uniform memory access)
- 發生在結合 CPU 與 memory boards 的系統中
- CPU scheduler 及 memory-placement 會一起工作
- process 被配置在有 affinity 關係的 CPU 的 memory board
- Load-balancing
- 讓不同 processors 間的 workload 盡量平均
- 只在 processor 有 private queue 的系統下才需要
- 兩種策略
- Push migration: 將 processes 移動到閒置或 less-busy 的 processor 中
- Pull migration: 閒置的 processor 將等待中的 task 從其他忙碌的 processor 中拉過來
- 通常是平行實作
- Load balancing 經常抵銷 processor affinity 帶來的效益

### Multi-core Processor Scheduling
- Multi-core Processor:
- 更快且更少的 power 消耗
- memory stall: 當存取記憶體時，花費許多時間在等待資料 available (e.g. cache miss)
- Multi-threaded multi-core systems
- 兩個(或更多)的硬體 thread 被 assign 給每一個 core (i.e. Intel Hyper-threading)
- 當一個 thread 在存取記憶體時，其他 thread 就可以執行 CPU 指令
- Two ways to multithread a processor
- coarse-grained: 當 memory stall 發生時切換到另一個 thread，因為 instruction pipeline 必須被 flush 所以成本很高
- fine-grained(interleaved): 把 pipeline 的狀態保留並切換到另一個 thread 執行，需要更多的 register 來保存資料
- Scheduling for Multi-threaded multi-core systems
- 1st level: 選擇某個 software thread 執行在每個 hardware thread[(logical processor)](https://www.directionsonmicrosoft.com/licensing/2012/03/understanding-logical-processors)
- 2nd level: 每個 core 如何決定執行哪一個 hardware thread

### Real-Time Scheduling
- Real-time 不代表越快越好，重點在 deadline 前要完成
- Soft real-time
- 雖然不希望超過 deadline，但並不會馬上出問題
- 例如影音串流
- Hard real-time
- 若超過 deadline 則導致 fundamental failure
- 例如核電廠的控制

### Real-Time Scheduling Algorithms
- FCFS scheduling algorithm -- Non-RTS
- T1 = (0, 4, 10) == (Ready, Execution, Period)
- T2 = (1, 2, 4)
- Rate-Monotonic (RM) algorithm
- 依據頻率的大小來做排程
- 更短的週期(週期是固定的數值，在 run time 期間不會變動) --> 更高的優先度
- 同一個 task 的所有 job 都有一樣的 priority
- task 的優先度是固定的
- Fixed-priority RTS scheduling algorithm

- Earliest-Deadline-First (EDF) algorithm
- 更早 deadline --> 更高的優先度
- 動態優先的演算法

## Operating System Examples
### Solaris Scheduler
- Priority-based multilevel feedback queue scheduling
- 有六類 scheduling，一個 process 只會屬於某一類:
1. real-time
2. system
3. time sharing
4. interactive
5. fair share
6. fixed priority
- 每一個類有自己的 priority & scheduling 演算法
- Scheduler 會將類的優先度轉換為 global 的優先度
#### Solaris Example(time sharing, interactive)
- 優先度與 time slices 成反向關係，time slice 越小的優先度越高
- Time quantum expired: 當 thread 在沒有 blocking 的狀況下使用整個 TQ，則重新排優先度
- Return from sleep: 若 thread 從 sleeping(I/O wait)回來 ready queue 時，會重新排優先度
- 期望 CPU-bound 的 process 慢慢往下沉，I/O-bound 的 process 慢慢上浮

### Windows XP Scheduler
- Multilevel feedback queue
- 優先度分為 0~31，由優先度最高的 queue 開始排程
- 優先度最高的 thread 永遠在執行
- 每一個 priority queue 使用 Round-robin
- 除了 Real-time 的 task 之外，優先度在 run time 時期動態變更

### Linux Scheduler
- Preemptive priority based scheduling
- 只有 user mode processes 可以被 preempted
- 兩個不一樣的 process priority ranges
- 值越低優先度越高
- TQ 較高者有更高的優先度
- Real-time tasks: (priority range 0~99)
- static priorities
- Other tasks: (priority range 100~14-)
- 依 task 執行狀況動態決定優先度
- Scheduling algorithm
- 若一個 task 還有剩餘的 TQ，則 task 可以被執行，只要還沒耗盡 TQ，都會保留在 active array，希望每一個 task 都能用完它的 TQ
- 當 task 耗盡 TQ，則為 expired 且不應被執行，移到 expired array
- task expire 後，系統會決定新的優先度以及 TQ

## Reference
1. [清大開放課程 - 作業系統](https://www.youtube.com/watch?v=aK0_PBLWCAM&list=PL9jciz8qz_zyO55qECi2PD3k6lgxluYEV&index=38)
2. [Operating System Concept 9th edition](https://www.os-book.com/OS9/slide-dir/index.html)