Clock-driven scheduling

tags: `RTS`

Clock-driven approaches definition

Clock-driven approach 只在 deterministic 的系統中才有用，因為她必須預先知道相當多有關 job 的資訊，只有少數符合 deterministic framework 的 aperiodic and sporadic jobs 才可以使用。

Notations

至於一般的 periodic task 限制條件如下 :

只要系統處於運算模式(operation mod)，那麼系統中就只能存在固定個數的 periodic tasks
所有 periodic task parameter 都必須在系統開始之前就取得
- inter-release time 必須要小到可忽略不計，也就是在
  $T_{i}$ 中的每一個 job 的 release time 都必須間隔
  $p_{i}$
每個 job
$J_{i, k}$ 只要一 release 就可以馬上被執行

對於符合標準的 periodic task 我們用 4-tuple 來表示其行為 :

(Φ_{i}, p_{i}, e_{i}, D_{i})

代號	意義
phase	$Φ$
period	$p$
execution time	$e$
relative Deadline	$D$

ex: (1, 10, 3, 6) : 第一個 job 在 time 1 時 release; 下一個 job 在 time 11 release; 所需最大執行時間為 3; 必須在 time 7 前完成; utilization = 0.3。

一般來說，所有的 task phase = 0 也就是一開始就可以執行，其 relative deadline 就等於 period，也就是下一個 job release 前。因此有時候會將 4-tuple 省略成 3-tuple(省略 phase) 或是 2-tuple(省略 phase + relative deadline)

Assumptions

上述有提到，符合某些條件下 aperiodic jobs (無法預測 release 的時間點)是可以被執行的，主要是因為其並不存在 hard deadline 因此只需要在 clock-driven 有空閒時去執行即可，但對於有 hard deadline 的 sporadic jobs 就不被允許使用 clock-driven approaches。此外，接下來的 approach 將 focus 在 one processor 的情況。

Static Time Driven Scheduler

clock-driven 主要是使用在存在很多 periodic job 的系統，但 clock-driven 其實也可以處理 aperiodic jobs。

Aperiodic jobs queue

在作業系統中存在一個專門儲存 aperiodic job 的 queue，所有 aperiodic job 都會被放入 queue 中，因此系統就不需要花心力在 aperiodic job 上，而是有空閒時直接從 queue 裡面拿即可。

queue order :
那麼 queue 裡的順序是怎麼排序的呢？其實是根據應用來決定，包含 priority. FIFO。

處理 periodic jobs

在 Off-line 時期會先根據 jobs 的 hard deadlines 和其他 timing constraints 建立一個 static schedule，在執行時期 scheduler 會照著該 schedule 分配(dispatch) job 來執行，而每個 job 的 processor time 會相當於他的 maximum execution time 且在系統中的 job 不存在 overrun 的情況下，每個 job 一定都會 meet deadline。

overrun : 系統在執行時期可能會發生一些意外或是錯誤導致 job 在執行時超過他的 deadline

example 1 :

Task	parameter	utilization
$T_{1}$	(4, 1)	0.25
$T_{2}$	(5, 1.8)	0.36
$T_{3}$	(20, 1)	0.05
$T_{4}$	(20, 2)	0.01

total urilization : 0.25 + 0.36 + 0.05 + 0.01 = 0.76 < 1 => 未 overrun
hyper-period : [4, 5, 20, 20] = 20
只要找出 hyper-period 後接下來只需要複製貼上這一段的排程就可以完成這一個 schedule

hyper-period : tasks period 的最小公倍數

下方為一條根據上方條件任意創造的 schedule :

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

這樣的排程中間存在著一些 not used interval，在這些 interval 的區段內 processor 處於 idle 階段其實可以拿到做其他事情 :

處理 aperiodic jobs
執行一些 response time 不太重要的背景 non real-time jobs
執行一些檢查系統健康狀況的 built-in self-test job

Table to store schedule
可以利用 table 的形式去儲存 schedule 上 processor 的狀態 :

k	$t_{k}$	$T (t_{k})$
0	0.0	$T_{1}$
1	1.0	$T_{3}$
2	2.0	$T_{2}$
3	3.8	I
4	4.0	$T_{1}$
5	5.0	I
6	6.0	$T_{4}$
7	8.0	$T_{2}$
8	9.8	$T_{1}$
9	10.8	I
10	12.0	$T_{2}$
11	13.8	$T_{1}$
12	14.8	I
13	16.0	$T_{1}$
14	17.0	I
15	18.0	$T_{2}$
16	19.8	I

Timer
系統會利用 timer 來喚醒(interrupt)接下來要處理的 job，通常 timer 會照著 entry(k) 的順序去將 timer 設為對應 entry 的 decision time(

t_{k}

)，當時間到時(expire)，timer 就會被設定成下一個 entry 的 decision time，並上一個 job 會自行中止，讓出 processor 使用權給指定的 job。

Pseudo code of schedule

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

H : Hyper-period
N : Number of entry

不斷重複執行 Hyper-period 區段的 schedule 稱為 cyclic schedule。
而利用 timer interrupt 作為驅動 job 執行的依據也就是其會被稱為 clock-driven 或 time-driven 的原因，而這一連串明確的排程也使得 clock-driven 不像 priority-driven 會有 anomalous timing behavior 的情況。

Advantage

因為 schedule 發生在 off-line 時期，因此 scheduler 計算的時間可以忽略不計，因此就可以採用精確度. 複雜度較高的演算法來獲得我們想要的排程，例如某個演算法的排程結果是會取得週期的 idle，這麼一來若選擇該 schedule 就可以利用 idle 的時間來處理 aperiodic jobs。

General structure of cyclic schedules

上面例子的那種排程稱為 ad hoc cyclic schedules，就是沒有特定週期而是隨便亂排的排程會讓每次被喚醒的時間間隔都不同，又因為 timer 是由硬體來維護，不特定(或是過短)的時間可能會造成硬體設備過多的負擔(或精細度需要調高)，因此我們希望可以找到一個 structure 將 decision time 週期化，並且需要每個週期可以拉長，也就可以節省硬體消耗。如下圖 :

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

t : 為 schedule time，代表下一次要被 wake up 的時間點
f : 為兩個 decision time 的時間間隔，而這樣的區間又稱為 frame，f 為 frame size。
改進目標 : 希望設定一次 timer 可以執行多個 jobs，而整個 schedule 的執行是不變得

scheduler 只在 decision time 時 wake up，這也意味著在 frame 與 frame 之間不存在任何的 preemption 因為 scheduler 處於 sleep 的狀態。

Frame Size Constraints

選擇 frame size 的條件 :

每個 job 都一定可以在一個 frame 中完成，也就是 frame size 必須比最大的 execution time 還要大
- 公式 (1):
  $f >= max_{1 <= i <= n} (e_{i})$
frame size 必須要可以整除 Hyperperiod(H)，也就代表在一個 Hyperperiod 中可以完整切成 frame size 的大小，才不會多出不知道如何處理的部份
- 公式 (2): …
frame size 必須小於每個 job 的 release time 和 deadline 的間間隔差，目的是希望讓 scheduler 在 wake up 時可以知道 job 是否都有 meet deadline，這的情形又分成兩種情況 :
- Job release time t' > frame t : 那麼該 job 將會在下一個 frame 才會執行且須確保該 job 可以 meet deadline，因此 deadline 必須在下下個 frame 之後 :
  $t + 2 * f <= t^{'} + D_{i}$
  $2 * f - (t^{'} - t) <= D_{i}$ 又 t' - t 一定會大於等於
  $g c d (p_{i}, f)$ 因此寫成 :
  $2 * f - g c d (p_{i}, f) <= D_{i}$
- Job release time t' == frame t : 該 job 在這個 frame 就可以開始執行，但為了確保 meet deadline，deadline 必須在下個 frame 之後 :
  $f <= D_{i}$ 但這其實已經包含在上一個條件中
- 公式 (3):
  $2 * f - g c d (p_{i}, f) <= D_{i}$

Example 1

Task	parameter
$T_{1}$	(4, 1)
$T_{2}$	(5, 1, 8)
$T_{3}$	(10, 1)
$T_{4}$	(20, 2)

規則	結果
公式(1)	$f >= M a x (1, 1.8, 1, 2) = 2$
hyper-period	$L c m (4, 5, 20, 20) = 20$
公式(2)	$F a c t o r (20) = 2, 4, 5, 10, 20$
公式(3)	僅 f = 2 滿足

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Example 2

Task	parameter
$T_{1}$	(15, 1, 14)
$T_{2}$	(20, 2, 26)
$T_{3}$	(22, 3)

規則	結果
公式(1)	$f >= M a x (1, 2, 3) = 3$
hyper-period	$L c m (15, 20, 22) = 330$
公式(2)	$F a c t o r (330) = 3, 4, 5, 10, 11, 15, 20, 22$
公式(3)	f = 3, 4, 5 滿足

frame size 的選擇不唯一

Job Slices

有時 job parameter 並無法符合上述的三個公式 :

Task	parameter
$T_{1}$	(4, 1)
$T_{2}$	(5, 2, 7)
$T_{3}$	(20, 5)

規則	結果
公式(1)	$f >= M a x (1, 2, 5) = 5$
hyper-period	$L c m (4, 5, 20) = 20$
公式(2)	$F a c t o r (20) = 2, 4, 5, 10, 20$
公式(3)	f <= 4 才滿足 => 不符合

這樣的情況下，通常會選擇將 job 切成多塊(partition)，也就是放寬公式(1)的標準，這樣的手法在網路傳輸很常見，如過大的網路封包，通常會分成多塊，分次傳輸。

用上面的例子舉例，將 execution time 最大的 (20, 5) 切成 3 個 subtasks => (20, 1). (20, 3). (20, 1) 稱為

T_{3, 1}

T_{3, 2}

T_{3, 3}

Process of constructing a cyclic schedule

建立一個 cyclic schedule 主要要考量以下三點 :

選擇 frame size
選擇 job 來切(partition)
把 partition 完的 subtask 塞進 frame 裡，且要注意一定要剛好執行完

這三項考量點彼此會互相影響，且若把 task 切的太碎，也會造成過度頻繁的 context switch 和 communication overhead，因此通常會在符合 frame-size constraints 的條件下選擇較少的 slice，但這樣的情況是非常難達成的。

Cyclic executives

儘管 arbitrary table-driven schedules 富有彈性但卻缺乏效率，主要是因為必須要有精準的 timer interrupt 且 timer 是基於每個 task 的 execution time 因此會造成相當高的 overhead。因此採用前面敘述的 cyclic schedule，其優點為 :

擁有週期性的 decision time，間隔時間為 length f
利用 list 將當下的 frame 要執行的 job 儲存下來，並且不允許 frame 之間發生 preemption
每個 task 的第一個 job 要在 frame 的一開始就被 release
- $ϕ = k * f; k 為非負整數, ϕ 為 p e r i o d i c t a s k p h a s e$
scheduler 可以容易的在 frame boundaries 時檢查 job 是否有 overrun 或 miss deadline 的情況發生
使用 periodic clock interrupt 而不需要使用特製的 programmable timer

實做 Cyclic executives

將 clock-driven scheduler 修改成其 scheduling decision 只在 frame boundaries 發生。其擁有以下特色 :

支援 multithreaded system
scheduling decision 只在 frame 的一開始發生
已經決定好 periodic task 要怎麼交錯 (interleaves) 在 processor 上執行
在 periodic task 沒使用到的 processor 時允許 aperiodic and sporadic job 使用 processor

圖為 cyclic executive on CPU 的 pseudocode

table 中有 F 個 entry，代表在一個 major cycle 中有 F 個 frame
每個 entry (k th)中都維護著該 frame 要執行的 job list
L(k) 為 scheduling block
current block 儲存馬上將被執行的一連串 periodic job
每個 clock interrupt 發生的同時 (frame 開始時) cyclic executive 會複製 table entry 中的 frame 到 current block 中
呼叫 periodic task server 來處理 current block 中的 job

在 clock interrupt 時檢查是否 overrun
- 若最後一個 job 為 aperiodic job
  - preempt 該 job
  - 未執行完的部份放回 aperiodic job queue
  - 在下次可執行 aperiodic job 時，從上次的地方繼續執行
- 若最後一個 job 為 periodic job 且還正在執行
  - frame overrun 發生了!!
  - …

當 periodic task 完成時，cyclic executive 會 wake up aperiodic jobs queue 中的 aperiodic job 來利用 periodic job 執行完後的時間執行
系統可以存在一個 aperiodic task server 目的在管理 aperiodic job 的執行

Improving response time of aperiodic jobs

上述的 schedule 是先將 periodic job 完成後剩餘的空閒時間才去執行 aperiodic job，這其實就代表著我們將 periodic job priority 視為最高，但回到最一開始的概念，提早完成 hard real-time job 並沒有任何好處，也就是 hard real-time job 只要在 deadline 前完成即可。但這樣的概念套在 aperiodic job 就行不通了，通常 aperiodic job 代表著系統中出現了一個 event 因此若 aperiodic job 可以更早被完成，也就是系統可以更早收到 event。因此最小化 aperiodic job response time 也就成為了 scheduler 的另一個目標。

Slack stealing

縮短 aperiodic job response time 在直觀的方式其實是讓 aperiodic job 在 periodic job 前就執行，那原本擁有 deadline 的 periodic job 該怎麼辦呢？就是利用所謂的 Slack stealing 的技巧。

Slack stealing
首先先將單一 frame k 中所需的所有時間加起來為

x_{k}

計算 slack time :

在 frame 的一開始 : slack (time) =
$f - x_{k}$
aperiodic job 已執行 y time unit : slack =
$f - x_{k} - y$

在 frame 開始後，會檢查 slack 只要其大於 0，就會優先執行 aperiodic job，概念大概是只要預先保留好 periodic job 的執行時間並確保其不會 miss deadline，那麼先執行 aperiodic job 也是可以的。

Slack 其實就代表著在該 frame 中剩下的 processor 空閒時間

aperiodic job	release time	execution time
$A_{1}$	4	1.5
$A_{2}$	9.5	0.5
$A_3	10.5	2

without slack stealing

aperiodic job	response time
$A_{1}$	10.5 - 4 = 6.5
$A_{2}$	11 - 9.5 = 1.5
$A_{3}$	16 - 10.5 = 5.5

Average response time = (6.5 + 1.5 + 5.5) / 3 = 4.5

slack stealing

aperiodic job	response time
$A_{1}$	8.5 - 4 = 4.5
$A_{2}$	10 - 9.5 = 0.5
$A_{3}$	13 - 10.5 = 2.5

Average response time = (4.5 + 0.5 + 2.5) / 3 = 2.5

實做 Slack stealing

計算每個 frame 的 slack 並儲存在 table 中(timer)
利用 cyclic executives 和 interval timer 持續追蹤並且更新 slack time
在開始執行 frame 後，若執行 aperiodic job 就將 timer 遞減，直到遞減到 0，就會啟動 cyclic executives 來 preempt 正在執行的 aperiodic job，並開始執行 periodic job

不過大部分的作業系統並沒有提供 sub-millisecond 等級的 interval timer，因此在實際應用上，slack stealing 的技巧只能用在精準度 hundreds of milliseconds 的 periodic task 上。

Scheduling sporadic jobs

sporadic jobs 和 periodic job 相同都擁有 hard deadline，但前者的 minimum release time 和 maximum execution time 並無法事先得知，也因此無法得知他的 priori，因此並無法保證他們都可以在時間內完成。

aperiodic job 並沒有 hard deadline 喔~~

Acceptance Test

當 sporadic job release 時，scheduler 會執行 acceptance test 來測試系統是否可以接受 aporadic job 使其不會 miss deadline 並且讓系統中原本的 aperiodic job 也不會 miss deadline，也就是說，acceptance test 是一個 scheduler 用來檢查釋放的 sporadic job 是否可以被 feasible scheduled 的機制。它會根據目前的 in system jobs 的排程檢查 frame 中是否有足夠的空閒時間來讓 release 的 sporadic job meet deadline。

in system jobs : 代表被排程好的 periodic job 或已經被排程和還未完成的 sporadic job，也就是說其代表著已經被排程且有 hard deadline 的 jobs

Example : Quality control system
在生產線上，假設輸送帶中出現一個有缺陷的零件並且必須在機械手臂封裝該有缺陷的零件前就移除該零件，因此系統就會發送一個 sporadic job 來移除零件，此時經過 acceptance test 後，假設系統無法排入 sporadic job 並且通知系統那麼就可以提早操作一些臨時措施如: 減低輸送帶的速度. 停止輸送帶. 警示工作人員並且請他的們手動移開。若 acceptance test 沒有即時告訴系統 sporadic job 會 miss deadeline，可能會造成 recovery action 太晚才開始而耗費更多的成本。

Sporadic task 的假設

其在系統中的 maximum execution time 要事先被 scheduler 知道
其必須要是 preemptable，也就是希望若在 frame 的空閒時間中無法一次做完，那麼希望在之後的 frame 中可以接續著做

Acceptance Test 流程

在 frame 的一開始(time t)就對 sporadic job 進行 acceptance test
令 sporadic job
$S (d, e)$ ;
- d => deadline 且 d 在 frame l 中又
  $l >= t$
- e => maximum execution time
該 sporadic job 必須在第 l 個 frame 就要被執行完畢
在 frame t ~ frame l 中的 slack time 總和(
$ϕ_{c} (t, l)$ )必須要大於等於 execution time
$e$
當
$e > ϕ_{c} (t, l)$ 時，scheduler 會 reject 該 sporadic job

考慮到 multiple sporadic jobs 系統在進行 acceptance test 時計算的 slack time 必須將已經加入排程的 sporadic job 也計算進去，避免新加入的 sporadic job 去影響到原本就被排程進入的 sporadic job 的執行

EDF Scheduling of Accepted Jobs

上述提到會有 multiple sporadic jobs 的情況，因此系統會透過一個 waiting queue 來維護這些 released sporadic job，並且利用 EDF (Earliest-Deadline-First) 來決定 waiting queue 中 sporadic jobs 的順序

EDF 是最好的方法的原因是 ???
是 waiting queue 跟 accepted queue 都是 EDF 嗎 ???

在 cyclic executive 中實做

psuedo code

系統中維護 3 個 queue :
- Aperiodic-job queue
- Sporadic-job waiting queue
- Accepted-sporadic-job EDF queue
主要分成 5 大部份 :
1. Check overrun
  每次在 frame 開始時，會先檢查先前的 job 是否有安全執行完畢也就是檢查是否有 overrun 得情況發生，若 overrun 發生，就通知系統並做出對應的應對方法
2. Acceptance test for sporadic jobs
  檢查 sporadic-job waiting queue 中是否為空，若不為空就取出 queue 中的第一個 sporadic job 出來接受 acceptance test，若通過就放入 accepted-sporadic-jobs queue 中照著 EDF 排序等待被執行，否則就刪除該 sporadic job 並通知系統做出對應的應對方法
3. Periodic task server
  喚醒 periodic task server 照著 currecntBlock 中的 job list 順序執行，接著 scheduler 就會 sleep 等待 currentBlock 的 periodic task 都完成或是 timer interrupt 發生才 wake up
4. Sporadic tasks
  scheduler 被喚醒後，會先檢查 accepted-sporadic-jobs queue 是否為空，若不為空，就把 queue 中的第一個 job 抓出來執行，執行完後就刪除該 job，若還有空閒時間就繼續重複 (4) 的動作
5. Aperiodic tasks
  檢查 aperiodic-jobs queue 是否為空，若不為空就把 queue 中的第一個 job 抓出來執行，執行完後就刪除該 job，若還有空閒時間就繼續重複 (5) 的動作

task 執行的先後順序為 Periodic task -> Sporadic tasks -> Aperiodic tasks

Example

Sporadic job	release time	execution time	deadline
$S_{1}$	3	4.5	17
$S_{2}$	5	4	27
$S_{3}$	11	1.5	22
$S_{4}$	14	5	44

$S_{1}$
- 在 frame 1 中 release 所以會在 frame 2 的一開始進行 acceptance test
- Deadline 在 frame 5 所以會在 frame 2. 3. 4 執行
- Total slack time = (8 - 7) + (12 - 10) + (16 - 15) = 4 < e (4.5) => reject

$S_{2}$
- 在 frame 2 中 release 所以會在 frame 3 的一開始進行 acceptance test
- Deadline 在 frame 8 所以會在 frame 3. 4. 5. 6. 7 執行
- Total slack time = (12 - 10) + (16 - 15) + … = 5.5 > e (4) => accept

$S_{3}$
- 在 frame 3 中 release 所以會在 frame 4 的一開始進行 acceptance test
- Deadline 在 frame 6 所以會在 frame 4. 5 執行
- 在 frame 3 中
  $S_{2}$ 已經執行 2 time unit，因此還須執行 4 - 2 = 2 個 time unit
- Total slack time = (16 - 15) + (20 - 19) = 2 > e (1.5) 且因為
  $S_{3}$ deadline 早於
  $S_{2}$ 若讓
  $S_{3}$ 先執行
  $S_{2}$ slack time : (5.5 - 2) - 1.5 = 2 >= remain
  $S_{2}$ e(2) => accept

$S_{4}$
- 在 frame 4 中 release 所以會在 frame 5 的一開始進行 acceptance test
- Deadline 在 frame 12 所以會在 frame 5. 6. 7. 8. 9. 10. 11 執行
- 在 frame 7 中
  $S_{2}$ 才執行完畢
- Total slack time = 4.5(remain) < e(5)=> reject

reject :
$S_{1}$ .
$S_{4}$
accept :
$S_{2}$ .
$S_{3}$
- 兩者會被放入 accepted-jobs queue
- 經過 EDF 後因為
  $S_{3}$ deadline <
  $S_{2}$ deadline，因此 deadline 會被提早執行，待
  $S_{3}$ 完成且被移出 queue 後，
  $S_{2}$ 才可被執行

Practical considerations and generalizations

主要可能遇到這三個問題

Frame overrun 的處理
Mode change
Schedule tasks on multiprocessor system

Frame overrun

發生 frame overrun 通常是以下三種情況

Input data dependent: 需要結合其他 input data，不過這些結合所需的時間並不在 recomputed schdule 時量化，因此可能造成時間被過多使用
短暫的硬體錯誤: 可能造成某些 job 執行超過預期的時間
Software flow 未偵測到 bug

針對不同的場景會採用不同的 frame overrun 方式

Overrun 的 job 的結果無效
- 在 frame 開始時直接將前一個 frame 中 overrun 的 job abort 掉，並記錄下來(log)，不過這樣可能會造成系統變成 inconsistent state，畢竟預期的 job 沒有完成，進而做一些後續的 recover，而這些操作都會對系統造成多餘的負擔。
- 將前一個 frame 中 overrun job 的 unfinished portion 變成 aperiodic job 利用 slack time 執行
Overrun 的 job 的結果有效且對後續的 aperiodic job 是可接受偶爾延遲執行的
讓 overrun 的 job (offending job)繼續執行，這樣會導致 frame 的其他 job 延後執行

Mode Changes

在原本的系統排程中新增或刪除 periodic job 導致整個系統需要 reconfigure，讓系統的 mode 需要重新改變，這就稱為 Mode Changes。而 Mode change 的發生是根據 mode change command 也就是系統管理者透過一些指令新增或刪除 periodic job，也可以視為新增了一個 mode change 的 job，需要將其安排到系統中去執行，因此其也存在 soft deadline 與 hard deadline 的分別:

Soft deadline
- 可視為 aperiodic job
- 指定要被刪除的 job 會直接被刪除並且釋放其 memory space 與 processor time
- During mode change
  - 利用 schduler 或 mode-change job 將 table 中指定要被刪除的 job 坐上標記(mark)，並在 change mode 的期間繼續保持 old schedule table 的執行，在執行 old schedule 時 scheduler 會檢查 job 是否有被 mark，若有就直接 return，等到 new table 完成並存放到 memory 後，才改成執行新的 table，且完成 mode change
  - For aperiodic jobs: 因為其本來就是 soft deadline，因此就等的 mode change 完成後再開始執行
  - For sporadic jobs: 由於其具有 hard deadline
    - 因此保證其 meet deadline 的方式是先照常執行，等到所有的 sporadic jobs 都完成後，才 mode change，不過這樣 mode change response time 會被拉的相當長。
    - 先 check sporadic job 在 new mode 中是否也可以被即時完成，若是，則就直接切換到 new mode; 若否，則就先抓出無法即時完成的 sporadic job 並等待他們在 old mode 完成後就直接切換到 new mode 中，藉此可以減少 mode change reponse time 的延遲

Psuedo code

Hard deadline
- 直接視為 sporadic job: 須接受 acceptant test，若被拒絕(reject)則延後 mode change 或是採用其他手段，在這種情況下可以直接採用上面那張圖的流程
- 視為 periodic job: 因為某些 mode change 不能被 reject，也就是一定要可以被執行，因此將其視為 periodic job。至於其 parameter 的設定如下:
  - period: 不可大於 maximum allowed response time 的一半

這塊不太懂

General Workloads and Multiprocessor Scheduling

當已知 workload parameter 的 priori 且擁有全域的 clock，那就可以直接在 schedule task 在 several processor 上執行，我們可以藉由建立一個明定在某個 processor 上應該要那什麼時間點執行哪些 jobs 的 global schedule，只要 clock drift 夠小就可以按照 global schedule 去執行 job

clock drift: 即 clock 偏移，在不同 CPU 上由於計算的硬體不同，時間久了可能會產生 clock 誤差

Pros and cons

好處
- conceptual simplicity
  - 一些比較麻煩的問題如: Complex dependencies, communication delays, resource contentions 都在建立 static schedule 時期就已經定義好了，並且可以確保不會有 deadlock 和 unpredictable delays 發生
  - 將 schedule 結果存放在保有 start time 和 completion time 的 table 中，scheduler 僅須在 run time 時按表操課
- 最小化 run time 時的問題
  - No concurrency control: mode 改變時，可以利用不同的 static schedule 來得到不同的 table
  - No need for synchronization mechanism: 不需要處理 dependency 或是 precedence constraints 的問題
  - Satisfy tight completion-time jitter requirements
- 在 frame boundary 時會去檢查 timing constraint
- 控制 frame size 的大小可以有效的降低 context switch 和 communication 的負擔，也就是藉由把 frame 調大，保證 job 可以在 frame 中完成，就可以降低 context switch 的負擔(減少 interrupt)
- 使用在 time 和 resource requirments 的變化很小的情況(就是 task infomation 幾乎不會變動)

不懂 = =

缺點
- 很脆弱: 有問題時，較難去修改，在 schdule 中新增 task 或是修改 timing constraint 就必須重新修改 schedule
- 需要固定的 release time
- 相較之下，priority-driven 只要其 interrelease time 不小於其 task period 就可以確保 job 可以完成
- 需要 on-line reconfiguration 的排程不適合
- 不適合 mix of periodic tasks 因為其無法被預測 (不懂)

Summary

Clock-driven scheduler 在 cyclic schedule 的基礎排程 periodic tasks，而其 task information (periodic task 的數量, tasks 的 parameter)必須事先就被知道，藉此可以在 off-line 的環境下排程，並將結果存在 table 中。

frame 的設置: scheduling decision time 在 frame 的開始時間，而 scheduler 在這個時間會做兩件事情: (1) 找出被 release 的 job 在接下來的 frame 中執行 (2) 檢查在上個 frame 中的 task 是否都 meet deadline 且執行完成，若有不符合上述兩點的情況，scheduler 會採取對應的 recovery action。

Aperiodic jobs: 利用 slack time 來規範在 periodic task 執行完的剩餘時間，其也表示 aperiodic job 的可執行時間，無論是在 periodic job 前或後執行都可以喔。

Sporadic jobs: 利用 slack time 來規範在 periodic task 執行完的剩餘時間，其也表示 Sporadic job 的可執行時間，和 aperiodic job 不同的是，sporadic jobs 進入排程前會先經過一個 acceptency test，另外 sporadic queue 是採用 EDF 的順序排隊。

Clock-driven scheduling

tags: RTS

Clock-driven approaches definition

Notations

Assumptions

Static Time Driven Scheduler

Aperiodic jobs queue

處理 periodic jobs

Advantage

General structure of cyclic schedules

Frame Size Constraints

Example 1

Example 2

Job Slices

Process of constructing a cyclic schedule

Cyclic executives

實做 Cyclic executives

Improving response time of aperiodic jobs

Slack stealing

實做 Slack stealing

Scheduling sporadic jobs

Acceptance Test

Sporadic task 的假設

Acceptance Test 流程

EDF Scheduling of Accepted Jobs

在 cyclic executive 中實做

Practical considerations and generalizations

Frame overrun

Mode Changes

General Workloads and Multiprocessor Scheduling

Pros and cons

Summary

Read more

2020q1 Homework1 (lab0)

Deploy nodejs server to Heroku

2020q1 Homework4 (khttpd)

Commonly Used Approaches

tags: `RTS`