---
title: Ch5:Process Scheduling
---
# 作業系統Ch5: Process Scheduling
###### tags: `Operating System` `Review` `Ch5`

## Basic Concepts

- <font color = red> CPU-I/O burst cycle</font>: Process 執行是由 CPU execution and I/O wait 的 cycle 所組成 (i.e., CPU burst and I/O burst).
- 一般來說，有很大數量的短 CPU bursts 和很小數量的長 CPU bursts。
- A I/O-bound program 通常會有許多非常短的 CPU bursts。
- A CPU-bound program 通常會有許多較長的 CPU bursts。

**CPU-I/O burst cycle**


**Histogram of CPU-Burst Time**


> 一般來說，CPU burst time 較短的頻率會比較多。

### CPU scheduler
- 從 ready queue 選擇 process 去執行。(也就是分配給 CPU 選中的 process)


### Preemptive vs. Non-preemptive scheduling
- CPU 排程決定會發生在一個 process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates

- Non-preemptive scheduling:
- 排程會發生在第一和第四種情況
- Process 會在 CPU 直到它完成中止或切換到 waiting state
- E.g., Window 3.x
- Preemptive scheduling
- 排程會發生在所有情況。
- E.g., Windows 95 and subsequent versions, Mac OS X

### Preemptive Issues

- Inconsistent state of shared data
- 需要 process synchronization
- 產生跟存取共享 data 相關的成本
- 影響 OS kernel 的設計
- 例如 process 在重要變化的過程中間被搶佔 (for instance, I/O queues)，而且 kernel (or the device driver) 需要去 read or modify the same structure 會怎麼樣? Chaos ensues
- non-preemptive kernel (Unix): <font color = red>waiting</font> either for a system call to complete or for an I/O block to take place before doing a context switch. (<font color = red>disable interrupt</font>)
- preemptive kernel: mutex locks to prevent race conditions when 存取共享 kernel data structure。

### Dispatcher

- 將 CPU 的控制權給 scheduler 選中的 process
- Switching context from one process to another
- Switching to user mode
- Jumping to the proper location in the user program 去恢復那個程式。
> dispatcher 是 kernel code segment，所以運作時是在 kernel mode 下。

> 額外補充: [Mode switch without context switch with processes in linux](https://stackoverflow.com/questions/57192112/mode-switch-without-context-switch-with-processes-in-linux)

- Dispatch latency - dispatcher 讓一個 process 停下來且使另一個 process 開始跑所花的時間。
- scheduling time
- interrupt re-enabling time
- context switch time

## Scheduling Algorithms

### Scheduling Criteria

- CPU utilization
- theoretically: 0% $\sim$ 100%
- real systems: 40% (light) $\sim$ 90% (heavy)
- Throughput
- 每單位時間完成的 processes 數量
- Turnaround time
- submission $\sim$ completion
> 可能會遇到搶佔情況，所以並不一定是從 arrive time 可以進入 CPU，加上 burst time 那麼簡單。
- Waiting time
- 在 ready queue 中總等待時間
- Response time
- submission $\sim$ first response is produced
> 從 arrive time 到首次進入 CPU 的時間 (burst time)

### First-Come, First-Served (FCFS) scheduling

- 先到先執行

- 例子一: Processs (Burst time) in arriving order

$\qquad\ P1(24),\ P2(3),\ P3(3)$

- Gantt Chart of the schedule
- 

- Waiting time: $P1\ =\ 0,\ P2\ =\ 24,\ P3\ =\ 27$
- **Average Waiting time(AWT)**: $(0\ +\ 24\ +\ 27)\ /\ 3\ =\ 17$
- **Convoy effect (護衛效應)**: 當 burst time 較短的 process 排在較長的 process 後面，會增加 average waiting time。

- 例子二: 例子一抵達順序的改變

$\qquad\ P2(3),\ P3(3),\ P1(24)$

- Gantt Chart of the schedule


- Waiting time: $P1\ =\ 6,\ P2\ =\ 0,\ P3\ =\ 3$
- Average Waiting Time (AWT): $(6\ +\ 0\ +\ 3)\ /\ 3\ =\ 3$
> Average Waiting Time 會大幅減小，從 17 到 3

### Shortest-Job-First (SJF) scheduling

- 與每個 process 的 CPU burst time 長度有關，越短的越先得到 CPU。
- SJF **提供最短 average waiting time (optimal!)**
- Two schemes
- **Non-preemptive** - 一旦 CPU 給了一個 process， 它直到完成都不能被搶佔。
- **Preemptive** - 如果有一個新的較短 burst length 的 process 到達， 搶佔就會發生。

- Non-Preemptive SJF Example
- 
- 

- $Wait\ time\ =\ completion\ time\ -\ arrival\ time\ -\ run\ time\ (burst\ time)$

- AWT = $[(7\ -\ 0\ -\ 7)\ +\ (12\ -\ 2\ -\ 4)\ +\ (8\ -\ 4\ -\ 1)\ +\ (16\ -\ 5\ -\ 4)\ /\ 4 ]\ =\ 4$

- Response time: $P1\ =\ 0,\ P2\ =\ 6,\ P3\ =\ 3,\ P4\ =\ 7$

- Preemptive SJF Example
- 
- 
- $Wait\ time\ =\ completion\ time\ -\ arrival\ time\ -\ run\ time\ (burst\ time)$

- AWT =
$\begin{split}\\
&[(16\ -\ 0\ -\ 7)\ +\ (7\ -\ 2\ -\ 4)\ +\ (5\ -\ 4\ -\ 1)\ +\ (11\ -\ 5\ -\ 4)]\ /\ 4\\
&= (9\ +\ 1\ +\ 0\ +\ 2)\ /\ 4\\
&=\ 3 \\
\end{split}$
- Response time: $P1\ =\ 0,\ P2\ =\ 0,\ P3\ =\ 0,\ P4\ =\ 2$

#### Approximate Shortest-Job-First (SJF)

- SJF difficulty: 沒有方法知道下一個 CPU burst 的長度
- Approximate SJF: 下一個 CPU burst 可以被預估，以先前 CPU bursts 的測量長度的 **exponential average**。

**Formula:**

$\tau_{n\ +\ 1}\ =\ \alpha t_{n}\ +\ (1\ -\ \alpha)\tau_{n}$

$\tau_{n\ +\ 1}:\ means\ our\ predicted\ value\ for\ the\ next\ CPU\ burst$
$t_{n}:\ means\ the\ length\ of\ the\ nth\ CPU\ burst$

- commonly, $\alpha\ =\ \cfrac{1}{2}$


> 在 $t_{0}$ 時，沒有過去真實經驗，所以隨便 guess 為 10。

### Priority scheduling

- A priority number 跟每個 process 相關。
- The CPU 分配給最高優先權的 process
- Preemptive
- Non-preemtpive
- SJF 也是一種 priority scheduling，它的 priority 是預測到下一次 CPU burst time 的預測值。
- Problem: starvation (餓死) $\rightarrow$ 低權限 processes 永遠不會執行到
- e.g., IBM 7094 shutdown at 1973，有一隻 process 自 1967 年都沒有被 run。
- Sol: aging (隨時間流逝，增加 process 的 priority)
- e.g., 每 15 分鐘增加 1 priority number。

### Round-Robin scheduling

- 每一個 process 得到一個小單位 CPU time (time quantum)，通常 10 $\sim$ 100 ms
- 當 TQ 流逝後， process 被搶佔且加入 ready queue 尾巴。
- Performance
- TQ large $\rightarrow$ FIFO
- TQ small $\rightarrow$ (context switch) <font color = red> overhead</font> increases

> 當 $TQ\ =\ 20$


### Multilevel queue scheduling
- Ready queue 切割成多個 queues。
- 每一個 queue 有自己的 scheduling algorithm
- Scheduling 在 queues 之間一定會完成
- Fixed priority scheduling: 餓死的可能性
- Time slice - each queue 得到一定的 CPU time (e.g., 80%, 20%)。


### Multilevel feedback queue scheduling

- A process 可以在多種不同 queues 間移動， aging 可以實作。
- 根據 CPU burst 的特性去分隔 processes
- I/O-bound and interactive processes in higher priority queue $\rightarrow$ short CPU burst
- CPU-bound processes 在 lower priority queue $\rightarrow$ long CPU burst

> 如果新的 job 進入 $Q_{0}$ 在 8 ms CPU time 還沒做完，就會搬到 $Q_{1}$， 而如果前面 $Q_{0}$ 為空且 $Q_{1}$ 輪到這個 job 執行，在 16 ms 沒有做完的話，就會往下搬到 FCFS 的這個 queue。
> $Q_{i}$ only gets executed if $Q_{0}\ \sim Q_{i\ -\ 1}$ is empty


- 一般而言， multilevel feedback queue scheduler 是由以下 parameters 去定義的。
- queue 的數量
- 每個 queue 的排程演算法
- 決定何時升級 process (到上層) 的方法
- 決定何時降級 process (到下層) 的方法

### Evaluation Methods

- Deterministic modeling - 採用特定預先決定的工作負載量去定義每個演算法針對那樣的負載量的效能。
- 不能一般化。
- Queueing model - mathematical analysis
- Simulation - random-number generator or trace tapes for workload generation
- Implementation - the only completely accurate way for algorithm evaluation (真實數據去實作出來評估)

## Special Scheduling Issues

### Multi-Processor Scheduling
- Asymmetric multiprocessing
- 所有 system activities 透過 一 processor (master) 去處理 。 (減輕對資料共享的負擔)
- 其他只在 user mode 執行 (由 master 分配)
- 設計上比 SMP 簡單。

- Symmetric multiprocessing (SMP)
- each processor is **self-scheduling**
- 所有 processes 可以共用 ready queue。
- 每個 processor 可以有自己 processes 的 private queue。
- 需要 **synchronization mechanism**

### Processor Affinity
- Processor Affinity(親合力): process 想儘量長時間運行在某個指定的 core 上，且不被轉移至其他 core。
- process 填充在 processor 中的 cache memory 最近使用的 data 。
- Cache invalidation and repopulation has high cost
- Solution
- soft affinity: 可能會在 processors 之間遷移。
- hard affinity: 不遷移到其他的 processors。


### NUMA and CPU Scheduling

- NUMA (non-uniform memory access)
- 發生在系統包含組合 CPU 和 memory boards。
> 將各系統視為節點。
- CPU scheduler 和 memory-placement 一起工作。
- 一個 process 被分配到在 CPU 位於電路板上的記憶體中。

> 跨節點存取 memory 很慢，節點內存取速度恨快。


### Load-balancing
- 將工作量平均分配給所有 processors

- Two strategies
- Push migration: overloaded 的 processor 搬移 processes 到 idle or less-busy processor。
- Pull migration: idle processor initialize，告訴那些 overloaded 的processors 可以搬移 processes 過來。

- Load-balancing 和 Processor Affinity 的好處是矛盾的。

### Multi-core Processor Scheduling
- Multi-core Processor
- faster and consume less power
- memory stall: 當存取 memory，它會花費很大量時間等待 data 變得可用。(e.g., cache miss)

- Multi-threaded multi-core systems
- 每個 core 指派兩個以上 threads
- 利用 memory stall 使另一 thread 有進展。


- Two ways to a multithread processor
- coarse-grained: 當 memory stall 發生時切換到另一 thread。 成本很高，因為 instruction pipeline 一定要被 flushed。

- fine-grained: threads之間切換，在 instruction cycle 的 boundary. 架構設計包含對於 thread switching 的 logic - cost is low
> 透過 register 保留 pipeline 上所有 state

> Fine-grained multithreading in a CPU with a 5-stage pipeline: there are never two instructions of the same thread concurrently active in the pipeline. If instructions can be executed out of order, then it is possible to keep the CPU fully busy even in case of a cache miss.


**Example:**


**Fine Grained Multithreading:**


**Coarse Grained Multithreading**


- Scheduling for Multi-threaded multi-core systems
- 1st level: 選擇哪一個 software thread 去 run 在每一個 hardware thread 上 (logical processor)。
- 2nd level: 每一個 core 如何決定哪一個 hardware thread 去 run。

### Real-Time Scheduling
- Real-time 不是指速度，而是保證 deadlines。
- Soft real-time requirements
- 錯過 deadline 是不想要的，但是不會立刻有嚴重錯誤
- Examples: multimedia streaming
- Hard real-time requirements
- Missing the deadline results in 根本性失敗。
- Examples: nuclear power plant controller

#### Real-Time Scheduling Algorithms
- FCFS scheduling algorithm – Non-RTS
- $T1\ =\ (0,\ 4,\ 10)\ =\ (Ready,\ Execution,\ Deadline)$
- $T2\ =\ (1,\ 2,\ 4)$
- Rate-Monotonic (RM) algorithm
- <font color = red>**Shorter period, higher priority**</font>
- Fixed-priority RTS scheduling algorithm
> 同一 task 的所有 jobs 有相同 priority。
> The task's priority is **fixed**。
- E.g., $T1\ =\ (4,\ 1),\ T2\ =\ (5,\ 2),\ T3\ =\ (20,\ 5) (Period,\ Execution)$

$\because\ period:\ 4\ <\ 5\ <\ 20 \\\therefore priority:\ T1\ >\ T2\ >\ T3$


- Earliest-Deadline-First (EDF) algorithm
- <font color = red>**Earlier deadline, higher priority**</font>
- Dynamic priority algorithm
> Task’s priority is not fixed
> Task’s priority is determined by deadline. (看 period 哪一個近)
- E.g., $T1\ =\ (2,\ 0.9),\ T2\ =\ (5,\ 2.3)$

> 到 t = 4 時，新的紅色 task 的 dealine 是 6 ，會晚於橘色的 deadline 5


## Scheduling Case Study
### Solaris
- Priority-based multilevel feedback queue scheduling

- 六個類別的 scheduling:
> real-time, system, time sharing, interactive, fair share, fixed priority
- Each class has its own priorities and scheduling algorithm
- scheduler 會轉變 class-specific priorities 為 global priorities


- priorities 跟 time slices 會反向關係，越高 priority，會有越小的 time slice。
- Time quantum expired: 用完整個 time quantum 還未完成中止，thread 會有新的 priority。
- Return from sleep: 從 sleeping (I/O wait) 回來的 thread會有新的 priority


<br>

### Windows

- Multilevel feedback queue
- Scheduling: from the highest priority queue to lowest priority queue (priority level: 0 ~ 31)
- 最高優先權的 thread always run
- RR in each priority queue
- Priority 動態改變，除了 Real-Time class，分配到哪一 relative 就不再改變。


<br>

### Linux
- user mode processes 可以搶佔，基於 preemptive priority
- 兩個獨立 process priority ranges
- Real-time tasks: (priority range 0~99)
- static priorities
- Other tasks (user space): (priority range 100~140)
- dynamic priorities based on task interactivity
- <font color = red>Lower values indicate higher priorities</font>
- <font color = red>**Higher priority with longer time quantum**</font> (跟前面不一樣)


- Scheduling algorithm
- A runnable task is eligible for execution as long as it has remaining time quantum.
> 一個可運行的任務只要有剩餘的時間量就可以被執行
> 如果某 task 被分配到 time quantum 有 100 ms，但是它只執行 80 ms 就完成的話，某 task 會繼續放在 active array 裡面所對應到優先權的 task lists
- When a task exhausted its time quantum, it is considered **expired** and not eligible for execution.
> 當一個任務用完它的時間量時，它被認為是過期的並且沒有資格執行
> 同樣的，某 task 用完 time quantum 還未執行完，會放入 expired array 裡面所對應到優先權的 task lists。
- New priority and time quantum is given after a task is expired
> 任務過期後給予新的優先級和時間量
> 在 expired array 裡面，task 會獲得New priority and time quantum，此時必須要等到 active array 的 task lists 都為空後，雙方指標會交換指向的位置，進行新的 active array (原先 expired array) 處理。


## Ref

[1] [上課影片 link](https://www.youtube.com/playlist?list=PLS0SUwlYe8czigQPzgJTH2rJtwm0LXvDX)
[2] [投影片 link](https://ocw.nthu.edu.tw/ocw/index.php?page=course_news_content&cid=141&id=999)