[toc]

## Chapter 3

### Program v.s. Process

Program: 是磁碟上的可執行檔 (executable file)，靜態不會動
Process: 是把該程式載入記憶體並執行後的「活的個體」，會隨時間推進
**同一個 Program 可以同時有很多個 Process**（例如你開兩個終端同時跑 `vim`）。

* 正式定義
**Process = program in execution**（執行中的程式），其執行必須依序推進（sequential fashion）。一旦把可執行檔載入記憶體並啟動（按滑鼠、CLI 呼叫），程式就成為程序。 

* 記憶體中的構成
一個程序的位址空間典型包含：
**text**（程式碼）、**PC/暫存器**（現行活動）、**stack**（參數/回傳位址/區域變數）、**data**（全域變數）、**heap**（動態配置）。


### Process States

#### 狀態集合
**new、ready、running、waiting、terminated** 是標準五態模型（有些圖上也會標出 zombie 作為終止後父未回收的特例）。


* 直觀流程
程序被建立（new）→ 進就緒佇列（ready）等待 CPU → 被排到 CPU 執行（running）→ 若需 I/O 或等待事件則進 **waiting** → 事件結束回 **ready** → 結束（terminated）。
* 小提醒
狀態轉換是由**排程器**與\*\*中斷/陷入（I/O 完成、time slice 用完）\*\*觸發，不是應用程式自行更改；這會牽涉到後面談的排程與情境切換。

### PCB (Process Control Block)

PCB 就是 OS 用來「**記住一個程序現在長怎樣**」的資料結構。**只要能把 PCB 存起來再載回來，就能把同一個程序在不同時間片間斷—續執行**。

* 欄位內容包括：
1. **process state**（狀態）
2. **program counter**（下一條要執行的指令）
3. **CPU registers**（所有與程序相關的暫存器）
4. **CPU scheduling info**（優先權、佇列指標）
5. **memory-management info**（位址空間/段頁表）
6. **accounting info**（已用 CPU 時間、時限）
7. **I/O status info**（配給的 I/O、開啟檔案清單）

### 情境切換 (Context Switch)

CPU 要把「舊程序的上下文（registers、PC 等）」**存**到它的 PCB，再把「新程序的上下文」載回來。這段時間系統不做實際工作，屬額外開銷。

*Context* 就是 PCB 代表的那份狀態；**OS/PCB 越複雜，切換成本越高**。硬體若有多組暫存器，能降低切換成本。


### 額外補充

1. 為什麼需要 PCB 與狀態機？
想像你在玩手遊（程序 A），收到訊息跳去回覆（切到程序 B），回完再回到手遊。
* 切走時，**A 的 PCB** 存下：目前關卡、角色座標、CPU 暫存器、程式計數器等
* 切回時，OS 讀回 **A 的 PCB**，你就從剛才停下的位置繼續玩。
這就是 **ready / running / waiting** 等狀態流轉與 **context switch** 在做的事。

---

### Scheduling

系統想讓 CPU 不閒著，就要把「準備好能跑的程序」快速接續上 CPU。誰先上？等誰回來？這就是 Scheduling 的工作。

**Process scheduler**：從可執行的程序中選出下一個在 CPU 核心上執行，並維護各種Process Queue。目標是**最大化 CPU 使用**並**迅速切換** Process。

### Queue

* **Ready queue**：在主記憶體、已就緒、只等 CPU 的程序集合。
* **Wait queues**：正在等事件（常見是 I/O 完成）的程序集合。
* **程序會在各 Queue 間「遷移」**：新建 → 就緒 → 執行；若發生 I/O 則進等待，I/O 完成再回就緒，如此往復至終止。


### 3 種 Schedulers
1. **Short-term / CPU scheduler（短程排程器）**
* 決定「**下一個**上 CPU 的是誰」，**極高頻率**觸發（毫秒級），所以**要很快**。很多系統只顯式實作這個。
2. **Long-term / Job scheduler（長程排程器）**
* 決定哪些程序**被帶入就緒佇列**（控制系統「**多道程度**」= 同時在記憶體的程序數）。**不常觸發**（秒到分鐘），追求好的**程序組合**（I/O-bound 與 CPU-bound 的平衡）。
* 定義：
* **I/O-bound**：程式大多時間在「等 I/O」（磁碟、網路...），CPU 只要短短算一下就又去等 I/O 了。
* **CPU-bound**：程式大多時間在拼命算，幾乎不等 I/O。
3. **Medium-term scheduler**
* 當需要**降低多道程度**時，把某些 Process **swap out** 到磁碟；之後再**swap in** 回來繼續。

### Dispatcher & Context Switch

* Dispatcher：當 short-term Scheduler 決定了「下一個要跑的程序」，實際把 CPU **交棒**給它的那段工作（切換模式、載入上下文、跳到目標程序起始位址）由派遣器完成。
* Context switch：把舊程序的 **PCB** 狀態（PC、暫存器…）**存**起來，並把新程序的上下文**載**回來。這段時間是**額外開銷**，OS/PCB 越複雜，切換時間越長；也受硬體是否支援多組暫存器影響。

### 額外補充

#### 為什麼「I/O-bound 與 CPU-bound 的比例」超重要？
* 若系統裡**全是 CPU-bound**，Ready Queue 會長、I/O 裝置閒置，互動體驗變差。
* 若**I/O-bound 很多**，I/O 裝置忙但 CPU 反而常空轉。
* Long-term Scheduler 試圖取得一個「好組合」，使 CPU 與 I/O 都能被充分利用。

#### Multitesk in Mobile System
行動裝置通常採取 foreground & background process 來執行 / 回收 Process

---

### Process Creation

#### 父子關係與 PID
* **parent** 可建立 **children**，子程序也能再生出後代，形成**Process Tree**；Process以 **PID** 被識別與管理。
* 建立後，OS 要為 Child Process 設定 Address、link resource與Add queue。

#### 資源共享策略

1. **父子共享所有資源**
2. **子分享父資源的子集**
3. **父子完全不共享**

#### 執行策略

* **concurrent**：父與子同時跑
* **parent waits**：父等待子結束後才往下走

#### 位址空間

* **子為父的複本**（傳統 `fork()` 模式；現代以 COW 優化）。
* **子載入一個全新的程式**（`exec()` 之後）。

#### UNIX：`fork()` → `exec()` → `wait()`

* `fork()` 產生子程序；
* `exec()` 在子程序**以新程式覆寫位址空間**；
* 父以 `wait()` 等子結束並取得狀態。

**最小可行 C 程式**

pid_t pid = fork();
if (pid == 0) { // child
    execlp("ls", "ls", "-l", (char*)NULL); // 以新程式覆寫子程序
    _exit(127);                            // 只有 exec 失敗才會到這
} else if (pid > 0) {
    int status; 
    pid_t c = wait(&status);               // 取得子程序結束狀態與 pid
}

> 關鍵理解：**fork 複製進程（含描述表等），exec 再把子進程的位址空間替換成新程式**；父親 `wait()` 以回收子程序與拿 exit code。 

### Process Termination

#### 正常終止與 `exit()`

* 程序執行到最後或主動呼叫 `exit()` 要求 OS 刪除自己；OS 回收資源，並把 **狀態碼** 回傳給父（透過 `wait()`）。

#### 非正常終止與 `abort()`（父殺子）

* 父可要求 OS 中止子程序，常見理由：**超過資源配額**、**子任務不再需要**、**父要退出而系統不允許遺留子**。

#### Cascading termination

* 某些 OS 規定「**父死子亦亡**」：當父終止時，所有**子孫程序一併被 OS 終止**。

#### `wait()` 的角色、zombie 與 orphan

* **父以 `wait()` 等子結束**，可得到 **pid** 與 **status**；若父不等，子結束後會成 **zombie**（核心只保留退出狀態等待回收）；若**父先終止**而**未 `wait()`**，子成 **orphan**（交由 init/systemd 收養）。 

### 補充
#### Mobile System 的 Process 回收與多程序架構
* **Android Process Importance Hierarchy**：為了回收記憶體，系統會依 **Foreground → Visible → Service → Background → Empty** 的重要度由低到高進行終止（先殺「最不重要」）。這與「多道程度/壓力控制」概念呼應。 
* **Chrome 瀏覽器的多程序架構**：早期單程序瀏覽器易被單一標籤頁拖垮；多程序（Browser/Renderer/Plugin 分離）可提升 **穩定性與隔離性**。

### Interprocess Communication (IPC)
* **動機**：
1. 資訊共享（Shared State）
2. 計算加速（並行/管線化）
3. 模組化（分離權限/容錯邊界）
4. 便利性（使用者與服務互動）
* **挑戰**：正確性（同步/互斥）、效能（複製 vs 共享、系統呼叫成本）、安全性（存取控制）

### Shared-Memory
* **概念**：兩個（或多個）程序把各自位址空間的一段**映射到同一份實體頁框**，彼此直接讀寫該區域。
* **特點**：
* 資料**零拷貝**（使用者態直接存取），吞吐高、延遲低。
* **同步交給應用**：必須搭配鎖/信號量/條件變數等，避免競爭與撕裂。
* **典型範式**：Producer–Consumer（bounded buffer）。

### Message-Passing
* **概念**：程序以 OS 提供的 `send/receive` 交換訊息（可能經核心緩衝）。
* **特點**
* **語義清楚**（OS 負責同步與隔離），較容易分散式化。
* 可能有**資料拷貝開銷**（使用者↔核心↔使用者），延遲較高。
* **三個設計維度**
1. 命名（naming）：
* **Direct**：`send(P, msg)`、`recv(Q, msg)`；彼此知道對方身分（PID/端點）。
* **Indirect**：透過 **mailbox/port**；多對一、一對多更自然，鬆耦合。
3. 同步（synchronization）：
* **Blocking send/receive**：像握手（rendezvous），簡單但可能降低併發。
* **Non-blocking**：呼叫立即返回；需自備輪詢、事件、或回呼/完成端口。
5. 緩衝（buffering）：
* **Zero capacity**：收發必同時到位（同步點）。
* **Bounded**：到上限即阻塞或錯誤（需定義策略）。
* **Unbounded**：理論上不阻塞（實作受限於記憶體）。


### Shared Memory

Producer          Shared Buffer (ring)         Consumer
  put(x)    ->   [ ... | slots | ... ]   ->     get()

* 生產者寫入、消費者讀出，**in/out** 兩個索引循環前進。
* 需保證：不讀空、不寫滿；多生產者/多消費者時須互斥與順序一致性。
* Unbounded-buffer v.s. bounded-buffer: 無限制、限制 buffer 空間

#### 同步關鍵
* **互斥（mutex）**：保護臨界區（更新 in/out、寫讀單位）。
* **計數（semaphore/condvar）**：
* `empty` 記錄剩餘空槽；`full` 記錄可讀項。
* `empty.P()` 才能寫；`full.P()` 才能讀。
* **記憶體一致性**：避免**指令重排/快取一致性問題**；跨程序常使用 **具可見性的同步原語** 或 **記憶體欄柵（fence）**。

### 常見 API

* **POSIX System V**：`shmget`（配置段）、`shmat`（附掛）、`shmdt`、`shmctl`。
* **POSIX shm\_open** + `mmap`：以檔名式共享記憶體（/dev/shm），方便權限管理與清除。
* **Windows**：File Mapping（`CreateFileMapping`/`MapViewOfFile`）。

### pipes
* *Ordinary pipes*：親子程序間單向（UNIX）。
* *Named pipes（FIFO）*：非親子也能通；可做雙向（兩條）。
* **UNIX Domain Sockets**：本機全功能 socket（支援傳檔案描述元）。
* **Windows**：LPC/ALPC、Named Pipe、`PostMessage`（GUI 訊息）等。
* **Mach（微核心）**：一切皆訊息，系統呼叫透過 port 傳遞。
* **網路 IPC**（Client–Server）
* Sockets（TCP/UDP/UDS）、RPC/RMI（stub + 序列化 + 傳輸 + 一次語義）、gRPC/Thrift 等。

### Client–Server

* **Sockets**：`<IP/UDS, port>` 為端點；TCP 提供可靠串流、UDP 提供低延遲資料報。
* **RPC**：遠端程序呼叫，本地以 **stub** 偽裝成函式，「封送（marshal）」參數後透過傳輸層送出；需處理 **失敗語義**（at-most-once / at-least-once）。
* **RMI**：物件導向版本（Java RMI 等），處理參考/物件生命週期與序列化。

### 補充
#### 設計抉擇與常見坑

* **延遲/吞吐**：Shared Memory ≫ Message Passing（省拷貝、少系統呼叫）。
* **安全/隔離**：Message Passing ≫ Shared Memory（OS 幫你隔離）。
* **分散式擴展**：Message Passing 更自然（RPC/消息佇列）。
* **共享資料結構複雜度**：Shared Memory 需要嚴格同步與記憶體語義；Message Passing 用訊息邊界營造不變量。

#### 效能細節

* **系統呼叫成本**：send/recv 進出核心；共享記憶體可在使用者態內迭代。
* **拷貝開銷**：核心緩衝 ↔ 使用者緩衝；Zero-copy 需要 pinning / scatter-gather / `sendfile` 類接口。
* **快取行為**：Shared Memory 容易**false sharing**；考慮對齊、填充、分區。

#### 正確性與死結

* **鎖順序**、**超時回退**、**有界緩衝**、**重試與冪等**（特別是 RPC）。
* 設計協定時明確規範：序列號、重送、去重、錯誤碼、backoff 策略。

#### 把 IPC 放入「OS 全局」

* **排程**：I/O-bound 服務通常以非阻塞 I/O 或多路複用提高併發；CPU-bound 工作則以共享記憶體 + 鎖/無鎖結構降低拷貝。
* **記憶體管理**：Shared Memory 實為特殊的 **多重映射頁**；TLB/快取行為會影響可見性與效能。
* **檔案系統**：命名管道、UNIX socket 檔、`shm_open` 名稱空間皆與 VFS/名稱空間整合，方便權限控管與生命週期管理。

## Chapter 4

### Single and Multithreaded Processes


### Thread

* 一個**程序（process）** 像是一個「容器」：裝著程式碼、位址空間、開啟檔案、權限與各種資源。
* **執行緒（thread）** 則是「容器裡的執行路徑」；同一個程序可以有多條路徑同時往前跑。
* 因為在**同一個容器**，多執行緒會**共享**：程式碼區、全域資料、heap、開檔表、工作目錄、信號處理設定等；但**各自擁有**：**PC（程式計數器）**、**暫存器**、**自己的 stack**、**執行緒專屬資料（TLS/TSD）**。
* **Thread = 程序內的一個可被排程的執行單位**。
* **TCB（Thread Control Block）**：核心或執行緒庫記錄每個執行緒的狀態（就緒/執行/等待）、PC、暫存器、堆疊指標、優先權、所屬程序等。
* **切換成本**：執行緒切換只換 per-thread 的上下文與（通常）不換位址空間，**比程序切換輕**。
* **實作模型**：
* *使用者層執行緒*（Many-to-One）：切換快、但阻塞 I/O 會卡整個程序，無法真平行。
* *一對一核心執行緒*（One-to-One，Linux/Windows/現代 JVM 常見）：可平行、阻塞互不影響，但數量成本較高。
* *Many-to-Many/Two-Level*：折衷，允許彈性對映與部分綁定。

#### 表對照

| 項目 | Process | Thread |
| ----------------- | -------- | ----------- |
| 程式碼 / 全域資料 / Heap | shared | shared |
| 開啟檔案（FD/Handle） | shared | shared |
| 訊號處理設定 | 程序層 | 多半共享（可指定目標） |
| **Stack** | 各程序獨立 | **每執行緒一份** |
| **PC/暫存器** | 各程序獨立 | **每執行緒一份** |
| **控制區塊** | PCB | **TCB** |

### Benefits
1. Responsiveness（回應性）
* GUI/互動式應用：把**耗時 I/O 或計算**丟背景執行緒，主執行緒保持可回應（不「無回應」）。
* 伺服器：I/O 等待期間，其他執行緒仍能服務請求。
2. Resource Sharing（易於共享資料）
* 同程序內的執行緒共享位址空間，**IPC 幾乎為 0 成本**（直接讀寫共享結構），比跨程序用管道/共享記憶體更簡單。
* 代價是**同步**：必須用 mutex、RWLock、條件變數、原子操作來保護臨界區。
3. Economy（經濟性）
* **建立/終止**、**情境切換**比程序便宜。
* 大量短生命週期的工作，用**執行緒池**（thread pool）比「一直 fork/exec」划算。
4. Scalability（可擴展性）
* 在多核心/多 CPU 上，**不同執行緒可同時平行**執行。
* 量化直覺：Amdahl’s Law
$$
Speedup \le \frac{1}{S + \frac{1 - S}{N}}
$$
假設程式 90% 可平行（$p=0.9$），在 8 核上上限約 $1/(0.1+0.9/8)\approx 4.7$。
→ 提醒：**減少不可平行部分**與**提升資料/快取區域性**，往往比盲目加執行緒更有效。

### Concurrency vs. Parallelism

* **Concurrency（並發）**：程式**結構上**有多條控制流，可交錯推進（單核也能並發，靠排程切換）。
* **Parallelism（平行）**：**同一時刻**有多條控制流在**不同核心**上同跑。
* 多核心程式設計的目標，是把「可並發」的工作**有效地映射**到多核心硬體上，取得**可伸縮**的加速。


### Parallellism

* **Data Parallellism**：同一計算對**獨立資料分片**重複執行（向量化/迴圈平行化）。
* **Task Parallellism**：多個**相對獨立任務**並行（如多張圖同時濾波）。


### User Threads v.s. Kernel Threads

* **User Level**：程式/執行緒庫看得到的「邏輯執行緒」。如：`pthread_create()`、`std::thread`、Java `Thread`。
* **Kernel Level**：OS 看到並排程的「內核執行實體」。如：Linux task、Windows thread。

| 模型 | 對映 | 特色關鍵字 | 優點 | 缺點 | 代表/歷史 |
| ---------------------- | --------------------- | -------------- | ------------------ | ------------------------- | ------------------------- |
| **Many-to-One** | 許多 UL | 「**快，但不平行**」 | 切換極快、平台要求低（舊時期） | **任一執行緒阻塞 = 全程阻塞**；無法利用多核 | 早期 Green Threads、舊式語言執行環境 |
| **One-to-One** | 1 UL | 「**普世主流**」 | 真平行、阻塞互不影響、診斷容易 | 建立/切換較貴；太多執行緒可能壓垮排程器/記憶體 | Linux NPTL、Windows、現代 JVM |
| **Many-to-Many** | 許多 UL → **少數 N 個** KL | 「**彈性、可控並行度**」 | 可平行；阻塞不拖累；UL 排程仍便宜 | 實作複雜；與 OS 互動（I/O、訊號）難 | 早期 Solaris / research 原型 |
| **Two-Level** | M:N + **允許部分 1:1 綁定** | 「**混合＋可綁定**」 | 關鍵執行緒可保證跑在獨占 KL 上 | 實作/維護更複雜 | Solaris 9+ 時期的混合線程 |

> **LWP（Lightweight Process）**：在某些系統（如老 Solaris）中，介於 UL 與 KL 之間的**可被核心排程**單位。UL threads 綁在 LWP 上，LWP 再由核心排程。


### Threads Library

提供一組 API 讓程式員建立／管理執行緒與同步。實作方式有兩種：純使用者態或作業系統支援的核心態。常見的三套庫是 **Pthreads、Windows、Java**。

#### POSIX Threads（Pthreads）

**定位**
* **POSIX 標準（IEEE 1003.1c）** 的 API 規格，定義行為而不拘泥實作；在 Unix-like（Linux、macOS）上廣泛使用。可做成使用者態或核心態版本。
**你需要記住的 API 類別**
* **建立/回收**：`pthread_create()`、`pthread_join()`／`pthread_detach()`
* **互斥/同步**：`pthread_mutex_*`、`pthread_cond_*`、`pthread_rwlock_*`、`pthread_barrier_*`
* **屬性/TLS/取消**：`pthread_attr_*`、`pthread_key_*`（TSD/TLS）、`pthread_cancel()`（延遲/非同步，預設延遲，涉及取消點與 cleanup）

#### Windows Threads

**定位**
* **Win32 API** 的核心執行緒，採 **一對一（1:1）** 映射（每個使用者執行緒對一個核心執行緒）。
**執行緒內容（Context）與資料結構**
* 每個執行緒具備：**thread id、暫存器組、使用者/核心態堆疊、私有儲存區**（DLL 及執行期用）。主要結構：**ETHREAD（executive）**、**KTHREAD（kernel）**、**TEB（user）**。

**你會用到的元素（觀念）**
* 建立/等待：`CreateThread()` / `WaitForSingleObject()`
* 同步：`CRITICAL_SECTION`、`SRWLOCK`、`CONDITION_VARIABLE`、`Event/Semaphore`
* 高併發 I/O：**Thread Pool** 與（課本另處提到的）I/O 完成機制（理解為配合池化，避免「每連線一執行緒」）

#### Java Threads（含 Executor）
**定位與建立方式**
* **JVM 管理** 的執行緒，通常以底層 OS 的執行緒模型實作；建立可用 **繼承 `Thread`** 或 **實作 `Runnable`**（標準做法）。
**Executor Framework（超重要）**
* 以 **Executor 介面** 把「任務的提交」與「執行緒的生命週期/排程」解耦，不必手動 `new Thread()`；課本附有使用示意。
**取消語義（對照 Pthreads）**
* Java 走 **協作取消**：以 `interrupt()` 設中斷旗標，目標執行緒自行檢查並收尾。

### Implicity Threading

> 當執行緒數上升，正確性與可維護性變難；**由編譯器/執行期**代為建立與管理，課本列出 5 種方法。

手動 `create/join` 很容易錯（race、死結）、也難以控制規模；把排程與並行度交給「通用機制」，可提升**正確性**與**維護性**。常見做法有五類：**Thread Pools、Fork–Join、OpenMP、GCD、TBB**。

#### Thread Pools

* **概念**：先準備一組執行緒，任務丟進佇列，池內執行緒自行撿取執行。
* **好處**：
1. 免去頻繁建立/銷毀的成本 → **反應更快**
2. 可以設定池大小 → **受控的並行度**
3. 可支援**延遲／週期任務**等策略
* **何時用**：大量短任務（例如網服請求處理、工作列隊）。

#### Fork–Join（分而治之框架）

* **概念**：把大任務遞迴切成小任務（fork），各自執行後再**合併結果（join）**。
* **執行期技術**：多用工作竊取（work-stealing）平衡負載，降低「尾部慢」問題。
* **適合**：分治演算法（如 quicksort、樹/圖遍歷、歸約）。


#### OpenMP

* **概念**：以 `#pragma`（或等價指示）標註**平行區域／平行迴圈**，編譯器與執行期幫你做切分與同步。
* **適合**：共享記憶體機器上的**資料平行**迴圈（獨立工作項）。


#### Grand Central Dispatch

Two types of dispatch queues:
* serial: blocks removed in FIFO order, queue is per process, called main queue
> Programmers can create additional serial queues within program
* concurrent: removed in FIFO order but several may be removed at a time

#### Intel TBB（oneTBB）

* **概念**：C++ 的平行骨架庫，提供 `parallel_for`、`parallel_reduce`、flow-graph 等高階構件；執行期負責工作分配與負載平衡。
* **適合**：需要可攜、可組合的 C++ 平行構件。

### Semantics of `fork()` and `exec()`

* 問題一：`fork()` 在多執行緒程式中，**只複製呼叫者執行緒**還是**複製全部執行緒**？（部分 UNIX 提供兩種 `fork` 版本）
* 問題二：`exec()` 一般會**以新程式映像取代整個執行中程序**（包含所有執行緒）。
* 備忘：多執行緒程式中常見建議是「**`fork()` 後儘快 `exec()`**」，避免子程序碰到父程序帶來的鎖/狀態不一致。

### Signal Handling

* UNIX 的 **signal**：用來通知程序發生事件；由**default handler**或**user-defined handler**處理（流程：產生→遞送→處理）。
* **單執行緒**：訊號送到整個程序等同送到那唯一執行緒。
* **多執行緒**：可選擇遞送策略
1. 送到**特定目標執行緒**
2. 送到**所有執行緒**
3. 送到**部份執行緒**
4. 指定**單一專責執行緒**接收全部訊號
* 備忘：實作上常用「**專責訊號執行緒 + 其他執行緒遮罩**」的做法來集中處理。

### Thread Cancellation

* 目標：**在尚未完成時終止目標執行緒（target thread）**。
* 兩種方式：
* **Asynchronous**：立刻終止目標執行緒。
* **Deferred**：目標執行緒**定期檢查**是否應取消（在「取消點」生效）。
* 進一步細節：
* 取消請求發出後，是否真的取消取決於**執行緒當前狀態**；若目前**禁止取消**，請求會被**延後掛起**。
* **預設型態是 deferred**，只有在**取消點**才會實際取消；可用 `pthread_testcancel()` 檢查，取消時會呼叫 **cleanup handler**。
* Linux 上**以訊號機制**處理 thread cancellation。
* Java 對照：以 `interrupt()` 實作**延遲/協作式取消**，設定**中斷旗標**後由執行緒自行檢查處置。
* 備忘：實務偏好 **Deferred / interrupt 協作式**，避免在臨界區被「硬殺」破壞不變量。


### Thread-Local Storage

* 定義：讓**每個執行緒擁有一份獨立資料副本**；與一般區域變數不同，TLS 的可見範圍可**跨越多次函式呼叫**；語義上像 static，但**每執行緒唯一**。
* 典型用途：**執行緒池**情境下的每執行緒暫存/狀態（你無法控制執行緒建立時機）。
* 記得在執行緒結束時清理 TLS，避免記憶體洩漏。

### Scheduler Activations

* 適用範圍：**M:M 與 Two-level** 模型需要**核心↔使用者層**雙向溝通，以維持**合適數量**的核心執行緒供應給應用。
* 常見中介：**LWP（lightweight process）**，像「虛擬處理器」，使用者層可把執行緒排到 LWP 上；每個 LWP 連到一個核心執行緒。
* 機制：**scheduler activations** 透過 **upcalls**（核心→執行緒庫的回呼）把事件與資源狀態上送，使應用能**維持正確的核心執行緒數量**。
* 備忘：重點不是 API，而是**雙層排程如何保持一致**與**I/O/阻塞事件如何回饋**。

### Windows Threads

* **模型**：實作 **one-to-one（1:1）** 對映，屬kernel-level執行緒；開發以 **Windows API** 為主。
* **每個執行緒包含**：
* **Thread ID**（識別）、**暫存器組**（處理器狀態）、**使用者態與核心態兩份堆疊**、**私有資料區**（供執行期與 DLL 使用）。這些合稱該執行緒的 **context**。
* **主要資料結構**：
* **ETHREAD**（executive thread block）：指向所屬流程與 **KTHREAD**（核心空間）。
* **KTHREAD**（kernel thread block）：排程/同步資訊、核心態堆疊、指向 **TEB**。
* **TEB**（thread environment block）：thread id、**使用者態堆疊**、**TLS**（thread-local storage），位於**使用者空間**。


> 小結：Windows 的執行緒是 OS 一等公民；1:1 對映帶來良好的平行度與清楚的觀測/除錯界面（ETHREAD/KTHREAD/TEB 架構）。

### Linux Threads

* **命名**：Linux 將執行緒稱為 **tasks**。
* **建立方式**：透過 `clone()` 系統呼叫；**旗標**（flags）決定子 task 與父 task 共享哪些資源（如位址空間），因此可形成**與程序不同程度的共享**。
* **核心結構**：`struct task_struct` 連結到各種**程序/執行緒的資料結構**（共享或獨有）。

> 小結：Linux 以 `clone()` 加上 flags 彈性控制「像程序」或「像執行緒」的共享程度；在實務上對應到我們熟知的 **NPTL（1:1）** 風格與 `task_struct` 為核心載體的管理方式。

# Chapter 5: CPU Scheduling

## Basic Concepts

* 透過多程式設計（multiprogramming）可獲得最大的 CPU 使用率。
* **CPU–I/O Burst Cycle（CPU–I/O 交替週期）**：
程式執行包含了 CPU 執行與 I/O 等待的循環。
* 一個 CPU burst 之後會接著一個 I/O burst。
* CPU burst 的分佈是主要關注的部分。

## Histogram of CPU-burst Times

* 有大量的短執行期（short bursts）。
* 有少量的長執行期（longer bursts）。

## CPU-bound and I/O-bound

* 若一個行程很少產生 I/O 請求，而大部分時間用於計算，則稱為 **CPU-bound process（CPU 密集行程）**。
– CPU-bound 行程可能有少數幾個非常長的 CPU burst。
* 若一個行程花更多時間執行 I/O 而非計算，則稱為 **I/O-bound process（I/O 密集行程）**。
– I/O-bound 行程通常有許多短的 CPU bursts。

## What does a CPU scheduler do?

* 當 CPU 處於閒置時，作業系統必須選擇另一個行程來執行。
– 此選擇的過程由 **短期排程器（short-term scheduler）** 或 **CPU scheduler** 負責進行。
* CPU 排程器會從 **就緒佇列（ready queue）** 中挑選一個行程，並將 CPU 分配給它。
– Ready queue 不一定要是先進先出（FIFO）。
– 有許多不同方式可組織 ready queue。

## Representation of Process Scheduling


## Schedulers (1/2)

* **Long-term / job scheduler（長期／作業排程器）**
– 負責決定哪些行程應被帶入就緒佇列。
– 執行頻率非常低（以秒或分鐘為單位）。
– 可能動作緩慢。
– 長期排程器控制系統中「多程式程度（degree of multiprogramming）」，
即記憶體中同時存在的行程數量。
– 應選擇良好的 I/O-bound 與 CPU-bound 行程組合。
* **Short-term / CPU scheduler（短期／CPU 排程器）**
– 負責選擇下一個要執行的行程並分配 CPU。
– 執行頻率非常高（以毫秒為單位）。
– 必須非常快速。
* **Medium Term Scheduling（中期排程）**
– 用於分時系統（time sharing system）。
– 當記憶體空間不足，而某些行程需要進入記憶體時執行。
– 控制多程式程度（degree of multiprogramming）與 I/O、CPU bound 行程的比例。

## CPU Scheduler

* 從記憶體中所有「準備好執行」的行程中選擇一個，並分配 CPU 給它。
* CPU 排程決策可能在以下情況下發生：
1. 行程由「執行（running）」切換為「等待（waiting）」狀態（例如執行 I/O）。
2. 行程由「執行」切換為「就緒（ready）」狀態（例如發生中斷）。
3. 行程由「等待」切換為「就緒」狀態（例如 I/O 完成）。
4. 行程結束（terminates）。


* 核心事件（kernel）：
* admit（進入系統）
* scheduler dispatch（派送到 CPU）
* I/O completion（I/O 完成）
* 使用者事件（user）：
* I/O wait（等待輸入輸出）
* exit（結束或錯誤中止）
* interrupt（中斷）
* **Preemptive（搶先式）** vs **Non-preemptive（非搶先式）**
* 當排程發生在情況 (1) 與 (4) 時，為 **非搶先式排程**。
– 簡單，但效率很差。
* 其他情況下的排程為 **搶先式（preemptive）**。
– 需考慮對共用資料的存取問題。
– 需考慮在核心模式（kernel mode）時被搶先的情況。
– 需考慮在關鍵作業活動中發生中斷的情形。

## Dispatcher

派工模組將 CPU 的控制權交給由短期排程器選出的行程；這包含：
– 內容切換（context switching）
– 切換至使用者模式（user mode）
– 跳至使用者程式的正確位置以重新開始該程式

派工延遲（dispatch latency）
– 指派工器停止一個行程並啟動另一個行程所需的時間。


## Scheduling Criteria

* **CPU utilization**：讓 CPU 盡可能保持忙碌。
* **Throughput**：每單位時間內完成執行的行程數量。
* **Turnaround time**：執行特定行程所需的總時間。
* **Waiting time**：行程在 ready queue 中等待的時間。
* **Response time**：從提交請求到產生第一次回應所需的時間（不含輸出，用於 time-sharing environment）。

### Scheduling Algorithm Optimization Criteria

* Max CPU utilization
* Max throughput
* Min turnaround time
* Min waiting time
* Min response time

## First-Come, First-Served (FCFS) Scheduling

假設行程的到達順序為 P1、P2、P3。

行程與執行時間如下：
P1：24
P2：3
P3：3

甘特圖如下：

waiting time：
P1 = 0
P2 = 24
P3 = 27

average waiting time：$(0 + 24 + 27) / 3 = 17$

---

假設行程的到達順序為 P2、P3、P1。

甘特圖如下：

等待時間：
P1 = 6
P2 = 0
P3 = 3

平均等待時間：(6 + 0 + 3) / 3 = 3，比前一例更佳。

**護航效應（Convoy effect）**：短行程被長行程擋在後面。
CPU 使用率可能降低。
例如一個 CPU-bound 行程搭配多個 I/O-bound 行程。

## Shortest-Job-First (SJF) Scheduling

為每個行程關聯其下一次 CPU 執行期的長度。
使用這些長度來排程最短的行程先執行。
SJF 是最佳的，能對給定的行程集合提供最小的平均等待時間。
困難在於如何得知下一次 CPU 請求的長度。
可由使用者提供。

### Example of SJF

行程與到達時間、執行時間如下：
P1：執行 6 -> 2
P2：執行 8 -> 4
P3：執行 7 -> 3
P4：執行 3 -> 1


average waiting time = (3 + 16 + 9 + 0) / 4 = 7

## Determining Length of Next CPU Burst

只能估計長度，通常與前一次相似。
接著選擇預測下一次 CPU 執行期最短的行程。

可利用過去的執行期長度進行指數平均（exponential averaging）：
$t_n$ = 第 n 次實際的 CPU 執行期長度
$t_{n+1}$ = 預測的下一次 CPU 執行期長度
$α$：$0 ≤ α ≤ 1$
公式：$t_{n+1} = αt_n + (1 − α)t_n$

通常 $α = 1/2$。
其搶先式版本稱為 **「最短剩餘時間優先（Shortest Remaining Time First）」**

## Prediction of the Length of the Next CPU Burst


### Examples of Exponential Averaging

當 α = 0：
$τ_{n+1} = τ_n$
最近的歷史資料不被考慮。

當 α = 1：
$τ_{n+1} = t_n$
僅考慮最後一次的實際執行期。

若展開公式：
$τ_{n+1} = α t_n + (1 − α)αt_{n+1} + ⋯ + (1 − α)^jαt_{n-j} + ⋯ + (1 − α)^{n+1}τ_0$

由於 $α$ 與 $(1 − α)$ 均小於或等於 1，
每個後續項的權重都比前一項小。

### Example of Shortest-remaining-time-first (SRTF)

現在我們將變動的到達時間與搶先機制加入分析。

| 行程 | arrival time | burst time |
| -- | ---- | ---- |
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |


average waiting time = $[(10−1) + (1−1) + (17−2) + (5−3)] / 4 = 26 / 4 = 6.5ms$

## Priority Scheduling

每個行程被分配一個優先等級（整數）。
CPU 分配給優先權最高（數字最小）的行程。
可以是搶先式或非搶先式。
SJF 是一種優先權排程，其優先權等於預測的 CPU 執行期長度的倒數。

問題：**飢餓（Starvation）**——低優先權行程可能永遠不會執行。
解決方法：**老化（Aging）**——隨著時間增加，提高行程的優先權。

### Example of Priority Scheduling

| 行程 | 執行時間 | 優先權 |
| -- | ---- | --- |
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |


平均等待時間 = (0 + 1 + 6 + 16 + 18) / 5 = 8.2 毫秒。

## Round Robin (RR)

每個行程取得一個小的 CPU 時間單位（time quantum q），通常為 10–100 ms
當時間到達後，行程被搶先並放到 ready queue 的尾端。

若有 n 個行程在就緒佇列且時間片為 q，
則每個行程在最多 q 的時間內取得 1/n 的 CPU 時間。
沒有任何行程需要等待超過 (n − 1)q 的時間。

計時器在每個時間片到期時觸發中斷，以安排下一個行程。

效能：
– 若 q 很大 → 近似 FCFS。
– 若 q 太小 → 內容切換開銷過高。
通常 q 應遠大於內容切換時間。

### Example of RR with Time Quantum = 4

| 行程 | 執行時間 |
| -- | ---- |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |


通常其平均 turnaround time 高於 SJF，但 response time 較好
時間片 q 應相對於 context switching 時間足夠大。
一般 q 為 10ms 至 100ms，內容切換小於 10μs。

### Time Quantum and Context Switch Time


### Turnaround Time Varies With The Time Quantum

80% 的 CPU 執行期應短於時間片 q。


（圖表顯示時間片太小導致高開銷，時間片太大則導致反應延遲。）

### Multilevel Queue

就緒佇列被劃分為多個獨立的佇列，例如：
* foreground（互動型，interactive）
* background（批次型，batch）

每個行程永久屬於某一個佇列。

每個佇列有自己的排程演算法：
* 前景：RR
* 背景：FCFS

必須在佇列間進行排程：
* Fixed priority scheduling：
先服務前景，再服務背景（可能導致飢餓）。
* time slice：
每個佇列獲得一定的 CPU 時間配額。
例如 80% 給前景（RR），20% 給背景（FCFS）。

### Multilevel Queue Scheduling


### Multilevel Feedback Queue

行程可在不同佇列之間移動；老化機制可透過此方式實現。

多層回饋佇列排程的定義參數如下：
– 佇列的數量。
– 各佇列的排程演算法。
– 何時提升行程等級的判斷方法。
– 何時降低行程等級的判斷方法。
– 當行程需要服務時，決定其進入哪一個佇列的方法。

### Example of Multilevel Feedback Queue

共有三個佇列：
* Q0：RR，時間片 8 毫秒。
* Q1：RR，時間片 16 毫秒。
* Q2：FCFS。

排程方式：
新作業進入 Q0，並以 FCFS 服務。
當它獲得 CPU 時，先執行 8 毫秒。
若未完成，移至 Q1。
在 Q1 再獲得 CPU 時，執行 16 毫秒。
若仍未完成，則移至 Q2 以 FCFS 方式執行。

### Summary（總結）

| 排程演算法 | 搶先式 | 公平性 | 無飢餓 |
| --------------------------------- | --- | --- | --- |
| First-Come, First-Served FCFS | ● | ● | |
| Shortest Job First SJF | | | |
| Shortest Remaing-Time First SRTF | ● | | |
| Preemptive Priority（搶先式優先權） | ● | | |
| Non-preemptive Priority（非搶先式優先權） | | | |
| RR（循環排程） | ● | ● | ● |
| Multilevel Queue（多層佇列） | ● | | |
| Multilevel Feedback Queue（多層回饋佇列） | ● | | |

## Quiz

1. 在 FCFS、搶先式 SJF、非搶先式 SJF 與 RR 之中，
X 與 Y 分別給出最短的「等待時間」與「回應時間」。
那麼 (X, Y) 是哪一組？

**(a) (搶先式 SJF, RR)**
(b) (非搶先式 SJF, RR)
(c.) (搶先式 SJF, FCFS)
(d) (非搶先式 SJF, FCFS)
(e) (RR, 搶先式 SJF)

Min Waiting Time: 找會讓執行時間短的排最前面的演算法 -> SRTF
Min Response Time: 找會輪流的演算法 -> RR

**2. 請計算下列行程在各種排程演算法下的平均等待時間與平均周轉時間。**
(a) FCFS
(b) SJF
(c.) SRTF
(d) Priority Non-preemptive（非搶先式優先權）
(e) Priority Preemptive（搶先式優先權）
(f) RR（時間片 = 3）

| 行程 | 到達時間 | 服務時間 | 優先權 |
| -- | ---- | ---- | --- |
| P1 | 0 | 7 | 3 |
| P2 | 2 | 4 | 2 |
| P3 | 5 | 2 | 5 |
| P4 | 7 | 10 | 1 |
| P5 | 10 | 6 | 4 |

* FCFS = (0 + 5 + 6 + 6 + 13) / 5 = 6
*

### Quiz 2 Answer

(a) FCFS：E[W] = 6
(b) SJF：E[W] = 4.8
(c) SRTF：E[W] = 4.4
(d) 非搶先式優先權：E[W] = 9.6
(e) 搶先式優先權：E[W] = 9.4
(f) RR（時間片 = 3）：E[W] = 8.0

---

### 第 39 頁：Quiz 3

某些類型的 CPU 排程演算法若設定適當的參數，會是其他類型的子集合。
以下哪一項關係是錯誤的？

(a) SJF ⊂ Priority
(b) FCFS ⊂ Priority
(c) FCFS ⊂ RR
(d) RR ⊂ MFQ
**(e) SJF ⊂ RR**

SJF 是依 最短剩餘時間 或 最短作業長度 排序，
而 RR 是固定時間片輪流執行，與作業長短無關。

### Thread Scheduling（執行緒排程）

區分使用者層級與核心層級執行緒。

當系統支援多執行緒時，排程的單位是執行緒而非行程。

在多對一（many-to-one）與多對多（many-to-many）模型中，
執行緒函式庫會在使用者層級排程執行緒到 LWP（輕量程序）。
這稱為 **程序競爭範圍（Process-Contention Scope, PCS）**，
因為競爭僅發生於同一行程內。

核心層級執行緒則由核心排程至可用的 CPU 上，
稱為 **系統競爭範圍（System-Contention Scope, SCS）**，
表示競爭發生於整個系統的所有執行緒之間

### Pthread Scheduling（Pthread 排程）

Pthread 的 API 允許在建立執行緒時指定 PCS 或 SCS。
– `PTHREAD_SCOPE_PROCESS`：使用 PCS 排程。
– `PTHREAD_SCOPE_SYSTEM`：使用 SCS 排程。

但某些作業系統有局限：
Linux 與 macOS 只允許使用 `PTHREAD_SCOPE_SYSTEM`。

### Multiple-Processor Scheduling

當系統擁有多個 CPU 時，排程變得更加複雜。

若系統內的處理器為同質（homogeneous），可使用下列模型：
**非對稱多處理（Asymmetric Multiprocessing）**：
– 只有一個處理器可存取系統資料結構，
因此避免了共享資料的需求。
**對稱多處理（Symmetric Multiprocessing, SMP）**：
– 每個處理器皆可自行排程。
– 所有執行緒可能共享同一個就緒佇列（情形 a）。
– 或是每個處理器擁有自己的私有就緒佇列（情形 b）。


### 第 46 頁：Multicore Processors（多核心處理器）

最近的趨勢是將多個處理核心放在同一個實體晶片上。
這樣的設計能更快且耗電更少。
每個核心可同時執行多個執行緒的情況也越來越常見。

當一個執行緒因記憶體存取停頓（memory stall）而暫停時，
系統可利用該時間讓另一個執行緒繼續執行。

---

### 第 47 頁：Multithreaded Multicore System (1/3)（多執行緒多核心系統 1/3）

（此頁為圖示，顯示多核心與多執行緒的互動結構。）

### Multithreaded Multicore System (2/3)（多執行緒多核心系統 2/3）

**晶片多執行緒（Chip-Multithreading, CMT）**
– 指定每個核心擁有多個硬體執行緒。
– Intel 稱之為超執行緒（Hyper-Threading）。

在一個四核心系統中，若每個核心擁有兩個硬體執行緒，
作業系統會看到八個邏輯處理器。

排程分為兩個層次：

1. 作業系統決定要讓哪個軟體執行緒在邏輯 CPU 上執行。
2. 每個核心再決定要讓哪個硬體執行緒在實體核心上執行。

排程方式可包括：
– 循環（Round-robin）
– 優先權（Priority）

效能會依據不同策略與核心配置而變化

### Load Balancing

若採用對稱多處理（SMP），
需確保所有 CPU 都有足夠的工作以維持效率。

**負載平衡（Load Balancing）**
目標是讓工作在各處理器間平均分配。
若系統使用單一共用的就緒佇列，則不需要此機制。

兩種常見的遷移策略：
– **推移遷移（Push Migration）**：定期檢查每個處理器的負載，
若有過載，將部分任務推送到其他處理器。
– **拉取遷移（Pull Migration）**：閒置的處理器主動從忙碌的處理器中拉取任務。

負載平衡有時會與處理器親和性相衝突。

### Processor Affinity（處理器親和性）

**處理器親和性（Processor Affinity）**
指執行緒對特定處理器的偏好。

當一個執行緒長期在同一處理器上執行時，
該處理器快取（cache）中會保留該執行緒常用的資料。
若負載平衡將執行緒移至其他處理器，
就會失去這些快取資料，導致效能下降。

親和性類型：
– **軟性親和性（Soft Affinity）**：作業系統盡量讓執行緒在同一處理器上執行，但不保證。
– **硬性親和性（Hard Affinity）**：允許行程指定可執行的處理器集合。

---

### 第 52 頁：NUMA and CPU Scheduling（非均勻記憶體存取與 CPU 排程）

**非均勻記憶體存取（NUMA）**
– 將 CPU 與記憶體模組組合成多個節點。
– 每個 CPU 對某些記憶體區塊的存取速度比其他區塊快。

排程時可搭配**記憶體放置演算法（memory-placement algorithms）**
以同時考慮處理器親和性與資料區域性。

---

### Real-Time CPU Scheduling

即時排程常面臨明顯的挑戰。

* **軟即時系統（Soft Real-Time Systems）**
– 不保證關鍵任務能在期限內執行完畢。
* **硬即時系統（Hard Real-Time Systems）**
– 任務必須在其截止時間前完成。

**事件延遲（Event Latency）**：
從事件發生到被處理的時間，應儘可能縮短。

包含兩部分：

1. **中斷延遲（Interrupt Latency）**：從中斷到達到服務例行程開始執行的時間。
2. **派工延遲（Dispatch Latency）**：從排程器移除當前行程到啟動新行程所需時間。

派工延遲的衝突階段包含：

1. 搶先任何在核心模式中執行的行程。
2. 讓低優先權行程釋放被高優先權行程所需的資源。

---

### Priority-based Scheduling

在即時排程中，排程器必須支援 **搶先式、以優先權為基礎的排程**。
但這只能保證軟即時的需求。

若要支援硬即時，系統還必須保證任務可在期限內完成。

行程具有新的特性：
週期性任務（periodic task）需要在固定的間隔使用 CPU。
– 具有處理時間 t、截止時間 d、週期 p。
– 0 ≤ t ≤ d ≤ p。
– 週期任務的速率為 1/p。

**進入控制（Admission Control）**
用來決定是否接受新的任務。

---

### 第 56 頁：Rate Monotonic Scheduling（速率單調排程）

每個任務的優先權依據其週期的倒數分配：
– 週期較短的任務 → 優先權較高。
– 週期較長的任務 → 優先權較低。

因此，CPU 需求頻繁的任務會被分配更高優先權。

例子：
P1：週期 p₁ = 50，執行時間 t₁ = 20，CPU 使用率 = 0.4
P2：週期 p₂ = 100，執行時間 t₂ = 35，CPU 使用率 = 0.35

---

### 第 57 頁：Missed Deadlines with Rate Monotonic Scheduling（速率單調排程的期限錯失）

例子：
P1：週期 p₁ = 50，執行時間 t₁ = 25，CPU 使用率 = 0.5
P2：週期 p₂ = 80，執行時間 t₂ = 35，CPU 使用率 = 0.44

總使用率 U = Σ(Ci/Ti) ≤ n(2^(1/n) − 1)
– 當 n = 1：可達 100%
– n = 2：83%
– n → ∞：69%

（出自 Liu & Layland, 1973，《Scheduling algorithms for multiprogramming in a hard real-time environment》）

---

### 第 58 頁：Earliest Deadline First Scheduling (EDF)（最早截止時間優先排程）

優先權依任務的截止時間決定：
– 截止時間越早 → 優先權越高。
– 截止時間越晚 → 優先權越低。

EDF 允許 P2 繼續執行，
而速率單調排程會讓 P1 搶先 P2。

EDF 理論上是最優的，但在實作上不切實際，
因為內容切換與中斷處理成本很高。

---

### 第 59 頁：Proportional Share Scheduling（比例分配排程）

將系統中的總 CPU 時間分為 T 份（shares）。
每個應用程式獲得 N 份，其中 N < T。
確保每個應用程式可獲得 N/T 的處理器時間比例。

例子：
A：50 份
B：15 份
C：20 份
若 D 請求 30 份，是否允許？
由進入控制政策（Admission Control）決定是否接受。

---

### 第 60 頁：POSIX Real-Time Scheduling（POSIX 即時排程）

POSIX.1b 標準定義了即時執行緒的管理函式。

提供兩種即時排程類別：

1. **SCHED_FIFO** – 以先進先出策略（FCFS）排程，
相同優先權的執行緒不會時間分片。
2. **SCHED_RR** – 與 SCHED_FIFO 類似，但相同優先權的執行緒會使用時間分片（RR）。

定義兩個函式用於查詢與設定排程政策：

1. `pthread_attr_getsched_policy(pthread_attr_t *attr, int *policy)`
2. `pthread_attr_setsched_policy(pthread_attr_t *attr, int policy)`

以下為 **Chapter 5 – CPU Scheduling**
**第 61–83 頁** 的 **純中文逐頁翻譯**（完全依照簡報內容順序，不改寫、不省略）。

---

### 第 61 頁：POSIX Real-Time Scheduling API (1/2)（POSIX 即時排程 API 第 1 部分）

#include <pthread.h>
#include <stdio.h>
#define NUM_THREADS 5

int main(int argc, char *argv[]) {
    int i, policy;
    pthread_t tid[NUM_THREADS];
    pthread_attr_t attr;

    /* 取得預設屬性 */
    pthread_attr_init(&attr);

    /* 取得目前的排程政策 */
    if (pthread_attr_getschedpolicy(&attr, &policy) != 0)
        fprintf(stderr, "Unable to get policy.\n");
    else {
        if (policy == SCHED_OTHER)
            printf("SCHED_OTHER\n");
        else if (policy == SCHED_RR)
            printf("SCHED_RR\n");
        else if (policy == SCHED_FIFO)
            printf("SCHED_FIFO\n");
    }
}

---

### 第 62 頁：POSIX Real-Time Scheduling API (2/2)（POSIX 即時排程 API 第 2 部分）

/* 設定排程政策 - FIFO, RR, 或 OTHER */
if (pthread_attr_setschedpolicy(&attr, SCHED_FIFO) != 0)
    fprintf(stderr, "Unable to set policy.\n");

/* 建立執行緒 */
for (i = 0; i < NUM_THREADS; i++)
    pthread_create(&tid[i], &attr, runner, NULL);

/* 等待所有執行緒結束 */
for (i = 0; i < NUM_THREADS; i++)
    pthread_join(tid[i], NULL);
}

/* 每個執行緒將從此函式開始執行 */
void *runner(void *param) {
    /* 執行工作... */
    pthread_exit(0);
}

---

### 第 63 頁：Operating System Examples（作業系統範例）

* Linux 排程
* Windows 排程
* Solaris 排程

---

### 第 64 頁：Linux Scheduling Through Version 2.5（Linux 2.5 版以前的排程）

* 版本 2.4：SMP（對稱多處理）採用全域就緒佇列與過期佇列。
– 排程時間複雜度 O(N)：插入或排序時依行程數目而變。
* 版本 2.5：改為常數時間 O(1) 排程。
– 採搶先式、以優先權為基礎。
– 有兩個優先權範圍：**分時（time-sharing）** 與 **即時（real-time）**。
– 即時優先權範圍 0–99；nice 值範圍 100–140。
– 轉換成全域優先權，數字越小代表優先權越高。
– 優先權越高的行程，獲得的時間片越大。
– 行程若時間片尚未用完則維持可執行狀態（active）。
– 若時間片用盡，則標記為過期（expired），需等待其他行程完成後才能再排程。
– 每個 CPU 各自維護 runqueue（執行佇列）資料結構。
– 使用兩個優先權陣列（active, expired），
當 active 陣列用完時兩者交換。
– 雖效率高，但對互動式行程的回應時間較差。

---

### 第 65 頁：Linux Scheduling in Version 2.6.23+（Linux 2.6.23 以後的排程）

* **完全公平排程器（Completely Fair Scheduler, CFS）**

* 採用 **排程類別（Scheduling Classes）**：
– 每個類別具有特定的優先權。
– 排程器會選擇最高優先權類別中的最高優先任務。
– 不再採用固定時間片，而是根據行程應得的 CPU 比例分配時間。
– 可新增不同的排程類別（預設有一般類與即時類）。

* 量化（quantum）根據 nice 值（–20 至 +19）計算。
– 值越小優先權越高。
– 定義「目標延遲（target latency）」：
每個行程應在此間隔內至少執行一次。
– 若系統中可執行行程變多，目標延遲會相應增加。

* CFS 會追蹤每個行程的 **虛擬執行時間（vruntime）**，
– 依優先權給定衰減係數，優先權低的行程 vruntime 增長更快。
– 預設優先權的 vruntime = 實際執行時間。

* 排程器選擇 vruntime 最小的行程執行。
– 可執行行程以紅黑樹（red-black tree）儲存，
每次選出最左節點（最小 vruntime）。

---

### 第 66 頁：CFS Performance（CFS 效能）

（圖表顯示 CFS 在互動回應時間與整體公平性上的改進情形。）

---

### 第 67 頁：Linux Scheduling (1/2)（Linux 排程 1/2）

* 即時排程依據 POSIX.1b 標準。
– 即時任務具有靜態優先權。

* 即時任務與一般任務會被映射至同一全域優先權架構。
– nice 值為 –20 的行程對應全域優先權 100。
– nice 值為 +19 的行程對應全域優先權 139。

---

### 第 68 頁：Linux Scheduling (2/2)（Linux 排程 2/2）

* Linux 支援負載平衡，且具備 NUMA 感知能力。
* **排程領域（Scheduling Domain）**：
– 一組可相互平衡的 CPU 核心。
– 根據共用資源（如快取記憶體）劃分領域。
– 目標是避免執行緒頻繁在不同領域間遷移。

---

### 第 69 頁：Windows Scheduling（Windows 排程）

* Windows 採用 **以優先權為基礎的搶先式排程**。
* 最高優先權的執行緒優先執行。
* **排程器（Dispatcher）** 負責調度。
* 執行緒會持續執行直到：

1. 發生封鎖（block）；
2. 時間片用完；
3. 被更高優先權的執行緒搶先。
* 即時執行緒可搶先非即時執行緒。
* 採用 32 級優先權架構：
– 可變類（Variable class）：1–15。
– 即時類（Real-time class）：16–31。
– 優先權 0 為記憶體管理執行緒。
* 每個優先權各有一個佇列。
* 若沒有可執行執行緒，系統執行 idle thread（閒置執行緒）。

---

### 第 70 頁：Windows Priority Classes (1/2)（Windows 優先權類別 1/2）

* Win32 API 定義多種優先權類別：
– REALTIME_PRIORITY_CLASS
– HIGH_PRIORITY_CLASS
– ABOVE_NORMAL_PRIORITY_CLASS
– NORMAL_PRIORITY_CLASS
– BELOW_NORMAL_PRIORITY_CLASS
– IDLE_PRIORITY_CLASS

除了 REALTIME 類外，其餘皆為可變優先權類。

* 每個類別內的執行緒還有相對優先權：
– TIME_CRITICAL, HIGHEST, ABOVE_NORMAL, NORMAL, BELOW_NORMAL, LOWEST, IDLE。

* 優先權類別與相對優先權組合後形成數值優先權。

* 基本優先權為類別內的 NORMAL 等級。

* 若時間片用完，優先權會降低，但不會低於基本值。

---

### 第 71 頁：Windows Priorities（Windows 優先權架構）

（圖示顯示 32 級優先權分布與可變區間、即時區間。）

---

### 第 72 頁：Windows Priority Classes (2/2)（Windows 優先權類別 2/2）

* 若執行緒進入等待狀態，返回後其優先權會提升，
依等待的資源類型而定。
* 前景視窗（foreground window）可獲得 3 倍的優先權提升。
* Windows 7 新增 **使用者模式排程（User-Mode Scheduling, UMS）**：
– 應用程式可自行建立與管理執行緒，無需核心介入。
– 當執行緒數量龐大時，效率顯著提升。
– 例如 C++ Concurrent Runtime（ConcRT）框架使用此功能。

---

### 第 73 頁：Solaris（Solaris 排程）

* 採用 **以優先權為基礎的排程**。

* 提供六種排程類別：

1. 時間分時（Time Sharing, TS）
2. 互動式（Interactive, IA）
3. 即時（Real Time, RT）
4. 系統（System, SYS）
5. 公平分配（Fair Share, FSS）
6. 固定優先權（Fixed Priority, FP）

* 每個執行緒同時僅屬於一個類別。

* 每個類別都有其專屬排程演算法。

* 時間分時類別（TS）為多層回饋佇列，
可由系統管理員設定表格以控制行為。

---

### 第 74 頁：Solaris Dispatch Table（Solaris 派工表）

（表格顯示不同優先權等級對應的時間片與調整策略。）

---

### 第 75 頁：Solaris Scheduling (1/2)（Solaris 排程 1/2）

排程器會將各類別的優先權轉換成全域執行緒優先權。
優先權最高的執行緒會先執行。

執行直到：

1. 被封鎖；
2. 用完時間片；
3. 被更高優先權的執行緒搶先。

相同優先權的多個執行緒以 RR（循環排程）方式執行。

---

### 第 76 頁：Solaris Scheduling (2/2)（Solaris 排程 2/2）

（圖示展示多類別優先權整合後的全域排程流程。）

---

### 第 77 頁：Algorithm Evaluation（演算法評估）

如何為作業系統選擇 CPU 排程演算法？

1. 先決定評估準則。
2. 再根據準則評估各種演算法。

方法包括：
– **確定性建模（Deterministic Modeling）**
一種分析性評估方式，
對特定輸入工作負載計算各演算法的效能。

---

### 第 78 頁：Deterministic Evaluation（確定性建模）

對每個演算法計算平均等待時間。
此方法簡單且快速，但僅適用於確定的輸入案例。

例如五個同時到達的行程：
– FCFS：平均等待時間 28 毫秒。
– 非搶先式 SJF：13 毫秒。
– RR：23 毫秒。

---

### 第 79 頁：Queueing Models（排隊模型）

以機率方式描述行程到達、CPU 執行與 I/O 間的分佈。
通常假設為指數分佈，並用平均值描述。

可計算：
– 平均產出率、使用率、等待時間等。

整個電腦系統可視為由多個服務節點組成的網路：
每個節點有其服務率與等待佇列。

根據到達率與服務率，
可求得利用率、平均佇列長度與平均等待時間。

---

### 第 80 頁：Little’s Formula（李特法則）

n = 平均佇列長度
W = 平均等待時間
λ = 平均到達率

在穩定狀態下，輸入速率等於輸出速率，因此：

**n = λ × W**

此公式適用於任何排程演算法與到達分佈。

例子：
若平均每秒有 7 個行程到達，而平均有 14 個行程在佇列中，
則平均等待時間 = 14 / 7 = 2 秒。

---

### 第 81 頁：Simulations（模擬）

排隊模型的準確度有限，
模擬可提供更精確的結果。

* 以程式模擬整個電腦系統。
* 使用變數模擬時鐘。
* 收集統計資料以評估演算法效能。

模擬輸入資料可透過：
– 根據機率分佈產生的亂數。
– 實測資料或數學分佈。
– 真實系統事件的追蹤檔（trace tape）。

---

### 第 82 頁：Evaluation of CPU Schedulers by Simulation（以模擬方式評估 CPU 排程器）

（圖示展示模擬排程器效能比較的流程。）

---

### 第 83 頁：Implementation（實作）

即使模擬也有限制。
最準確的方式是實際實作新的排程器並在真實系統上測試。
但這成本高且風險大。

不同的環境條件可能導致結果差異。

最具彈性的排程器可針對特定站點或系統調整。
有些系統提供 API 以修改優先權設定。

然而，不同的環境仍可能有顯著差異。