Rate Monotonic Scheduling - ianchen0119/AwesomeCS GitHub Wiki

動機

  • 有多項任務需要處理，每個任務都有它的時間壓力。
  • 共享資源應該要能被排程

Cyclic Executive

  • 系統重複的執行固定排程
    • 類似按表操課，每個禮拜的每一堂課都是固定的。
  • 目前仍有許多系統採用這種方式做排程
    • 它的好處是：容易除錯與實現，並且有很高的確定性（因為任務數量、長度、出現頻率都是固定的）。
    • 它的壞處是：不容易修改或是更新（也就是 programmable 的程度很低）。

定義

  • hyper-period (h) 表達了任務集的 Time window，它的計算方式是取每一個任務的 period 的最小公倍數。
    • 假設： Task A(1,3) 與 Task B(2,5) 要做排程，它們的 hyper-period 就是 15，每 15 個時間單位一個 frame，每個 frame 裡面的任務順序都會是一樣的。

    Task n(c,p) p 是 period，即任務出現的頻率、c 是 computation time，即處理時間。

定理

在 time interval [t,t+x] 以及 [t+h,t+h+X] 執行的 routines 是相同的。

Rate-Monotonic Sheduling

Rate-Monotonic Sheduling (RM) 又稱 Fixed-Priority Scheduling。

  • 所有 job 繼承了 task 的固定優先權。
  • task 的優先權與 task rate 成反比。
    • 更小的 period 會有更高的 priority

Critical instant of Task

  • Task 不一定永遠趕上它的 deadline
  • 假設一個 Task T(i)，如果在 T(i) 的 Critical instant 釋出 job J(i,c)，則它會有最長的回應時間。
  • 在這個 Case 下，要趕上 J(i,c) 的難度是最大的。
  • 也就是說，如果 J(i,c) 能在這個 Case 下趕上 deadline，那之後釋放 T(i) 的 job 都能夠被順利完成。

Theorem

T(i) 的 critical instance 會在所有更高優先權的 job 與它的 job 被釋出時出現，比如說，現在有 3 個 Task，分別是：

  • Task A(1, 3)
  • Task B(3, 6)
  • Task C(2, 9)

對 priority 最小的 Task B 來說，它的 critical instance 會在 Time t = 18 時出現。

Interference

  • 對於 Ti 的第一個週期來說，它有可能會被比它要高優先權的任務干擾。
  • 至於為何要取 ceiling function 是因為任務不一定要等到下一個完整週期才會加進來。

Response time analysis

在 critical instance 的 T(i) 的 job 的回應時間可以被 recursive function 計算：

Theorem

若一個任務集 {T1, T2, T3, ..., Tn} 可以被排程，則代表該任務集當中的每一個任務的 worst-case response time 都小於它們各自的 period。

Example

Task set = {T1(2,5), T2(2,7), T3(3,8)}

For T1

  • R0 = 2 ≤ 5 (pass)

For T2

  • R0 = 2 + 2 = 4 ≤7 (pass)
  • R1 = 2 * ┌4/5┐+2 * ┌4/7┐ = 4 ≤ 7 (pass)

For T3

  • R0 = 2 + 2 + 3 = 7 ≤ 8 (pass)
  • R1 = 2 * ┌7/5┐ + 2 * ┌7/7┐ + 3 * ┌7/8┐ = 9 > 8 (failed)

Response Time 需要算到前後兩次都沒有增加為止，舉例來說：如果 R0 是 6，R1 也是 6，前後並沒有增加，那我們就能確定之後的 Response Time 不會再增加。

由於 T3 的 R1 超出時間，所以可以認定這個 Task Set 是 non-schedulable。

Proof

  • 如果 response time 於 Rn 收斂，則 first lowest-priority job 會在 Rn 完成。
  • 如果 Rn 早於 Pn，則 first lowest-priority job 會在它的 critical instance 碰上 deadline。
  • 由於 job 在 critical instance 存活下來，我們可以確保它永遠會滿足任何 task 層面的 deadline。

Time complexity

這樣的估算方法非常浪費時間，時間複雜度高達 O(n^2 * Pn)。

  • 如果任務週期很小並且相互優先時會非常慢。
  • RMA 更適合應用在 static systems。

Utilization test

我們先假設一個估量方法：

  • 如果滿足以下兩個條件，系統一定能處理這個 task set：
    • 只有一個 task
    • c/p ≤ 1，也就是說 CPU 使用率未滿
    • 超低的時間複雜度 O(1)
    • 這樣做過於悲觀

基於這個估量方式，如果更進一步去考慮多個任務的 Case，就是 Utilization Test。

Definition

1. Utilization factor Task 的 utilization factor 為 c/p。

2. 一個 task set {T1, T2, T3, ..., Tn} 的 utilization factor 為：

3. 如果 total utilization 超過 1，那這個 task set 一定不可排。

Theorem

如果滿足下方的條件，那麼這個 task set 一定能被 RMS 排程：

  • 當 task set 的 total utilization 小於 U(n) 估量的結果，那麼 task set 是一定可被 RM 排程的。
  • 時間複雜度 O(n) 是可以接受的。

當 U(n) 的 ｎ 非常大，U(n) 會非常接近 0.68：

image

Example

假設一個 Task Set = {T1(1,3), T2(2,5)}：

  • 它們的 utilization 分別為 １／３ 與 2/5，加總後為 0.73。
  • 0.73 小於 U(2) = 0.828，所以這個 task set 能被 RM 排程。

缺點

雖然 Utilization test 提供一個更高效的測試方法，但是這個方法是存在誤差的：

  • 即使 Test 告知該 task set 不可排，但是這個 task set 仍可能是可排的。
  • 因此，Utilization Test 只能保證當一個 Task set 通過測試那一定是可排程的。