# Operating System #5
## CPU scheduler
* 當CPU閒置時，OS就得趕快選其他process讓CPU繼續運作。
* 從ready queue選擇一個process給CPU的動作就是CPU scheduler。
* 這個queue並不是一定FIFO，有很多種實作方法。
### Schedulers
* Schedulers的該部分[前面](https://hackmd.io/@Zero871015/OS-Note3#Type-of-schedulers)有講過，可以先複習一下。
* 對於process，可能有的情形...
* running換到waiting state (例如：遇到需要I/O的情況)
* running換到ready state (例如：時間到了，中斷發生)
* waiting換到ready stare (I/O完成，準備繼續執行)
* Terminates
* 如果排程時上述四種狀況只有一和四會發生，我們稱該排程**nonpreemptive**。
* 簡單但沒效率
* 相對地，如果四種都會發生則是**preemptive**。
* 需要考慮資料分享問題
* 中斷需要發生在kernel mode
* 考慮OS活動其中如果發生中斷
## Scheduling Criteria
* CPU utilization：CPU使用時間，越大越好
* Throughput：每個單位時間完成工作數，越大越好
* Turnaround time：完成時間，process進去到出來的時間，越小越好
* Waiting time：在ready queue的時間，越小越好
* Response time：從提出要求到反應的時間，越小越好
* 
## First-Come, First-Served (FCFS) Scheduling
* 誰先進來就誰先執行，無搶佔。
* 假設以下程序之時間
| Process | Burst Time |
| -------- | -------- |
| A | 24 |
| B | 3 |
| C | 3 |
* 其表現為以下甘特圖(時間日期可以忽略，重點在於實行順序)
```mermaid
gantt
title FCFS
section Time
P1 :a1, 2014-01-01, 24d
P2 :a2, 2014-01-25, 3d
P3 :after a2,3d
```
* 等候時間：
* P1 = 0
* P2 = 24
* P3 = 27
* 平均等候時間 = 17
* 但如果將順序改為`2` `3` `1`
```mermaid
gantt
title FCFS
section Time
P1 :a1, 2014-01-07, 24d
P2 :a2, 2014-01-01, 3d
P3 :after a2,3d
```
* 等候時間：
* P1 = 6
* P2 = 0
* P3 = 3
* 平均等候時間 = 3
* **Convoy effect**：FCFS時，short process最早執行越好。
## Shortest-Job-First (SJF) Scheduling
* 根據Convoy effect，SJF就是將最短的最先執行。
* 一樣無搶佔。
| Process | Burst Time |
| -------- | -------- |
| A | 6 |
| B | 8 |
| C | 7 |
| D | 3 |
```mermaid
gantt
title SJF
section Time
P1 :a2, 2014-01-04, 6d
P2 :a4, 2014-01-17, 8d
P3 :a3, 2014-01-10, 7d
P4 :a1, 2014-01-01, 3d
```
* 平均等候時間：(3 + 16 + 9 + 0) / 4 = 7
## Determining Length of Next CPU Burst
* 實際上我們並不能在執行前得知process的執行時間，因此需要用評估的方法去得到它。
* t𝑛 = 第n次實際執行時間
* 𝜏𝑛+1 = 下次預測的執行時間
* 𝛼, 0 ≤ 𝛼 ≤ 1
* 定義 𝜏𝑛+1 = 𝛼t𝑛 + (1 − 𝛼)𝜏𝑛-1
* 正常𝛼設為`0.5`，越接近`1`越容易受上次實際時間影響預測值
## Shortest-remaining-timefirst Scheduling (SRTF)
* SJF再加上搶占，每個時間都去check哪個process時間最短就去執行它。
| Process |Arrival Time | Burst Time |
| --------|---| -------- |
| A | 0| 8 |
| B | 1| 4 |
| C | 2| 9 |
| D | 3| 5 |
```mermaid
gantt
title SRTF
section Time
P1 :a1, 2014-01-01, 1d
P2 :a2, 2014-01-02, 4d
P3 :a5, 2014-01-18, 9d
P4 :a3, 2014-01-06, 5d
P1 :a4, 2014-01-11, 7d
```
* 平均等候時間： [(10-1)+(1-1)+(17-2)+5-3)]/4 = 26/4 = 6.5 msec
## Priority Scheduling
* 直接賦予process優先度欄位，根據優先度去執行。
* Priority Scheduling也分為可搶占和不可搶占，不過沒有特別的名字。
* 有可能的問題：低優先度的可能永遠不會被執行到，因為一直有更高優先度的process進來。
* 解決方法：使用Aging，讓沒有被執行到的process優先度越來越高，直到它被執行。
| Process | Burst Time |Priority|
| --------|---| -------- |
| A | 10| 3 |
| B | 1| 1 |
| C | 2| 4 |
| D | 1| 5 |
| E | 5| 2 |
```mermaid
gantt
title Priority
section Time
P1 :a3, 2014-01-07, 10d
P2 :a1, 2014-01-01, 1d
P3 :a4, 2014-01-17, 2d
P4 :a5, 2014-01-19, 1d
P5 :a2, 2014-01-02, 5d
```
* 平均等候時間：8.2 msec
## Round Robin (RR)
* 每個Process都得到一段執行時間`q`，若時間`q`內沒有結束就強制換下一個process。
* 為現今OS最常見的排程方法(通常會混和Priority)。
* `q`太大 = FCFS
* `q`太小 = 浪費時間在context switch上
| Process | Burst Time |
| -------- | -------- |
| A | 24 |
| B | 3 |
| C | 3 |
* 懶得用圖了，直接複製...
* 
* 雖然turnaround time不如SJF的表現，然而可以在response time有很好的表現。
* `q`應該要比context switch time大
* 通常`q`在10ms到100ms，而context switch應 < 10ms
## Multilevel Queue
* 對於不同種類的process有不同排程的queue。
* 例如互動性重要的process使用RR、背景執行的則用FCFS。
## Multilevel Feedback Queue
* 在不同的round使用不同的queue。
* 例如第一次用`q` = 4 的RR，如果沒有結束就丟就`q` = 8 的RR，再不結束就使用FCFS等。
---
## Multiple-Processor Scheduling
* 想想看，多個核心的排程中，上圖的a和b有什麼優缺點？
* a可以分配得很平均，減少核心空閒的機會
* b可以將需要共享資料的任務分配給同一個核心，減少衝突的機會
## Linux's Scheduling
* Linux系統中主要使用Priority和RR合併的方式實作排程。
* 在這邊主要想提到裡面一個獨特的變數－－**Nice Value**。
* 在每個Process的PCB中有個Nice Value的變數，代表這個Process的**好人程度**，其範圍是`-20`到`19`。
* Nice Value其實就是一般系統中的Priority Value，代表優先度。
* 當Process的Nice Value越高，代表它人越好，容許別的Process先做事，因此該Process的優先度低。
* 反過來說，一個Process的Nice Value越靠近`-20`代表它人很不Nice，所以它會一直搶占CPU不讓別人做事，該Process的優先度高。
## Processor Affinity
* Thread可能有急迫需要馬上完成的工作或是沒那麼重要的工作，在OS上有兩種排程設定：
* Soft affinity：排程時盡量在時間內完成需求，但如果沒辦法完成也沒關係。
* Hard affinity：**保證**時間內必定完成，若無法保證能夠完成就直接不讓你進行要求。
###### tags: `note`
Sign in with Wallet
Connect another wallet