###### tags: `operating system` `note` `thu`

# OS-Final (PIC) Scheduling

## Chapter 5. CPU Scheduling

### 5.1.1 CPU–I/O Burst Cycle (p.212)
#### 程序(Process)的執行由兩種狀態交替組合而成:
- CPU execution
- I/O Wait
---

### 5.1.4 Dispatcher (p.215)
#### 派遣(Dispatch)的過程包含了下列程序:
- Switching Context
- Switching to user mode
- 跳轉到合適的Process地方以恢復執行。
#### 我們也希望切換的過程越快越好，否則就會產生如圖的派遣(Dispatch)延遲。
---

### 5.3.5 Multilevel Queue Scheduling (p.226/p.215)
#### Multilevel Queue將程序(Process)分成多種不同的優先順序:
- Real-time process
- System process
- Interactive Process
- Batch Process
#### 並依優先次序進行程序(Process)的選擇。可以看成是Round-Robin的更多選項的進化版。

#### 另外有可以動態調整程序優先順位的進化版，可依固定的規則對程序進行升降(5.3.6)。
---

### 5.6.1 Minimizing Latency(p.239/p.228)
#### 有兩種延遲會影響Real Time System:
- 1. Interrupt Latency
- 先禁止更多的 INT(中斷)
- 將CPU暫存器目前的內容取出(pop)，並存入PCB。
- Check中斷的種類。
- Check中斷的來源。(e.g 哪個裝置)
- 執行中斷(插入)的工作。
- 設定Timer
- 清除中斷暫存器、事件暫存器(Input/Output/Timer)、中斷旗標。
- 排程(找下一個process、資料轉換)
- Select a process from Ready Queue
- Context switch (把PCB內的資料換入CPU的暫存器裡)

- 2. Dispatch Latency
#### 在上圖中，我們有兩個部份構成Dispatch Latency:
- 前一個正在使用資源的程序(Process)
- 低優先度的程序釋出資源的速度太慢。
#### 我們在Real Time System的Scheduling當中，會把Process都當作是週期性的，也就是定時定量。
---

## Chapter 6. Synchronization Tools
### 6.2 The Critical-Section Problem
#### 如果要解決Critical Section的問題，我們需要滿足下列條件:
- Mutual exclusion: 無法同時存取
- Progress: 在沒人用的時候可以把空位讓出來，讓想存取的人選看誰要先(不會一直不用但又不讓)。
- Bounded Waiting: 不會無限等待
#### 可參考[Peterson Algorithm](https://hackmd.io/@tunghaifsm/SkfQ1S5z3#Processes-資源調用)

#### 圖為fork的資源競爭PID情形

#### 圖為使用Mutex Lock跟[Philosopher's Dining Problem](https://hackmd.io/@tunghaifsm/SkfQ1S5z3#f-Philosopher-Dining-Problem)解決問題的示意圖

## Chapter 8. Deadlocks
### 8.3 Deadlock Characterization
#### Deadlock的發生要件有下一面四樣，缺一不可：
- Mutual exclusion: 同時只有一人能存取資源
- Hold and Wait: 只少有一個程序佔用了一個以上的資源，並在等待另一個資源的釋出。
- No preemption: 資源只能由程序自發性的釋出(但他就是要用完才會釋出，只是他也在等別人)。
- Circular Wait: 當下還有他人在等待
#### 而我們也可以從下圖直覺看到，只要$T_2$用完$R_1$並釋出，$T_1$就可以取得$R_1$並繼續執行)。
#### 可以看到出現我們需要考慮這些因素的原因，主要是他們形成了一個Cycle，要不是$R_2$有兩個資源，不然就會形成Deadlock了。只是有Cycle就一定會有Deadlock嗎？
#### 以下圖為例，假設$T_3$向$R_2$又索要了一個資源，那麼就會有Deadlock了，因為$T_2$, $T_3$的願望不可能會同時實現。
#### 我們也可以觀察發生Deadlock的當下有下列兩種Cycle:
$$T_1 \rightarrow R_1 \rightarrow T_2 \rightarrow R_3 \rightarrow T_3 \rightarrow R_2 \rightarrow T_1 \\
T_2 \rightarrow R_3 \rightarrow T_3 \rightarrow R_2 \rightarrow T_2
$$

#### 假設我們今天有另一組下圖的情形。則就沒有Deadlock了，因為有爭議(也就是有Cycle)的資源會在$T_4$結束執行後釋出

#### 所以我們可以有一個小結論，就是 **如果有Cycle，而有爭議的資源又無法在有限的未來中釋出，則我們就進入了Deadlock。**

### Banker's Algorithm
#### Safety Algorithm
* 初始化Work & Finish，"Work"表示可用資源，"Finish"用於記錄進程是否能夠完成執行。
* "Work"的初始值設置為可用資源，將"Finish"的初始值設置為false（即未完成）

Finish[i] == false
Need_i <= Work

* 檢查進程是否能夠滿足其資源需求。如果進程能夠滿足需求，將其標記為已完成（將"Finish"設置為true）並釋放其已分配的資源。並重複此步驟，直到所有進程都被標記為已完成，或者沒有更多可以滿足需求的進程

Work = Work + Allocation_i
Finish[i] = true

#### Resourse-Request Algorithm
* Let $Request_i$ be the request vector for thread $T_i$
* If $Request_i$[j] == k, then $T_i$ wants k instances type $R_j$
* When resources request made by thread $T_i$:
1. $Request_i$ <= $Need_i$ $\rightarrow$ step 2
2. $Request_i$ <= $Avaiable$ $\rightarrow$ step 3
3. 假裝系統分配給$T_i$:

    Available = Available - Request
    Allocation = Allocation + Request_i
    Need_i = Need_i - Request_i

* Need = Max - Allocation
##### 參考教學影片: https://youtu.be/bIX2MTwsUDc