# 摘要（中文）

本文研究單處理器、硬即時（hard real-time）環境中的多工作排程。作者證明：
1. 以**固定優先權**（依請求週期遞減＝Rate-Monotonic, RM）排程在最壞情況下的**處理器可利用率上界**為 $U \le m(2^{1/m}-1)$，當工作數 $m\to\infty$ 時趨近 $\ln 2 \approx 0.693$；
2. 以**截止時間驅動**（Earliest Deadline First, EDF）動態指派優先權可在滿足$\sum C_i/T_i \le 1$時達100%利用率；
3. 並討論**混合式**作法：高頻中斷採固定優先權，其餘用EDF。
4. T:請求時間 t:週期任務 C:執行時間

# 重點（中文）

* **模型假設**：週期性請求、截止僅為可執行性限制（每次請求須在下次請求前完成）、工作彼此獨立、執行時間常數、非週期工作僅作初始化/復原。這些假設使每個工作可由$(C_i,T_i)$完全表示。
* **關鍵概念**：

* **關鍵時刻/區間**：當某工作與所有較高優先工作同時被請求時，其回應時間達最大，用以檢驗可行性。
* **RM 最佳性（在固定優先權中）**：若存在任何固定優先權能排得動，依速率單調（週期短者高優先）亦可排得動。
* **RM 利用率上界**：兩工作時 $U\le 2(2^{1/2}-1)\approx0.828$；一般 $m$ 件時 $U\le m(2^{1/m}-1)$，最壞趨近 $\ln 2$。
* **EDF 最佳性（全域）與判準**：在單機上，若且唯若 $\sum_i C_i/T_i \le 1$ 則 EDF 可排程；且在溢出（deadline miss）前不會出現 CPU 閒置。
* **混合式 RM+EDF**：實務上可讓最短週期（中斷驅動）用硬體固定優先權，其餘工作由 EDF 於剩餘可用處理器時間內排程；可行性需檢查「可用度函數」不等式。

# 演算法

**Rate-Monotonic (RM, 固定優先權)**

1. 依週期 $T_i$ 由小到大賦予較高優先權。
2. 任一時刻，執行就緒佇列中優先權最高者，可搶先(preempt)。
3. 可行性檢查：最安全用**臨界區間檢驗**（每工作在關鍵時刻與所有較高優先同時釋出，檢查其在截止前是否完成）；快速保守近似用上界 $U \le m(2^{1/m}-1)$。

**Earliest Deadline First (EDF, 動態優先權)**

1. 每次釋出時設定該工作實例(deadline)＝下次釋出時刻。
2. 任一時刻，選擇**最早截止**的就緒實例執行，可搶先。
3. 判準：若 $\sum_i C_i/T_i \le 1$ 則可行，且可達 100% 利用率；若不等式不成立，則任何演算法都無法使全部截止滿足。

**混合式（前 $k$ 件 RM，其餘 EDF）**

1. 令最短週期的 $k$ 件工作用 RM 固定優先權先行排走一部分處理器時間。
2. 其餘工作在「可用度函數」$a_k(t)$ 所描述的剩餘處理器時間上，用 EDF 排程。
3. 可行性需驗證：對所有與某一週期對齊的 $t$，都有 $\sum_j \big\lfloor t/T_j\big\rfloor C_j \le a_k(t)$。

# 結論（中文）

* 在固定優先權類別中，**RM 最佳且簡潔**，但最壞情況利用率僅約 **69.3%**。
* **EDF 全域最佳**，滿足利用率條件即可達 **100%**。
* **混合式**能兼顧現有硬體中斷優先與高利用率，但其可行性須以可用度不等式檢驗，整體上仍優於純 RM。