Maurice Bach：the Design Of The Unix Operating System@1986

本書《UNIX 作業系統的設計》由 Maurice J. Bach 撰寫，旨在深入探討 UNIX 作業系統核心（Kernel）的內部演算法與資料結構，以及它們與程式設計師介面之間的關聯。不同於許多描述使用者層面（例如 Shell 指令、文書處理或程式撰寫介面）的書籍，本書的核心重點聚焦在作業系統的核心部分如何運作，以及系統呼叫（System Call）是如何被實現的。

本書的主要論點可以概括為以下幾個方面：

1. 核心目的與範圍： 本書的根本目的是為讀者提供對 UNIX 作業系統內部運作機制透徹的理解。它詳細闡述了構成核心的各種演算法和資料結構，並解釋了這些內部組件如何支撐使用者層面的服務和程式設計師介面提供的功能。本書的描述基於 AT&T 的 UNIX System V Release 2，同時也會探討 Release 3 的一些新特性以及 Berkeley Software Distribution (BSD) 版本中值得關注的功能。然而，本書刻意避免深入探討特定硬體平台的特性，儘可能以通用術語來描述核心與硬體之間的介面，除非硬體細節對於理解核心的特定實現至關重要。本書也不涉及絕對的系統效能數據、組態參數建議或對未來 UNIX 特性的預測，除非在進階主題中需要討論研究方向。

2. 目標讀者與先備知識： 本書的目標讀者是具有一定程式設計經驗的讀者。具體來說，對於進階大學部或研究所一年級的學生，本書可以作為作業系統課程的教科書，尤其適合與系統原始碼配合閱讀。對於系統程式設計師，本書可以作為參考資料，幫助他們更好地理解核心的運作方式，並將 UNIX 系統中的演算法與其他作業系統中的演算法進行比較。對於在 UNIX 系統上進行程式開發的程式設計師，本書則有助於更深入地理解他們的程式如何與系統互動，從而編寫出更有效率和精密的程式。雖然本書建議讀者具有高階語言（最好是組合語言）的經驗，以及熟悉 C 語言和 UNIX 系統環境，但作者也努力使得沒有這些背景的讀者仍能理解書中內容。書末附錄提供了簡化的系統呼叫描述，足以理解書中的概念。

3. 核心架構與結構化組織： 本書按照模組化的方式組織，反映了 UNIX 核心在邏輯上的架構。核心被分為兩大主要部分：檔案子系統（File Subsystem）和處理程序控制子系統（Process Control Subsystem）。書本的章節安排遵循一種循序漸進的「積木式」方法，先介紹較為基礎的概念和組件，再疊加更複雜的內容。例如，先介紹檔案子系統的概念，因為其概念比處理程序控制更容易理解。這種結構化的方式有助於讀者逐步建立對整個核心的完整認識。

4. 主要核心組件與概念的詳細闡述（依章節順序）：

   • 系統概觀與核心簡介 (第一章和第二章)： 介紹 UNIX 系統的歷史、整體架構（使用者層、核心層、硬體層）和使用者視角下的重要特性（檔案系統、處理程序環境、積木式原語，如管道和 I/O 重定向）。隨後深入核心，描繪其模組結構（檔案子系統、處理程序控制子系統、裝置驅動程式等），並引入核心運作的基礎概念，如檔案的內部表示（inode）、處理程序的結構（文本、資料、堆疊、u area、區域）、處理程序的狀態與轉換，以及核心資料結構（如處理程序表、檔案表、inode 表）的管理哲學（例如，固定大小的表格和鎖定機制）。
   • 緩衝區快取 (第三章)： 作為檔案子系統的基礎，詳細描述了核心如何使用緩衝區快取來管理磁碟區塊的讀寫，以減少磁碟存取次數並提高效能。闡述了緩衝區標頭（Buffer Header）的結構、緩衝區池（Buffer Pool）的組織方式（雜湊佇列和空閒列表），以及分配和釋放緩衝區的各種情境和演算法（getblk, brelse）。討論了緩衝區快取的優缺點，特別是延遲寫入（Delayed Write）對資料一致性的影響。
   • 檔案的內部表示 (第四章)： 深入檔案系統的內部，解釋了 inode 的結構及其包含的資訊（權限、所有者、時間戳記、磁碟區塊地址等）。詳述了正規檔案如何通過直接和間接區塊來定位資料。描述了目錄的結構（檔名與 inode 編號的對應）以及如何將路徑名稱轉換為 inode（namei 演算法）。介紹了檔案系統的超級區塊（Super Block）及其包含的用於管理空閒 inode 和磁碟區塊的資訊。闡述了分配和釋放 inode (ialloc, ifree) 和磁碟區塊 (alloc, free) 的演算法。
   • 檔案系統的系統呼叫 (第五章)： 建立在檔案系統內部表示的基礎之上，詳細解釋了使用者與檔案系統互動的各種系統呼叫的實現，如 open, close, read, write, lseek, creat, mknod, chdir, chroot, chown, chmod, stat, fstat, pipe, dup, mount, unlink。闡述了這些系統呼叫如何利用底層的內部演算法來操作檔案系統資料結構。引入了檔案鎖定、檔案系統抽象（支援不同檔案系統類型）和檔案系統維護（fsck）等概念。
   • 處理程序的結構與控制 (第六章和第七章)： 深入處理程序子系統。詳細定義了處理程序的上下文（使用者層上下文、暫存器上下文、系統層上下文），並解釋了記憶體管理模型的基礎（區域、頁面、頁表）。描述了核心如何儲存和恢復處理程序的上下文（在中斷、系統呼叫和上下文切換時）。闡述了操作處理程序地址空間的演算法（例如，分配、附加、更改大小、載入、釋放、分離、複製區域）。詳細解釋了處理程序狀態轉換的機制和相應的演算法（sleep, wakeup），以及它們如何用於同步和避免核心資料不一致。在此基礎上，詳述了處理程序控制的系統呼叫實現，如 fork (創建處理程序)、exec (執行新程式)、exit (終止處理程序)、wait (等待處理程序終止)、signal (處理信號)、kill (發送信號)、setpgrp (設置處理程序組)。也解釋了 setuid 機制和 brk 系統呼叫對記憶體大小的影響。最後，簡要介紹了 Shell 和 init 處理程序的結構，說明它們如何利用這些底層系統呼叫來提供使用者環境。
   • 處理程序排程與時間 (第八章)： 探討了多處理程序環境下的 CPU 排程策略，特別是多層次回饋的循環排程。描述了處理程序優先權的計算方式以及 nice 系統呼叫的影響。介紹了與時間相關的系統呼叫（stime, time, times, alarm）以及時鐘中斷處理程序的功能，包括計時、內部核心定時器、效能分析和排程控制。
   • 記憶體管理政策 (第九章)： 深入探討核心管理實體記憶體的策略，包括交換（Swapping）和需求分頁（Demand Paging）。解釋了交換空間的分配、處理程序的換出和換入機制（特別是 fork 和 brk 導致的交換）。描述了需求分頁的資料結構（頁表條目、磁碟區塊描述符、頁框資料表、交換使用計數表）和演算法，包括頁面竊取（Page Stealer）、頁面錯誤處理（有效性錯誤和保護錯誤），以及寫時複製（Copy-on-Write）機制的實現。最後，簡要介紹了交換和需求分頁的混合系統。
   • I/O 子系統 (第十章)： 詳細討論了裝置驅動程式的結構和功能，以及它們與核心和其他系統組件之間的介面。區分了區塊裝置和字元裝置，並解釋了它們各自的裝置開關表。闡述了裝置驅動程式中系統呼叫（open, close, read, write, ioctl）和中斷處理程序的實現方式。以磁碟驅動程式和終端機驅動程式為例，詳述了具體細節，包括磁碟分區、原始介面與區塊介面的區別、終端機的 clist 緩衝機制、規範模式與原始模式、訊號處理以及控制終端機的建立。最後，介紹了 STREAMS 機制，一種更模組化和靈活的裝置驅動程式實現方式。
   • 處理程序間通訊 (第十一章)： 介紹了處理程序間通訊（IPC）的各種形式。首先是處理程序追蹤（ptrace），一種用於偵錯的原始 IPC 形式。然後是 System V IPC 套件，包括訊息佇列、共用記憶體和號誌（Semaphore），描述了它們各自的系統呼叫及其內部實現。最後，簡要介紹了網路通訊的傳統方法和 BSD 的 Sockets 機制，作為 UNIX 系統中支援網路程式設計的介面。
   • 多處理程序系統 (第十二章)： 探討了在具有多個 CPU 的系統上執行 UNIX 核心的挑戰和解決方案。解釋了單處理程序設計中的保護機制如何在多處理程序環境中失效。介紹了兩種主要的設計方法：主從（Master-Slave）處理程序配置，以及使用號誌來保護核心資料結構的方案。討論了這些方案的實現細節和潛在的效能限制。
   • 分散式 UNIX 系統 (第十三章)： 介紹了將多個獨立的 UNIX 機器連接起來以實現資源共享的模型。討論了幾種不同的分散式檔案系統實現方案，包括衛星處理程序系統、Newcastle 連線（在 C 函式庫層實現遠端檔案存取）和透明分散式檔案系統（在核心層實現遠端檔案存取）。比較了這些方案的優缺點、實現複雜度和對使用者透明度的影響。

5. 教學工具： 為了幫助讀者理解這些複雜的概念和演算法，本書使用了多種教學工具：以 C 語言風格的偽碼呈現核心演算法、使用圖形描述資料結構之間的關係、提供小型 C 程式示例來說明使用者層面的概念如何與系統互動，並在每章末尾包含練習題，其難度各異，從簡單的驗證性問題到更具挑戰性的探索性問題。

總之，本書為讀者提供了對 UNIX 作業系統核心內部機制全面、深入的解釋，揭示了其簡潔和優雅的設計哲學如何通過精巧的資料結構和演算法來實現。通過詳細分析每個主要組件（如檔案系統、處理程序控制、記憶體管理、I/O 子系統和 IPC）的內部工作原理及其相互作用，本書旨在使讀者不僅理解「是什麼」（系統呼叫的功能），更能理解「為什麼」和「如何」（核心的實現細節）。