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

# Chapter 5: CPU Scheduling

## 0. 名詞解釋
### a. Throughput
- 吞吐量: 單位時間內Terminate的process數量。
### b. Turnaround Time
- 執行程式從created到terminated的時長。
### c. Job time
- CPU的計算時間(不含I/O)

## 1. 排程演算法
### a. First Come First Serve (FCFS)
- 先來的就先處理(Queue)
#### i. 優點
- 簡單
#### ii. 缺點
- 可能會因為一個很長的Job Time而使每個人都要等很久
- 平均每人等待時間可能最長。

### b. Shortest Job First (SJF)
- Job time最短的先做
- 電腦在預測時通常使用Exponential Average來計算Job Time:
$$
\tau_{n+1} = \alpha \cdot t_n + (1 - \alpha) \cdot \tau_n
$$
#### i. 優點
- 平均每人等待時間最短。
#### ii. 缺點
- Job Time的時間難以凖確估計。
#### Q. Job Time會重新計算嗎？

### c. Round-robin (RR)
- 按優先等級排好，從優先等級高的選。
- 為了公平地調度進程，通常採用分時機制，為每個作業分配一個時隙或時間片（它允許的 CPU 時間），如果作業到那時還沒有完成就中斷作業。
#### i. 優點
- 量少的人不需要浪費時間等待量大的人。
#### ii. 缺點
- 量大的人會因為不斷的被中斷而花多餘的時間來完成作業。
### d. Priority
- 基於優先級的進程調度方法，選你要的優先處理。在優先級，為每個進程分配一個數字，表示其優先級。數字越小，優先級越高。
### e. Multi-level Queue
#### i. Priority
- 就緒隊列中的進程可能會被分為不同的類，每個類都有自己的process需求。
##### 優點
- process永久分配到隊列中，因此具有調度開銷低的優點。
##### 缺點
- 如果一些更高優先級的隊列永遠不會變空，一些process可能會餓死CPU。
- 它本質上是不靈活的。
#### ii. Feedback
- 順序是有意義的，系統會依循 queue 順序執行程序，必須等上面的 queue 內容為空，才會往下執行下一個 queue 裡的程序。

## Processes 資源調用

### 1. Critical Section
- ***兩個*** 以上的processes的某一個區段都想共用同一塊資源，則這些區段就被稱為***Critical Section***。
- 因此我們會需要對同一個資源的存取進行管理。
- e.g. 電腦帳戶, Process ID(可能同時Request到同一個)

#### a. Peterson Algorithm
- 如果今天我們有兩個人都想要用同一個資源，就會有下面兩個變數影響存取的情形:
- i. 意願: 自己想不想存取
- ii. 規則: 有沒有輪到自己
- 因此 ***Peterson Algorithm*** 假設有兩支程式P0, P1, 並且使用下列參數:

// 兩個變數都為兩支程式共用
// flag[] is boolean array; and turn is an integer
flag[] = {false, false}
int turn;

- 其中`flag[]`表示所有人想存取資源的意見陣列，而`turn`則表示所有人同意使用資源的人(共識/規則)。
- P0:

// 表示自己希望存取資源
flag[0] = true;

// 先輪到對方(P1)存取資源。
// 如果對方(P1)後來，他就會把turn設成自己(P0)。
// 因為對方(P1)也會先把turn設成對方(P0)
// 就會有先到先用的功能。
turn = 1;

// 在對方希望存取資源，而且也輪到對方時
while (flag[1] == true && turn == 1)
{
    // 存取沒有衝突的資源
}
/* 
 * 存取有衝突的資源 (Critical Section)
 */

// 表示自己已經用完了，對方要用可以用。
flag[0] = false;

- P1:

// 表示自己希望存取資源
flag[1] = true;

// 先輪到對方(P0)存取資源。
// 如果對方(P0)後來，他就會把turn設成自己(P1)。
// 因為對方(P0)也會先把turn設成對方(P1)
// 就會有先到先用的功能。
turn = 0;

// 在對方希望存取資源，而且也輪到對方時
while (flag[0] == true && turn == 0)
{
    // 存取沒有衝突的資源
}
/* 
 * 存取有衝突的資源 (Critical Section)
 */

// 表示自己已經用完了，對方要用可以用。
flag[1] = false;

- 因此這個演算法解決了下面的問題:
- i. 衝突: 我想存取，但還沒輪到我
- ii. 浪費: 我不想存取，但輪到我

#### b. Bakery Algorithm

#### c. Test and Set Lock (TSL)

#### d. Compare and Swap (CAS)

#### e. Semaphore

#### f. Philosopher Dining Problem
- 假設今天有n個Process同時想使用同一個資源
- 就像有n個哲學家在同一個餐桌上月餐，但餐具卻少於n個。
- 問題在於如何設計一套規則，使得在哲學家們在完全不交談，也可以持續的用餐(no deadlock)，沒有人會餓死(no starvation)。
##### i. 服務生解法
- 哲學家必須經過他的允許才能拿起餐叉。
- 因為服務生知道哪支餐叉正在使用，所以他能夠作出判斷避免死結。
##### ii. 資源分級解法
- 資源（餐叉）按照某種規則編號為1至5，每一個工作單元（哲學家）總是先拿起左右兩邊編號較低的餐叉，再拿編號較高的。
- 用完餐叉後，他總是先放下編號較高的餐叉，再放下編號較低的。
##### iii. 使用Dirty的標記

### 2. Entry Section

## Deadlock的必要條件
### 1. Mutual Exclusion
#### 一個資源一次只能被一個process所使用
### 2. Hold & Wait
#### process取得一個資源之後等待其他的資源
### 3. Circular wait
#### 一組process形成循環等待的關係。資源只能由process自己釋放，不能由其他方式釋放

### 4. No preemption
#### 每個process都握有另一個process請求的資源，導致每一個process都在等待另一個process釋放資源

### Solutions:
#### 1. Prevention
提供一組方法去確認至少一個必要的死結情況不會發生。這些方法靠著限制資源的需求來達成預防死結。

#### 2. Avoidance
要求作業系統給出額外的資訊，關於一個process在他的lifetime裡會要求的resource。有了這些額外的資訊，作業系統可以決定是否讓程序的要求繼續等候。為了決定現在的要求是否能滿足，作業系統必須考慮現在資源的存量、資源的分配量、和未來資源的要求與釋放。

#### 3. Detection & Recovery
不多加限制，讓Process任意取得Resource，不過OS要能夠偵測目前是否有Deadlock存在，如果發現有則執行Recovery破除Deadlock，恢復正常狀況。簡而言之就是浪費時間一個一個檢查看有沒有Deadlock並且修復。