# Ch8 ~ Ch9 其他 CPU scheduling
在第七章的 CPU scheduling 都符合四大公設，然而在現實，我們不會事先知道每個 process 的 execution time。在這兩章，我們會介紹其他 CPU scheduling。

## Multi-level Feedback Queue（MLFQ）
- **目標**：在不考慮 **execution time** 的情況下排程
- **結構**：
- 由多個 queue 組成，每個 queue 的 priority 不一樣
- 會先執行 priority 較高的 queue
- **基本原則**：
- 當 **Priority(A) = Priority(B)**：對 A、B 做 **RR（Round-robin）**
- 當 **Priority(A) > Priority(B)**：只執行 A
- 每個 process 抵達時皆從** top priority** 開始
- 當 process 跑完時：降低 priority
- 無論是一次跑完還是分批跑完
- 定期將所有 process 提升到 top priority，避免飢餓，回應行為改變

## Proportional Share
### Ticket
- 使用 ticket 來表示資源分配比例
- 例如：
| Job | Ticket | CPU use time |
| -------- | -------- | -------- |
| A | 100 | 33% |
| B | 50 | 16% |
| C | 250 | 49% |
- **目的**：不進行任何其他排序，較為直接
- **好處**：抽中票券者得以執行（隨機但趨近公平）

### Lottery Scheduling
:::warning
一個**完全隨機**的 CPU schduling
:::
- **Ticket Currency**：使用者可依內部邏輯分配票券，系統自動換算成全域票值。
- **Ticket Transfer**：作業可暫時轉讓票券（如 client → server）。
- **Ticket Inflation**：作業可臨時調整票數（限於信任環境）。
- **執行方法**：
- 隨機抽取一張票，尋找中獎的 process，執行中獎的 process
- 例如：
- 系統抽到 296 號 ticket
- 執行 Job C
- 執行次數愈多，愈接近機率
- **問題**：必須大量執行才可能接近機率，執行次數過少會產生不公平

### Stride scheduling
:::warning
並非隨機，有精確計算的正確比例 CPU time
:::
#### 基本原理
每個 job 會被分配一個：
- **Tickets**：代表它會使用到的 CPU time 比例
- **Stride**： $\mathrm{Stride_{i}} = \frac{\mathrm{LCM(all\ tickets\ of\ jobs) 的倍數}}{Tickets_i}$
- **Pass**：
- 追蹤目前 job 累積的進度
- 每次執行完 job 就會增加一個 stride

#### 執行流程
- 計算 stride
| Job | Ticket | CPU use time | Stride |
| -------- | -------- | -------- | ---- |
| A | 100 | 33% | 100 |
| B | 50 | 16% | 200 |
| C | 250 | 49% | 40 |
- 初始 pass 為 0：
- pass 不同時：執行 Pass 最低 job
- pass 相同時：隨機執行 job
- 範例：