# 作業系統 2025_謝仁偉
## Chapter 1: Introduction
- **作業系統**（Operating System）：介於使用者與電腦硬體之間的程式，用於：
- 執行使用者程式
- 讓解決問題更容易
- 使系統好用
- 有效率地運用硬體
- 電腦系統分四部分，由低到高為：
- **硬體**（Hardware）：CPU、記憶體、I/O設備
- **作業系統**（Operating system）
- **應用程式**（Application programs）：文字編輯器、瀏覽器、資料庫、遊戲
- **使用者**（Users）：人、機器、其他電腦

- OS沒有絕對的定義，一般有兩個職責：
- **資源分配者**：管理所有資源，並在競爭時公平分配
- **控制程式**：防止錯誤與不當使用。

- 開機或重啟時，會載入開機程式（Bootstrap Program），這程式會初始化系統、載入作業系統核心（Kernel）、開始執行。
- CPUs和裝置控制器透過匯流排來共享記憶體

- 裝置完成任務會中斷（Interrupt）CPU，讓 OS 處理下一步。中斷機制可暫停目前程式，轉而執行中斷服務程式（ISR）
- trap/exception是軟體引發的中斷（錯誤、請求）
- 作業系統是由中斷驅動，不會一直主動檢查所有事件，而是靠「中斷」來推動工作
- OS會保存CPU狀態（暫存器、程式計數器），判斷中斷的類型（polling、vector），做出對應的處置
==（會考）==
- **同步IO**：CPU 必須等待裝置完成
- **非同步IO**：I/O開始後先返回使用者程式，I/O會被放到等待佇列中，等待系統呼叫，使用者不能直接下I/O指令
- OS透過裝置表（Device-status table）來更新I/O條目，紀錄類別、地址、狀態

- **主記憶體**：隨機、揮發
- **二級儲存區**：非揮發
- **SSD**（Solid-state disks）：比硬碟快、非揮發
- **快取**（Caching）：將資訊複製到更快的儲存系統中，主記憶體可以被視為二級儲存的快取
- 

- **多處理器（Multiprocessor）系統**：
- 有多個 CPU
- 優點：==（會考）==
1. Increased throughput（提高吞吐量）
2. Economy of scale（規模經濟效益）
3. Increased reliability / fault tolerance（提高可靠性）
- 又稱作平行系統（parallel systems）、緊密耦合系統（tightly-coupled systems）
- **Graceful Degradation**：在部分元件發生故障時，仍能維持有限的服務，而不是完全停止運作 ==（會考）==
- **Fault Tolerant**：在故障發生時仍能正常運作 ==（會考）==

- 多處理器系統分為：
- **非對稱**（Asymmetric）：每個處理器負責特定任務
- **對稱**（Symmetric）：所有 CPU 可執行所有任務

- 電腦系統組成的定義 ==（會考）==：
- **CPU（中央處理器）**：執行指令的硬體
==（The hardware that executes instructions）==
- **Processor（處理器）**：一個包含一（多）個 CPU 的實體晶片
==（physical chip that contains one or more CPUs.）==
- **Core（核心）**：CPU 的基本運算單元
==（The basic computation unit of the CPU）==
- **Multicore（多核心）**：在同一個 CPU 上包含多個運算核心
==（Including multiple computing cores on the same CPU.）==
- **Multiprocessor（多處理器）**：包含多個處理器的系統
==（Including multiple processors）==

- **叢集系統**（Clustered System）：
- 多台電腦（節點）透過儲存區域網路（san，storage-area network）共享儲存資源
- 可用於高可用性（High Availability）或高效能運算（HPC）
- 熱備援（Hot-standby）模式可在主伺服器故障時自動接手
- **非對稱叢集**（Asymmetric Clustering）：其中一台機器處於熱備援（hot standby）模式
- **對稱叢集**（Symmetric Clustering）：多個節點同時執行應用程式，並互相監控狀態

- **多程式設計**（Multiprogramming/Batch system）：讓 CPU 交替執行多個工作，避免閒置

- **分時系統**（Time Sharing/multitasking）：
- CPU 以極高頻率在不同工作之間切換，讓使用者能夠同時操作多個程式
- 若有多個工作要執行，由CPU排成決定順序
- 若行程無法全部放入主記憶體，透過交換（swapping） 將部分程式暫時移出再載入
- 虛擬記憶體（virtual memory） 允許執行不完全載入至記憶體的程式

- OS 由「中斷」驅動：
- **硬體中斷**：裝置發出的信號
- **軟體中斷**（Trap / Exception）：軟體錯誤（如除以零）、要求 OS 服務、無限迴圈、程式互相干擾等問題

- **雙模式**（Dual-mode）：
- 讓 OS 保護自己與其他系統元件
- 兩種模式為**使用者模式**（User Mode）、**核心模式**（Kernel Mode）
- 模式位元由硬體提供，用來判斷當前執行權限，核心模式下才能執行特權指令
- **系統呼叫**（System Call）會從使用者模式切換到核心模式
- 某些 CPU 支援多重模式，例如虛擬機管理模式（VMM Mode）

- User Mode 切換至 Kernel Mode

- **行程**（Process）：執行中的程式
- 程式是靜態的、行程是動態的
- 結束時需釋放資源
- 單執行緒（Single-threaded）行程只有一個指令計數器（program counter），多執行緒（Multi-threaded）行程有多個指令計數器

- 在多處理器環境下，必須確保每份資料一致（cache
coherency）

- **輸入輸出子系統**（I/O Subsystem）：
- I/O記憶體管理，包含 ==（會考）==：
- **緩衝（Buffering）**：在傳輸資料時暫存資料
- **快取（Caching）**：將部分資料儲存在更快的儲存區中以提高效能
- **周邊設備同步操作（Spooling）**：用硬碟當作中介緩衝區，讓 I/O（輸入輸出）與 CPU 能同時運作
==（讓一個task的輸出和另一task的輸入同時進行）==
- 把 I/O 任務先暫存在硬碟或磁碟檔案中，等裝置有空再執行，讓慢速裝置（例如印表機、磁帶機）能與高速的 CPU 同步運作
- 通用裝置介面（Device Driver Interface）
- 特定硬體的驅動程式

- 保護與安全：
- **保護**（Protection）：控制行程或使用者對資源的存取權限
- **安全**（Security）：防禦內部與外部攻擊，如病毒、DDoS、身份竊取。
- 系統透過User ID與group ID來控制存取權
- 權限提升（Privilege Escalation）允許程式臨時獲得更高權限

- Virtualization ==（會考）==：
- **虛擬化**（Virtualization）：一台實體電腦分成多個獨立環境，使主機 OS（Host）同時運行多個客體 OS（Guest）
- **模擬**（Emulation）：用於模擬不同的架構（如 PowerPC → x86），但速度慢
- **VMM**（Virtual Machine Manager）：提供虛擬化服務

- **分散式系統**（Distributed Systems）：
- 由多台實體電腦透過網路（TCP/IP）連接而成，常見形式有：
- Local Area Network (LAN，區域網)：房間、校園
- Wide Area Network（WAN，廣域網）：城市間、國家間
- Metropolitan Area Network（MAN，都會網）：同個城市內的建築
- Personal Area Network （PAN，個人網）：如藍牙

- **核心資料結構**（Kernel Data Structures）：
- OS 內部使用各種資料結構：
- 單向、雙向、循環鏈結串列
- 二元搜尋樹（BST）與平衡樹（如紅黑樹）
- 雜湊表（Hash Map）：用雜湊函數快速查找 [key:value]
- 位元圖（Bitmap）：用 0/1 表示多個項目的狀態

- OS 運算環境：
- **傳統運算**（Traditional）：獨立桌機或工作站，但大多與網路連接
- **行動運算**（Mobile）：手機與平板，具 GPS、感測器等
- **用戶端-伺服器**（Client-Server）：伺服器提供資料或檔案服務
- **計算伺服器**（Compute Server）：提供運算服務，如資料庫查詢
- **檔案伺服器**（File Server）：提供檔案存取介面以儲存與擷取檔案
- **對等式網路**（P2P）：節點彼此都是客戶端也是伺服器，如 Skype
- **雲端運算**（Cloud Computing）：
- **IaaS**（基礎建設即服務，Infrastructure as a Service）：提供硬體資源（伺服器、儲存）
- **PaaS**（台即服務，Platform as a Service）：提供應用平台（資料庫服務）
- **SaaS**（軟體即服務，Software as a Service ）：提供應用軟體（Google Docs）
- **公有雲**（Public Cloud）：任何人都可付費使用
- **私有雲**（Private Cloud）：公司內部自行運行
- **混合雲**（Hybrid Cloud）：兩者結合
- **即時與嵌入式系統**（Real-Time Embedded）：
- 具有時間限制（如汽車控制器、醫療裝置）
- 必須在固定時間內完成任務

## Chapter 2： Operating-System Structures
- 作業系統提供的服務：
- **使用者介面**（UI）：提供圖形介面（GUI）、命令列介面（CLI）或觸控介面（Touch-Screen Interface）
- **程式執行（Program Execution）**：載入程式到記憶體並執行
- **I/O 操作（I/O Operations）**：控制與管理輸入/輸出裝置
- **檔案系統操作（File-System Manipulation）**：讀寫檔案、建立與刪除、存取控制
- **通訊（Communication）**：行程之間或遠端系統之間交換資訊（訊息傳遞、共用記憶體）
- **錯誤偵測（Error Detection）**：偵測並回報硬體或軟體錯誤
- **資源分配（Resource Allocation）**：為行程分配 CPU、記憶體、裝置、檔案等資源
- **紀錄（Accounting）**：追蹤資源使用量，用於評估效能
- **保護與安全（Protection and Security）**：
- **保護（Protection）**：確保所有對系統資源的存取都受到控制
- **安全（Security）**：防止外部使用者或惡意程式入侵系統

- **命令列介面**（CLI/command interpreter）：使用者輸入文字命令，例如 Linux shell 或 Windows cmd
- **圖形介面**（GUI）：使用視窗、滑鼠、圖示，如 macOS、Windows

- **系統呼叫**（System Calls）：
- 應用程式與作業系統之間的程式設計介面
- 通常以高階語言（C 或 C++）撰寫
- 多數程式不會直接呼叫系統呼叫，而是透過**高階應用程式介面（API，Application Programming Interface）** 間接存取
- 每個系統呼叫都有一個對應的編號，系統呼叫介面（System-call interface）會以這些編號作為索引建立表格

- 三種系統呼叫常見參數傳遞方式 ==（會考）==：
1. 暫存器傳遞：直接在 CPU 暫存器中傳參數，若參數過多，暫存器數量可能不足
==（將參數存在 CPU register中傳送）==
2. 記憶體區塊傳遞：將參數存在記憶體中的一個表格或區塊，再把該區塊的位址存入暫存器
- Linux 混合使用這兩種，五個以內的參數放暫存器，超過五個就用區塊
==（將參數存在 memory 的 block，傳 block 的 address）==
3. 堆疊傳遞：程式把參數壓入堆疊，OS 再從堆疊取出，不限制參數的數量與長度
==（程式把參數push進堆疊，再由 OS POP）==

- 系統呼叫的種類 ==（會考，例如舉五個例子）==：
- **Process Control（行程控制）**：
- create process, terminate process（建立、終止行程）
- load, execute（載入與執行）
- get process attributes, set process attributes（取得與設定屬性）
- wait for time, wait event, signal event（等待事件或時間）
- allocate and free memory（分配與釋放記憶體）
- Dump memory if error（錯誤傾印）
- Debugger for determining bugs, single step execution（除錯）
- Locks for managing access to shared data between processes（使用鎖以控制共享資料存取）

- **File Management（檔案管理）**：
- create file, delete, open, close file（建立、刪除、開啟、關閉檔案）
- read, write, reposition（讀取、寫入、重新定位檔案指標）
- get and set file attributes（取得或設定檔案屬性）

- **Device Management（裝置管理）**：
- request device, release device（請求、釋放裝置）
- read, write, reposition（讀寫裝置資料）
- get device attributes, set device attributes（設定裝置屬性）
- logically attach or detach devices（邏輯上掛載或卸除裝置）
-
- **Information Maintenance（資訊維護）**：
- get time or date, set time or date, get system data, set system data（取得或設定時間、日期、系統資訊）
- get and set process, file, or device attributes（修改行程、檔案或裝置屬性）

- **Communications（通訊）**：
- create, delete communication connection（建立與刪除通訊連線）
- send, receive messages（若使用訊息傳遞模式（message passing），可依主機或行程名稱傳送與接收訊息）
- Shared-memory model create and gain access to memory regions（共享記憶體模式下可建立並存取記憶區域）

- **Protection（保護）**：
- Control access to resources（控制資源存取）
- Get and set permissions（取得與設定權限）
- Allow and deny user access（允許或拒絕使用者存取）

- **系統程式**（System Programs）：提供使用者開發與執行的便利環境
- **檔案管理**：建立、刪除、複製、列印、清單管理
- **狀態資訊**：查詢時間、記憶體用量、使用者數量，或效能、日誌、除錯資料
- **檔案修改**：文字編輯器、搜尋與轉換指令。
- **程式語言支援**：編譯器、組譯器、除錯器。
- **程式載入與執行**：載入器、連結器、除錯系統。
- **通訊工具**：訊息傳遞、網頁瀏覽、郵件、遠端登入、檔案傳輸。
- **背景服務**：
- 開機時啟動，提供排程、錯誤紀錄、列印等功能。
- 在使用者模式運作，稱為 daemon（守護行程） 或 subsystem（子系統）。
- **應用程式**：使用者自行執行的程式，不屬於作業系統本身

- OS 設計沒有單一最佳解，需先定義目標與規格，兩類目標：
- **使用者目標**：好用、易學、可靠、安全、快速
- **系統目標**：易設計、易維護、具彈性、可靠、無錯且高效

- 設計原則 ==（會考）==
- **Policy**：**What** will be done?
- **Mechanism**： **How** to do it?
- 使用高階語言更容易**移植（port）**但稍慢。
- **模擬**可讓 OS 跑在非原生硬體上。

- 作業系統結構：
- **MS-DOS**：
- 沒有模組劃分
- 功能層交錯、界線不明
- 為節省空間，犧牲了模組化與安全性

- **UNIX**：
- 分為系統程式與核心兩層
- 核心提供檔案系統、排程、記憶體管理等

- **Layered Approach（分層設計）**：
- 系統分成多層，由底層硬體至最高層使用者介面
- 每層僅能使用下層的服務
- 優點：模組化高、容易維護

- **Microkernel（微核心）**：
- 將非核心功能移至使用者空間
- 核心僅保留基本的記憶體、行程、通訊功能
- 優點：可靠、安全、可移植
- 缺點：效能稍低

- **Modules（模組化核心）**：
- 現代 OS（如 Linux、Solaris）採可載入核心模組設計
- 物件導向概念，每個模組可獨立載入、卸載、互通
- 比分層結構更靈活

- **Hybrid Systems（混合式系統）**：
- 多數現代 OS 都是混合設計
- Linux / Solaris：單核心（monolithic）＋模組化
- Windows：主要為單核心，但含微核心元素
- macOS X：Mach 微核心 + BSD + 動態核心模組 +（Kernel Extensions） + Aqua 介面

- 除錯與效能調整：
- 除錯是找出並修復錯誤的過程
- OS 會記錄錯誤日誌（log files）
- **應用程式錯誤**可生成**核心傾印檔**（core dump）
- **系統錯誤**可生成**崩潰傾印**（crash dump）
- 效能調整（Performance Tuning）可藉由觀察追蹤紀錄與統計樣本進行

- 系統開機（System Boot）：
- 儲存在韌體（ROM）中的開機載入器（Bootstrap Loader）會定位核心、載入記憶體並啟動
- 常見開機載入器：GRUB，可選不同核心與版本

## Ch3 Processes

### Process
- 正在執行中的程式（job 與 process 幾乎可互換），活動狀態由兩項內容表示：
- **程式計數器**（program counter）：記錄下一行要執行的指令位址
- **處理器暫存器**（processor’s registers）：儲存目前運算狀態
- 一個行程的記憶體配置依位址 **由低到高** 可分四個部分（**會考**）：
- **程式碼區**（text section）：儲存可執行**程式碼** ==（code）==
- **資料區**（data section）：儲存**全域變數** ==（global variables）==
- **堆積區**（heap）：儲存執行期間**動態配置**的記憶體（例如 `malloc()` 或 `new`）==（dynamic memory allocation）==
- **堆疊**（stack）：函式呼叫**暫存資料**（函式參數、返回位址、區域變數）==（temporary data）==
- **Program** 是被動實體，**Process** 是主動實體

### 行程狀態（Process State）==（會考）==：
- **new**（建立中）：正在被建立
- **running**（執行中）：CPU 正在執行指令
- **waiting**（等待中）：等待某事件發生
- **ready**（就緒）：等待被分配到 CPU
- **terminated**（結束）：已完成執行
- new → ready：被接納（admitted）
- ready → running：被排程（ scheduler dispatch）
- running → waiting：因 I/O 或事件等待（I/O or event wait）
- waiting → ready：I/O 或事件完成（I/O or event completion）
- running → ready：因中斷（interrupt）
- running → terminated：執行結束（exit）

### 行程控制區塊（Process Control Block, PCB）
- 紀錄行程相關資訊，又稱任務控制區塊（task control block）：
- Process state（行程狀態）：例如 running、waiting 等
- Program counter（程式計數器）：記錄下一個要執行的指令位址
- CPU registers（CPU 暫存器）：儲存行程在 CPU 上的暫存資料
- CPU scheduling information：排程資訊，例如優先權、排程佇列指標
- Memory-management information：記憶體分配資訊
- Accounting information：紀錄 CPU 使用量、執行時間、時間限制等。
- I/O status information：輸入輸出裝置使用情況、開啟的檔案清單等

### Process Scheduling
- 目標：最大化 CPU 使用率
- **行程排程器**（Process scheduler）：從所有可執行的行程中選擇下一個要分配給 CPU 的行程
- 系統維護多個 scheduling queues（排程佇列）：
- Ready queue：準備好執行、等待被分配 CPU 的行程
- Wait queue：正在等待某事件（例如 I/O 完成）的行程

### 排程器(Schedulers）（==會考==）
- **短期排程器**（**Short-term Scheduler** 或 **CPU Scheduler**）：
==（決定哪個process被放入CPU）==
- **負責選擇下一個要執行的行程並分配 CPU**
- 必須非常快速
- **長期排程器**（**Long-term Scheduler** 或 **Job Scheduler**）：
==（決定哪個process被放入ready queue）==
- **負責決定哪些行程要被放入 ready queue**
- 被觸發的頻率較低（秒或分鐘級）。
- 控制系統中的多程式程度（degree of multiprogramming）
- **中期排程器**（**Medium-term Scheduler**）：
==（當負載過高時，將 process 從 memory 移到 disk ，需要時再移回來）==
- 當系統的多程式程度過高時，可以用來降低負載
- 暫時從記憶體中移除某些行程，存放到磁碟，等需要時再載回記憶體繼續執行，稱為交換（Swapping）。

- 行程可以分為兩種類型：
- **I/O 密集行程**（I/O-bound process）：花較多時間在輸入輸出操作（I/O），CPU 執行時間短但頻繁
- **CPU 密集行程**（CPU-bound process）：花較多時間做運算（computation），CPU 執行時間長但次數少。

### 上下文切換（Context Switch）
- 當 CPU 從一個行程切換到另一個行程時，需要：
- 儲存舊行程的狀態
- 載入新行程的已儲存狀態
- 上下文被儲存在行程控制區塊（PCB）中

### 行程建立（Process Creation）
- **父行程**（Parent Process）可以建立**子行程**（Child Processes），子行程也可以再建立其他行程，形成行程樹（Tree of Processes）
- 每個行程都有行程識別碼（Process Identifier, PID）
- A Tree of Processes in Linux：
- 新行程的記憶體位址空間有兩種可能：
- 子行程是父行程的完全複製（duplicate）
- 子行程載入一個新的程式來執行
- **fork()**：用來建立新行程
- **exec()**：通常在 fork() 之後使用，以新程式取代原行程的記憶體內容

### 行程終止
- 行程執行完最後一條語句後，會呼叫 exit() 系統呼叫請 OS 刪除自己
- 狀態資料透過 wait() 回傳給父行程
- 父行程可使用 abort() 系統呼叫強制終止子行程
- 父行程可使用 wait() 等待子行程終止，並取得其結束狀態與行程識別碼（PID）
- 連鎖終止（Cascading Termination）：某些OS中，若父行程結束，所有子孫行程都會被終止
- **殭屍行程**（Zombie Process）（==會考==）
- 行程已經結束，但父行程尚未呼叫 wait()的子行程
- 父行程呼叫 wait() 時被釋放
- **孤兒行程**（Orphan Process）（==會考==）
- 父行程在未呼叫 wait() 前就終止的子行程
- OS會將其父行程改為 init 行程，init 行程會定期呼叫 wait() 回收它們

### 行程間通訊（Interprocess Communication）
- 在一個系統內，不同行程可以是：
- 獨立的（independent）
- **合作的**（cooperating）
- 合作行程（Cooperating Process）
- 原因包括（==會考==）：
- **資訊共享**（Information sharing）
- **計算加速**（Computation speedup）
- **模組化**（Modularity）
- 透過行程間通訊（Interprocess Communication, IPC） 來互動，有兩種主要模型（==會考==）：
- 共享記憶體（Shared memory）
- 訊息傳遞（Message passing）
- 生產者、消費者問題（Producer-Consumer Problem）
- 生產者（Producer）行程負責產生資料
- 消費者（Consumer）行程負責取用資料
- 依照緩衝區（buffer）的設定可分為：
- 無界緩衝區（unbounded buffer）：緩衝區容量理論上無限大
- 有界緩衝區（bounded buffer）：緩衝區大小固定，以循環陣列（circular array）方式實作

### 訊息傳遞（Message Passing）
- 一種行程用來通訊與同步行為（synchronize their actions）的機制
- IPC（行程間通訊）機制提供兩種操作：
- 傳送訊息：send(message)
- 接收訊息：receive(message)
- 當行程 P 和 Q 想要通訊時，它們需要：
- 建立一個通訊連結（communication link）
- 透過 send/receive 交換訊息
- 直接通訊（Direct Communication）：行程必須明確指定對方的名稱
- send(P, message)：傳訊息給行程 P
- receive(Q, message)：從行程 Q 接收訊息
- 間接通訊（Indirect Communication）：訊息透過郵箱（mailbox）或埠口來收發
- 每個 mailbox 有唯一的 ID
- 只有共享同一個 mailbox 的行程才能互相通訊

- 同步機制（Synchronization） ==（會考）==
- **阻塞式**（Blocking）為 **同步（Synchronous）** 傳輸：
- 阻塞式傳送（Blocking send）：傳送方會被卡住，直到訊息被接收為止
- Blocking receive（阻塞式接收）：接收方會被卡住，直到有訊息可用為止
- **非阻塞式**（Non-blocking）為 **非同步（Asynchronous）** 傳輸：
- 非阻塞式傳送（Non-blocking send）：傳送方送出訊息後立即繼續執行。
- 非阻塞式接收（Non-blocking receive）：接收方會立刻收到：
- 一則有效訊息（valid message）
- 空訊息（null message）

- **通訊端**（Sockets）
- 一個通訊的端點（endpoint），一個連線包含一對 socket
- IP 位址：哪一台電腦
- Port（埠號）：哪個應用程式
- IP 位址 127.0.0.1（loopback） 代表本機系統
- Java 中有三種類型的 socket：
- **Connection-oriented (TCP)**：有連線導向的通訊（可靠、有順序）
- **Connectionless (UDP)**：無連線導向的通訊（快速但不保證送達）
- 遠端程序呼叫（Remote Procedure Calls，RPC）
- Stubs（存根）：用戶端的代理程式，代表伺服端上的實際程序
- 資料表示透過 External Data Representation (XDL) 格式處理
- 包含 Big-endian（高位元組在前） 與 Little-endian（低位元組在前）
- 遠端通訊比本地通訊更容易發生錯誤，因此通常設計兩種傳遞策略 ==（會考）==：
- **exactly once**：每個 RPC 只執行一次
- **at most once**：每個 RPC 最多執行一次（可能丟失）

## Ch4 Threads & Concurrency
### 執行緒（threads）
- 程序內的執行單元，不同任務可以由不同的執行緒分別執行
- 大多數現代應用程式都是多執行緒（multithreaded）
- 優點 ==（會考）==：
- **回應性**（Responsiveness）：當程式的一部分被阻塞時，其他執行緒仍可繼續執行
- **資源共享**（Resource Sharing）：多個執行緒共享同一程序的資源，比起使用共享記憶體或訊息傳遞更容易
- **經濟性**（Economy）：建立與切換執行緒比建立與切換程序便宜得多
- **可擴展性**（Scalability）：程序能在多處理器架構上同時利用多核心運算

### 多核心、多處理器（Multicore, Multiprocessor）
- **平行系統（Parallel system）**：能同時執行多個任務
- 資料平行（Data parallelism）：分配相同資料到多個核心上執行，每個核心執行相同的操作
- 任務平行（Task parallelism）：分配不同的執行緒到不同核心上，每個執行緒執行不同的任務
- **並行系統（Concurrent system）**：任務之間交錯執行，非同時進行
- **晶片多執行緒**（Chip Multithreading, CMT）
- 每條硬體執行緒都有自己的架構狀態，因此可被視為一個邏輯 CPU（Logical CPU）
- 例如CPU有4核心 x 2 硬體執行緒 = 8 個邏輯 CPU

- 並行 vs. 平行 ==（會考）==
- 並行（Concurrent）：多個任務在單核心交錯執行
- 平行（Parallel）：多個任務於不同核心同時執行

- Amdahl’s Law ==（會考）==
- 計算在增加核心數量時，應用程式性能可提升的上限
- S：序列化比例（serial portion）
- N：處理核心數量（number of processing cores）

### 多執行緒模型（Multithreading Models）
- 執行緒支援可以出現在使用者層級（User level）或核心層級（Kernel level）
- 使用者層級的稱為使用者執行緒（User Threads）
- 核心層級的稱為核心執行緒（Kernel Threads）
- 使用者執行緒與核心執行緒之間有三種對應模型 ==（會考）==：
- 多對一（Many-to-One Model）
- 一對一（One-to-One Model）
- 多對多（Many-to-Many Model）
- 雙層（Two-level Model）
- **多對一（Many-to-One Model）**
- **許多**使用者層級執行緒會對應到**單一**核心執行緒
- 若其中一個執行緒被阻塞（blocking），則所有執行緒都會被阻塞
- 多個執行緒無法同時平行執行
- 目前只有極少系統使用此模型
- **一對一（One-to-One Model）**
- **每個**使用者層級執行緒都對應到**一個**核心層級執行緒
- 建立一個使用者執行緒時，也會自動建立對應的核心執行緒
- 與多對一模型相比，可支援更多的並行（concurrency）
- 但若核心執行緒數量太多，會對系統效能造成負擔
- 範例：Windows、Linux、Solaris 9 之後版本
- **多對多（Many-to-Many Model）**
- **多個**使用者層級執行緒對應到**少於或等於**數量的核心層級執行緒
- 開發者可以自由建立所需的使用者執行緒數量，核心執行緒則可在多處理器上平行（parallel）執行
- 當某個執行緒執行阻塞系統呼叫時，核心可以改排程其他執行緒執行
- 較少採用：實作困難、現今核心執行緒數量

### 執行緒函式庫（Thread Libraries）
- 提供建立與管理執行緒的 API，有兩種實作方式：
- 完全在使用者空間實作，不依賴核心支援
- 核心層級函式庫，由作業系統直接支援
- 主要有三種執行緒函式庫：
- POSIX Pthreads（可為使用者層或核心層函式庫）
- Windows Threads（核心層函式庫）
- Java Threads（以主機系統上的執行緒函式庫實作）

- Pthreads（POSIX 執行緒）
- 可以是使用者層級或核心層級的實作
- 是規範（specification），不是實作（implementation）
- 常見於 UNIX 系統：如 Solaris、Linux、macOS

- Windows Threads
- WaitForMultipleObjects() 函式用於等待多個執行緒完成，需傳入四個參數：
- 要等待的物件數量
- 指向物件陣列的指標
- 一個旗標（flag），用來指示是否要等待所有物件都完成才繼續
- 超時時間（timeout），可以設定為具體時間或 INFINITE

- Java Threads
- 由 JVM（Java Virtual Machine） 管理
- 透過底層作業系統的執行緒模型實作
- 兩種建立方式：
- 繼承 Thread 類別（class） 並覆寫其中的 run() 方法
- 實作 Runnable 介面

### 隱式多執行緒（Implicit Threading）
- 顯式多執行緒過多會使程式正確性更難維護
- 開始由編譯器與執行期函式庫自動建立與管理執行緒
- 常見三種方法：
- Thread Pools
- OpenMP
- Grand Central Dispatch（GCD）
- Thread Pools（執行緒池）
- 建立一組固定數量的執行緒，等待被分派任務
- 優點：
- 更快速
- 限制執行緒數量，避免系統負載過重。
- 將「要執行的任務」與「建立執行緒的細節」分離，讓排程策略更彈性
- OpenMP（開放式多處理）
- 編譯器指令（compiler directives） 和 API，支援 C、C++、Fortran
- 用於在共享記憶體環境（shared-memory environment）中實現平行化程式
- 定義平行區塊，這些區塊可以同時在多核心上執行
- Grand Central Dispatch（GCD）
- Apple 為 macOS 與 iOS 開發的技術
- serial queue（序列佇列）：
- 任務以 FIFO（先進先出）順序執行，一次只跑一個
- 每個行程都有一個 main queue（主佇列）
- concurrent queue（並行佇列）：
- 仍然是 FIFO，但允許多個任務同時執行

### 執行緒區域儲存（Thread-Local Storage, TLS） ==（會考）==
- 允許每個執行緒擁有自己的資料副本
- 與一般區域變數不同：區域變數僅在函式呼叫期間有效，**TLS 在整個執行緒生命週期內都可見**
- **相較於靜態變數（static），每條執行緒都有獨立副本**

## Ch5： CPU Scheduling
### 多重程序（Multiprogramming）
- 目標是讓系統中隨時都有某個程序在執行，以達到最大化 CPU 使用率
- 程序由一連串的 **CPU–I/O 週期（CPU–I/O Burst Cycle）** 組成，每個周期包括：
- CPU burst（CPU 密集計算階段）
- I/O burst（等待輸入輸出階段）

### CPU Scheduler
- 短期排程器（Short-term scheduler）：從就緒佇列（ready queue）中挑選一個程序分配給 CPU 執行
- 排程決策可能發生在以下四種情況：
1. 程序從執行狀態（running）→ 等待狀態（waiting）
2. 程序從執行狀態（running）→ 就緒狀態（ready）
3. 程序從等待狀態（waiting）→ 就緒狀態（ready）
4. 程序終止（terminate）
- **非搶先式（nonpreemptive）或合作式（cooperative）排程** ：排程只在情況 1 與 4 發生
- **搶先式（preemptive）**：排程在所有情況發生
- 當多個程序共用資料時，搶先式排程可能導致競爭條件（race condition）
- 若程序在修改關鍵核心資料時被搶先（例如 I/O 佇列），而核心或驅動程式同時讀寫該資料，將造成錯誤
- 因為中斷（interrupt）可隨時發生，且核心不能忽略它，
所以被中斷影響的程式區段必須受到保護

### 派遣器（Dispatcher）
- 負責把 CPU 控制權交給短期排程器選出的程序
- 派遣延遲（Dispatch latency）：派遣器從停止一個程序到開始另一個程序所需的時間

### Scheduling
- Scheduling Criteria（排程評估準則）==（會考）==
- CPU 利用率（CPU utilization）：讓 CPU 儘量保持忙碌
- 吞吐量（Throughput）：每單位時間內完成的程序數
- **周轉時間**（Turnaround time）：完成一個程序所花的總時間（程序到達 => 完成）
- **等待時間**（Waiting time）：程序在就緒佇列中等待的時間（程序進入Ready queue => 得到CPU開始執行的**總時間**）
- **回應時間**（Response time）：從送出請求到第一次回應出現的時間（程序到達 => 得到CPU開始執行）

### First- Come, First-Served (FCFS) Scheduling（先來先服務排程） ==（會考）==
- 車隊效應（Convoy Effect）：當短任務排在長任務後面時，所有短任務都必須等待。

### Shortest-Job-First (SJF) Scheduling（最短工作優先） ==（會考）==
- 選擇最短的程序先執行
- 最佳（optimal）演算法，可得到最小平均等待時間
- 難點：系統無法預知下一次 CPU burst 的長度

### Shortest Remaining Time First（最短剩餘時間優先） ==（會考）==
- 可搶先版本的SJF
- 利用先前 CPU 執行期的長度進行指數平均法（exponential averaging），估計下一次 CPU 執行期的長度：
1. 𝑡ₙ = 第 n 次實際的 CPU 執行期長度
2. τₙ₊₁ = 下一次預測的 CPU 執行期長度
3. α，滿足 0 ≤ α ≤ 1
4. 定義：τₙ₊₁ = α·𝑡ₙ + (1 − α)·τₙ
- 當 α = 0 時：最近的觀測值（tₙ）不影響結果
- 當 α = 1 時：只考慮最近一次的 CPU burst

### Priority Scheduling ==（會考）==
- 每個程序會被分配一個優先權值（priority number），數字越小、優先權越高
- 分為可搶先（Preemptive）、不可搶先（Nonpreemptive）
- 問題：Starvation（飢餓）：低優先權程序可能永遠等不到執行機會。
- 解法：Aging（老化）：隨著等待時間增加，逐漸提高程序的優先權

### Round Robin (RR) ==（會考）==
- 每個程序都獲得一小段 CPU 時間（稱為 time quantum q），當時間到達時，該程序會被搶先（preempted）並移到就緒佇列尾端
- 效能分析：
- 若 q 很大：變成 FIFO（先來先服務）
- 若 q 太小：上下文切換開銷太高
- 通常 RR 的平均週轉時間比 SJF 高，但回應時間（response time）較佳
- q 應該比上下文切換時間大

### Multilevel Queue（多層佇列排程）
- 就緒佇列（ready queue） 被分成多個獨立的佇列，例如：
- foreground（前景）：互動型程序（interactive），使用RR
- backgound（背景）：批次程序（batch），使用FCFS
- Multilevel Feedback Queue（多層回饋佇列）：一個程序可以在不同佇列間移動，可藉此實現老化（aging）機制

### Thread Scheduling
- 使用者層執行緒：
- PCS（Process-Contention Scope）：CPU 的競爭發生在同一個程序的執行緒之間
- 核心層執行緒：
- SCS（System-Contention Scope）：系統中所有執行緒共同競爭 CPU

### Multiple-Processor Scheduling
- 同質處理器（homogeneous processors）：每顆 CPU 的能力相同
- 多處理器排程有兩種方式：
1. 非對稱多處理（Asymmetric multiprocessing）：
- 只有一顆 CPU 負責系統資料存取與排程
- 其他 CPU 只執行工作，減少共享資料的衝突
2. 對稱多處理（Symmetric multiprocessing, SMP）：
- 每顆 CPU 都能自行排程
- 所有 CPU 共用一個就緒佇列，或各自有私有佇列
- 目前最常見
- Processor affinity（處理器親和性）：程序傾向在同一顆 CPU 上持續執行
- Soft affinity（軟性親和性）：儘量讓程序留在同一顆 CPU，但在負載平衡時仍可移動
- Hard affinity（硬性親和性）：程序明確指定可運行的 CPU 子集合
- NUMA（Non-Uniform Memory Access）：雖然系統中的所有 CPU 可共用一個記憶體空間，但每個 CPU 對本地記憶體的存取速度更快，若要存取其他 CPU 的記憶體，速度會較慢
- Load Balancing（負載平衡）：讓工作平均分配，確保所有 CPU 保持忙碌
- Push migration：由特定任務定期檢查各處理器的負載，若發現不平衡，就**推送**工作到閒置的處理器
- Pull migration：閒置的處理器主動**拉取**工作，從忙碌的 CPU 移轉部分任務過來

### CPU Scheduling
- Soft real-time systems（軟即時系統）：不保證關鍵任務會準時被排程
- Hard real-time systems（硬即時系統）：任務必須在截止時間前完成

### Rate Monotonic (RM) Scheduling（速率單調排程）
- 優先權依據任務週期的倒數決定：
- 週期短：優先權高
- 週期長：優先權低

### Earliest Deadline First Scheduling（最早截止時間優先）
- 優先權依照「截止時間」分配：
- 截止時間越早：優先權越高
- 截止時間越晚：優先權越低

## Ch6: Synchronization Tools

- Race Condition：多個行程共同讀寫一個資料，會因為交錯執行而產生問題（e.g. i++會被拆成三個指令）
- Critical section（臨界區）：
- 每個行程中需要共享資料的區域
- 一次只能有一個行程進入
- entry section：嘗試排隊進入臨界區
- critical section：讀寫共享資料，一次只有一個行程進入
- exit section：離開臨界區要做的處理
- remainder：不需要共享資料的程式碼區段
- 臨界區問題的解法需要滿足以下三個條件：
- Mutual Exclusion（互斥）：某個行程在臨界區中，其他行程都不能進入自己的臨界區
- Progress（進度性）：決定下一個行程能進臨界區的決定不能無限拖延
- Bounded Waiting（有限等待）：每個請求的等待次數有上限
- 作業系統核心分為兩種：
- Preemptive(可搶先)：行程在核心模式執行時，仍然允許被搶先
- Non-Preeptive(不可搶先)：進入核心模式後行程會持續執行，直到離開核心模式（早期使用）

### Peterson’s Solution （==會考==）
- 針對兩個行程競爭的寫法，假設讀寫是原子操作
- 行程共用：
- turn：輪到哪一個行程可以進入臨界區
- flag[2]：表示該行程是否準備進入臨界區（true）
- 互斥、進度、有限等待皆成立

### Synchronization Hardware
- 利用上鎖來保護臨界區
- Atomic：不可中斷的操作

### test_and_set Instruction （==會考==）
- 
1.指令以原子方式執行
2.回傳參數target原本的值
3.把參數target的新值設為True
- 用法：lock是共享變數
### compare_and_swap Instruction：
1.指令以原子方式執行
2.回傳參數value原本的值
3.只有當value等於expected，value才會改成new_value
- 用法：lock是共享變數，初始為0
### Bounded-Waiting Mutual Exclusion：
- 考慮n個process互斥且有限等待的解法，像是在排隊等號碼牌（待補充）
### Mutex Locks（互斥鎖）：
- 互斥鎖是用來保護臨界區的一種方式
- 先呼叫acquire()取得鎖，結束後再用release()釋放鎖，兩個函式為原子操作
- 缺點：需要busy waiting，因此也被稱為spinlock（自旋鎖）

### Semaphore（號誌）
- 同步工具，比mutex lock更進階
- S：一個整數變數，同時允許多少個資源被使用
- 使用wait()和signal()兩個原子操作來做存取
- Counting semaphore：S的整數值沒有限制範圍
- Binary semaphore：S的整數值為0或1，功能與mutex lock相同
- 事件順序控制範例：
- 必須保證沒有兩個process在同一個Semaphore執行wait()或signal()，這導致變成一個新的critical section problem
- Implementation with No Busy Waiting：
- block：將呼叫這個操作的peocess放到waiting queue中
- wakeup：從wating queue中拿出一個process，把它放會到ready queue
- Deadlock（死結）：兩個程序無限互相等待對方
- Starvation（飢餓）：indefinite blocking（無限期阻塞），某個程序永遠不會被喚醒，永遠無法進入臨界區
- Priority Inversion（優先順序反轉）：
- 當低優先序程序擁有高優先序所需的lock，會導致高優先程序被延遲
- 解決方法：使用Priority-Inhertance protocol(優先繼承協定)，讓低優先序暫時提升優先權

### Problems with Semaphores（==會考==）
- 錯誤使用semaphores可能導致是時間錯誤，只在特定執行順序下發生，不一定可以重現
- e.g. signal(mutex)...wait(mutex)：會導致多個程序同時進入臨界區（破壞互斥）
- e.g. wait(mutex)...wait(mutex)：第二次wait()會導致程序永久堵塞，因為semaphore永遠不可用
- e.g. 漏掉wait(mutex)或signal(mutex)，可能造成mutual exclusion（互斥失效）或permanent block（永久阻塞）

### Monitors（監控器）
- 高階同步機制，提供方便且安全的方式讓多個程序共享資源
- 一種抽象資料型別（abstract data type），內部變數只能被Monitor中的程序存取
- 任一時間只允許一個程序在Monitor內執行

### Condition Variables
- condition x,y;
- 在一個條件變數上允許兩種操作：
- x.wait()：呼叫這個操作的process會被暫停，一直等到有人對x呼叫x.signal()
- x.signal()：喚醒其中一個先前呼叫x.wait()而睡著的process，如果不存在則沒有效果
- 可以想成排隊的概念，x,y=某個隊伍，程序是在等待得人
- 如果 process P 呼叫 x.signal()，而 process Q 目前在 x.wait() 中被暫停，會有兩種情況發生：
- Signal and wait：P 呼叫 signal 後，自己等待，直到 Q 離開 monitor 或 Q 去等其他條件
- Signal and continue：P 呼叫 signal 後，自己繼續執行，Q 要等到 P 離開 monitor 後才會拿到機會進入
- process 在進入 monitor 前必須先執行 wait(mutex)，離開 monitor 時必須執行 signal(mutex)
- signal-and-wait-scheme：
- 發出 signal 的 process 可以使用 next 這個 semaphore 來暫停自已
- 變數 next_count 用來記錄目前有多少 process 被暫停在 next 上
- 對 monitor 中的每個 procedure F 改成下圖，可以保證 monitor 內的互斥（==會考排列、填空或改錯==）
- Variables：
- semaphore mutex; // (initially = 1)
- semaphore next; // (initially = 0)
- int next_count = 0;
- x.wait 和 x.signal 的實做：
- 用 FCFS 來喚醒條件變數上排隊的 process通常不夠好，因此會用有優先權的方式 x.wait(c) 的寫法， c 是 priority number（優先權數字），數字越小代表優先權越高
- Single Resource Allocation（單一資源配置）：
- 使用優先權數字來把單一資源分給多個競爭的程序，數字代表某個 process 打算使用這個資源的最長時間
- R 是型別 ResourceAllocator 的一個實例
- 用 monitor 來配置單一資源：

## Ch8 Deadlocks
- 每個行程使用資源的步驟都是：request（請求）、use（使用）、release（釋放）
- DeadLcok Characterization：死結發生的條件是以下四個條件同時（simultaneously ==考單字==）成立（==會考簡答，6分寫標題，12分加說明==）
1. **Mutual exclusion（互斥）**：某些資源一次只能給一個process用，e.g.印表機
2. **Hold and wait（持有且等待）**：程序已經拿到至少一個資源，但還需要等別人的資源
3. **No preemption（不可搶佔）**：資源只能等持有持有的程序完成才能釋放
4. **Circular wait（循環等待）**：P0等p1的資源、P1等p2的資源......Pn等p0的資源，形成閉環
- 例如以下的 Mutex Locks 會發生死結：
- Resource-Allocation Graph：死結可以用系統配置圖來描述
- 頂點 (Vertices)：
- $P$：所有行程的集合 $\{P_1, P_2, ...\}$
- $R$：所有資源類型的集合 $\{R_1, R_2, ...\}$
- 邊 (Edges)：
- 請求邊 (Request Edge)：$P_i \rightarrow R_j$ （行程 P 請求資源 R）
- 分配邊 (Assignment Edge)：$R_j \rightarrow P_i$ （資源 R 已分配給行程 P）
- 資源分配圖範例：
- 有死結的資源分配圖：
- 有循環但無死結的圖
- **死結判斷方式**：
- 如果圖中沒有循環 -> 沒有死結
- 如果途中有循環：
- 若每種資源只有一個實例 -> 必有死結
- 若每種資源有多個實例 -> 可能有死結
- 處理死結的方法：
- 做預防和避免，確保系統永遠不進入死結
- 允許死結發生再做修復
- 無視問題，假裝死結不存在，大多作業系統採用的辦法（包含Windows 和 Linux(UNIX)）
- **預防死結**：
- **互斥（Mutual Exclusion）**：對於不可共用的資源（如印表機）必須保持互斥，但可共用資源（如唯讀檔案）則不需要
- **持有並等待（Hold and Wait）**：
- 規定行程在執行前必須一次申請完所有資源，或申請資源時手上不能有其他資源
- 缺點：資源利用率低，且可能導致飢餓（Starvation）
- **不可搶佔（No Preemption）**：如果申請不到新資源，就必須釋放手上所有資源，之後再全部重新申請
- **循環等待（Circular Wait）**：將所有資源編號，強制行程只能依照編號順序（例如由小到大）申請資源
- **避免死結**：
- 需要行程預先提供資訊（例如最多需要多少資源）
- 演算法會動態檢查資源分配狀態，確保永遠不會出現循環等待
- 安全狀態（Safe State）：（==會考==）
- 如果系統能找到一個安全序列 (Safe Sequence) $<P_1, P_2, ..., P_n>$，讓所有行程都能順利執行完畢，系統就是處於安全狀態
- 就算 $P_i$ 要的資源現在不夠，只要等前面的 $P_j$ 用完歸還，$P_i$ 最終還是能拿到資源
- **死結判斷方式**：
- 安全狀態 -> 沒有死結
- 不安全狀態 -> 可能有死結
- 避免死結演算法：確保系統永遠保持在安全區
- **宣告邊（Claim Edge）**：
- 虛線，表示行程未來可能會請求該資源
- 當請求發生時，虛線變實線
- 只有當把請求邊變成分配邊不會導致圖中出現循環時，才允許分配

### Banker’s Algorithm （==會考==）
- 適用於多重資源實例
- 行程需預先宣告最大需求（Maximum use）
- 行程請求資源時若不安全則需等待
- Banker’s Algorithm 資料結構：
- Available: 目前系統還剩多少資源
- Max: 每個行程最多需要多少資源
- Allocation: 目前已經給每個行程多少資源
- Need: 每個行程還需要多少資源才能完成（$Need = Max - Allocation$）

#### Safety Algorithm
- 安全性演算法：檢查當前狀態是否安全，用來找找安全序列，步驟如下：
1. 設定工作向量 Work：一開始 Work = Available (目前的閒置資源)
2. 設定 Finish 向量：所有 Process 的 Finish[i] = false (還沒做完)
3. 尋找可執行的 Process：
- 從頭掃描，找到一個 Process $P_i$ 滿足：
1. Finish[i] == false (還沒做完)
2. Need[i] <= Work (它缺的資源，我們現在夠給它)
4. 模擬執行與回收：
- 如果找到了這樣的 $P_i$，假設它執行完畢，釋放它手上的資源：$$Work = Work + Allocation[i]$$
- 標記 Finish[i] = true
- 回到步驟 3，繼續找下一個
5. 判斷結果：
- 如果所有 Process 都能被標記為 true，則系統處於 Safe State
- 找到的順序 (例如 $<P_1, P_3, P_4, P_2, P_0>$) 即為 Safe Sequence 2

#### Resource-Request Algorithm
- 資源請求演算法
- 當行程 $P_i$ 提出請求時：
1. 檢查請求是否超過它宣告的最大值（Request[i] <= Need[i]）
2. 檢查系統有沒有足夠資源 (Request[i] <= Available)
3. 假裝分配給它，更新狀態：
- Available = Available - Request[i]
- Allocation[i] = Allocation[i] + Request[i]
- Need[i] = Need[i] - Request[i]
4. 執行安全性演算法：
- 如果是安全的，就給資源給 $P_i$ （Granted）
- 不安全，收回分配的資源，讓 $P_i$ 繼續等待

#### Banker’s Algorithm範例（==會考==）

### Deadlock Detection
- 若是允許系統進入死結狀態，就需要偵測演算法和恢復機制
- 單一實例系統：
- 維護一張等待圖（wait-for graph）：
- 圖中的節點（Nodes）代表行程（Processes）
- $P_i \rightarrow P_j$ 表示行程 $P_i$ 正在等待行程 $P_j$（釋放資源）
- 定期執行演算法來搜尋圖中是否存在循環（cycle），如果圖中存在循環，就代表存在死結
- 偵測圖中循環的演算法所需的運算量級為 $n^2$，其中 $n$ 是圖中頂點（即行程）的數量
- 多重實例系統：
- Available（可用資源向量）：一個長度為 $m$ 的向量，表示每種資源類型目前還剩下多少可用
- Allocation（已分配矩陣）：一個 $n \times m$ 的矩陣，定義了目前已經分配給每個行程的各類資源數量
- Request（請求矩陣）：
- 一個 $n \times m$ 的矩陣，表示每個行程目前正在請求的資源
- 如果 $Request[i][j] = k$，代表行程 $P_i$ 正在請求 $k$ 個 $R_j$ 類型的資源實例

#### Detection Algorithm（==會考==）
- $n$：行程 (Process) 的數量
- $m$：資源種類 (Resource types) 的數量
- Available：目前可用的資源向量
- Allocation：每個行程目前已持有的資源矩陣
- Request：每個行程目前正在請求的資源矩陣
- 執行步驟：
1. 初始化：
- 設定暫存向量 $Work$ (代表當前可用的模擬資源量) 初始化為 $Available$
- 設定向量 $Finish$ (標記行程是否能完成) 的初始值：
- 若 Allocation[i] $\neq 0$ (該行程持有資源)，則設 Finish[i] = fals
- 若 Allocation[i] $== 0$ (該行程沒佔用任何資源)，則設 Finish[i] = true
2. 尋找可執行行程：
- 尋找一個索引 $i$ (行程 $P_i$) 同時滿足以下兩個條件：
1. Finish[i] == false (尚未標記為完成)
2. Request[i] <= Work (該行程目前的請求量 $\le$ 系統目前的可用量)
- 如果找不到這樣的 $i$，跳到步驟 4。
3. 回收資源：
- 假設該行程 $P_i$ 獲得資源並執行完畢，將其資源歸還給系統：
- Work = Work + Allocation[i]
- Finish[i] = true
- 回到步驟 2 繼續檢查下一個行程
4. 判斷死結：
- 檢查 $Finish$ 向量
- 如果存在某個 $i$ 使得 Finish[i] == false，則代表系統處於死結狀態
- 所有 Finish[i] == false 的行程 $P_i$ 都是死結的一部分。
- 如果太常偵測死結，系統開銷會太大，如果太久沒偵測的話，影響的範圍會越來越大

### Recovery from Deadlock（從死結恢復）
- 終止行程：
- 方法一：殺掉所有死結行程
- 方法二：一次殺一個，殺到死結解開為止
- 選擇程序標準：優先權、已執行時間、已用資源等
- 從死結恢復需要考慮以下三個問題：
1. 選擇受害者（Selecting a victim）：成本最小化
2. 回滾（Rollback）：把行程退回到安全狀態再重啟
3. 飢餓（Starvation）：要確保同一個行程不會倒楣一直被選中當受害者

## CH9 Main Memory
- 記憶體單元只會看到一連串的位址與讀取請求（addresses + read requests），或者是位址加上數據與寫入請求（address + data and write requests）
- 存取暫存器只需要一個 CPU 時脈週期
- 存取主記憶體可能需要多個週期，這會導致 CPU 停頓（stall）
- 快取（Cache） 位於主記憶體和 CPU 暫存器之間
- 一對基底（base、起點）和限制（limit、長度）暫存器定義了邏輯位址空間，限制每個程式的存取範圍

### Address Binding（位址綁定）
- 程式以二進制形式存在磁碟上，執行時將其放入記憶體，若沒有支援，則載入到位址 0000
- 位址在程式生命週期的不同階段有不同的表示方式：
- 原始碼位址（Source code）：通常是符號（例如變數 count）
- 編譯碼位址（Compiled code）：綁定到可重定位（relocatable）位址
- 連結器或載入器（Linker/Loader）：將可重定位位址綁定到絕對位址
- 每個綁定過程都是將一個位址空間映射到另一個位址空間
- 指令和數據綁定到記憶體位址可以在三個不同階段發生：
- 編譯時期（Compile time）：
- 如果在編譯時就已經知道記憶體位置，就可以產生絕對代碼（absolute code）
- 如果位置變了就需要重新編譯
- 載入時期（Load time）：
- 如果編譯時不知道行程將駐留在記憶體的何處，編譯器必須產生可重定位代碼（relocatable code）
- 最終的綁定會延遲到載入時期
- 如果起始位址改變，只需要重新載入使用者程式碼
- 執行時期（Execution time）：
- 如果行程在執行過程中可以從一個記憶體區段移動到另一個區段，則綁定會延遲到執行時期
- 需要硬體支援位址映射

- 使用者程式的多步驟處理： （==考填空==）
- 編譯時期（Compile time）：原始程式（Source program） -> 編譯器（Compiler） -> 目的檔（Object file）
- 載入時期（Load time）：目的檔 + 其他目的檔 -> 連結器（Linker） -> 執行檔（Executable file）
- 執行時期（Execution time/Run time）：執行檔 + 動態連結函式庫（Dynamically linked libraries） -> 載入器（Loader） -> 記憶體中的程式
- 「邏輯位址空間」綁定到單獨的「實體位址空間」的概念，是正確記憶體管理的核心
- 邏輯位址（Logical address）：虛擬位址（virtual address），由 CPU 產生
- 實體位址（Physical address）：記憶體單元看到的位址
- 編譯、載入時期：邏輯位址和實體位址相同
- 執行時期：邏輯位址和實體位址不同
- 邏輯位址空間：程式產生的一組所有邏輯位址
- 實體位址空間：對應於這些邏輯位址的一組所有實體位址

### Memory-Management Unit (MMU)
- 記憶體管理單元：在執行時期將虛擬位址映射到實體位址的硬體裝置
- 簡單方案：在使用者行程產生位址並送往記憶體時，將重定位暫存器（Relocation register）的值加到每一個位址上
- 基底暫存器（Base register）在此稱作重定位暫存器
- 使用者程式處理的是邏輯位址，不會看到真實的實體位址

### Dynamic Relocation Using a Relocation Register
- 常式（Routine）直到被呼叫時才載入
- 未使用的常式永遠不會被載入，有更好的記憶體空間利用率
- 所有常式都以可重定位的載入格式保存在磁碟上
- 當需要大量程式碼來處理不常發生的情況時特別有用

### Dynamic Linking and Shared Libraries
- 動態連結函式庫（Dynamically linked libraries，DLLs）：系統函式庫，在程式執行時才連結到使用者程式
- **靜態連結（Static linking）**：系統函式庫和程式碼由載入器合併成一個二進位程式映像
- **動態連結（Dynamic linking）**：連結被推遲到執行時期
- 通常用於系統函式庫，例如標準 C 語言函式庫
- 這些函式庫可以在多個行程之間共享，因此主記憶體中只需有一個 DLL 的實例，DLLs 也被稱為共享函式庫（shared libraries）
- DLLs 可以擴展到函式庫更新（例如錯誤修復），函式庫可以被新版本取代，所有引用該函式庫的程式將自動使用新版本

### Swapping
- 一個行程可以暫時從記憶體被置換（swapped）到備用儲存裝置（backing store），然後再帶回記憶體繼續執行，使得行程的總實體記憶體空間可以超過實際的實體記憶體
- 備用儲存裝置（Backing store）：快速的磁碟，夠大以容納所有使用者的記憶體映像副本，必須提供對這些映像的直接存取
- Roll out, roll in：用於優先級排程演算法的置換變體，低優先級行程被換出，以便載入並執行高優先級行程
- 置換時間的主要部分是傳輸時間，總傳輸時間與置換的記憶體量成正比
- 系統維護一個就緒佇列（ready queue），包含那些記憶體映像在磁碟上的就緒行程
- 現代作業系統通常不再使用標準置換，因為所需時間太長
- 如果下一個要上 CPU 的行程不在記憶體中，需要換出（swap out）一個行程並換入（swap in）目標行程
- 上下文交換（Context switch）時間會變得非常長，e.g. 100MB 的行程置換到傳輸率為 50MB/sec 的硬碟需要4秒
- 置換不能用於待處理的 I/O，或者總是透過核心（kernel）的緩衝區進行傳輸，然後再從核心複製到行程的位址空間，這稱為雙重緩衝（double buffering），會增加負擔
-
### Contiguous Allocation（連續配置）
- 主記憶體通常分為兩個分區（partitions）：
- 常駐作業系統（Resident OS），通常放在低位址記憶體，包含中斷向量
- 使用者行程則放在高位址記憶體
- 每個行程包含在記憶體的一個單一連續區段中
- 使用重定位暫存器來保護使用者行程彼此不受影響，也不受作業系統程式碼和資料改變的影響
- 基底暫存器（Base register）：包含最小實體位址的值
- 限制暫存器（Limit register）：包含邏輯位址的範圍（每個邏輯位址必須小於限制暫存器）
- MMU 動態映射邏輯位址
- 這允許核心程式碼是暫時的 (transient) 且核心大小可以改變

### Multiple-partition Allocation（多重分區配置）
- **可變分區大小**（Variable-partition sizes）：根據特定行程的需求調整大小，用於提高效率
- **孔洞**（Hole）：一塊可用的記憶體區塊，各種大小的孔洞散布在記憶體各處
- 當一個行程到達時，系統會從一個夠大的孔洞中配置記憶體給它
- 當行程離開時，它會釋放其分區，相鄰的空閒分區會被合併
- 作業系統維護：
1. 已配置的分區（allocated partitions）
2. 空閒的分區（free partitions）
- 如何動態分配儲存位址：
- 首次配適（First-fit）：配置「第一個」夠大的孔洞
- 最佳配適（Best-fit）：配置「最小」但夠大的孔洞，必須搜尋整個清單，除非清單依大小排序
- 剩餘孔洞最小
- 最差配適（Worst-fit）：配置「最大」的孔洞，必須搜尋整個清單
- 剩餘孔洞最大
- First-fit 和 Best-fit > Worst-fit

### Fragmentation（碎片化）（==會考==）
- **外部碎片（External Fragmentation）**：總記憶體空間足以滿足請求，但它不是連續的
- **內部碎片（Internal Fragmentation）**：配置的記憶體可能比請求的記憶體稍大，但多餘部分未被使用
- 緊縮（Compaction）：重新排列記憶體內容，將所有空閒記憶體集中成一個大區塊，來減少外部碎片

### 分段（Segmentation）
- 支援使用者觀點的記憶體管理機制
- 一個程式是區段（segments）的集合
- 一個區段是一個邏輯單元，例如：主程式、程序、函數、方法、物件、區域變數、全域變數、堆疊、陣列
- 邏輯位址：由二元組（two tuple）組成，<區段編號（segment-number）, 位移量（offset）>
- **區段表（Segment table）**：映射二維的實體位址，每個表項目有：
- **基底（base）**：包含區段在記憶體中開始的實體位址
- **限制（limit）**：指定區段的長度
- **區段表基底暫存器（Segment-table base register，STBR）**：指向區段表在記憶體中的位置
- **區段表長度暫存器（Segment-table length register，STLR）**：指示程式使用的區段數量
- 如果區段編號 s < STLR，則 s 是合法的
- 保護（Protection）：每個區段表項目紀錄
- 驗證位元 (validation bit)：0 代表非法區段
- 讀／寫／執行權限 （read/write/execute privileges）

### Paging（分頁）
- 行程的實體位址空間可以是不連續的，只要有可用的實體記憶體，就可以配置給行程
- 優點：避免了外部碎片、避免了記憶體區塊大小不一的問題
- 缺點：仍然會有內部碎片
- 頁框（frames）：實體記憶體分割成固定大小的區塊
- 分頁（pages）：邏輯記憶體分割成同樣大小的區塊
- 要執行大小為 N 個分頁的程式，需要找到 N 個空閒頁框並載入程式
- 分頁表（page table）：將邏輯位址轉換為實體位址
- 位址轉換機制：
- **分頁編號**（Page number, p)：用作分頁表的索引，分頁表包含每個分頁在實體記憶體中的基底位址
- **分頁位移**（Page offset, d）：與基底位址結合，定義送往記憶體單元的實體記憶體位址
- 分頁表保存在主記憶體中
- **分頁表基底暫存器（Page-table base register，PTBR）** 指向分頁表
- **分頁表長度暫存器（Page-table length register，PTLR）** 指示分頁表的大小
- 每一次資料／指令存取需要兩次記憶體存取，查分頁表+拿資料／指令
- **轉譯後備緩衝區（TLBs, translation look-aside buffers）** ：或稱關聯式記憶體（associative memory），使用特殊的快速查找硬體快取來解決兩次記憶體存取的問題
- 固定（Wired down）：重要資訊會被固定在TLB上
- 位址空間識別碼（ASIDs）：識別每個行程位址，避免拿錯

### 有效存取時間（EAT） （==會考==）
- 命中率（Hit ratio）$\alpha$：在關聯式暫存器（TLB）中找到分頁編號的機率
- 有效存取時間（Effective Access Time）：$\alpha$ $\times$ 存取時間 + (1 - $\alpha$) $\times$ 2倍存取時間
- 考慮 $\alpha = 80\%$，記憶體存取時間為 10ns：
- $EAT = 0.80 \times 10 + 0.20 \times 20 = 12ns$ 2
- 考慮 $\alpha = 99\%$
- $EAT = 0.99 \times 10 + 0.01 \times 20 = 10.1ns$

### 記憶體保護（Memory Protection）
- 透過保護位元 (protection bit) 來指定為唯讀（read-only）或讀寫（read-write）
- **有效-無效位元（Valid-invalid bit）** 附在分頁表的每個項目上：
- Valid（有效）：表示該分頁在行程的邏輯位址空間內，是合法的分頁
- Invalid（無效）：表示該分頁不在行程的邏輯位址空間內
- 或使用分頁表長度暫存器（page-table length register，PTLR）

### 共享分頁（Shared Pages）
- **共享代碼**（Shared code）：
- 一份唯讀（read-only）或重入（reentrant） 程式碼在行程間共享
- 類似於多個執行緒共享同一個行程空間
- **私有代碼與數據**（Private code and data）：
- 每個行程保存一份獨立的代碼和數據副本
- 私有代碼和數據的分頁可以出現在邏輯位址空間的任何地方

### 分頁表（Page Table）（==會考==）
- 直接建立分頁表需要巨大的主記憶體連續空間
- 解法：使用階層式分頁（Hierarchical Paging）或雜湊分頁表（Hashed Page Tables）或反向分頁表（Inverted Page Tables）

#### 階層式分頁（Hierarchical Paging）
- 將邏輯位址空間拆解成多個分頁表，例如兩層分頁表
- 兩層分頁表（two-level page table）：
- 外部分頁表（Outer page table）：只有一個，項目指向內層分頁表
- 分頁表的分頁（Page of page table）：內層表格，項目指向真正的記憶體 Frame
- 一個邏輯位址（在 32-bit 機器，1K 分頁大小）被分為：
- 一個 22 bits 的分頁編號，分為：
- 一個 12-bit 的分頁編號（$p_1$）
- 一個 10-bit 的分頁位移（$p_2$）
- 一個 10 bits 的分頁位移
- **前向映射分頁表**（forward-mapped page table）：
- $p_1$（12 bits）：外部分頁表的索引
- $p_2$（10 bits）：內部分頁表的位移
- d（10 bits）：分頁位移
- 兩層分頁表對於 64 bit 不太夠用，須拆成三層，但會導致效率變差

#### 雜湊分頁表（Hashed Page Tables）
- 虛擬分頁編號透過雜湊（hushed）進入一個分頁表
- 該分頁表包含一個元素鏈結串列（linked list），雜湊到同一位置的元素串在一起
- 每個元素包含：(1) 虛擬分頁編號、(2) 映射的頁框值、(3) 指向下一個元素的指標
- 虛擬分頁編號在鏈結中比對、尋找匹配，如果找到則提取對應的實體頁框
- 64-bit 的變體是叢集分頁表（clustered page tables）：
- 類似雜湊表，但每個項目指向多個分頁（例如 16 個），而非 1 個
- 對於稀疏（sparse）位址空間特別有用

#### 反向分頁表（Inverted Page Tables）
- 追蹤所有實體分頁，記憶體的每個實體分頁只有一個項目
- 項目包含：存放在該實體位置的虛擬位址，以及擁有該分頁的行程資訊（PID）
- 優點：減少儲存分頁表所需的記憶體
- 缺點：當分頁引用發生時，搜尋表格的時間增加

## Ch10 Virtual Memory
- 虛擬記憶體（Virtual Memory）：
- 將「使用者邏輯記憶體」與「實體記憶體」分開，只有部分程式需要存在記憶體中才能執行
- 「邏輯位址空間」可以比「實體位址空間」大得多
- 允許位址空間被數個行程共享
- 允許更有效率的行程建立
- 更多程式可以同時並行、載入或置換行程所需的 I/O 更少
- 虛擬記憶體可以透過請求分頁（Demand paging）、請求分段（Demand segmentation）實作

### 虛擬位址空間（Virtual address space）
- 行程如何儲存在記憶體中的邏輯視圖
- 邏輯位址空間設計為堆疊從最大邏輯位址開始並「向下」增長，而堆積則「向上」增長
- 兩者之間未使用的位址空間是洞（hole）
- 允許稀疏（sparse）的位址空間，留下的洞可用於增長、動態連結函式庫（DLLs）等

### 請求分頁（Demand Paging）
- 在載入時將整個行程帶入記憶體，或者只有當需要時才將分頁帶入記憶體
- 減少 I/O、減少記憶體需求、更快的回應、更多使用者
- 懶惰置換器（Lazy swapper）：除非分頁被需要，否則絕不將分頁置換入記憶體
- Pager：處理分頁的置換器

### 有效-無效位元（Valid-Invalid Bit）
- 每個分頁表項目都有一個有效-無效位元，V 代表在記憶體中，i 代表不在記憶體中
- 最初，所有項目的位元都設為 i
- MMU 位址轉換期間，如果分頁表項目中的位元是 i 會觸發分頁錯誤（Page Fault）

### 分頁錯誤（Page Fault）
- 如果有個參考指向一個分頁，第一次參考到該分頁時會觸發作業系統的 trap：
1. 檢查是否為無效的參考，是的話終止，否則開始交換分頁
2. 找到一個空閒的頁框，透過排程磁碟操作，將分頁置換到頁框中
3. 設定位元為 v
4. 重新啟動指令
- 純請求分頁（Pure demand paging）：記憶體中沒有任何分頁，接著每個其他分頁都在第一次存取時發生 page fault
- 請求分頁的效能（==有可能考排序==）
- 服務時間分成三個部分：
- 服務分頁錯誤中斷：很快
- 讀取分頁：花很多時間
- 重新啟動行程：很快
- 分頁錯誤率（Page Fault Rate）$0 \le p \le 1$
- 如果 $p = 0$，沒有分頁錯誤
- 如果 $p = 1$，每次參考都發生錯誤
- 有效存取時間（EAT）：$EAT = (1 - p) \times \text{記憶體存取時間} + p \times (\text{分頁錯誤負擔} + \text{換出時間} + \text{換入時間})$

### Copy-on-Write
- 寫入時複製（Copy-on-Write, COW）：
- 允許父行程和子行程最初在記憶體中共享相同的分頁
- 如果任一行程寫入共享分頁，則會建立該共享分頁的副本

### 頁面置換（Page Replacement）
- 透過頁面置換來防止記憶體過度分配
- 使用修改位元（modify/dirty bit）來減少頁面傳輸的負擔，只有被修改過的頁面才需要寫回磁碟
- Process 1 需要載入分頁 B，但hysical Memory 已經滿了：
- 基本頁面置換：
1. 在磁碟上找到所需分頁的位置
2. 找到一個空閒頁框：
- 如果有空閒頁框，就使用它
- 如果沒有空閒頁框，使用頁面置換演算法選擇一個受害者頁框（victim frame），受害者是髒 （dirty）的話就寫回磁碟
3. 將所需分頁帶入空閒頁框；更新分頁表和頁框表
4. 透過重新啟動造成 trap 的指令來繼續行程
- 頁框配置演算法（Frame-allocation algorithm）決定：
- 給每個行程多少個頁框？
- 要置換哪些頁框？
- 頁面置換演算法 (Page-replacement algorithm)：
- 希望在第一次存取和重新存取時都有最低的分頁錯誤率
- 後續的範例都使用此參考字串：7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1,3,0,3,2,1,2,0,1,7,0,1

### 演算法
#### FIFO Algorithm （==會考==）
- 先進先出（First-In-First-Out，FIFO）演算法：最早來的最先被移除
- Belady's Anomaly（貝拉迪異常）：增加更多頁框反而導致更多分頁錯誤 （==會考==）

#### Optimal Algorithm （==會考==）
- 最佳化演算法（Optimal Algorithm）：置換「在最長時間內不會被使用」的分頁
- 缺點：無法實作，只能作為評估其他演算法的標準

#### LRU Algorithm （==會考==）
- 最近最少使用演算法（Least Recently Used Algorithm）：置換「最長一段時間沒有被使用」的分頁
- 主流演算法，效果比 FIFO 好
- 實作方式：
- 計數器實作：每個分頁項目有個計數器，需置換時，搜尋表格找最小值（較慢）
- 堆疊實作：用雙向鏈結串列保存分頁編號堆疊，分頁被參考時移到頂端（較快，不需要搜尋，但麻煩）
- LRU 和 OPT 是 **Stack Algorithm**：當分配給行程 $n$ 個頁框 (frames) 時，記憶體中的頁面集合，永遠是分配 $n+1$ 個頁框時的子集，不會發生 Belady's Anomaly （==會考==）

##### LRU 近似演算法
- 附加參考位元演算法（Additional-Reference-Bits Algorithm）：
- 每個分頁關聯一個位元，初始為 0，被參考時設為 1
- 定期將位元右移到歷史紀錄中
- 二次機會演算法（Second-Chance Algorithm）：又稱時鐘演算法（clock algorithm）
- FIFO 加上硬體提供的參考位元
- 如果要置換的頁面：
- 參考位元 = 0：置換它
- 參考位元 = 1：設為 0，檢查下一個分頁，給它第二次機會
- Enhanced Second-Chance Algorithm：增強型二次機會演算法，同時使用參考位元（reference bit）和修改位元（modify bit）來改進
考慮有序對（reference, modify）：
- (0, 0)：最近沒用過也沒修改 -> 最佳置換對象
- (0, 1)：沒用過但修改過 -> 須寫回磁碟，次佳
- (1, 0)：最近用過但乾淨 -> 可能很快又要用
- (1, 1)：最近用過且修改過 -> 最不該置換

#### Counting Algorithms
- 計數演算法：以下兩個算法效果普通且少用
- 最不常使用（Least Frequently Used，LFU）演算法：置換計數最小的分頁
- 最常使用（Most Frequently Used，MF）演算法：置換計數最大的分頁

#### Page-Buffering Algorithms
- 頁面緩衝演算法：始終保留一個空閒頁框池（pool of free frames）
- 當發生 page fault，像以前一樣選擇受害者
- 但在寫出受害者之前，先將所需分頁讀入空閒池中的頁框，藉此提升速度

### 頁框的配置（Allocation of Frames）
- 每個行程都需要最少數量的頁框，最大數量為系統中的總頁框數
- 兩種主要的配置方案：
- 固定配置（fixed allocation）
- 優先權配置（priority allocation）

#### 固定配置（fixed allocation）
- 均等配置（Equal allocation）：
- e.g. 如果有 100 個頁框和 5 個行程，每個行程分給 20 個頁框
- 保留一些作為空閒頁框緩衝池
- 比例配置（Proportional allocation）：
- 依照行程的大小來動態配置
- 公式：$a_i = (s_i / S) \times m$
- $s_i$ = 行程 $i$ 的大小
- $S$ = 所有行程總大小
- $m$ = 總頁框數
- e.g. 總共 62 頁框，P1 = 10、P2 = 127
- P1 分到 $10/137 \times 62 \approx 4$
- P2 分到 $127/137 \times 62 \approx 57$

#### 優先權配置（priority allocation）
- 使用比例配置方案，但依照優先權而非行程大小
- 如果行程 $P_i$ 產生分頁錯誤：
- 選擇置換它自己的一個頁框
- 或者選擇置換一個優先權較低的行程的頁框

### 全域 vs. 區域置換（Global vs. Local Replacement）
- 全域置換（Global replacement）：
- 行程從所有頁框的集合中選擇一個置換頁框
- 一個行程可以奪走另一個行程的頁框
- 行程執行時間可能變異很大，但吞吐量較高，所以較常見
- 區域置換（Local replacement）：
- 每個行程只從它自己分配到的頁框集中選擇
- 每個行程的效能較一致
- 但可能導致記憶體利用率不足

### 非均勻記憶體存取（Non-Uniform Memory Access）
- 非均勻記憶體存取（NUMA）：記憶體存取速度會變動
- 記憶體配置在「靠近」執行該執行緒的 CPU 處效能最佳

### 抖動（Thrashing） （==會考==）
- **抖動（Thrashing）**：行程忙於換入換出分頁，而非執行工作
- 如果一個行程沒有「足夠」的分頁，分頁錯誤率會非常高
- Page fault 取得分頁 => 置換現有的頁框 => 很快又需要被置換掉的頁框
- 導致低 CPU 利用率
- 作業系統以為 CPU 沒事做，加入另一個行程到系統中
（==會考==）
- 請求分頁（Demand Paging）： （==會考==）
- 區域性模型（Locality model）：當行程執行時，它會從一個區域移動到另一個區域
- 執行中的程式通常由數個不同的區域組成，它們可能會重疊
- 區域大小總和 > 總記憶體大小 => Thrashing

### Working-Set（工作集）
- $\Delta \equiv$ 工作集視窗 (working-set window) $\equiv$ 固定數目的分頁參考（例如 10,000 個指令）
- $WSS_i$ (行程 $P_i$ 的工作集大小) = 在最近 $\Delta$ 時間內參考到的分頁總數
- 如果 $\Delta$ 太小，無法包含整個區域性
- 如果 $\Delta$ 太大，會包含數個區域性
- 如果 $\Delta = \infty$，將包含整個程式
- $D = \Sigma WSS_i \equiv$ 對頁框的總需求
- 如果 $D > m$（總需求 > 總頁框數），則發生 Thrashing
- 暫停或換出其中一個行程

#### 追蹤工作集 （==會考==）
- 範例：$\Delta = 10,000$
- 計時器每 5,000 個時間單位中斷一次
- 為每個分頁在記憶體中保留 2 個位元
- 每當計時器中斷時，複製並將所有參考位元設為 0
- 如果記憶體中的任一位元 = 1 -> 該分頁在工作集中
- 改進：使用 10 個位元並每 1,000 個時間單位中斷一次

#### 分頁錯誤頻率（Page-Fault Frequency，PFF）
- 比工作集模型更直接控制 Thrashing 的方法
- 建立「可接受的」分頁錯誤頻率（PFF）率，並使用區域置換策略
- 如果實際頻率太低（沒什麼錯誤），代表分給它的格子太多了 => 行程失去頁框
- 如果實際頻率太高（一直錯誤），代表格子不夠用 -> 行程獲得頁框

#### 工作集與分頁錯誤率（Working Sets and Page Fault Rates）
- 行程的工作集與其分頁錯誤率之間有直接關係
- 隨時間改變出現工作集、波峰和波谷 （==會考 working set==）

### 記憶體映射檔案（Memory-Mapped Files）
- 記憶體映射檔案 I/O 允許檔案 I/O 被視為一般的記憶體存取，透過將磁碟區塊映射到記憶體分頁
- 將記憶體映射檔案技術用於所有 I/O
- 有些 OS 使用記憶體映射檔案來處理標準 I/O

### 夥伴系統（Buddy System） （==會考==）
- 從由實體連續分頁組成的固定大小區段中配置記憶體
- 使用 2 的次方配置器來配置記憶體（無條件進位到下一個最高的 2 的次方）
- 當需要的配置比可用的還小時，目前的區塊會分裂成兩個 夥伴 (buddies) （下一個較低的 2 的次方）
- 繼續分裂直到有合適大小的區塊可用
- e.g. 假設有 256KB 的區塊可用，核心請求 21KB
- 分裂成 $A_L$ 和 $A_R$，各 128KB
- 其中一個進一步分裂成 $B_L$ 和 $B_R$，各 64KB
- 其中一個進一步分裂成 $C_L$ 和 $C_R$，各 32KB ，其中一個用來滿足請求
- 優點：可以快速將未使用的區塊合併（coalesce）X成較大的區塊
- 缺點：碎片化

### Slab 配置器（Slab Allocator）（==會考==）
- Slab：一或多個實體連續的分頁（==會考==）
- Cache：一或多個 Slabs 組成（==會考==）
- 每個唯一的核心資料結構都有一個單獨的 Cache
- 每個 Cache 填滿了物件（objects）：該資料結構的實例（==會考==）
- 當 Cache 建立時，填滿了標記為空閒（free）的物件
- 當結構被儲存時，物件標記為已使用（used）
- 如果 Slab 中的已用物件滿了，下一個物件從空閒 Slab 配
- 如果沒有空閒 Slabs，則配置新的 Slab
- 優點：沒有碎片化（剛好符合物件大小）、記憶體請求滿足速度快

### 其他考量
#### 預先分頁（Prepaging）
- 用來減少行程啟動時發生的大量分頁錯誤
- 在參考之前，預先將行程需要的所有或部分分頁載入
- 但如果預先載入的分頁沒被使用，I/O 和記憶體就浪費了

#### 分頁大小（Page Size）
- 碎片化（Fragmentation）：頁面越大，最後一頁浪費的空間（內部碎片）越多
- 分頁表大小（Page table size）： 頁面越小，頁數越多，分頁表越大（浪費記憶體）

#### TLB 覆蓋範圍（TLB Reach）（==會考==）
- TLB Reach：透過 TLB 可以存取的記憶體總量
- TLB Reach = (TLB Size) $\times$ (Page Size)
- 理想情況下，每個行程的工作集（Working set）都儲存在 TLB 中
- 增加分頁大小：可能導致碎片化增加，因為並非所有應用程式都需要大分頁
- 提供多種分頁大小：允許需要大分頁的應用程式有機會使用它們，而不會增加碎片化

#### I/O 互鎖（I/O Interlock）
- I/O 互鎖（I/O Interlock）：分頁有時必須被鎖定（locked）在記憶體中
- 用於從裝置複製檔案的分頁必須被鎖定，防止被頁面置換演算法選中並驅逐
- 釘選（Pinning）分頁以將其鎖定在記憶體中