**論文:**
A Scheme for Scheduling Hard Real-Time Applications in Open
System Environment

好的，這篇論文詳細描述了一種在開放系統環境中調度實時應用和非實時應用的兩層層次結構的調度方案，並深入探討了其運作機制和理論基礎。以下是更詳細的說明：

### 1. 引言
在引言部分，論文指出現有的大多數實時應用是實現在獨立的嵌入式系統或專用計算機上，其可調度性通過分析所有應用的整體來確定。然而，隨著硬體技術的巨大進步，現在有可能在快速的通用工作站和個人計算機上同時運行實時應用和非實時應用。這帶來了一個挑戰：如何在這樣的開放系統中調度複雜、獨立開發的實時應用和非實時應用。

### 2. 調度方案的目標
調度方案的設計目標包括：
1. 允許每個實時應用的開發者在其他應用之外驗證其可調度性。
2. 提供一個簡單的接納測試，使操作系統能夠決定是否接納新的實時應用，而不需要分析所有現有應用的可調度性。
3. 一旦接納新的實時應用，保證其任務的可調度性。
4. 維持非實時應用的響應性。
5. 在不依賴固定的時間或資源分配和細粒度時間分片的情況下，適應具有不同時間和資源需求的應用。

### 3. 兩層層次調度方案
論文提出了一種兩層層次的調度方案：
1. **頂層**：操作系統分配處理器時間給各個服務器，設置它們的截止時間，並根據EDF算法調度這些服務器。
2. **底層**：每個應用的服務器調度器根據為該應用選擇的優先驅動算法來調度應用中的任務。

### 4. 系統模型與假設
論文採用的系統模型包括：
- 開放系統中的處理器速度為1。
- 處理器上的工作負載包括實時應用和非實時應用。
- 每個實時應用由一個常量利用率服務器執行，所有非實時應用由一個常量利用率服務器執行。
- 常量利用率服務器的定義、運作方式及其與應用的交互。

### 5. 可調度性條件
論文提出了一般的可調度性條件，即如果在任何時間點，系統中所有活動任務的總密度小於或等於1，那麼這些任務是可調度的。這一條件保證了所有實時應用和服務器在使用EDF算法調度時的可調度性。

### 6. 具體算法描述
論文詳細描述了操作系統如何維持不同類型應用的服務器，具體包括：
1. **非搶占性應用**：操作系統創建一個常量利用率服務器來執行該應用，並根據應用的特性設置服務器的預算和截止時間。
2. **搶占性應用**：操作系統需要跟踪應用的下一個事件（如任務釋放或完成）的發生時間，並根據這些事件動態調整服務器的預算和截止時間。
3. **資源競爭的應用**：操作系統還需要處理應用中任務之間的資源競爭，並根據資源訪問協議調整任務的優先級和服務器的預算。

### 7. 相關工作和總結
論文討論了與其提出的方案相關的其他研究工作，並總結了本文提出的兩層層次調度方案的優點，如降低上下文切換開銷和提高非實時應用的響應性。

### 總結
這篇論文提供了一個解決在開放系統中調度實時和非實時應用的方案，這個方案通過兩層層次的調度機制來模擬細粒度的加權輪轉調度，並保護實時應用免受其他應用的干擾。這一方案在保證實時應用可調度性的同時，也能夠適應具有不同時間和資源需求的應用，提高了系統的靈活性和效能。

---

在這篇論文中，CUS 指的是 "Constant Utilization Server"（常量利用率服務器）。這是一種調度機制，用於確保實時應用在開放系統中的可調度性。以下是關於 CUS 的一些詳細說明：

### 常量利用率服務器（Constant Utilization Server, CUS）

1. **定義**：
- 常量利用率服務器由其服務器大小 \( U \) 定義，這是分配給服務器的處理器利用率的分數。
- 當操作系統給服務器分配執行預算時，服務器變得可執行。預算在服務器執行時消耗，直到預算用完。
- 每個常量利用率服務器的運行類似於具有固定利用率的任務，因此被稱為常量利用率服務器。

2. **工作原理**：
- 當一個實時應用被接納到系統中時，操作系統為其創建一個常量利用率服務器，並設置其大小 \( U \)。
- 所有的非實時應用都由一個常量利用率服務器執行。
- 在高層次上，操作系統使用最早截止時間優先（EDF）算法來調度所有的服務器。
- 在低層次上，每個服務器的調度器根據應用選擇的優先驅動算法來調度應用中的任務。

3. **預算和截止時間的設置**：
- 當一個新的實時應用被釋放並放置在服務器的就緒隊列中時，如果服務器當前的截止時間已過，操作系統將設置服務器的預算和新的截止時間。
- 在服務器的截止時間到達時，如果服務器的就緒隊列中仍有任務，操作系統將重新設置服務器的預算和截止時間。

4. **優勢**：
- CUS 允許在不影響其他應用的情況下，獨立驗證每個實時應用的可調度性。
- 一旦實時應用被系統接納，其可調度性將得到保證。
- CUS 能夠適應不同時間和資源需求的應用，避免依賴固定的時間或資源分配和細粒度時間分片。

### 常量利用率服務器在調度中的應用
論文詳細描述了如何使用 CUS 來調度實時應用和非實時應用，包括：
- **非搶占性調度**：當一個非搶占性任務到達時，服務器會根據該任務的執行時間和服務器大小來設置預算和截止時間。
- **搶占性調度**：服務器需要跟踪應用的下一個事件，並根據這些事件動態調整預算和截止時間。
- **資源競爭**：操作系統需要處理應用中任務之間的資源競爭，根據資源訪問協議調整任務優先級和服務器預算。

總之，CUS 是一種有效的調度機制，能夠在開放系統中保證實時應用的可調度性，同時維持非實時應用的響應性。這種機制通過兩層層次的調度方案，既保證了實時應用的時間需求，又提高了系統的靈活性和效能。

---
這張圖展示了在開放系統中實時應用和非實時應用的調度模型。讓我們逐步分析這張圖的各個部分：

### 圖的整體結構
- **圖的頂部**：展示了不同類型的應用，包括非實時應用（Non-Real-Time Applications）和多個實時應用（Real-Time Applications）。
- **中間部分**：展示了各個應用的調度器（Scheduler），每個調度器負責調度相應的應用。
- **圖的底部**：展示了操作系統的調度器（OS Scheduler），該調度器根據最早截止時間優先（EDF）算法來調度整個系統中的所有應用。

### 圖的詳細部分
1. **非實時應用**：
- **左上角**：標示為“Non-Real-Time Applications”，表示非實時應用。
- **Time Sharing Scheduler（SO）**：這是時間共享調度器，負責調度所有非實時應用。這些應用可能會在同一時間片內多次切換。

2. **實時應用**：
- **中間部分**：
- **A1, A2, ..., AN**：表示多個實時應用，每個應用有自己的調度器。
- **RM-PCP Scheduler（S1）**：為應用A1服務的調度器，使用的是Rate Monotonic - Priority Ceiling Protocol（RM-PCP）調度算法。
- **EDF-SBP Scheduler（S2）**：為應用A2服務的調度器，使用的是Earliest Deadline First - Stack Based Priority（EDF-SBP）調度算法。
- **Cyclic Executive Scheduler（SN）**：為應用AN服務的調度器，使用的是循環執行調度算法。

3. **調度器和就緒隊列（Ready Queue）**：
- 各個應用的調度器會將其應用的任務放入就緒隊列中，就緒隊列中的任務準備執行。

4. **操作系統調度器（OS Scheduler）**：
- **OS Scheduler（EDF）**：操作系統調度器使用EDF算法來調度所有服務器（包括實時應用的服務器和非實時應用的服務器）。
- **Operating System**：操作系統本身，包含了操作系統的內核和其他必要組件。
- **Open System**：表示這是一個開放系統，可以接受不同類型的應用。

### 總結
這張圖展示了在一個開放系統中，如何通過兩層層次的調度模型來調度實時應用和非實時應用。頂層是操作系統調度器，使用EDF算法來調度所有的應用，而底層是各個應用的專用調度器，它們負責調度各自的應用任務。這種模型保證了實時應用的可調度性，同時維持了非實時應用的響應性。

---
這張圖展示了在不同處理器設置下，應用 \( A_k \) 的調度計劃。圖中的三個子圖分別展示了慢速處理器和快速處理器在不同預算補充方案下的調度情況。讓我們逐步解析這張圖。

### 子圖 (a): Slow Processor with Speed 0.25
1. **描述**：這部分展示了應用 \( A_k \) 在速度為0.25的慢速處理器上的調度情況。
2. **任務 \( J_1 \)**：
- \( r_1 \)：任務 \( J_1 \) 的釋放時間為0。
- \( a \)：\( J_1 \) 開始執行。
- \( a + 4 \)：\( J_1 \) 的完成時間。
3. **任務 \( J_2 \)**：
- \( r_2 \)：任務 \( J_2 \) 的釋放時間為 \( a \)。
- \( d_2 \)：\( J_2 \) 的截止時間為 \( a + 4 \)。
- \( J_2 \) 開始執行的時間。
- \( J_2 \) 的完成時間。

### 子圖 (b): Fast Processor with Improper Amount of Budget Replenishment
1. **描述**：這部分展示了在快速處理器上，預算補充不正確的情況下的調度計劃。
2. **任務 \( J_1 \)**：
- \( r_1 \)：任務 \( J_1 \) 的釋放時間為0。
- \( a \)：\( J_1 \) 開始執行。
- \( a + 4 \)：\( J_1 \) 的完成時間。
3. **任務 \( J_2 \)**：
- \( r_2 \)：任務 \( J_2 \) 的釋放時間為 \( a \)。
- \( d_2 \)：\( J_2 \) 的截止時間為 \( a + 4 \)。
- \( a / U_k \)：預算耗盡，\( J_2 \) 開始執行。
- \( (a + 1) / U_k \)：\( J_2 \) 的完成時間。
4. **預算**：
- 預算從 \( a \) 開始，隨著時間減少。
- 在 \( a / U_k \) 時重新補充預算。

### 子圖 (c): Fast Processor with Proper Amount of Budget Replenishment
1. **描述**：這部分展示了在快速處理器上，預算補充正確的情況下的調度計劃。
2. **任務 \( J_1 \)**：
- \( r_1 \)：任務 \( J_1 \) 的釋放時間為0。
- \( a \)：\( J_1 \) 開始執行。
- \( a + 4 \)：\( J_1 \) 的完成時間。
3. **任務 \( J_2 \)**：
- \( r_2 \)：任務 \( J_2 \) 的釋放時間為 \( a \)。
- \( d_2 \)：\( J_2 \) 的截止時間為 \( a + 4 \)。
- \( J_2 \) 開始執行的時間。
- \( J_2 \) 的完成時間。
4. **預算**：
- 預算從 \( a/4 \) 開始，隨著時間減少。
- 在 \( a + 4 \) 時重新補充預算，預算設置為3a/4。

### 總結
這張圖通過三個子圖比較了不同處理器速度和預算補充方案下應用 \( A_k \) 的調度計劃：
- 子圖 (a) 顯示了在速度為0.25的慢速處理器上的調度情況。
- 子圖 (b) 顯示了在快速處理器上，預算補充不正確的情況下，應用任務的調度計劃。
- 子圖 (c) 顯示了在快速處理器上，預算補充正確的情況下，應用任務的調度計劃。

---
# 比較:

這些比較展示了適當的預算補充對於確保應用任務在快速處理器上按時完成的重要性。

以下是恒定利用率伺服器 (Constant Utilization Server) 和總帶寬伺服器 (Total Bandwidth Server) 在演算法和硬體複雜度方面的比較：

| 比較項目 | 恒定利用率伺服器 (Constant Utilization Server) | 總帶寬伺服器 (Total Bandwidth Server) |
| ------------------ | ----------------------------- | ------------------------ |
| **伺服器配額補充** | 在任務截止時間補充 | 在任務完成後立即補充 |
| **適合硬實時期限** | 更適合，因為能保證實時應用程序的可調度性 | 不如恒定利用率伺服器適合，但仍有較好表現 |
| **執行方法** | 主要針對實時應用程序設計，穩定性更高 | 更靈活，適合不同類型的應用程序 |
| **對就緒隊列的響應** | 隊列不空時等到當前截止時間補充 | 隊列不空時立即補充 |
| **容量** | 固定分配，根據伺服器大小設置 | 動態分配，根據任務需求調整 |
| **配額補充** | 配額在每個週期固定分配 | 配額在每個任務完成後立即補充，根據需求分配 |
| **演算法複雜度** | 由於固定週期補充，複雜度較低 | 由於動態調整和立即補充，複雜度較高 |
| **硬體複雜度** | 由於調度較簡單，硬體需求較低 | 由於需要更頻繁和動態的調度調整，硬體需求較高 |

### 關於容量和配額補充的差異

- **容量 (Capacity)**:
- **恒定利用率伺服器**: 伺服器的大小 (利用率) 是固定的，分配給每個伺服器的處理器利用率的分數在系統初始化時設置，並在整個運行過程中保持不變。
- **總帶寬伺服器**: 伺服器的容量是動態分配的，根據任務的需求進行調整，以確保每個任務在需要時都能獲得足夠的資源。

- **配額補充 (Budget Replenishment)**:
- **恒定利用率伺服器**: 配額在每個伺服器的當前截止時間到達後補充。這意味著伺服器在執行其分配的任務時，直到當前配額用完並到達截止時間，配額才會被重新設置。
- **總帶寬伺服器**: 配額在每個任務抵達後立即補充，並根據需求進行分配。這使得伺服器能夠更快地響應就緒隊列中的任務，並更靈活地適應不同的工作負載。

### 演算法和硬體複雜度的差異

- **演算法複雜度**:
- **恒定利用率伺服器**: 由於伺服器配額在固定的時間間隔（即當前截止時間）補充，因此演算法複雜度較低。這種週期性和可預測的補充減少了複雜計算和頻繁調整的需求。
- **總帶寬伺服器**: 由於伺服器配額在每個任務完成後立即補充，因此演算法複雜度較高。這需要系統不斷監控任務完成情況並動態調整配額，導致更頻繁和複雜的調度決策。

- **硬體複雜度**:
- **恒定利用率伺服器**: 由於調度機制較簡單，硬體複雜度較低。伺服器配額的可預測性和週期性補充降低了硬體資源的需求，使其實施和管理更容易。
- **總帶寬伺服器**: 由於需要更頻繁和動態的調度調整，硬體複雜度較高。系統必須能夠立即響應任務完成並快速調整配額，這增加了對硬體資源的需求。

這些比較突顯出恒定利用率伺服器在需要嚴格實時保證的場景中的優勢，而總帶寬伺服器則在需要更高靈活性和響應速度的場景中表現更佳。