貪心算法應用：速率單調調度(RMS)問題詳解

在這里插入圖片描述

Java中的貪心算法應用：速率單調調度(RMS)問題詳解

1. 速率單調調度(RMS)概述

速率單調調度(Rate Monotonic Scheduling, RMS)是一種廣泛應用于實時系統中的靜態優先級調度算法，屬于貪心算法在任務調度領域的經典應用。

1.1 基本概念

RMS基于以下原則：

每個周期性任務都有一個固定的執行時間?和周期(T)
任務的優先級與其周期成反比：周期越短，優先級越高
采用搶占式調度方式

1.2 RMS的數學基礎

RMS的理論基礎是Liu & Layland提出的利用率界限定理：

對于n個任務，RMS可調度的充分條件是總利用率U ≤ n(2^(1/n) - 1)
當n→∞時，這個界限趨近于ln2 ≈ 0.693

2. RMS問題建模

2.1 任務模型

在Java中，我們可以這樣表示一個周期性任務：

class PeriodicTask {private int id;             // 任務IDprivate int period;         // 周期(ms)private int executionTime;  // 執行時間(ms)private int deadline;       // 相對截止時間(通常等于period)private int priority;       // 優先級// 構造函數public PeriodicTask(int id, int period, int executionTime) {this.id = id;this.period = period;this.executionTime = executionTime;this.deadline = period; // 通常截止時間等于周期this.priority = 1 / period; // 速率單調優先級}// Getters and Setters// ...
}

2.2 調度器模型

class RateMonotonicScheduler {private List<PeriodicTask> taskSet;private int currentTime;private boolean isSchedulable;public RateMonotonicScheduler(List<PeriodicTask> tasks) {this.taskSet = tasks;this.currentTime = 0;// 按照速率單調優先級排序(周期越短優先級越高)Collections.sort(taskSet, Comparator.comparingInt(PeriodicTask::getPeriod));this.isSchedulable = checkSchedulability();}// 檢查任務集是否可調度private boolean checkSchedulability() {// 實現將在后面詳細講解}// 執行調度public void schedule() {// 實現將在后面詳細講解}
}

3. RMS可調度性分析

3.1 利用率界限測試

private boolean checkSchedulability() {double totalUtilization = 0.0;for (PeriodicTask task : taskSet) {double utilization = (double) task.getExecutionTime() / task.getPeriod();totalUtilization += utilization;}int n = taskSet.size();double bound = n * (Math.pow(2, 1.0/n) - 1);// 如果總利用率小于界限，則肯定可調度if (totalUtilization <= bound) {return true;}// 否則需要進行時間需求分析return timeDemandAnalysis();
}

3.2 時間需求分析

當利用率超過界限時，需要進行更精確的時間需求分析：

private boolean timeDemandAnalysis() {for (int i = 0; i < taskSet.size(); i++) {PeriodicTask task = taskSet.get(i);boolean found = false;// 檢查所有可能的t值for (int t = task.getExecutionTime(); t <= task.getDeadline(); t++) {double demand = calculateTimeDemand(i, t);if (demand <= t) {found = true;break;}}if (!found) {return false;}}return true;
}private double calculateTimeDemand(int taskIndex, int t) {double demand = 0.0;for (int i = 0; i <= taskIndex; i++) {PeriodicTask task = taskSet.get(i);demand += Math.ceil((double)t / task.getPeriod()) * task.getExecutionTime();}return demand;
}

4. RMS調度算法實現

4.1 調度主循環

public void schedule() {if (!isSchedulable) {System.out.println("任務集不可調度！");return;}System.out.println("開始速率單調調度...");// 模擬調度過程int hyperperiod = calculateHyperperiod();for (currentTime = 0; currentTime < hyperperiod; currentTime++) {// 檢查是否有任務到達PeriodicTask highestPriorityTask = getHighestPriorityReadyTask();if (highestPriorityTask != null) {executeTask(highestPriorityTask);} else {System.out.println("時間 " + currentTime + "ms: CPU空閑");}}
}

4.2 輔助方法

private int calculateHyperperiod() {int hyperperiod = 1;for (PeriodicTask task : taskSet) {hyperperiod = lcm(hyperperiod, task.getPeriod());}return hyperperiod;
}private int lcm(int a, int b) {return a * (b / gcd(a, b));
}private int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}private PeriodicTask getHighestPriorityReadyTask() {for (PeriodicTask task : taskSet) {// 檢查任務是否到達(時間是否是周期的整數倍)if (currentTime % task.getPeriod() == 0) {return task; // 因為已經按優先級排序，第一個找到的就是最高優先級的}}return null;
}private void executeTask(PeriodicTask task) {System.out.println("時間 " + currentTime + "ms: 執行任務 " + task.getId() + " (周期=" + task.getPeriod() + "ms, 執行時間=" + task.getExecutionTime() + "ms)");// 模擬任務執行int remainingTime = task.getExecutionTime();while (remainingTime > 0 && currentTime < hyperperiod) {remainingTime--;currentTime++;// 檢查是否有更高優先級任務到達PeriodicTask higherPriorityTask = checkForHigherPriorityTask(task);if (higherPriorityTask != null) {System.out.println("時間 " + currentTime + "ms: 任務 " + task.getId() + " 被任務 " + higherPriorityTask.getId() + " 搶占");executeTask(higherPriorityTask);}}if (remainingTime == 0) {System.out.println("時間 " + currentTime + "ms: 任務 " + task.getId() + " 完成");}
}private PeriodicTask checkForHigherPriorityTask(PeriodicTask currentTask) {for (PeriodicTask task : taskSet) {if (task.getPeriod() < currentTask.getPeriod() && currentTime % task.getPeriod() == 0) {return task;}}return null;
}

5. 完整示例與測試

5.1 完整RMS調度器實現

import java.util.*;public class RateMonotonicScheduling {public static void main(String[] args) {// 創建任務集List<PeriodicTask> tasks = new ArrayList<>();tasks.add(new PeriodicTask(1, 50, 12));  // 高優先級tasks.add(new PeriodicTask(2, 100, 25)); // 中優先級tasks.add(new PeriodicTask(3, 200, 50)); // 低優先級// 創建調度器RateMonotonicScheduler scheduler = new RateMonotonicScheduler(tasks);// 執行調度scheduler.schedule();}
}class PeriodicTask {private int id;private int period;private int executionTime;private int deadline;public PeriodicTask(int id, int period, int executionTime) {this.id = id;this.period = period;this.executionTime = executionTime;this.deadline = period;}// Getterspublic int getId() { return id; }public int getPeriod() { return period; }public int getExecutionTime() { return executionTime; }public int getDeadline() { return deadline; }
}class RateMonotonicScheduler {private List<PeriodicTask> taskSet;private int currentTime;private boolean isSchedulable;private int hyperperiod;public RateMonotonicScheduler(List<PeriodicTask> tasks) {this.taskSet = new ArrayList<>(tasks);this.currentTime = 0;Collections.sort(taskSet, Comparator.comparingInt(PeriodicTask::getPeriod));this.isSchedulable = checkSchedulability();this.hyperperiod = calculateHyperperiod();}private boolean checkSchedulability() {double totalUtilization = taskSet.stream().mapToDouble(task -> (double)task.getExecutionTime() / task.getPeriod()).sum();int n = taskSet.size();double bound = n * (Math.pow(2, 1.0/n) - 1);System.out.printf("總利用率: %.3f, 界限: %.3f%n", totalUtilization, bound);if (totalUtilization <= bound) {System.out.println("任務集通過利用率界限測試，可調度");return true;}System.out.println("利用率超過界限，進行時間需求分析...");return timeDemandAnalysis();}private boolean timeDemandAnalysis() {for (int i = 0; i < taskSet.size(); i++) {PeriodicTask task = taskSet.get(i);boolean found = false;for (int t = task.getExecutionTime(); t <= task.getDeadline(); t++) {double demand = calculateTimeDemand(i, t);if (demand <= t) {found = true;break;}}if (!found) {System.out.println("任務 " + task.getId() + " 無法滿足截止時間要求");return false;}}System.out.println("任務集通過時間需求分析，可調度");return true;}private double calculateTimeDemand(int taskIndex, int t) {double demand = 0.0;for (int i = 0; i <= taskIndex; i++) {PeriodicTask task = taskSet.get(i);demand += Math.ceil((double)t / task.getPeriod()) * task.getExecutionTime();}return demand;}public void schedule() {if (!isSchedulable) {System.out.println("任務集不可調度！");return;}System.out.println("開始速率單調調度...");System.out.println("超周期長度: " + hyperperiod + "ms");for (currentTime = 0; currentTime < hyperperiod; currentTime++) {PeriodicTask highestPriorityTask = getHighestPriorityReadyTask();if (highestPriorityTask != null) {executeTask(highestPriorityTask);} else {System.out.println("時間 " + currentTime + "ms: CPU空閑");}}}private int calculateHyperperiod() {int hyperperiod = 1;for (PeriodicTask task : taskSet) {hyperperiod = lcm(hyperperiod, task.getPeriod());}return hyperperiod;}private int lcm(int a, int b) {return a * (b / gcd(a, b));}private int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;}private PeriodicTask getHighestPriorityReadyTask() {for (PeriodicTask task : taskSet) {if (currentTime % task.getPeriod() == 0) {return task;}}return null;}private void executeTask(PeriodicTask task) {System.out.println("時間 " + currentTime + "ms: 執行任務 " + task.getId() + " (周期=" + task.getPeriod() + "ms, 執行時間=" + task.getExecutionTime() + "ms)");int remainingTime = task.getExecutionTime();while (remainingTime > 0 && currentTime < hyperperiod) {remainingTime--;currentTime++;PeriodicTask higherPriorityTask = checkForHigherPriorityTask(task);if (higherPriorityTask != null) {System.out.println("時間 " + currentTime + "ms: 任務 " + task.getId() + " 被任務 " + higherPriorityTask.getId() + " 搶占");executeTask(higherPriorityTask);return;}}if (remainingTime == 0) {System.out.println("時間 " + currentTime + "ms: 任務 " + task.getId() + " 完成");} else {System.out.println("時間 " + currentTime + "ms: 任務 " + task.getId() + " 未完成，剩余時間 " + remainingTime);}}private PeriodicTask checkForHigherPriorityTask(PeriodicTask currentTask) {for (PeriodicTask task : taskSet) {if (task.getPeriod() < currentTask.getPeriod() && currentTime % task.getPeriod() == 0) {return task;}}return null;}
}

5.2 輸出示例

運行上述程序，輸出可能如下：

總利用率: 0.745, 界限: 0.780
任務集通過利用率界限測試，可調度
開始速率單調調度...
超周期長度: 200ms
時間 0ms: 執行任務 1 (周期=50ms, 執行時間=12ms)
時間 12ms: 任務 1 完成
時間 12ms: CPU空閑
...
時間 50ms: 執行任務 1 (周期=50ms, 執行時間=12ms)
時間 62ms: 任務 1 完成
時間 62ms: CPU空閑
...

6. RMS的優缺點分析

6.1 優點

簡單高效：優先級分配規則簡單，調度開銷小
最優性：在所有靜態優先級調度算法中，RMS對于周期性任務集是最優的
可預測性：可以提前進行可調度性分析
適合嵌入式系統：實現簡單，適合資源受限的實時系統

6.2 缺點

利用率限制：最壞情況下CPU利用率不能超過69.3%
僅適用于周期性任務：不適合處理非周期性或偶發任務
優先級反轉問題：高優先級任務可能被低優先級任務阻塞
不考慮任務重要性：僅根據周期分配優先級，不考慮任務的實際重要性

7. RMS的擴展與變種

7.1 截止時間單調調度(DMS)

與RMS類似，但優先級根據相對截止時間分配：

// 在PeriodicTask類中添加
public int getRelativeDeadline() {return deadline;
}// 在調度器中使用截止時間排序
Collections.sort(taskSet, Comparator.comparingInt(PeriodicTask::getRelativeDeadline));

7.2 響應時間分析

更精確的可調度性測試方法：

private boolean responseTimeAnalysis() {for (int i = 0; i < taskSet.size(); i++) {PeriodicTask task = taskSet.get(i);int responseTime = calculateResponseTime(i);if (responseTime > task.getDeadline()) {return false;}}return true;
}private int calculateResponseTime(int taskIndex) {PeriodicTask task = taskSet.get(taskIndex);int responseTime = task.getExecutionTime();int prevResponseTime;do {prevResponseTime = responseTime;responseTime = task.getExecutionTime();for (int i = 0; i < taskIndex; i++) {PeriodicTask higherPriorityTask = taskSet.get(i);responseTime += Math.ceil((double)prevResponseTime / higherPriorityTask.getPeriod()) * higherPriorityTask.getExecutionTime();}if (responseTime > task.getDeadline()) {return responseTime; // 已經超過截止時間，無需繼續}} while (responseTime != prevResponseTime);return responseTime;
}

8. 實際應用中的考慮

8.1 上下文切換開銷

在實際系統中，需要考慮任務切換的開銷：

class RateMonotonicScheduler {private final int CONTEXT_SWITCH_TIME = 1; // 假設上下文切換需要1msprivate void executeTask(PeriodicTask task) {// 添加上下文切換時間currentTime += CONTEXT_SWITCH_TIME;System.out.println("時間 " + currentTime + "ms: 上下文切換(1ms)");// ... 原有執行邏輯}
}

8.2 資源共享與優先級繼承

處理共享資源時的優先級繼承協議：

class SharedResource {private boolean locked = false;private int ceilingPriority = Integer.MAX_VALUE;public synchronized void acquire(int taskPriority) {while (locked && ceilingPriority < taskPriority) {// 優先級繼承邏輯// ...}locked = true;}public synchronized void release() {locked = false;notifyAll();}
}

9. 性能優化技巧

9.1 提前終止時間需求分析

private boolean timeDemandAnalysis() {for (int i = 0; i < taskSet.size(); i++) {PeriodicTask task = taskSet.get(i);boolean found = false;// 優化：只檢查特定的時間點int t = task.getExecutionTime();while (t <= task.getDeadline()) {double demand = calculateTimeDemand(i, t);if (demand <= t) {found = true;break;}// 下一個可能的t值是當前demand的下一個整數t = (int) Math.ceil(demand);}if (!found) return false;}return true;
}

9.2 利用周期性優化調度

public void schedule() {// ... 初始檢查// 只需要調度一個超周期，因為之后模式會重復for (currentTime = 0; currentTime < hyperperiod; currentTime++) {// ... 調度邏輯}System.out.println("調度模式將在每個超周期(" + hyperperiod + "ms)后重復");
}