深度探秘

中介軟體底下那層在做什麼

作業系統層的任務

分散式系統的核心是資源共享：client 呼叫另一個節點上的資源，靠的是**中介軟體（middleware）**幫忙跨節點溝通。但中介軟體不是憑空運作的，它底下還有一層——作業系統（OS）。

任何作業系統的任務，就是把底層的實體資源（處理器、記憶體、網路、儲存）包裝成問題導向的抽象。

例如 UNIX、Windows 給你的是檔案而不是磁碟區塊，是 socket 而不是赤裸的網路存取。OS 接管單一節點的硬體，透過 system call 介面把這些好用的抽象端出來。

中介軟體要跑得好，就要求 OS 提供：對實體資源高效又穩固的存取，以及實作各種資源管理政策的彈性。

生活妙喻

網路 OS vs 分散式 OS

兩種截然不同的『管家』

把每台電腦想成一棟房子，作業系統就是房子的管家。

網路作業系統（network OS）——像 UNIX、Windows——是「每棟房子各有一位管家」。你可以透過 NFS 之類的分散式檔案系統透明地存取遠端檔案，也能用 ssh 登入別人家跑程式。但關鍵是：每個節點保有自主，各自管自己的行程，沒人統一指揮。這叫多個系統映像。

分散式作業系統（distributed OS）則像「整個社區只有一位總管」。使用者完全不必管程式在哪裡跑、資源在哪裡。總管掌控所有節點，會自動把新行程丟到最閒的節點。這叫單一系統映像。

現實是：分散式 OS 幾乎沒有普及，大家用的都是網路 OS。

實用超能力

為什麼分散式 OS 沒成功

為什麼大家不用分散式 OS？

兩個很實際的理由：

1. 既有應用的包袱：使用者已經在現有軟體上投入大量心血，不會為了效率就換一個跑不動自己應用的新 OS。模擬舊核心又跑不快、維護成本巨大。
2. 想保有自主：就算在同一個組織裡，大家還是想對自己的機器有掌控權，主要是為了效能。Jones 在寫文件時要好的互動反應，不希望 Smith 的程式把她拖慢。

現實的折衷

flowchart TD
  A[使用者需求] --> B[自主性]
  A --> C[網路透明資源存取]
  B --> D[網路作業系統]
  C --> E[中介軟體]
  D --> F[可接受的平衡]
  E --> F

網路 OS ＋ 中介軟體的組合，剛好在「自主」與「透明存取」之間取得可接受的平衡。

深度探秘

核心的四個管理員

核心 OS 功能

把 OS 核心拆開來看，主要由幾個『管理員』組成，各司其職：

• 行程管理員（Process manager）：建立行程、操作行程。一個行程是資源管理的單位，包含一個位址空間與一或多個執行緒。
• 執行緒管理員（Thread manager）：建立、同步、排程執行緒。執行緒是依附在行程上的可排程活動。
• 通訊管理員（Communication manager）：負責同一台電腦上、不同行程的執行緒之間的通訊；有些 kernel 也支援跨機通訊。
• 記憶體管理員（Memory manager）：管理實體與虛擬記憶體，並支援高效的資料複製與共享。
• 監督程式（Supervisor）：派送中斷、system call 陷阱與例外，控制記憶體管理單元與硬體快取。在 Windows 中稱為硬體抽象層。

為了可攜性，OS 大多用 C、C++ 等高階語言寫成，把機器相依的部分縮到最底層一小塊。

生活妙喻

資源管理者的三條守則

比喻：圖書館的管理規範

把 kernel 與 server 想成圖書館，書籍就是資源。對任何資源管理者，我們至少要求三件事：

1. 封裝（Encapsulation）：提供好用的服務介面。讀者只要說『我要借這本書』，不必知道書放在哪一排、館內怎麼搬運。實作細節（記憶體、裝置管理）對 client 隱藏。
2. 保護（Protection）：資源要防止非法存取。沒有借閱權限的人不能拿走限閱書；應用行程不能亂碰裝置暫存器。
3. 並行處理（Concurrent processing）：多位讀者可同時使用館藏，管理者要做到並行透明——大家同時用，卻像各自獨享。

怎麼存取這些資源？

client 透過**呼叫機制（invocation mechanism）**存取被封裝的資源，例如對 server 物件做 RMI，或對 kernel 做 system call。

實用超能力

呼叫背後要做的兩件事

一次呼叫，背後忙什麼？

當 client 發出一次呼叫，函式庫、kernel 與 server 可能要合力完成兩類『呼叫相關』任務：

• 通訊（Communication）：把操作的參數與結果在資源管理者之間傳來傳去——可能跨網路，也可能在同一台電腦內。
• 排程（Scheduling）：當操作被呼叫時，必須在 kernel 或 server 內安排處理時機。

flowchart TD
  C[Client 發出呼叫] --> COMM[通訊 傳參數與結果]
  C --> SCHED[排程 安排處理時機]
  COMM --> R[資源管理者執行操作]
  SCHED --> R

為什麼這些劃分很重要

本章接下來會看到：把功能放在 kernel 還是使用者層、放在同行程還是不同行程，會直接影響效能與穩固性。理解這四個管理員與三大職責，是看懂後面所有取捨的地基。

深度探秘

什麼叫『非法存取』

兩種非法存取

資源要防止非法存取，而威脅不只來自惡意程式——一個有 bug 的善意程式也可能搞壞整個系統。

以一個只有 read 與 write 操作的檔案為例，保護分成兩個子問題：

1. 權限問題：每個操作只能由有權限的人執行。Smith 擁有讀寫權，Jones 只能讀。若 Jones 想辦法寫了檔案，就是非法存取。（完整解法需要密碼學，留到第 11 章。）
2. 繞過介面問題（本節重點）：行為失常的 client 繞過資源對外公開的操作。例如 Smith 直接動到檔案指標變數，自製一個 setFilePointerRandomly 把指標設成亂數——這是個會破壞檔案正常使用的無意義操作。

怎麼擋住繞過介面？

一種方式是用型別安全語言（如 Sing#、Modula-3）：模組除非持有目標的參照，否則無法存取它，也不能亂造指標、只能做被允許的呼叫。另一種方式是用硬體支援——這就需要一個 kernel。

生活妙喻

兩種權限的鑰匙

比喻：保險箱與管理員

把硬體想成一間放滿貴重物的金庫。

• kernel 是擁有萬能鑰匙的金庫管理員：它從系統啟動就常駐，以完全的存取權限執行，能控制記憶體管理單元、設定處理器暫存器，讓其他人只能用『被允許的方式』碰硬體。
• 大多數處理器有個模式暫存器，決定能不能執行特權指令。kernel 跑在監督模式（privileged）；其他行程則被安排跑在使用者模式（unprivileged）。

位址空間：看不見的隔間牆

kernel 還會替每個行程設好位址空間——一組虛擬記憶體範圍，各自帶著唯讀或讀寫等存取權。

一個行程不能存取自己位址空間以外的記憶體。

這就像每個房客只能進自己的房間，牆把彼此隔開，誰也不能闖進別人或金庫管理員的房間亂翻。

實用超能力

安全進入 kernel 的唯一通道

怎麼安全地請 kernel 幫忙？

當行程跑應用程式碼時，在自己的使用者層位址空間；當它要跑 kernel 程式碼時，必須切到 kernel 的位址空間。切換只能透過例外——例如中斷或 system call 陷阱（trap）。

• system call 陷阱由機器層的 TRAP 指令實作：它把處理器切到監督模式並換到 kernel 位址空間。
• 一旦執行 TRAP，硬體強制處理器去跑 kernel 提供的處理函式，確保沒有行程能偷偷奪取硬體控制權。

flowchart LR
  U[使用者模式行程] -->|TRAP 指令| K[切到監督模式與 kernel 位址空間]
  K --> H[執行 kernel 指定的處理函式]
  H -->|返回| U

保護是要付代價的

切換位址空間要花掉許多處理器週期；system call 陷阱也比單純的函式呼叫昂貴得多。這些代價會在後面的呼叫成本分析中反覆出現——安全不是免費的。

深度探秘

行程＝執行環境＋執行緒

為什麼傳統行程不夠用

1980 年代發現：傳統那種『只跑單一活動』的行程，無法滿足分散式系統與需要內部並行的應用。問題在於——傳統行程讓相關活動之間的共享變得笨拙又昂貴。

解法是把行程的概念升級，讓它能對應多個活動。於是現代的行程由兩部分組成：

行程 ＝ 一個執行環境（execution environment） ＋ 一或多個執行緒（thread）。

• 執行緒是 OS 對『一個活動』的抽象（源自 thread of execution，執行的線）。
• 執行環境是資源管理的單位：一組由 kernel 管理的本地資源，主要包含：
  • 一個位址空間；
  • 執行緒同步與通訊資源（如 semaphore、socket）；
  • 更高階的資源（如開啟的檔案、視窗）。

執行環境建立與管理成本高，但多個執行緒可以共享它——也就是共享其中所有可存取的資源。換句話說，執行環境就是其中執行緒執行的保護領域。

生活妙喻

罐子裡的蒼蠅

比喻：一只蓋緊的罐子

這是 USENET 上一個有名（雖然有點噁）的比喻：

• 執行環境＝一只蓋緊的玻璃罐，加上裡頭的空氣與食物（資源）。
• 執行緒＝罐子裡的蒼蠅。

一開始罐裡有一隻蒼蠅。牠可以生出更多蒼蠅、也能殺掉牠們，子孫亦然。任何蒼蠅都能消耗罐裡的任何資源（空氣或食物）。

• 蒼蠅們可以排好隊有秩序地取用資源；要是沒這紀律，就會在罐裡互撞——也就是當牠們胡亂搶用同一資源時，產生不可預測的結果。
• 蒼蠅能對別的罐子裡的蒼蠅送訊息，但沒有蒼蠅能逃出罐子，外面的也進不來。

在這個比喻裡，最早的 UNIX 行程就是『一只罐子裡只有一隻不孕的蒼蠅』——單執行緒。

實用超能力

位址空間的區域與共享

位址空間長什麼樣

位址空間是行程虛擬記憶體的管理單位，很大（常見 2^32，甚至 2^64 位元組），由一或多個**區域（region）**組成，區域之間隔著不可存取的空隙、彼此不重疊。每個區域有：

• 範圍（最低虛擬位址與大小）；
• 讀／寫／執行權限；
• 能否向上或向下成長。

經典的 UNIX 位址空間有三區：text（程式碼，唯讀不可改）、heap（堆積，向高位址長）、stack（堆疊，向低位址長）。

為什麼要『不限數量的區域』？

• 每個執行緒要各自的 stack，方便偵測堆疊溢位。
• 把檔案映射進記憶體（mapped file），當成位元組陣列存取。
• 共享記憶體區域：背後是同一塊實體記憶體，可被多個位址空間共用。

共享區域的三大用途

深度探秘

建立行程的兩件事

建立新行程＝兩件獨立的事

傳統上建立行程是 OS 提供的不可分割操作（如 UNIX 的 fork 複製一個行程、exec 把自己換成某程式）。但在分散式系統裡，因為要用到多台電腦，建立行程被拆成兩個獨立面向：

1. 選擇目標主機：新行程要落在哪個節點？例如從一群當作運算伺服器的叢集中挑一台。這是行程配置決策，屬於政策問題。
2. 建立執行環境（以及裡頭的初始執行緒）。

選主機的政策光譜很廣：從『一律在發起者的工作站跑』到『把負載分散到一群電腦』。Eager 等人把**負載分享（load sharing）**分成兩類政策：

• 轉移政策（transfer policy）：決定新行程要放本地還是遠端，例如看本地節點是輕載還是重載。
• 位置政策（location policy）：一旦決定要轉移，挑哪個節點來放，可能看各節點相對負載、機器架構或特殊資源。

選主機對程式設計師與使用者都是透明的。

生活妙喻

餐廳帶位的各種策略

比喻：餐廳怎麼帶位

把『把新行程放到哪個節點』想成餐廳『帶客人入座』。帶位策略可以這樣分類：

• 靜態 vs 適應（static vs adaptive）：
  • 靜態＝按事先設計好的規則，不看現場狀況（例如『A 桌的客人一律帶去 B 區』，或隨機帶去 B–E 區）。
  • 適應＝看現場即時狀況（哪一區比較空）用啟發法決定。
• 集中 / 階層 / 分散：
  • 集中＝只有一位領班統一帶位。
  • 階層＝多位領班排成樹狀，盡量在低層就近決定。
  • 分散＝各區服務生彼此交換資訊自己決定。Spawn 系統甚至把節點當成資源的『買方』與『賣方』，搞成市場經濟。
• 送方發起 vs 收方發起：
  • 送方發起＝自己太忙（超過門檻）就主動把客人送出去。
  • 收方發起＝自己太閒就對外廣告『我這裡有空位』，讓忙的地方把工作丟過來。

實用超能力

行程遷移與簡單至上

不只在建立時搬

遷移式（migratory）負載分享系統可以在任何時候搬動負載，而不只在建立行程時。它用的是行程遷移（process migration）：把一個正在執行的行程從一個節點搬到另一個節點。

flowchart TD
  A[負載分享系統] --> B[非遷移式 只在建立時決定主機]
  A --> C[遷移式 任何時候都能搬]
  C --> D[行程遷移 搬移執行中的行程]
  D --> E[昂貴且難以普及]

為什麼行程遷移沒普及

雖然有人做出來，但很少實際部署。主因是成本高，而且要從 kernel 內部抽取一個執行中行程的狀態搬到別處，極為困難。

一個重要結論：簡單至上

Eager 等人研究三種負載分享方法後得到一個關鍵啟示：

簡單是任何負載分享方案的重要特質。

因為太複雜的方案，光是收集狀態的開銷就可能抵銷它帶來的好處。寧可簡單有效，也不要複雜得划不來。

深度探秘

繼承位址空間的兩種方式

新行程的位址空間怎麼初始化

選好主機後，新行程需要一個內容已初始化的位址空間。有兩種做法：

1. 靜態定義：位址空間格式固定（例如就是 text + heap + stack），依清單建立區域，從可執行檔載入內容或填零。
2. 參照既有執行環境：以 UNIX fork 為例，子行程實體共享父行程的 text 區域，而 heap 與 stack 則是父行程的副本（範圍與初始內容都一樣）。

這個概念被一般化：父行程的每個區域都可以被子行程繼承或省略；繼承的區域可以是與父共享，或邏輯上從父複製。

問題來了：複製很貴

如果『邏輯上複製』真的把每一頁都立刻一頁一頁實體複製，會非常浪費——很多頁可能根本不會被改到。Mach、Chorus 等系統用了一個漂亮的優化：copy-on-write（寫入時才複製）。

生活妙喻

先共用一份文件，誰要改才印副本

比喻：辦公室的共用文件

主管把一份報告『複製』給兩位同事 A 和 B。

• 笨方法：立刻印兩份完整副本。但如果 B 整份都沒改，那份副本就白印了。
• 聰明方法（copy-on-write）：先讓兩人看同一份正本，但貼上『唯讀』標籤。
  • 只要兩人都只是看，就一直共用，半張紙都不必多印。
  • 等到 B 真的要改某一頁時，才針對那一頁印一份副本給 B 改，其他沒改的頁仍共用。

這就是 copy-on-write 的精神：複製是『邏輯上』先成立，實體複製延遲到真正寫入的那一刻、而且只複製被改的那一頁。

實用超能力

page fault 觸發複製的流程

它在硬體層怎麼運作

假設區域 RA（行程 A）被『複製繼承』成行程 B 的 RB：

1. 一開始兩行程的頁表都指向同一批共享頁框，且這些頁在硬體層被設成唯讀（即使邏輯上可寫）。
2. 若任一行程想修改資料，硬體會丟出一個**page fault（頁錯誤）**例外。假設是 B 要寫。
3. page fault 處理函式替 B 配置一個新頁框，把原頁框的資料逐位元組複製過去。
4. 在其中一個行程的頁表把舊頁框號換成新頁框號（哪個都行），另一個保留舊的。
5. 兩個對應頁都在硬體層重新設為可寫，然後讓 B 的那條修改指令繼續執行。

flowchart TD
  A[兩行程共享頁框 設為唯讀] --> B[B 嘗試寫入]
  B --> C[硬體觸發 page fault]
  C --> D[配置新頁框並複製內容]
  D --> E[更新頁表 兩頁設回可寫]
  E --> F[B 的寫入繼續執行]

不只用在 fork

copy-on-write 是通用技術：複製大訊息時也會用到它，避免無謂的整塊複製。

深度探秘

用一個算式看懂多執行緒的威力

為什麼伺服器要多執行緒

多執行緒的核心目的，是最大化操作之間的並行，讓計算與 I/O 重疊，並能在多處理器上並行運算。對伺服器尤其有用：一個執行緒在等磁碟時，另一個可以繼續服務別的請求，避免伺服器變成瓶頸。

一個經典推演

假設每個請求平均要 2 毫秒處理 ＋ 8 毫秒 I/O（讀磁碟、無快取），且跑在單處理器上：

• 單執行緒：每個請求週轉時間 2+8＝10 毫秒，最多 100 req/s。
• 兩執行緒：一個等 I/O 時另一個處理，吞吐提升。但若都卡在單一磁碟（每次 I/O 8 毫秒且序列化），上限變成 1000/8＝125 req/s。
• 加入磁碟快取（75% 命中）：平均 I/O 降到約 2 毫秒，理論上限升到 500 req/s；但若快取讓處理時間升到 2.5 毫秒，受處理器限制變成 1000/2.5＝400 req/s。
• 改用雙處理器紓解處理器瓶頸：兩執行緒可達 444 req/s，三個以上受 I/O 限制達 500 req/s。

生活妙喻

一個店員 vs 多個店員

比喻：飲料店的店員

把伺服器想成飲料店，請求是客人，處理＝結帳，I/O＝去後場等珍珠煮好。

• 單店員：結完帳就傻站著等珍珠煮好，等完才能服務下一位。客人大排長龍。
• 多店員（多執行緒）：A 店員去等珍珠時，B 店員馬上服務下一位。等待時間被重疊起來，整體出杯速度大增。
• 但只有一台煮珍珠的鍋（單磁碟）：再多店員也得排隊用鍋，瓶頸卡在鍋子上。
• 裝個保溫櫃放現成珍珠（快取）：多數時候直接拿，不用等鍋，速度又上一層。
• 再加一台收銀機（多處理器）：連結帳都能同時做，瓶頸再被推開。

重點：瓶頸會移動——從磁碟到處理器；解一個瓶頸，下一個就浮現。

實用超能力

client 端也能多執行緒

不只伺服器，client 也受益

執行緒對 client 同樣有用：

• 一個 client 執行緒不斷產生要送出的結果，另一個執行緒負責做 RMI／RPC。即使遠端呼叫會阻塞呼叫者，第一個執行緒仍能繼續算下一批結果，把結果放進緩衝區，直到緩衝區滿才被擋。
• 網頁瀏覽器是最好的例子：抓網頁常常很慢，瀏覽器必須同時處理多個網頁／圖片請求，使用者才不會卡在那裡乾等。

flowchart LR
  T1[執行緒一 持續產生結果] --> BUF[緩衝區]
  BUF --> T2[執行緒二 做遠端呼叫]
  T2 --> S[伺服器]

重點回顧

多執行緒不是萬靈丹，而是把等待時間變成有用時間的關鍵手段。

深度探秘

四種把請求對應到執行緒的方式

怎麼把『請求』分配給『執行緒』

Schmidt 整理 CORBA ORB 的執行緒架構，這些模式適用於各種伺服器。主要有四種：

1. Worker pool（工作者池）：伺服器啟動時建立固定的一池 worker 執行緒。一個 I/O 執行緒從各 socket 收請求、丟進共享請求佇列，worker 們從佇列取出處理。可加多佇列支援不同優先權。
2. Thread-per-request（每請求一執行緒）：I/O 執行緒為每個請求生一個 worker，處理完即自我銷毀。
3. Thread-per-connection（每連線一執行緒）：client 建連線時建一個 worker，連線關閉時銷毀；期間該連線的多個請求都由它處理。
4. Thread-per-object（每物件一執行緒）：每個遠端物件配一個執行緒，搭配每物件佇列。

每種模式在吞吐量、建立成本、佇列競爭、負載均衡之間有不同取捨。

生活妙喻

餐廳的四種人力配置

比喻：餐廳怎麼安排服務生

• Worker pool：固定請 5 位服務生，所有點單丟進一張共用待辦清單，誰有空誰接。
  • 缺點：人數固定，尖峰時 5 人不夠用；而且大家搶同一張清單，爭用頻繁。
• Thread-per-request：每來一張點單就臨時叫一位工讀生處理，做完就讓他下班。
  • 優點：沒人搶清單，吞吐潛力大。缺點：一直叫人、遣散，人事成本高。
• Thread-per-connection：每來一桌客人配一位專屬服務生，這桌點幾道都他負責，客人走了他才下班。
• Thread-per-object：每道招牌菜配一位專師傅，點到那道就排他的隊。

per-connection 與 per-object 的人事成本比 per-request 低，但可能出現『某位服務生忙翻、另一位閒著』的負載不均。

實用超能力

怎麼選？看你的取捨

取捨總表

flowchart TD
  IO[I/O 執行緒收請求] --> Q[共享請求佇列]
  Q --> W1[Worker 一]
  Q --> W2[Worker 二]
  Q --> W3[Worker 三]

實務建議

• 請求短而量大、想避免建立成本 → 偏好 worker pool。
• 請求處理很重、希望吞吐拉滿且能容忍建立成本 → thread-per-request。
• 連線長且互動多 → thread-per-connection。
• 不同遠端物件負載差異大 → 視情況用 per-object，但小心忙閒不均。

Schmidt 還討論了這些架構的混合版；下一節的 LRPC 則是另一種『client 執行緒直接進 server』的模型。

深度探秘

同樣能重疊，為什麼偏好執行緒

多執行緒 vs 多行程

你可能會問：用多個單執行緒行程也能達到計算與 I/O 重疊，何必用多執行緒？答案有兩點：

1. 執行緒建立與管理比行程便宜；
2. 執行緒間共享資源比行程間更有效率，因為它們共享同一個執行環境。

比較兩者的狀態：

• 執行環境有：位址空間表、通訊介面與開啟的檔案、semaphore 等同步物件、所屬執行緒清單。
• 執行緒有：排程優先權、執行狀態（如 BLOCKED、RUNNABLE）、BLOCKED 時保存的處理器暫存器、軟體中斷處理資訊、所屬執行環境的識別碼。

四點總結：

• 在既有行程內建新執行緒，比建一個行程便宜。
• 更重要的是：在同行程內切換執行緒，比在不同行程的執行緒間切換便宜。
• 同行程的執行緒能方便高效地共享資料與資源。
• 但代價是：同行程的執行緒彼此不受保護。

生活妙喻

同間辦公室 vs 不同公司

比喻：同事 vs 外部廠商

• 同行程的多執行緒＝同一間辦公室的同事：
  • 多請一位同事（建執行緒）很快、很便宜。
  • 大家共用同一批檔案櫃與白板（共享資源），交接資料只要指一下白板，不必寄信。
  • 換人接手（切換執行緒）只要轉個椅子，幾乎沒成本。
  • 但：大家在同一空間，一個人亂改白板會害到別人——彼此不受保護。
• 多個行程＝不同公司：
  • 開一間新公司（建行程）手續繁瑣昂貴。
  • 要交換資料得正式寄信（訊息傳遞），慢。
  • 但各公司有自己的門禁，互相保護，一家出包不會直接弄壞另一家。

數字感受

Anderson 等人在某架構上量到：建一個 UNIX 行程約 11 毫秒，建一個執行緒約 1 毫秒——差了約十倍。

實用超能力

context switch 與快取的隱形成本

切換成本：最關鍵的開銷

切換之所以重要，是因為一條執行緒一生會切換很多次。

• 處理器情境（context）＝處理器暫存器（如 program counter）＋當前硬體保護領域（位址空間與處理器保護模式）。
• context switch＝切換情境時保存舊暫存器、載入新暫存器；有時還要轉換保護領域（domain transition）。

aliasing 問題：為什麼跨行程更貴

記憶體管理單元有個 TLB 快取加速虛擬→實體位址轉換。但同一個虛擬位址在不同位址空間可能指向不同實體資料（aliasing 問題）。除非快取項目用情境識別碼標記，否則切換到不同位址空間時，TLB 與快取必須清空（flush）——這就是跨行程切換昂貴的隱形成本。

深度探秘

執行緒生命週期與同步基本功

Java 執行緒的一生

執行緒程式設計就是並行程式設計，會用到幾個核心概念：競爭條件（race condition）、臨界區間（critical section）、monitor、條件變數、semaphore。

Java 執行緒在同一個 JVM 上建立，初始為 SUSPENDED；呼叫 start() 變成 RUNNABLE 後開始跑物件的 run() 方法。執行緒可設優先權，支援優先權的實作會優先跑高優先權者。執行緒從 run() 返回或被 destroy() 時結束生命。

為什麼需要同步

每條執行緒的區域變數是私有的（各有私有 stack），但靜態變數與物件實例變數不是私有的——大家共享。

回想前面 I/O 與 worker 共用的請求佇列：若多執行緒同時亂動佇列的指標，可能發生競爭條件，導致請求遺失或重複。所以必須協調。

生活妙喻

只有一把鑰匙的更衣室

比喻：更衣室與排隊牌

synchronized（monitor）＝一間只有一把鑰匙的更衣室：

• 你把 Queue 的 addTo()、removeFrom() 標成 synchronized，就等於規定『同一時間最多一人能進這間更衣室』。其他人想進就得在外面等，於是對佇列的操作自動互斥，不會撞在一起。

wait() / notify()＝叫號等待機制：

• worker 發現沒請求可做，就呼叫佇列的 wait()，乖乖去旁邊睡（阻塞並讓出鑰匙）。
• I/O 執行緒放進一個新請求後，呼叫 notify() 把一位 worker 叫醒回來搶鑰匙。notifyAll() 則叫醒全部。

sequenceDiagram
  participant W as Worker 執行緒
  participant Q as Queue 物件
  participant IO as I O 執行緒
  W->>Q: 沒事做 呼叫 wait 去睡
  IO->>Q: 放入新請求
  IO->>Q: 呼叫 notify
  Q-->>W: 叫醒 W 回來處理

注意：Java 物件的 monitor 只有一個隱含的條件變數，一般 monitor 可有多個。

實用超能力

搶占式 vs 非搶占式排程

兩種排程哲學

• 搶占式（preemptive）：執行緒隨時可能被暫停讓位給別人，即使它還想繼續跑。
• 非搶占式（non-preemptive，又稱 coroutine）：執行緒一直跑，直到它主動呼叫排程系統（如 system call）才可能被換下。

與群組／優先權

Java 還能把執行緒分群組：預設一群的執行緒不能管理另一群（安全用途），瀏覽器、伺服器藉此限制 applet／servlet 執行緒的最高優先權，且 applet 無法用 setPriority() 覆蓋管理者設的群組優先權上限。

同步原語還有 join()（等目標執行緒結束）與 interrupt()（提早喚醒等待中的執行緒）。

深度探秘

誰來排程執行緒

兩種執行緒實作

關鍵問題是：誰知道、誰排程這些執行緒？

• 核心層執行緒（kernel-level）：kernel 原生支援多執行緒，提供建立／管理的 system call，並獨立排程每條執行緒。Windows、Linux、Solaris、Mach、Mac OS X 都是這類。
• 使用者層執行緒（user-level）：有些 kernel 只有單執行緒行程抽象，多執行緒得靠連結到應用程式的函式庫實作。kernel 根本不知道這些執行緒，也無法獨立排程它們。由一個執行緒執行期函式庫自己排程，並利用 kernel 的非阻塞 I/O 與計時器來分時。

使用者層的兩大痛點

當 kernel 不支援多執行緒時，純使用者層實作有幾個問題：

• 行程內的執行緒無法利用多處理器。
• 一條執行緒若觸發 page fault，會阻塞整個行程與其中所有執行緒。
• 不同行程的執行緒無法用單一的相對優先權方案統一排程。

生活妙喻

公司自己排班 vs 總公司排班

比喻：誰幫你排班

• 使用者層執行緒＝部門自己排班：
  • 好處：排班很有彈性、可依部門需求客製，調動同部門人員（切換執行緒）不必跑去總公司報備（不需 system call），很便宜；還能養比總公司願意配給的更多人手。
  • 壞處：總公司（kernel）根本不知道你部門有幾個人。一旦有一人去總公司辦事卡住（page fault／阻塞系統呼叫），總公司以為整個部門都停擺，全員被擋；而且部門間無法用統一標準排優先順序，也用不到多個分公司（多處理器）。
• 核心層執行緒＝總公司統一排班：每個人總公司都認得、能獨立調度，能分派到不同分公司（多處理器），但每次調動都要報備，較貴。

各自優勢一覽

實用超能力

Scheduler activations：兩全其美

能不能兩全其美？

可以，用混合式設計。Solaris 用階層式排程（使用者層執行緒映射到 kernel 的『輕量行程』），但若一條阻塞在 kernel，映射上去的使用者層執行緒也全被擋——仍不夠彈性。

**Scheduler activations（排程器活化）**更進一步。關鍵洞見：使用者層排程器要的不只是『一組可映射的 kernel 執行緒』，還需要 kernel 通知它與排程相關的事件。

• kernel 負責配虛擬處理器給各行程；數量可隨需求增減。
• **scheduler activation（SA）**是 kernel 對行程的一次呼叫，通知其排程器某事件發生——這種『從下層 kernel 進入上層程式碼』叫 upcall。
• kernel 會通知四類事件：虛擬處理器已配置、SA 阻塞、SA 解除阻塞、SA 被搶占。使用者層排程器據此把 READY 執行緒分派給目前在跑的 SA。

flowchart TD
  K[Kernel 配虛擬處理器] -->|upcall 通知事件| US[使用者層排程器]
  US -->|把 READY 執行緒指派給 SA| RUN[執行]
  US -->|P idle 或 P needed| K

它彈性（政策全在使用者層，kernel 只送事件）又高效（只要有虛擬處理器可跑，就沒有 READY 執行緒會空等）。

深度探秘

kernel 該提供多高階的通訊

呼叫與通訊

本節聚焦在呼叫（invocation）背後的通訊。呼叫是一種構造（如 RMI、RPC、事件通知），目的是讓另一個位址空間的資源執行某操作。我們問四個關於 OS 的問題：提供哪些通訊原語？支援哪些協定、開放程度如何？怎麼讓通訊盡量有效率？怎麼支援高延遲與斷線操作？本節先談前兩個。

通訊原語放哪裡

有些為分散式系統設計的 kernel 提供量身打造的原語。Amoeba 提供 doOperation、getRequest、sendReply，並支援群組通訊。

把高階通訊功能放進 kernel 的好處是效率。

例如中介軟體若用 TCP socket 做 RMI，每次遠端呼叫要做兩次通訊 system call（socket 的寫與讀）；在 Amoeba 上只需一次 doOperation。群組通訊省下的更多。

但實務上，多數高階通訊（RPC/RMI、事件通知、群組通訊）是由中介軟體而非 kernel 提供，因為在使用者層開發這類複雜軟體比在 kernel 簡單得多。

生活妙喻

通用插座 vs 客製專線

比喻：為什麼大家用 socket

中介軟體大多建在 socket 上（多用 TCP，有時用 UDP），主要理由是可攜性與互通性：

• 想像 socket 是各國通用的萬國插座。UNIX、Windows 都提供相似的 socket API，能接上 TCP/UDP。中介軟體要在盡可能多的 OS 上跑，用通用插座最保險。
• 1980 年代有些研究 kernel 自製了調校過的 RPC 專用協定（Amoeba RPC、VMTP、Sprite RPC），就像客製專線——效率好，但只在自家研究環境通用，走不出去。

所以 Mach 3.0、Chorus、L4 等 kernel 乾脆完全開放協定選擇：kernel 只負責本地行程間的訊息傳遞，把網路協定處理交給上層的 server。

因為大家天天要上網，TCP/UDP 相容性對幾乎所有連網裝置都是必備的。

實用超能力

靜態安裝 vs 動態組合協定

還要能接納新協定

OS 不只要支援 TCP/UDP，還得讓中介軟體能用上新的低階協定——例如紅外線（IrDA）、藍牙、IEEE 802.11，而且最好不必改應用程式。

協定通常排成層的堆疊。整合新層有兩種做法：

• 靜態整合：把某層（如 IrDA）當成永久安裝的協定驅動程式。
• 動態協定組合（dynamic protocol composition）：協定堆疊可即時拼裝，配合應用需求與當前可用的實體連線。

flowchart TD
  APP[應用需求與當前連線] --> DC[動態協定組合]
  DC --> S1[選用無線層或乙太層]
  DC --> S2[選用客製請求回覆協定]

真實情境

• 筆電在路上用廣域無線，回辦公室自動切到更快的乙太或 802.11。
• 在無線層上用客製的請求-回覆協定減少來回延遲——因為標準 TCP 在易丟封包的無線媒介上表現不佳。

支援協定組合的例子有 UNIX Streams、Horus、x-kernel，以及較新的 Cactus 上的 CTP。

深度探秘

軟體開銷常大於網路傳輸

為什麼呼叫效能這麼重要

設計者把功能分散到越多位址空間，需要的遠端呼叫就越多。client 與 server 一生可能做數百萬次呼叫，所以零點幾毫秒都很要緊。

null RPC 揭露的真相

null RPC＝沒有參數、執行空程序、不回傳值的 RPC，只交換系統資料、沒有使用者資料。在 LAN 上，一次 null RPC 約十分之一毫秒；而一次本機空函式呼叫只要不到一微秒。

一次 null RPC 約傳 100 位元組，以 100 Mbps 計算，純網路傳輸只要約 0.01 毫秒。但實測延遲遠大於此——

大部分延遲其實來自作業系統 kernel 與使用者層 RPC 執行期程式碼的動作，而非網路本身。

這是 LAN／intranet 的情況。網際網路則相反：延遲高且變動大、吞吐低、伺服器負載常主導。書中舉例：跨美國地理區的 UDP 來回約 400 毫秒，而同樣電腦在單一乙太網路上只要約 0.1 毫秒。

生活妙喻

寄一個包裹的隱形工序

比喻：寄包裹的隱藏成本

你以為寄包裹的時間都花在『運送途中』，其實大半花在打包與處理：

• Marshalling（封送）＝把要寄的東西打包、轉換格式裝箱。資料越多，打包與拆包越花時間。
• 資料複製（data copying）＝包裹在過程中被搬來搬去好幾趟：使用者↔kernel 邊界一趟、每經一個協定層一趟、網路介面↔kernel 緩衝區一趟（這趟常由 DMA 代勞）。
• 封包初始化（packet initialization）＝貼標籤、填寄件資訊、算檢查碼，成本部分與資料量成正比。
• 執行緒排程與情境切換＝換不同窗口辦理：RPC 過程做多次 system call（即多次情境切換），還要排程 server 執行緒；若有獨立網路管理行程，每次 Send 又多一次切換。
• 等待確認（acknowledgement）＝等簽收回條，大量資料時尤其影響延遲。

flowchart LR
  M[封送打包] --> C[多次資料複製]
  C --> P[封包初始化貼標]
  P --> SCH[排程與情境切換]
  SCH --> ACK[等待確認]

實用超能力

延遲、吞吐量與共享記憶體

延遲 vs 吞吐量

• 延遲（latency）：null 呼叫成本衡量的是固定開銷。即使加大參數，這個固定延遲仍常佔可觀比例。
• 吞吐量（throughput／頻寬）：單次 RPC 傳大量資料時的傳輸速率。資料量小時固定開銷主導、吞吐低；資料量增大，固定開銷被攤薄、吞吐上升。

當請求資料量超過一個封包大小門檻，就得多送封包（可能還多一個確認封包），延遲圖會出現跳階。

OS 能怎麼幫忙

• 適當的執行緒支援可減少多執行緒開銷（前面已談）。
• 記憶體共享可大幅減少複製成本：用共享區域在使用者行程與 kernel、或行程之間直接讀寫，資料不必複製進出 kernel 位址空間。但同步時仍需 system call 或軟體中斷，且共享區域要用得夠多才划得來。
• 更激進的 U-Net 架構甚至讓使用者層程式直接存取網路介面，把資料送上網路而完全不複製。

深度探秘

其實大多數呼叫發生在同一台機器

一個出乎意料的事實

Bershad 等人的研究發現：在他們觀察的安裝中，大多數跨位址空間呼叫其實發生在同一台電腦內，而不是想當然的跨機 client-server。

為什麼？因為服務功能越來越被放進使用者層 server，而且快取被積極使用——client 要的資料常就在本機 server裡。於是『本機 RPC』的成本越來越重要，值得特別優化。

傳統做法的問題

傳統把同機的跨位址空間呼叫，當成跟跨機一模一樣處理，只是底層訊息傳遞剛好在本機發生。這其實很浪費。Bershad 等人為此設計了 LRPC（lightweight RPC，輕量級 RPC），針對兩個地方優化：資料複製與執行緒排程。

生活妙喻

共用桌面 vs 反覆轉抄

比喻：兩部門怎麼交件

假設 client 與 server 是同一棟樓的兩個部門。

傳統 RPC（即使在本機）＝即便在隔壁，也照跨城市流程走：把文件抄四次——

1. client stub 的桌面 → 訊息；2. 訊息 → kernel 緩衝；3. kernel 緩衝 → server 訊息；4. 訊息 → server stub 的桌面。

LRPC＝在兩部門之間放一張共用辦公桌（A stack）：

• client 與 server 共用一塊私有的共享記憶體區域，裡頭有一或多個 A（argument）stack。
• 參數與回傳值直接放在 A stack 上傳遞，client 與 server 的 stub 共用同一個 stack。
• 於是參數只複製一次（封送到 A stack 時），相較傳統 RPC 的四次，省很多。

每個本機 client 與 server 之間用**各自獨立（私有）**的區域，且一個區域可有多個 A stack，因為同一 client 的多個執行緒可能同時呼叫 server。

實用超能力

讓 client 執行緒直接進 server

第二招：省下執行緒排程

回想 system call：多數 kernel 不會另排新執行緒，而是讓呼叫者自己的執行緒做情境切換去處理。但傳統 RPC 因為遠端程序可能在別台機器，得排一條不同的執行緒去跑。

本機情況下，更有效率的做法是：讓原本會被 BLOCKED 的 client 執行緒，直接進入 server 的位址空間去呼叫那個程序。

server 因此要寫得不一樣：它不是先建好執行緒在 port 上聽，而是匯出一組可被呼叫的程序。本機行程的執行緒只要先呼叫 server 匯出的程序，就能進入 server 的執行環境。

一次 LRPC 的步驟

sequenceDiagram
  participant C as Client 與 stub
  participant K as Kernel
  participant S as Server
  C->>C: 把參數複製到 A stack
  C->>K: trap 到 kernel 並出示 capability
  K->>S: 驗證後 upcall 切換情境進 server
  S->>S: 執行程序 並把結果寫回 A stack
  S->>C: 返回 經由 trap 切回 client

它有多好、代價是什麼

• Bershad 等人實測：LRPC 延遲約是本機執行 RPC 的三分之一。
• 位置透明性不犧牲：client stub 在 bind 時看一個位元決定 server 是本機或遠端，自動選 LRPC 或 RPC，應用無感。
• 但遷移透明性可能較難：資源從本機 server 搬到遠端（或反之）時，得換呼叫機制。
• 前提：呼叫要夠多，才能攤平設定共享記憶體的成本。

深度探秘

高延遲與斷線的世界

OS 幫得了的、幫不了的

前面看到 OS 能幫中介軟體把遠端呼叫做得有效率。但在網際網路環境，高延遲、低吞吐、高伺服器負載，常蓋過 OS 能提供的好處。再加上斷線與重連——可視為延遲極高的通訊（行動裝置進隧道就斷線）。

對付高延遲的招式：非同步操作

**非同步操作（asynchronous operation）**有兩種程式模型，主要屬於中介軟體領域：

1. 並行呼叫（concurrent invocations）：中介軟體只提供阻塞式呼叫，但應用開多個執行緒同時做多個阻塞呼叫。
2. 非同步呼叫（asynchronous invocations）：呼叫本身非阻塞，送出請求訊息就立刻返回。

這兩種模型把『等待』的時間重疊或藏起來，正是對抗高延遲的核心思路。

生活妙喻

一次點多杯 vs 領餐取餐單

比喻：飲料店點餐

並行呼叫＝一次把多杯一起點：

• 序列做法：點第一杯→站著等做好→拿到→才點第二杯。慢。
• 並行做法：第一個執行緒點第一杯後，第二個執行緒馬上點第二杯，各自等各自的。總時間明顯縮短。瀏覽器抓一頁多張圖正是這樣——不必按順序拿，同時發多個請求。

非同步呼叫＝拿到一張取餐單（promise）：

• 你點完餐立刻離開櫃台（非阻塞返回），手上拿著一張取餐單。
• 餐好了，系統把結果放進這張單對應的位置。
• 你之後用 claim 去取餐：若還沒好就在那等（阻塞）；也能先用 ready 問一聲『好了沒？』（不阻塞，回 true/false）。
• 有時根本不需回應（如 CORBA oneway，maybe 語意）。

flowchart LR
  CALL[非同步呼叫] --> PR[立即拿到 promise]
  PR --> READY[ready 問好了沒]
  PR --> CLAIM[claim 取結果 可能阻塞]

實用超能力

斷線也不怕：持久非同步呼叫

傳統非同步呼叫的弱點

Mercury、CORBA oneway 這類傳統非同步呼叫建在 TCP 串流上，串流一斷（網路掛掉或目標當機）就失敗。它們設計成『逾時幾次後就放棄』，但在斷線或極高延遲時，這種短期逾時並不合適。

持久非同步呼叫（persistent asynchronous invocation）

程式操作和 Mercury 類似，差別在失效語意：

系統會無限期地持續嘗試，直到確定成功、確定失敗，或被應用取消。

典型例子是 Rover 工具箱的 Queued RPC（QRPC）：

• 沒連線時，把外送的呼叫請求排進穩定的記錄檔（log）；有連線時再排程送出。
• 同樣把回傳結果排進 client 的『信箱』，等 client 重連再領。
• 排隊時可壓縮請求與結果，省低頻寬。
• 可用不同連線送請求與收回覆（去程用行動數據、回程用乙太）。
• 排程不一定 FIFO：應用可設優先權，連線出現時先送高優先權的；慢又貴的連線可能先不送、等更快更便宜的連線。

代價：使用者在結果未知前繼續操作，可能產生衝突更新等問題（留到第 18 章）。

深度探秘

什麼該放進 kernel

從開放性出發

一個開放的分散式系統應該能夠：只在每台電腦跑它角色所需的系統軟體（別載入冗餘模組浪費記憶體）；讓任一服務的實作能獨立替換；提供同一服務的不同替代版本；以及在不傷害既有服務下引入新服務。

核心設計的長期指導原則是：把固定的資源管理機制（mechanism），與隨應用而異的資源管理政策（policy）分開。理想上，kernel 只提供最基本的機制，server 模組則按需動態載入來實作政策。

兩大設計

核心設計有兩個關鍵範例：單體核心（monolithic）與微核心（microkernel）。差別主要在於——哪些功能放進 kernel，哪些留給可動態載入的 server 行程。

生活妙喻

巨石 vs 樂高

比喻：兩種蓋房子的方式

單體核心＝一塊巨大的整石（monolith）：

• 字典定義 monolith 是『單一石柱；龐大、不可分割』。UNIX kernel 就被稱為單體——它執行所有基本 OS 功能，達數 MB 程式碼，而且非模組化地寫在一起，導致難以更動：要改一個元件來適應新需求很困難。
• 它的 kernel 位址空間內可含一些 server 行程（如檔案伺服器、部分網路功能），這些都是標準 kernel 配置的一部分。

微核心＝一盒樂高積木：

• kernel 只提供最基本抽象：位址空間、執行緒、本地行程間通訊。
• 其他所有系統服務都由動態載入的 server提供——而且只載到分散式系統中真正需要它的那些電腦上。
• client 透過 kernel 的訊息式呼叫機制存取這些服務。

flowchart TD
  subgraph 單體核心
  M[kernel 含 S1 S2 S3 S4 全包在內]
  end
  subgraph 微核心
  K[微核心 只有基本機制]
  K --> A[S1 server]
  K --> B[S2 server]
  K --> C[S3 server]
  end

實用超能力

各自的優缺點與折衷

比較

折衷與後續

• 單體核心的『無結構』可用軟體工程手法緩解：分層（MULTICS）、物件導向（Choices）；Windows 兩者並用，但仍『龐大』且多數功能無法常態替換。
• 微核心設計者另一目標是二進位模擬標準 OS（如在 Mach 上跑 UNIX 與 OS/2），同平台可呈現多個 OS 介面。注意：OS 模擬不同於機器虛擬化（下節）。
• 有些後續設計（SPIN 用型別安全語言、Nemesis／Exokernel／L4）想用更聰明的方式兼顧效率與保護。

一位微核心設計者說：『微核心的故事充滿好點子與死胡同。』最終，支援並隔離多個子系統的需求，被虛擬化接手——它取代微核心成為 OS 設計的關鍵創新。

深度探秘

一台機器變很多台

系統虛擬化的目標

系統虛擬化（system virtualization）的目標：在一台實體機器上提供多台虛擬機器（virtual machine, VM），每台 VM 各跑一份獨立的作業系統。背後觀察是：現代電腦效能足以支撐大量 VM 並在它們之間多工分配資源。可以跑多份相同 OS，也可跑各種不同 OS。

為什麼要虛擬化

• 伺服器整合：每個服務配一台 VM，再把 VM 最佳地分配到實體伺服器。VM 比行程更容易遷移，提升管理彈性、降低投資與能耗。
• 雲端運算：IaaS 直接由虛擬化實現——把一或多台 VM 提供給雲端使用者。
• 動態建立/銷毀：多人線上遊戲、分散式多媒體等需要快速、低開銷地建立與銷毀 VM。
• 多 OS 桌面：例如在 Mac OS X 上用 Parallels 同時跑 Windows 或 Linux。

實作者：hypervisor

虛擬化由一層薄薄的軟體實作，叫**虛擬機器監督器（virtual machine monitor）**或 hypervisor，它在實體架構之上提供一個貼近底層硬體的介面。

生活妙喻

整層改套房 vs 量身打造

比喻：一棟樓隔成多間套房

hypervisor 像把一棟大樓隔成多間獨立套房，每間住一戶（一個 OS），共用水電（實體資源）卻互不干擾。

全虛擬化（full virtualization）＝每間套房都做成跟原始樣品屋一模一樣：

• hypervisor 提供與底層實體架構完全相同的介面。
• 好處：既有 OS 可原封不動、透明地跑。
• 壞處：在某些架構（如 x86）上難有令人滿意的效能。

Paravirtualization（半虛擬化）＝稍微改一下格局，換取更好住起來的效能：

• 提供一個修改過的介面。
• 壞處：OS 必須被**移植（port）**到這個改過的介面。
• 好處：許多指令可直接在裸硬體上跑、不必模擬，效能更好。

注意：虛擬化不同於微核心的 OS 模擬。虛擬化是讓 OS（幾乎不改地）直接跑在虛擬硬體上，所以應用不必重寫或重編譯——這正是它勝過微核心的關鍵。

實用超能力

Xen 的 domain 架構

Xen 怎麼設計

Xen 的 hypervisor 是核心，負責虛擬化 CPU 與指令集、CPU 排程與實體記憶體，並確保各 VM 之間強隔離。它遵循 Exokernel 的精神：只實作最小的資源管理與隔離機制，把高階政策留給上層；hypervisor 本身不懂裝置，只當與裝置互動的管道。

為什麼要極簡？

• hypervisor 一旦有 bug 會讓整台機器崩潰，所以必須最小、徹底測試、無 bug。
• 它是執行在裸硬體上的必然開銷，越輕量越好。

Xen 的 VM 叫 domain：

flowchart TD
  HW[實體硬體 x86] --> HV[Xen hypervisor]
  HV --> D0[domain0 控制平面 有硬體特權]
  HV --> DU1[domainU 來賓 OS]
  HV --> DU2[domainU 來賓 OS]

x86 為何需要 paravirtualization

Popek 與 Goldberg 指出：一個架構可虛擬化的條件是所有敏感指令都是特權指令（才能被 hypervisor 攔截）。但 x86 有 17 條敏感卻非特權的指令（如 LAR、LSL），無法被攔。全虛擬化得對整個指令集做模擬層（貴）；paravirtualization 則讓多數指令直接跑、特權指令陷入 hypervisor，那些『敏感非特權』指令則交由改過的來賓 OS自己處理。