# OS chapter 5
###### tags: `作業系統`
:warning: <font color=#ffa07a>橘色字體標題為老師強調要背的</font>

## *Basic Concepts*
**名詞解釋**
- CPU burst : 使用 CPU 的時間（使用期）
- I/O burst : 使用 I/O 的時間（使用期）

**CPU-I/O Burst Cycle**
| Process execution | Burst |
| ------------------------------------- |:---------------------- |
| a cycle of CPU execution and I/O wait | CPU burst -> I/O burst |
---

## *CPU Scheduler*
CPU scheduler 選擇一個在ready state的process進入running state

**CPU scheduling decisions會發生在一個process在...**
1. running state -> waiting state
2. running state -> ready state
3. waiting state -> ready state
4. 終止

**nonpreemptive**
process在狀態1和4的時候是不可以出現插隊(不可中斷的)的狀況

**preemptive**
process除了狀態1和4其他都可以插隊(可中斷的)
雖然說是可以插隊(中斷)，但還是需要先考量到共用資料、是否在kernel mode及它們是不是真的能中斷

## *Dispatcher*
**名詞解釋**
short-term scheduler: 馬上要用的
media-term scheduler: 可能過一段時間才會執行到，所以先放到其他地方，等需要的時候再呼叫
long-term scheduler : 決定長期process載入kernel
dispatcher : 在scheduling中，真正把process搬上搬下(context switch、user-mode switch)，還有把CPU控制權交給scheduler所選的process

**Dispatch latency**
dispatcher停止一個process到開始另一個process的時間

## <font color=#ffa07a>*Scheduling Criteria*</font>
- CPU utilization :arrow_up: : 讓CPU越忙越好
- Throughput :arrow_up: : 每個時間單位內完成越多個process越好
- Turnaround time :arrow_down: : 執行一個process的總共時間
- Waiting time :arrow_down: : 一個process在ready queue裡面等待被安排到running state的時間，越少越好
- Response time :arrow_down: : 發出一個請求信號直到process第一次回應的時間，越少越好

**Turnaround Time = Total waiting time + Total burst time**

## <font color=#ffa07a>*Scheduling Algorithms*</font>
### **First-Come , First-Served(FCFS) Scheduling**
先來的process就先處理
:::success
#### 範例一

**Gantt Chart**
:::

:::info
#### 範例二
:::

**Convoy effect** : 從上面兩個範例可以發現，如果burst time比較長的先執行的話，比較短的process會等比較久

***

### **Shortest-Job-First(SJF) Scheduling**
process的burst time比較短的優先

:::success
:question: 那如果新進的process更短，那它是不是可以排在更前面(插隊)?
因為考慮到可以插隊及不可以插隊的情況，該scheduling需要探討兩個方法

**方法一 : nonpreemptive**
如果來了一個process更短的，必須等到現在在執行的process跑完才可以輪到它

**方法二 : preemptive**
如果來了一個process更短的，就算現在這個process還沒執行完也可以先以新來的這個優先安排
這個方法又有另一個別稱 : **Shortest-Remaining-Time-First(SRTF)**

:warning: 考試的時候如果沒有特別要求是哪一種寫法的話，那兩種都要寫 :cry:
:::

:::info
#### 範例一 SJF
在這個範例裡面假設process是同時間抵達的，因為是nonpreemptive所以只需按照burst time從小排到大即可
:::

:::warning
#### 範例二 SRTF
時間表
:heavy_check_mark: : scheduler選擇
:o: : 該process已完成
:x: : 該process還沒出現

| time\burst | P1 | P2 | P3 | P4 |
|:---------- |:-------------------- |:--------------------- |:-------------------- |:-------------------- |
| 0 | 8 :heavy_check_mark: | :x: | :x: | :x: |
| 1 | 7 | 4 :heavy_check_mark: | :x: | :x: |
| 2 | 7 | 3 :heavy_check_mark: | 9 | :x: |
| 3 | 7 | 2 :heavy_check_mark: | 9 | 5 |
| 5 | 7 | :o: | 9 | 5 :heavy_check_mark: |
| 10 | 7 :heavy_check_mark: | :o: | 9 | :o: |
| 17 | :o: | :o: | 9 :heavy_check_mark: | :o: |
| 26 | :o: | :o: | :o: | :o: |

---

計算avg waiting time的兩種算法
1. total waiting time - arrival time
2. end time - arrival time - burst time

:warning: 這邊第一個算法應該是10-0

:::

:::info
#### 範例三

**SJF**

1. total waiting time - arrival time
2. end time - arrival time - burst time
avg time = [(0 - 0) + (7 - 2) + (8 - 4) + (12 - 5)] / 4 = 4
avg time = [(7 - 0 - 7) + (8 - 2 - 4) + (12 - 4 - 1) + (16 - 5 - 4)] / 4 = 4

| time\burst | P1 | P2 | P3 | P4 |
|:---------- |:-------------------- |:-------------------- |:-------------------- |:-------------------- |
| 0 | 7 :heavy_check_mark: | :x: | :x: | :x: |
| 2 | 5 :heavy_check_mark: | 4 | :x: | :x: |
| 4 | 3 :heavy_check_mark: | 4 | 1 | :x: |
| 5 | 2 :heavy_check_mark: | 4 | 1 | 4 |
| 7 | :o: | 4 | 1 :heavy_check_mark: | 4 |
| 8 | :o: | 4 :heavy_check_mark: | :o: | 4 |
| 12 | :o: | :o: | :o: | 4 :heavy_check_mark: |
| 16 | :o: | :o: | :o: | :o: |


**SRTF**

1. total waiting time - arrival time
2. end time - arrival time - burst time
avg time = [(11 - 2 - 0) + ((5 - 4) + (2 - 0) - 2) + (4 - 0 - 4) + (7 - 0 - 5)] / 4 = 3
avg time = [(16 - 0 - 7) + (7 - 2 - 4) + (5 - 4 - 1) + (11 - 5 - 4)] / 4 = 3

| time\burst | P1 | P2 | P3 | P4 |
| ---------- |:-------------------- |:-------------------- |:-------------------- |:-------------------- |
| 0 | 7 :heavy_check_mark: | :x: | :x: | :x: |
| 2 | 5 | 4 :heavy_check_mark: | :x: | :x: |
| 4 | 5 | 2 | 1 :heavy_check_mark: | :x: |
| 5 | 5 | 2 :heavy_check_mark: | :o: | 4 |
| 7 | 5 | :o: | :o: | 4 :heavy_check_mark: |
| 11 | 5 :heavy_check_mark: | :o: | :o: | :o: |
| 16 | :o: | :o: | :o: | :o: |


:::
***

### **Round Robin(RR)**
剛剛SRTF的方法有一個問題，如果進來的一直是比較短的process，那這樣比較長的process就永遠不會被安排到(俗稱**starvation problem**)，為了解決這個問題，我們給定一個固定的時間**time quantum(q)**，使每一個process都可以輪流到執行，其中不管process完成了沒，只要時間到了就換其他的process執行

:::success
**範例 time quantum = 4**
因為題目沒特別說所以視所有process同時間抵達
avg time
1. total waiting time - arrival time
2. end time - arrival time - burst time
avg time = [(6 - 0) + (4 - 0) + (7 - 0)] / 3
avg time = [(30 - 0 - 24) + (7 - 0 - 3) + (10 - 0 - 3)] / 3
:::

:::info
**Effect of time quantum**
結論 : time quantum越小，切換次數越多
:::

***

### **Priority Scheduling**
每一個process都會有一個權重，權重越高者優先，但以權重去處理的話就會像SRTF的問題一樣，權重越低者可能永遠都不會執行到，所以我們可以結合其他的方法使其不會出現starvation problem

:::success
**範例一**
權重高者做完才換低的做
:::

:::info
**範例二 w/ Round-Robin**

權重高者做完才換低的做
因為有權重相同者，所以權重相同者會以time quantum去輪流執行
我們可以看到雖然time quantum只有2 ms，但在t = 16 ~ t = 20的時候都是P3，這是因為權重 = 2者在這個時候只剩下P3了，所以就不需要去管time quantum了
:::

***

### **Multilevel Queue**
我們按照不同的權重去將process們分成不同的列隊

***

### **Multilevel Feedback Queue**
給予每個列隊time quantum，如果這個列隊時間到了但裡面的process還有沒做完的，就得換另一個列隊

## Thread Scheduling
**process-contention scope(PCS)** : M:M 和 M : 1 models，thread library把user-level thread放在LWP上面執行，由programmer操作

**system-contention scope(SCS)** : kernel thread是被排程給可使用的CPU，由系統操作

## Multiple-Processor Scheduling
**Symmetric multiprocessing(SMP)** : 每個processor自己排程，可以讓所有的thread在共同的ready queue裡面，或是每一個processor的thread有其各自的queue

***
#### 架構
:::success
**架構一 : Multicore Processors**
- 在同一個晶片上面放上多個處理器
- 快速且低耗能
- 當memory被取回時，利用memory停滯時間，取得其他行程中的progress。
:::

:::info
**架構二 : Multithreaded Multicore System**
- **Chip-multithreading(CMT)** 將每個core指派**兩個以上的thread**，如果正在執行的thread正在**memory stall**的話，那就切換到另一個thread執行

- Intel將CMT稱為**hyperthreading**

- two levels of scheduling
1. OS決定哪一個**software thread**要在哪一個**CPU**上執行
2. 每一個core決定哪一個**hardware thread**要在哪一個**physical core**上執行

:::

***
#### 介紹完幾個多重處理器的架構之後我們來討論多重處理器應該要注意的重點
- **Load Balancing(負載平衡)** : 讓工作量保持平均分配
- Push migration : 比較忙得CPU把工作分散出去
- Pull migration : 比較悠閒的CPU去要求工作
- **Processor Affinity(姻親關係)** : 行程有affinity(姻親關係)給正確執行的處理器
- Soft affinity : OS讓一個thread在同一個processor跑完，but **no guarantees**
- Hard affinity : 指定一個process只能在某個處理器或某群處理器裡面執行

## NUMA and CPU Scheduling
如果OS是馮紐曼的話，它會讓記憶體離有thread在CPU上跑的那個CPU近一點，這樣能夠更快去存取記憶體和資料

## Real-Time(及時) CPU Scheduling
- Soft real-time systems：不保證重要的real-time process會何時被排程。
- Hard real-time system：必須在dead line前完成工作。

- **event latency** : 某個事件第一次出現到回應它的時間

兩種會影響表現的latency :
1. Interrupt latency : 從中斷抵達到開始執行中斷的時間

2. Dispatch latency : dispatcher停止一個process到開始另一個process的時間
conflict phase :
- 任何可中斷的行程在kernel mode中執行。
- 從低優先行程中釋放出資源，將資源放到高優先行程中使用。

## Priority-based Scheduling
為了real-time scheduling，所以排程需要**能夠支持可中斷且priority-based的排程**。
- 但只保證soft real-time。
- hard real-time必須要提供能符合dead line的能力。
- 如果process是週期性的需要CPU的話，那就需要進行periodic(週期性的)檢查。

## Rate Montonic Scheduling
在這種scheduling中權重為period的倒數，所以短的週期就會有高的權重，長的週期就會有低的權重

:::success
**範例一**

deadline沒說就視同於period time

**第一個P1**的deadline = 50，因為burst time只有20所以它有在deadline前完成

**第一個P2**的deadline = 100，時間到了50的時候剛好是第一個P1的deadline到，所以P1的新的一輪又開始了，所以換成P1，時間到了70的時後又回到P2這邊，因為剛剛就有先執行了所以現在burst time只剩5，所以它也有在deadline前完成

**第二個P1**的deadline = 100，因為burst time只有20所以它有在deadline前完成

**時間到了100的時候**剛好是第二個P1和P2的deadline結束，兩個process都開始新的一輪，但因為P1的權重比P2高所以P1先執行，接著以此類推

:warning: 這邊我有去問老師它的waiting time怎麼算，但老師回答我說它沒有waiting time，但我覺得有點怪怪的，可以參考一下
:::

:::info
**範例二**

**第一個P1**的deadline = 50，因為burst time只有25所以它有在deadline前完成

**第一個P2**的deadline = 80，時間到了50的時候剛好是第一個P1的deadline到，所以P1的新的一輪又開始了，所以換成P1，時間到了75的時後又回到P2這邊，因為剛剛就有先執行了所以現在burst time只剩10，但它跑完的時候已經超過deadline的時間了，所以它沒有在deadline之前完成

:::

## Earliest Deadline First Scheduling(EDF)
- 因為Rate Montonic Scheduling會miss掉沒有在deadline前完成的，所以有了這個scheduling，在這個scheduling就不會出現沒辦法在deadline前完成的process
- 權重根據deadline決定，越早的deadline權重越高，越晚的deadline權重越低

:::success
**範例**

:warning: 這邊我有去問老師它的waiting time怎麼算，但老師回答我說它沒有waiting time，但我覺得有點怪怪的，可以參考一下

(Period , Burst) of P1 and P2 are (50 , 25) and (80 , 35)

:heavy_check_mark: : scheduler選擇
:o: : 已完成，如果在deadline之前完成的話可以讓下一個process提早執行

| time\process deadline | P1 | P2 |
|:--------------------- |:---------------------- |:---------------------- |
| 0 | 50 :heavy_check_mark: | 80 |
| 25 | :o: | 80 :heavy_check_mark: |
| 50 | 100 | 80 :heavy_check_mark: |
| 60 | 100 :heavy_check_mark: | :o: |
| 80 | 100 :heavy_check_mark: | 160 |
| 85 | :o: | 165 :heavy_check_mark: |
| 100 | 150 :heavy_check_mark: | 165 |
| 125 | :o: | 165 :heavy_check_mark: |

:::

## Test Bank
:::warning
( A ) 1. throughput為單位時間內完成的process數，所以應該是越多越好
( D ) 2. 按照每個選項的定義就可以得到答案，定義在Scheduling Criteria
( B ) 3. turnaround time = waiting time + burst time；response time = 抵達到開始執行的時間，因為不一定會一次就執行完所以也可視為first waiting time
( AB ) 4. starvation probelm : 有些process可能永遠都不會被執行到，因為SRTF原理是越短的burst time越優先，所以長的burst time可能永遠都不會被執行到
( A ) 5. 因為SRTF講求的就是越短的burst time排越前面，所以它的avg waiting time會是最短，至於RR因為加入time quantum所以不會是最小
( C ) 6. response time = first waiting time,所以先FCFS已抵達優先順序，所以它的waiting time = response time
( C ) 7. nonpreemptive的意思是在現在執行的這個process執行完畢才可以換別的process執行，按照定義即可知道答案
( B ) 8. SFJ和SRTF會以burst time比較小的優先，所以response time不會是最長的；RR因為有time quantum所以也不會是最短( :shit: 好難解釋喔自己領悟一下)
( D ) 9. 不太清楚feasible response time是什麼意思 :shit:
( D ) 10. time sharing : 時間共享，RR以time quantum公平分配每個process的執行時間
:::
***
參考 :
https://ithelp.ithome.com.tw/articles/10205122
https://ithelp.ithome.com.tw/articles/10204690