4 Rate-Monotonic Scheduling是否schedulable

admin

如何判斷Rate-Monotonic Scheduling是否schedulable?

1.Response time analysis
2.Utilization bound

Response time analysis
響應時間分析是一種確定任務是否能在截止時間前完成的方法。其基本思想是計算每個任務的最壞響應時間（Worst-case response time, WCRT），並確保其小於或等於該任務的截止時間。

在RMS中，響應時間分析通常遵循以下步驟：
1. 對於每一個任務，首先假設它的響應時間就是它的執行時間。

2. 然後，為了考慮可能的干擾，將高優先級任務的執行時間加到響應時間中。

3. 如果在一個循環中，響應時間沒有增加，則算法停止。如果響應時間大於截止時間，則任務集不可調度。



Utilization bound
在RMS中，利用率界限是一種快速但保守的檢查可調度性的方法。它基於的觀察是，一個可調度的任務集的CPU利用率有一個上界。

對於n個任務的任務集，該界限可以計算為 n*(2^(1/n) - 1)。如果任務集的CPU利用率超過這個界限，那麼該任務集可能不可調度。但如果CPU利用率在此界限之下，那麼任務集一定可調度。這種方法的缺點是，有些任務集的CPU利用率可能超過界限，但實際上仍然可調度。

值得注意的是，這兩種方法都有其局限性。響應時間分析需要知道所有任務的確切參數，並可能過於保守。而利用率界限可能會過於悲觀，因為它可能會排除一些實際上可調度的任務集。