僅僅「快」還不夠？從數學上保證「準時完成」的即時作業系統（RTOS）與排程理論

1. 「快（Fast）」與「即時（Real-Time）」的本質鴻溝

在日常語境中，「即時處理」常被誤解為「速度極快」。然而，一台配備多核心超純量 CPU 與大容量快取的頂級電競 PC 或雲端伺服器，即便平均回應時間低至 1 毫秒，也絕不能直接用於控制客機線傳飛控系統（Fly-by-Wire）、汽車安全氣囊點火或心律調節器。因為通用電腦追求的是平均吞吐量最大化（Average Throughput），若百萬次操作中有一次因快取未命中、分頁錯誤或垃圾回收（GC）而延遲了 200 毫秒，飛機就會失速墜毀，氣囊就會在碰撞發生後才引爆。

根據 Donald Gillies 與 Hermann Kopetz 的經典定義，即時計算的公理指出：系統的正確性不僅取決於計算結果的邏輯/算術正確性，更取決於結果產出的物理時刻（是否在截止期 $d_i$ 之前）。根據任務完成時刻 $t$ 超過截止期 $d$ 後時間效用函數 $U(t)$ 的衰減特徵，即時系統嚴格分為三類：

$$U_{\text{hard}}(t) = \begin{cases} V & (t \le d) \\ -\infty & (t > d) \end{cases}, \qquad U_{\text{firm}}(t) = \begin{cases} V & (t \le d) \\ 0 & (t > d) \end{cases}, \qquad U_{\text{soft}}(t) = \begin{cases} V & (t \le d) \\ V e^{-\alpha(t-d)} & (t > d) \end{cases}$$

硬即時（Hard Real-Time）：單次逾時（$t > d$）即導致災難性後果（$U = -\infty$），如飛行控制、ABS 煞車，必須透過離線靜態數學證明確保 $100\%$ 滿足截止期。
固即時（Firm Real-Time）：逾時結果毫無價值並被立即丟棄（$U = 0$），如高速產線視覺分揀、高頻交易撤單，通常受 $(m,k)$-firm 約束。
軟即時（Soft Real-Time）：逾時後價值連續衰減，如 60fps 影片播放或 VoIP 通話，僅表現為偶發卡頓。

對比維度	通用作業系統 (GPOS: Linux / Windows / macOS)	即時作業系統 (RTOS: VxWorks / QNX / FreeRTOS / seL4)
核心最佳化目標	最大化平均吞吐量、公平性（CFS / EEVDF）與平均回應速度	保證時間確定性（Determinism）與最壞回應時間（WCRT）的嚴格上界
中斷與排程延遲	微秒至數十毫秒（隨機波動大，存在長尾分佈）	數百奈秒至數微秒（嚴格受界的 $O(1)$ 硬體級常數上限）
核心可搶佔性	巨核心中存在較長的不可搶佔臨界區與自旋鎖路徑	完全可搶佔核心或極小微核心架構（如 QNX, seL4）
記憶體與硬體管理	虛擬記憶體分頁錯誤、動態 `malloc`、垃圾回收；全面啟用投機執行	靜態記憶體分割區、$O(1)$ 記憶體池、鎖頁；採用片上緊耦合記憶體（TCM）與快取鎖定

2. 最壞執行時間（WCET）分析的噩夢

所有即時排程理論都依賴於預先獲知每個任務 $\tau_i$ 的最壞執行時間（Worst-Case Execution Time, $C_i$）。然而現代電腦體系結構中存在一個深刻悖論：幾乎所有提高 CPU 平均速度的微架構特性（L1/L2/L3 快取、動態分支預測、亂序執行 OoO、TLB、動態調頻 DVFS 以及不可遮罩的系統管理中斷 SMI）都在徹底摧毀最壞執行時間的可預測性。

在亂序執行與快取耦合的處理器上，甚至會出現時序反常（Timing Anomaly）：某條指令發生快取命中（局部變快）反而導致投機路徑提前搶佔匯流排，使程式整體執行時間比快取未命中時更長！因此，航太（DO-178C Level A）與汽車（ISO 26262 ASIL-D）硬即時系統一方面在硬體上採用無抖動的緊耦合片上 SRAM（Scratchpad / TCM）和快取鎖定（Cache Locking）；另一方面在軟體上採用隱式路徑枚舉技術（IPET）——將控制流圖（CFG）上的基本區塊最壞耗時 $c_i$ 與執行次數 $x_i$ 建構為整數線性規劃（ILP）求最大值，從而在不遍歷天文數字路徑的前提下給出嚴格的數學 WCET 上界：

$$\text{WCET} = \max \sum_{i=1}^{N} c_i x_i \quad \text{subject to} \quad \sum_{j} d_{j \to i} = x_i = \sum_{k} d_{i \to k} \quad (\text{克希荷夫流量守恆與迴圈上界約束})$$

3. Liu & Layland（1973）：週期性即時排程定理（RMS vs. EDF）

設單處理器上有 $n$ 個獨立的週期性任務 $\Gamma = \{\tau_1, \dots, \tau_n\}$，每個任務由三元組 $\tau_i = (C_i, T_i, D_i)$ 定義（最壞執行時間 $C_i$、釋放週期 $T_i$、相對截止期 $D_i = T_i$）。系統的總處理器使用率（Total Utilization）為：

$$U = \sum_{i=1}^{n} \frac{C_i}{T_i}$$

1973年，劉炯朗（C. L. Liu）與 James W. Layland 發表了即時系統領域的奠基之作，嚴格對比了靜態優先權與動態優先權排程：

3.1 單調速率排程（RMS: Rate Monotonic Scheduling）與 $\ln 2 \approx 69.3\%$ 界限

在固定優先權搶佔式排程中，RMS 規則規定：任務的週期 $T_i$ 越短（頻率 $1/T_i$ 越高），賦予的靜態優先權越高（與 $C_i$ 無關）。Liu & Layland 證明了臨界瞬刻定理（Critical Instant Theorem）：任務 $\tau_i$ 的最壞回應時間發生在它與所有更高優先權任務在同一時刻（$t=0$）同時釋放的瞬間；並證明了 RMS 在所有固定優先權演算法中是最優的，其無條件可排程的最小上界（Least Upper Bound）為：

$$U = \sum_{i=1}^{n} \frac{C_i}{T_i} \le U_{\text{lub}}(n) = n\left(2^{1/n} - 1\right) \xrightarrow{n \to \infty} \ln 2 \approx 0.6931 \quad (69.3\%)$$

注意：$69.3\%$ 只是充分條件而非必要條件！若所有週期互為整數倍（諧波週期任務集，Harmonic Task Set，如 $5\,\text{ms}, 10\,\text{ms}, 20\,\text{ms}$），RMS 同樣能達到 $100\%$ 的使用率。對於一般任務集，可透過 Joseph & Pandya（1986）提出的回應時間分析（RTA）不動點迭代方程進行充要判定（收斂於 $R_i \le D_i$ 即安全）：

$$R_i^{(k+1)} = C_i + \sum_{j \in hp(i)} \left\lceil \frac{R_i^{(k)}}{T_j} \right\rceil C_j$$

3.2 最早截止期優先（EDF: Earliest Deadline First）與 $100\%$ 最優性

在動態優先權搶佔式排程中，EDF 隨時將最高優先權賦予絕對截止期 $d_{i,k} = r_{i,k} + D_i$ 距離當前時刻最近的就緒作業。Liu & Layland 證明了在單處理器上，EDF 可排程的充分必要條件直接達到物理極限：

$$U = \sum_{i=1}^{n} \frac{C_i}{T_i} \le 1.00 \quad (100\%)$$

例如，給定 $\tau_1 = (C_1=2, T_1=5)$ 與 $\tau_2 = (C_2=4, T_2=7)$，總使用率 $U = 2/5 + 4/7 = 97.14\%$。在 RMS 下，第 $t=5\,\text{ms}$ 到達的 $\tau_{1,2}$（截止期 $10$）會強行搶佔還剩 $1\,\text{ms}$ 就能完成的 $\tau_{2,1}$（截止期 $7$），導致 $R_2 = 8 > 7$ 逾時失敗；而在 EDF 下，由於 $d_{2,1} = 7 < d_{1,2} = 10$，EDF 禁止 $\tau_{1,2}$ 搶佔，使 $\tau_{2,1}$ 在 $t=6$ 順利完成，所有截止期完美達成！

然而，工業界主流 RTOS（VxWorks, FreeRTOS, QNX, AUTOSAR）依然首選固定優先權（RMS/DMS），原因在於：當發生瞬時過載（$U > 1.0$）時，EDF 會引發災難性的骨牌效應（Domino Effect）——已逾時作業因截止期最老而霸佔 CPU，拖垮後續所有任務；而 RMS 能保證高優先權關鍵任務完全不受過載影響，僅犧牲最低優先權任務，且核心可透過位元圖與 CLZ 指令實現極速 $O(1)$ 排程。

評估維度	單調速率排程 (RMS: 靜態固定優先權)	最早截止期優先 (EDF: 動態優先權)
優先權分配規則	靜態固定：週期 $T_i$ 越短，優先權越高	動態更新：絕對截止期 $d_{i,k}$ 越近，優先權越高
可排程使用率上界	充分條件：$n(2^{1/n}-1) \to 69.3\%$（諧波週期可達 $100\%$）	充要條件：恆為 $100\%$（$\sum C_i/T_i \le 1$）
核心排程時間複雜度	$O(1)$（固定長度位元圖 + 硬體 `CLZ` 前導零指令）	$O(\log n)$（需維護按截止期排序的最小堆積/紅黑樹）
瞬時過載（$U > 1$）表現	優雅降級：高優先權關鍵任務 100% 存活，僅低優先權延遲	骨牌崩潰：連鎖反應導致全部任務接連逾時

4. 1997年 NASA 火星探路者號事故與「優先權反轉」的根治

1997年7月，成功登陸火星的 NASA 火星探路者號（Mars Pathfinder）在執行 Wind River VxWorks 即時系統時，突然頻繁發生神秘的硬體看門狗強制重啟，導致探測資料不斷遺失。

事故元兇是三個不同優先權的任務圍繞共享「資訊匯流排」互斥鎖 $M$ 發生的無界優先權反轉（Unbounded Priority Inversion）：

低優先權氣象任務 $\tau_L$（ASI/MET）鎖定了共享匯流排互斥鎖 $M$；
高優先權匯流排管理任務 $\tau_H$（bc_dist）週期性喚醒並請求鎖 $M$，因 $M$ 被 $\tau_L$ 持有而進入阻塞（Blocked）等待；
此時，與鎖 $M$ 毫無關係的多個中優先權通訊任務 $\tau_M$ 到達！由於 $\text{Priority}(\tau_M) > \text{Priority}(\tau_L)$，$\tau_M$ 強行搶佔了 $\tau_L$ 的 CPU 並長時間執行，導致 $\tau_L$ 遲遲無法釋放鎖 $M$，進而使最高優先權的 $\tau_H$ 被中優先權的 $\tau_M$ 無限期阻塞，最終觸發看門狗逾時重啟！

  flowchart TD
    subgraph Bug["火星探路者號的無界優先權反轉 (Unbounded Priority Inversion)"]
        B1["1. 低優先權任務 τ_L 鎖定互斥鎖 M"] --> B2["2. 高優先權任務 τ_H 到達並請求 M，因鎖被佔而阻塞"]
        B2 --> B3["3. 不使用鎖 M 的中優先權任務 τ_M 到達！<br/>因 Priority(τ_M) > Priority(τ_L)，τ_M 搶佔 τ_L 並霸佔 CPU"]
        B3 --> B4["4. τ_L 無法釋放 M，導致最高優先權的 τ_H 被無限期拖延<br/>看門狗逾時觸發火星探測器全系統強制重啟！"]
    end

  flowchart TD
    subgraph Fix["Sha, Rajkumar & Lehoczky (1990) 同步協定根治方案"]
        F1["方案A：優先權繼承協定 (PIP)<br/>當 τ_H 在鎖 M 上阻塞瞬間，核心立即將鎖持有者 τ_L 的有效優先權<br/>提升至 τ_H 的高優先權！τ_M 無法搶佔，τ_L 迅速解鎖交還 τ_H"]
        F2["方案B：即時優先權上限協定 (ICPP / Highest Locker)<br/>每個鎖 M 預設上限 Ceil(M) = 使用 M 的最高任務優先權。<br/>任務一旦加鎖立即升至 Ceil(M)：徹底消除死結，且最多僅阻塞 1 次 (B_i)！"]
        F1 --> F2
    end

事實上，Sha、Rajkumar 與 Lehoczky 早在1990年就提出了兩大根治協定：

優先權繼承協定（PIP: Priority Inheritance Protocol）：當高優先權任務 $\tau_H$ 在低優先權任務 $\tau_L$ 持有的鎖 $M$ 上阻塞時，核心立即將 $\tau_L$ 的有效優先權臨時提升至 $\tau_H$ 的級別，阻止中優先權任務 $\tau_M$ 插隊。JPL 工程師正是透過地球測試台重現該漏洞後，跨越 1.9 億公里向火星發送了一行 C 語言指令，將 VxWorks 核心中 pipe 互斥鎖的全域變數 SEM_INVERSION_SAFE 從 0 改為 1 啟用 PIP，徹底拯救了火星探路者號！
優先權上限協定（PCP / ICPP: Immediate Priority Ceiling Protocol）：PIP 仍可能出現鏈式阻塞（Chained Blocking）與死結。ICPP（POSIX PTHREAD_PRIO_PROTECT 與 AUTOSAR OS 標準）為每個互斥鎖 $M_k$ 靜態指定一個上限 $\text{Ceil}(M_k) = \max\{\text{Priority}(\tau_i) \mid \tau_i \text{ 使用 } M_k\}$；任何任務一旦取得 $M_k$，其有效優先權立即提升至 $\text{Ceil}(M_k)$。ICPP 從數學上同時保證了完全無死結，且任何高優先權任務最多只會被低優先權臨界區阻塞唯一一次（最大阻塞時間 $B_i$）：

$$R_i^{(k+1)} = C_i + B_i + \sum_{j \in hp(i)} \left\lceil \frac{R_i^{(k)}}{T_j} \right\rceil C_j$$