# CH5 Scheduling
:::spoiler
[TOC]
:::
## 一、CPU 排程簡介
:::success

OS 用 multiprogramming 方法得到 CPU 最大使用率，一般 process 一開始都是 CPU Burst，交由 CPU 去處理該 process，接著是 I/O Burst，做 I/O 資料的傳送。在正常的狀況下，process 就在這兩個狀態間一直循環，最後會呼叫一個終止行程執行的 system call 作為行程的結束。
:::
:::info

CPU scheduling 從在 ready queue 的 process 中挑選 process 進入 CPU 執行。CPU scheduling 選擇的 process 會在以下情況改變 :

- Switches from running to waiting state.
- Switches from running to ready state. e.g. time sharing 因為 time out 回到 - - ready
- Switches from waiting to ready.
- Terminates
:::
:::warning

**[注意] Scheduling under only 1 and 4 is nonpreemptive**
:::

### 1. Preemptive vs Cooperative
:::info

**Preemptive scheduling (當前主流)**

- Higher responsiveness
- Hard to share resources race conditions
- Higher overheads
:::
:::info

**Cooperative scheduling**

- Simpler in design
- Poor responsiveness
- Potential hazards
:::

### 2. Dispatcher
:::info
dispatcher 負責將 CPU 控制權交給經由 Short-term scheduler 所挑選出的 process。

下列情況Dispatcher須執行：

- switching context
- switching to user mode
- jumping to the proper location in the user program to restart that program
:::
:::warning

**[注意] Dispatch latency** – time it takes for the dispatcher to stop one process and start another running ( Context-switch overhead )
:::

### 3. Scheduling Criteria
:::info
CPU 使用名詞

<font color="green">**CPU utilization**</font>：CPU process exec. / CPU total time，CPU 使用的時間
<font color="green">**Throughput**</font>：單位時間內完成的工作數目
<font color ="blue"> Burst time</font>: 執行時間(BT)
<font color ="blue"> Complete time</font>: 完成時間(CT)
<font color ="blue"> Arival time</font>: 到達時間(CT)
<font color="red">**Turnaround time**</font>：完成時間 (**TT=CT-AT**)，進去process到出來花的時間
<font color="red">**Waiting time**</font>：waiting in the ready queue(**WT=TT-BT**)
<font color="red">**Response time**</font>：自使用者命令交付到系統產生第一個回應所需的時間(RT = AT-ST)
(time-sharing system, user-interactive App 特別重視)

:::warning

**[用心去感覺]**

i. <font color="green">**綠色**</font>越大越好，<font color="red">**紅色**</font>越小越好。
ii. <font color="green">throughput</font>vs <font color="red">waiting time</font> : 雖然一直小的效能好，但一直先做小的，大的會餓死。:::
:::

## 二、排程演算法

### 1. FCFS (First-come,First-served) 排程

:::success

就是一般的序列，不可插隊(Non-preemptible)。

- 優點：很公平
- 缺點：低 CPU 利用度
:::
:::info

**護衛效應 (Convoy Effect)**

很多 process 均在等待一個需要很長 CPU Time 來完成工作 process，造成平均等待時間大幅增加的不良現象。對 I/O-bound process 有極糟糕的影響，會造成低 I/O 利用度。
:::

### 2. SJF (Shortest-Job-First) 排程


:::success

短任務先做，分可插隊與不可插隊。
:::
:::info
- 優點：short waiting time.
- SJF (nonpreemptive) : optimal in terms of total waiting time if bursts all ready at 0
- SRTF (preemptive) : optimal in terms of total waiting time if jobs'arrival times are arbitrary
- 缺點：Not fair, starvation issue (low priority processes may never execute)
- Solution：Aging – as time progresses increase the priority of the process
:::
:::warning

**Determining Length of Next CPU Burst**

It is hard to know the precise length of a CPU burst in advance.

**t~n~= 上一次預估的 CPU Burst Time
τ~n~= 上一次實際的 CPU Burst Time
τ~n~+1= 此次預估的 CPU Burst Time
α= 分配比率，常用 α=^1^/~2~**
:::

### 3. RR (Round Robin) 排程

:::success

知更鳥式循環排程法，分時系統所使用的排程法。
:::
:::info

- 優點：
- No process waits more than (n-1)q time units.
- better response (Users feel that processes run "smoothly slow")
- Performance：
- q large：FIFO
- q small：q must be large with respect to context switch, otherwise overhead is too high
- Better response <— (小) Time quantum (大) —> better turnaround time
:::

### 4. Multi-level queue

:::success

**Ready queue** is partitioned into separate queues. Each queue has its own scheduling algorithm.
每個 queue 都有自己的 行程演算法會跑
:::
:::info
**e.g.**
- foreground (interactive) – RR
- background (batch) – FCFS
:::

### 5. Multi-level feedback queue
:::success
運用時間來限制 Mlevel queue 來跑演算法 超過時間的順延

A process can move between the various queues. Aging can be implemented this way.
:::
:::info

e.g. Three queues :

- Q0 – RR with time quantum 8 milliseconds (If not finish, moved to next queue.)
- Q1 – RR time quantum 16 milliseconds
- Q2 – FCFS
:::


:::danger

[用心去感覺] I/O-bound and CPU-bound proces in m-queue
:::
:::warning

- Why do we prefer I/O-bound processes?

- To improve I/O utilization (vs the convoy effect of FCFS)
- To improve the responsiveness (in favor of interactive processes)

- Why CPU processes are given to larger time quantum?

- To improve the throughput / turnaround.
:::

## 三、Multiple-Processor Scheduling (處理器之間)

:::success

**Processor affinity :**
Processor affinity takes advantage of the fact that remnants of a process that was run on a given processor may remain in that processor's state (for example, data in the cache memory) after another process was run on that processor.
:::
:::info

load balancing :

- Push migration – push a process away from a heavily loaded processor to an idle processor
- Pull migration – pull a waiting process from a heavily loaded processor into an idle processor
可以用主被動去思考
- PUSH 被動
- PULL 主動
:::
:::warning

[感覺] The two issues conflict with each other!
互相衝突的
:::