--- # System prepended metadata title: Commonly Used Approaches tags: [RTS] --- # Commonly Used Approaches ###### tags: `RTS` ## Clock-driven approach 又稱為 **time-driven**，他的 scheduler 在什麼時間點要做什麼事情在一開始就決定好了，也就是在系統開始執行(**off-line**)之前 **time instants** 就被決定，也就是說，schedule 的計算是在 **off-line** 就計算好了，因此 run-time 時的 scheduling overhead 將會被最小化。而 `hard real-time` 中其參數是固定且被知道的。 通常 scheduling 採取的手段是 regularly spaced time instants，也就是必須是週期性的如: 每過一個小時鬧鐘會響起，而為了達成這樣的要求，也就必須使用 hardware timer 來設定週期性的響起(awake scheduler)，藉此 scheduler 就不需要去維護該 clock Scheduler : 1. 選擇當初被排程好，應該要被執行的 job 2. 分配 processor 和 resource 給該 job 3. 讓 job 執行直到下一個 decision time 4. 更換 job 5. 更換完後 scheduler 會將自己 block (**sleep**) 6. 等到下次 timer expiration 時，scheduler 會被喚醒(Awakes)並重複 (1) ## Weight round-robin(RR) approach 通常被使用在 ==time-shared== application。round-robin 的概念即是**輪流**，每個人使用完後換下一個，實做的方式是利用 First-in-first-out(FIFO) 的 queue，在 queue 的 head 的 job 則會被最先執行。在 round-robin 中保證公平，每個人將會使用固定的時間(time slice)，其也是一個最基本的時間單位，用來分配 job 使用 processor 或 resource 的時間，那 time slice 要如何決定呢？通常會設成數十個 milliseconds，並且會根據應用的需求來決定 time slice 是多少。 :::info time slice 選擇其實相當重要，不希望 job 在 time slice 的一開始就完成留下剩下很多的 idle，造成資源的浪費 ::: 通常 job 都無法在一個 time slice 就完成執行，因此未執行完成的 job 會被 **preepemted** 並且放回 queue 的最尾端等待下次被執行，否則可能會造成一個 job 不斷在佔用資源，其他的 job 則需要等待非常久才可被執行。另外，通常 time slice 都不會太長，因為希望每個 jobs 等待時間不要太長，就可以感覺每個 job 都是等待一下就又馬上被執行。我們假設 processor 的時間總和為 1，每個 job 得到的 processor 時間則為 ==$1/nth$==; n 為 job 的數量。也是因為上述的定義，round-robin 又被稱為 ==processor-sharing== algorithm weighted round-robin 根據不同種的 job 會給予不同的 weight，而 weight 代表 processor 給了多少的 time slice 給該 job，如: weight = wt 代表該 job 每一 round 會獲得 wt 個 time slice，而 weight 其實也代表了該 job 的重要性差異，因為透過這樣的機制可以去加快(speed) job 或延遲(retard) job 的完成時間，而這樣的技巧也常被使用在 **high-speed switched networks** 這樣的技巧雖然能讓 job 以公平且看似不斷被執行的方式排程著，但缺點是會拉長每個 job 的 completion time，一旦 task 中的 jobs 存在著 precedence constrained(一定要某些 job 完成後才可執行的 job) 就會造成大量的 processor idle 且 response time 會變得非常大 * Round-robin for pipeline 某些情況下，pipeline 可以解決 precedence constrain 的問題，下圖為兩種 time slice 下 pipeline 的示意圖 ![](https://i.imgur.com/JQr1Ljo.png) 上圖的 time slice 較小，讓 $J_{11}$ 和 $J_{21}$ 幾乎同時執行完 下圖的 time slice 較大，讓 $J_{11}$ 先執行完後，processor 2 就可以開始執行 $J_{12}$ 讓整個完成時間提前 * high-speed switched networks 使用到 **Round-robin for pipeline** 好處是收到 message 的前面一部分時，即可開始做傳輸，並不需要等整個 message 都收到後才開始進行傳輸。另外，利用 Weight RR 僅須一個簡單的 FIFO queue 就可以完成，而不需要另外使用 sorted 或 priority queue，也就是可以降低成本 ## Event-driven approach 又被稱為 **priority-driven** algorithm，其絕不會讓任何 resource idle 除非是已經沒有任何需要執行的 jobs，而這邊的 resource 包含 processor 和 passive resource，而 scheduling decision 會在 event (release of jobs occur or completions of jobs occur) 發生時發生。 * release of jobs : 代表有 job 被 release 也就是有新的 job 進來時 * completions of jobs : 代表有 job 完成時 ### Greedy scheduling 另外也被稱為 *list scheduling*, *work-conserving scheduling*，為什麼會被稱為貪婪呢？因為 priority-driven 總是希望可以 locally optimal，也就是如果有 resource 是 avable 且可以被使用，那就一定會提供給 job 使用而不會讓她等待。 ### List scheduling priority-driven 是根據優先權來決定她得執行順序，當 job 可被執行時，會被放進 queue 中，而放進 queue 中則是按照 job 的 priority 來決定，在任何一個 decision time 總是會先選擇 priority 高的 job 來執行。這也代表的其實 priority-driven algorithm 就是藉由 list of priority 來選擇 job。 ### Priority 指的是每個 job 的優先權，也就是當兩個 job 要競爭同一個 resource 時，會根據 priority 決定誰先拿到該 resource。而通常在 non-real-time system 會使用 priority-driven 因為其變動的原因較大，因此比較無法掌控 hard constrain 的完成度或是即時性，而 scheduler 會根據 `release time` 和 `execution time` 來決定其 priority * release time * FIFO(First-In-First-Out) * LIFO(Last-In-First-Out) * execution time * SETF(Shortest-Execution-Time-First) * 需要的執行時間最少，代表可以越快做完越快出去 * LETF(Longest-Execution-Time-First) * 需要的執行時間最大，就讓她越早開始時間 因為我們可以動態的去改變 job 的 priority，因此其實 round robin 也可以被視為是 priority-driven，因為 round robin 會將已經執行完 time slice 的 job 排到 queue 的最後面，也就相當於將該 job 的 priority 調到最小。 下圖是 priority-driven 的圖解 1. Preemptive ![](https://i.imgur.com/EcESdz1.png) * 是一個 precedence graph * edges 代表 precedence constrants * $J$ 旁邊的數字代表其 execution time * 除了 $J_5$ 的 release time = 5 外，其他都是 0 * 這些 job 會藉由 shared memory 進行溝通，因此可忽略 communication * 編號越小的 priority 就越高 * 所有的 job 都是 reemptable * Scheduling decision 為有 job 被 release 或有 job 完成執行的時候 ==time 0== * 僅有 $J_1 J_2 J_5 J_7$ 可以被執行 * 有兩個 processor 可以執行，因此根據 priority 選出 $J_1 J_2$ 先執行 ![](https://i.imgur.com/GhOhMDP.png) ==time 1== * $J_2$ 完成執行 * 根據 greedy 並不會允許資源閒置，因此選擇 priority 較高的 job * 因為 $J_2$ 的完成，使得 $J_3$ 被 release 又 $J_3$ priority 較 $J_5 J_7$ 高，因此先執行 $J_3$ ![](https://i.imgur.com/1N3QLSG.png) ==time 3== * $J_1 J_3$ 完成 * 目前的 queue 中有 ${J_4, J_7}$ * 因 $J_5$ release 未到，因此還不能被執行 ![](https://i.imgur.com/TKAv7QN.png) ==time 4== * $J_7$ 未完成但 $J_5$ release，因為是 preemptable 所以需要先執行 $J_5$ 而中斷掉 $J_7$ ![](https://i.imgur.com/LXTC1r0.png) ==time 5== * $J_4$ 完成，因此開始執行剩下的 $J_7$ ![](https://i.imgur.com/w5rdGaT.png) ==time 6== * 只剩 {$J_8$, $J_6$} 未被執行 * 但其 precedence $J_7$ 還未完成，因此 idle ![](https://i.imgur.com/tXMkhkT.png) ==time 8== * $P_1$ 的 reponse time 為 12 * $P_2$ 的 reponse time 為 9 ![](https://i.imgur.com/pezZ18T.png) 2. Non-preemptive * 兩者的差別在於 ==time 4== 時，因為 non-preemptable 的關係 $J_7$ 沒有被換成執行 $J_7$，這也導致了後續的排程不同 * $P_1$ 的 reponse time 為 11 * $P_2$ 的 reponse time 為 8 * 整體的 response time 減少 ![](https://i.imgur.com/59trfgl.png) 3. preemptive v.s. non-preemptive 在正常情況下，preemptive 的效果會較 non-preemptive 好，但又會在某些特殊例子下得到相反的結果，並且 non-preemptive 和 preemptive 間又找不到決定何者較優的關鍵條件。不過在 preemptive 的情況下，需要用到較多的 context-switch，也就會導致 cost 的增加，進一步來說，若 cost 小到可忽略，preemptive 基本上會比 non-preemptive 優。 * **Coffman and Garey (CoGa)** 證明了在 two processor 且 cost 可被忽略的情況下，non-preemptive 的 minimum makespan 絕不會超過 preemptive 的 minimum makespan 的 $4/3$ 倍 ## Dynamic v.s Static System ### Dynamic systems - migratable 上述 priority 的例子中，$J_1~J_8$ 共用一個 queue 並輪流到 processor 1~2 上執行的 multiprocessor system 被稱為 dynamic system，可以根據不同的 processor 狀態，動態的決定 job 要被放到哪個 processor 上執行。 * `migratable job` : 當有一個 job 在 processor 中執行到一半被 preempt 掉，再後來可被執行時，可被放到另一個 processor 上執行，則稱該 job 為migratable。eg: job from processor 1 migrates to processor 2 ### Static system 在一開始就將 job 分群到不同 prioriy 的 queue 上，而不同的 queue 就會被分到相對應的 processor 上執行，除了 job 改變或 processor 損壞... 等不可抗力，否則 job 都不可被轉移到別的 processor 上去。 * `Synchronize` : 若在不同的 processor 上執行的 jobs 具有相依性，則 scheduler 需要採取 synchronization 或 resource access-control protocol(shared memory) 來達到同步。 * `Schedule independent` : 對於 jobs 而言，每個 processor 的 scheduled 是各自獨立的 用上面的例子舉例 : * 將 job 分成兩群 ${J_1, J_2, J_3, J_4}, {J_5, J_6, J_7, J_8}$ * ${J_1, J_2, J_3, J_4}$ => $P_1$ * ${J_5, J_6, J_7, J_8}$ => $P_2$ ![](https://i.imgur.com/t6hNIUY.png) ### Dynamic v.s Static 直覺上，dynamic system 可以得到較好的 average response time，但 dynamic 的 worst-case real-time performance 常常會比 static 來的不好。且目前沒有任何的方法可以驗證 dynamic system 的 timing constrains 是否都被滿足，但 static system 卻有足夠的驗證方法，也因此，大部分 hard real-time system 大部分都是採用 ==static==，在一開始就將 jobs 分群，並且在固定 processor 上執行。 ## Effective release time and deadline job 本身有 release time 和 deadline 的 constaints，而 jobs 之間存在著 precedence constraints，而這兩者的 constraints 可能並沒有保持其一致性。 :::info **inconsistent** 今有 $J_1, J_2, J_3$，$J_1$ 執行完後才可執行 $J_2$，$J_2$ 執行完後才可執行 $J_3$。 但 $J_2$ 的 release time 可能早於 $J_1$ => 這樣並沒有意義，因為 $J_2$ 還是必須等到 $J_1$ 執行完後才可執行。 $J_3$ 的 deadline 比 $J_2$ 還來的早 => $J_2$ 的 deadline 較晚，可能導致$J_3$ miss deadline。 ::: 也因為一致性的問題，並不會去使用 job 本身的 release time 和 deadline，而是透過其他方式去取得與 precedence constaint 一致(consistent)且吻合的 effetive release time 和 deadline 作為 timing constrants。那要如何計算呢？以下是在 ==one processor 且 preemptable== 的情況下 : * Effective Release Time * 若該 job 無 predecessors，則該 effective release time = job's release time * 若該 job 有 predecessors，則該 effective release time = job's release time 和所有 predecessors' effective release time 的最大值 * 可以利用 one pass 的方式，也就是根據 precedence graph 從第一個掃到最後一個，時間複雜度為 $O(n^2)$ : ![](https://i.imgur.com/nO9UHQl.png) * Effective Deadline * 若該 job 無 successor，則該 effective deadline = job's deadline * 若該 job 有 successor，則該 effective deadline = job's deadline 和所有 successors' effective deadline 的最小值 * 可以利用 one pass 的方式，也就是根據 precedence graph 從最後一個掃到第一個，時間複雜度為 $O(n^2)$ : ![](https://i.imgur.com/KjFejCU.png) * 更精準的算法 : 考慮到 execution time * effective release time = predecessor's release time + execution time * effective deadline = successor's deadline - execution time :::info Gary and Johnson (GaJo77) : 只要 effective constraint feasible 那麼原本的 constraints 也會 feasible ::: ### Swap 在計算出 effective timing constaints 後，其實就可以忽略 job 間的 precedence constraints 並將 job 視為 independent，但這樣可能會發生問題(invalid)。原存在 precedence constraint 的 $J_1, J_3$ 的 release time 和 deadline 完全相同(2, 8)，那麼 scheduler 就可能會將 $J_3$ 排在 $J_1$ 前先執行。 ![](https://i.imgur.com/Omp6Imn.png) 解法 : ==利用 swap 的機制== 在演算法後面加入一段邏輯，若將 $J_3$ 排在 $J_1$ 後面的話，就將兩者 swap，透過簡單的 swap 機制，就可以將 invalid 的 schdule 轉換成 valid 的 schedule ## Optimality of the EDF algoritm :::info Earlies deadline first (EDF) algoritm 通常 job 的 priority 會根據其 ==deadline== 來給定，因為越快 deadline 的 job 通常需要越早執行完畢。 ::: EDF 以下情況下，就是一個 optimal 的 scheduler : * one processor * preemptive * job 之間沒有互相競爭 resource (non resource dependency) ### Theorem 在 preemptive, job do not contend for resources, one processor 且該群 job 確定存在 feasible schedule 的情況下，EDF 為 optimal > When preemption is allowed and jobs do not contend for resources, the EDF algorithm can produce a feasible schedule of a set J of jobs with arbitrary release times and deadlines on a processor if and only if J has feasible schedules. ### Proof 在任何的 feasible schedule 中，都一定可以轉換成 EDF 的形式。 ![](https://i.imgur.com/HaZqJZj.png) * $J_i$ 被 schedule 在 $I_1$，$J_k$ 被 schedule 在 $I_2$ * 原 schedule 中，$J_i$ 的 deadline 在 $J_k$ 後，但 $J_i$ 的 priority 卻比 $J_k$ 高 根據不同的 release time 分成兩種 case : 1. $J_k$ 在 $I_1$ 之後才被 release ![](https://i.imgur.com/McPkXTe.png) 這種情況下，$J_k$ 不可能在 $I_1$ 的期間被執行，而這也就代表其排程本來就為 EDF。 2. $J_k$ 在 $I_1$ 之前就被 release ![](https://i.imgur.com/MFMx695.png) 這種情況不符合 EDF。因此利用 ==swap== 來轉成 EDF。 首先利用 $I_1, I_2$ 的大小做區分 : 1. $I_1$ < $I_2$ 將 $I_2$ 分成兩份，其中一份與 $I_1$ 相同，並將其移到前面執行。 再將 $J_i$ 的區段移到 $J_k$ 的後面執行。 ![](https://i.imgur.com/PZnxYEJ.png) 2. $I_1$ > $I_2$ 將 $I_1$ 分成兩份，其中一份與 $I_2$ 相同，並將 $J_k$ 移到 $J_i$ 的前面執行。 再將 $J_i$ 的還沒執行完的區段移到 $I_2$ 執行。 ![](https://i.imgur.com/fuVgA8t.png) :::info 透過不斷重複上述的 swap，最後就可以得到符合 EDF 的 schedule ::: 因為 priority schedule 是 greedy 且 local optimal，因此不可有 idle 的情況發生，因此需要消除 idle 的部份。 * 將 jobs 往前推 * 尋找符合的 job 插入其中 ![](https://i.imgur.com/eCbSW7Z.png) ### NON-OPTIMAL situations 1. Non-preemtable jobs ![](https://i.imgur.com/RRzIwSO.png) * jobs : $J_1 J_2 J_3$ * release time : $r_1, r_2, r_3 = 0, 2, 4$ * deadline : $d_1, d_2, d_3 = 10, 14, 12$ * 在 $r_3$ 時，雖然 priority $J_3 > J_2$ 但因 non-preemptive 所以不能換 * $J_3$ miss deadline * 又其存在 feasible schedule : ![](https://i.imgur.com/UB9yBO3.png) :::success 沒 preemptable 無法排出 optimal ::: 另外這組 schedule 其實並無法被任何的 priority-driven algorithm 排程出來，主要是因為 priority-driven 採取 greedy 策略，因此不會排出有 processor idle 的情況 2. Multiple processors ![](https://i.imgur.com/9BbSn9j.png) * jobs : $J_1 J_2 J_3$ * release time : $r_1, r_2, r_3 = 0, 0, 0$ * deadline : $d_1, d_2, d_3 = 1, 2, 5$ * execution time : $e_1, e_2, e_3 = 1, 1, 5$ * priority : $J_1 > J_2 > J_3$ * time 0 時，選取 $J_1 J_2$ 執行，導致 $J_3$ miss deadline * 又存在 feasible schedule : ![](https://i.imgur.com/JB6cpop.png) * 其實只要有 priority : $J_3 > J_2$ 就可以找出該 schedule * `LST` : slack -> 0, 1, 0 -> $J_1 J_3$ 先執行 ## Optimality of the LRT algorithm :::info **Latest release time (LRT)** 又被稱為 **reverse EDF**，方式是將 release 和 deadline 交換後，並從後面開始 schedule jobs，也就是從 latest deadline 開始執行，並且使用 priority-driven manner，也就是用 assign priority 的方式。 ::: 通常 scheduling 的目標是要讓 job meet deadlines，但其實只要在時間內完成即可，將 job 提早做完並沒有任何好處。且對於某些 soft real-time job 他們的 response time 對他們來說是非常重要的，因此會透過延後 hard real-time job 的 execution time 提早執行 soft real-time job 藉此讓其可以提早完成。 :::warning 哪些時候 soft real-time job 提早完成會比較好？ ::: 上述提到 LRT 是使用了 assign priority 的方式，那麼要怎麼給定 priority 呢? ==release time 越晚的 job 其 priority 越高==，不過這樣的排程可以會造成 processor 的 idle，不符合 greedy 的策略，因此她並不是 priority-driven algorithm。 ==範例== ![](https://i.imgur.com/5HLIh4E.png) * $J_1 J_2 J_3$ * 右邊的字數代表 execution time * 區間為 (release time, deadline] * 可以看到 $J_3$ 的 deadline 為 8 (latest) * 視 latest deadline 8 為 release time 0 往回推其他 job * 根據原 release time 給予 priority -> $J_2 > J_3 > J_1$ ![](https://i.imgur.com/UgqIlML.png) * `time 8(0)` : $J_2$ ready，因此被放進 schedule * `time 7(1)` : $J_3$ ready，但 priority 低於 $J_2$，因此繼續執行 $J_2$ * `time 6(2)` : $J_1$ ready $J_2$ complete，因 priority: $J_3 > J_1$ 因此排 $J_3$ * `time 4(4)` : $J_3$ complete，$J_1$ 排進去摟 * `time 1(7)` : $J_1$ complete，排程結束。但可以看到 execution 並不是在 time0 開始，也就是說 processor 在 time 0-1 期間 idle，此舉不符合 greedy => 非 priority driven algorithm(但是符合 priority-driven manner) ### Optimal LRT 1. preemption 2. 不競爭 resource 3. one processor ## Optimality of the LST algorithm :::info **Least-Slack-Time-First(LST)** 又被稱為 Minimum-Laxity-First(MLF) algorithm，排程也是 priority-driven manner，是 slack 越低 priority 越高，也就是其需要執行的需求越急迫 ::: 那什麼是 slack ? 在 time t 且 job deadline 為 d 時 $slack (laxity) = d - t - (執行中剩下的執行時間)$ ![](https://i.imgur.com/vpzDrcV.png) * 範例中，$J_1$ 在 time 0 $slack = 6(deadline) - 0(current time) - [3(execution time) - 0(current time)]$ * 只要 job 被執行，該 job 的 slack 就不會變動 $6 - t - (3 - t) = 3$ * 假設在 time 2 時，$J_1$ 被 preempt 成 $J_3$ 並執行兩秒 * 在 time 4 時，$J_1$ 的 $slack = 6 - 4 - 1 = 1$ :::info 只有在正在執行中的 job 其 t 可抵銷，slack 固定 ::: ### Optimal LST 1. preemption 2. 不競爭 resource 3. one processor ### Compare to EDF |項目|EDF|LST| |--|--|--| |須知|deadline only| deadline and execution time for slack| |缺點|...|actual execution time 只在 job 完成時才會真的知道| 估計 execution time 時，會給定一個執行時間的範圍 $[e_i^-, e_i^+]$，通常 LST 在計算 *slack* 時，會採用 maximum execution time ($e_i^+$) 作為執行時間，來確保不會 miss deadline。另外在 sporadic 或 aperiodic job 的 *slack* 計算上，因為 execution time 較難估計，所以不好算。 ## Anomalous behavior of priority driven ### Clock-driven vs. Priority-driven Priority-driven 相較於 Clock-driven 擁有更多的優點 : 1. 較易實做 因 priority-driven 可以利用非常簡單的 priority 給定方式即可實做出來，如利用 EDF 的方式。 2. run-time overhead 低 因為只須 maintain priority queue 也就是一個儲存 jobs 的 memory 即可，因此可以壓低非常多。 3. 彈性好，容易適應變動下的條件 clock-driven 需要在系統開始前就得到相當多的 information ，如 release time. execution time 並且直接利用這些預設值去 schedule，而 priority-driven 則僅須 job 的 priority 就可以 schedule，因此若在執行過程中 timing constraints 或 require resource 有變動時，priority-driven 是擁有較大的彈性去適應這樣的變動。 儘管 priority-driven 擁有這麼多的好處，也並沒有在 hard real-time 系懂中被廣泛的應用。主要是因為其 timing behavior 是會變動的且無法被事先決定的，因此非常難去預先驗證(validate) deadline 是否有被滿足，也就是不能保證 job 不會 miss deadline。 :::info validation problem (LiHa) 在給定 jobs. jobs 可使用的 resource. scheduling algorithm 的情況下，就必須可以得知該情況是否有 job 會 miss deadline。 ::: ### Anomalous behavior validation ![](https://i.imgur.com/llQx9PP.png) * 四個獨立(indepedent)的 jobs * 在兩個完全相同的 processor 上排程 * processors 上使用同一個 priority queue * priority : $J_1 > J_2 > J_3 > J_4$ * 因為是單一 queue 可以被排程到不同的 processor 上，因此是 ==dynamic system== * preemptable * 不行 migrate，也就是 job 只能在特定某個 processor 上執行，不可被分配到另外一個執行 * $J_2$ 的 execution time 是變動的 $[2, 6]$ ==[暴力法]== 假設我們想要驗證系統是否能 1. meet 所有的 deadlines 2. 控制每個 job 的 completion-time jitter 不超過 4 > maximum completion time - minimum completion time <= 4 ![](https://i.imgur.com/zw5izUx.png) * 圖 (a) : 利用 $J_2$ 的 maximum ==execution time 6== * 圖 (b) : 利用 $J_2$ 的 minimum ==execution time 2== * completion time jitter 須逐個檢查 $J_1 = 0, J_2 = 6 - 2 = 4, J_3 = 13 - 12 = 1, J_4 = 20 - 16 = 4$ :+1: ![](https://i.imgur.com/6UmS8gZ.png) * 利用 $J_2$ 的 ==execution time 3== * $J_4$ miss deadline ![](https://i.imgur.com/D7PERiq.png) * 利用 $J_2$ 的 ==execution time 5== * 得到 best-case，因 ==max band ??== 也就是整個系統完成的時間最早 * 與圖 (b) 比較，得到 $J_4$ 的 $jitter = 20 - 15 = 5 > 4$ :-1: :::info 這樣的狀況稱為 ***Scheduling anomaly***，也就是結果與預期的不同。 1. 通常會認為 job 的 execution time 變少，scheduling 的結果也會更好，如 response time 會變少. max band??? 會變短...等，但卻出現了執行時間短，會發生了 miss deadline 的情況。 2. 通常會認為越多 processor scheduling 的結果也會更好，但卻得到更晚的 completion time。 3. 較少的 depedencios 也有相同的情況發生。 ::: 其實 ***Scheduling anomaly*** 不只會發生在 multipable processors 的情況，若 job 是 non-preemptable，那麼 ***Scheduling anomaly*** 也可能在 one processor 的情況下發生。 ![](https://i.imgur.com/VjQ6Yqu.png) * $J_1$ execution time 為 3 時 $J_3$ miss deadline * $J_1$ execution time 為 4 時 $J_3$ 卻 meet deadline 因為存在著 ***Scheduling anomaly*** 的情況，使得驗證 priority-driven 變得困難，因其 job parameter 是可變動的，且 release time 和 execution time 的變動是不可避免的，因此需要使用暴力法列出所有的可能，假設有 n 個 job. execution time 的變動範圍有 X 個，那麼必須花 $O(Xn)$ 的時間複雜度來驗證，這對於大型系統其實是非常耗時的，因此是一個相當不實際的作法。 ## Predictability of execution 什麼樣情況下的 priority-driven 具有可預測性? ### Validation 在即時系統中，希望的是排程的結果都可以 meet deadline，也就是希望每個 job 都可以在時限內被完成，那麼我們就需要去驗證(validate)該 scheduling algorithm 是否可以讓每個 job 都 meet deadline，而驗證的方式即是根據該 scheduler 排出的 schedule 的每個 job 的最大 completion time，藉此就可以得知該 job 是否有 miss deadline。當然，在不存在 ***Scheduling anomaly*** 的情況下，也就意味著這群 job 的執行狀況是可以被預測的，因此 validation problem 就會變得容易許多。以下都是在不存在 ***Scheduling anomaly*** 的前提下，去 validate schedule 的方式。 * maximal schedule : 該 job 中都利用其 maximum execution time 作為他的 execution time 去 schedule。 * minimal schedule : 該 job 中都利用其 minimum execution time 作為他的 execution time 去 schedule。 * actula schedule : 該 job 中都利用其 actual execution time 作為他的 execution time 去 schedule。 ![](https://i.imgur.com/0zytglT.png) * 圖 (a) 採用 $J_2$ 的最大執行時間作為 execution time，因此稱為 maximum schedule * 圖 (b) 採用 $J_2$ 的最小執行時間作為 execution time，因此稱為 minimun schedule * 而 $J_2$ 採用 execution time 為 2, 3, 4, 5, 6 則稱為 possible asctual schedule ### Predictability jobs 是否為 predictable 關係到 validation 的難易度，因此 predictable 是相當重要的。若 actual schedule 的 start time 和 complition time 可分別被 maximum schedule 和 minimun schedule 的 的 start time 和 complition time bound 住的話，就代表這些 job 在該 scheduling algorithm 是 predictable。 * $s(J_i)$ : 在 actual schedule 中，$J_i$ 被執行的開始時間點 * $s^+(J_i)$ : 在 maximum schedule 中，$J_i$ 被執行的開始時間點 * $s^-(J_i)$ : 在 minimum schedule 中，$J_i$ 被執行的開始時間點 * ==start-time predictable== : $s^-(J_i) <= s(J_i) <= s^+(J_i)$ * $f(J_i)$ : 在 actual schedule 中，$J_i$ 被完成執行的時間點 * $f^-(J_i)$ : 在 maximum schedule 中，$J_i$ 被完成執行的時間點 * $f^+(J_i)$ : 在 minimum schedule 中，$J_i$ 被完成執行的時間點 * ==complition-time predictable== : $f^-(J_i) <= f(J_i) <= f^+(J_i)$ ![](https://i.imgur.com/tjj4hEO.png) * 圖 (a) (b) 分別為 maximum schedule 和 minimum schedule * $s^-(J_4) = 2$, $s^+(J_i) = 6$ * $s^-(J_4) <= s(e(J_2) = {3, 4, 5}) <= s^+(J_4)$，因此 $J_4$ 為 start-time predictable * $f^-(J_4) = 20$, $f^+(J_i) = 16$ * $f^-(J_4) <= f(e(J_2) = {3, 4, 5}) <= f^+(J_4)$ ==不成立==，$J_4$ 不為 completion-time predictable :::info 當 job 同時為 start-time preditable 和 completion time predictable 時，稱該 job 為 predictable。 若全部的 jobs 都是 predictable 代表其 execution behavior 皆為 predictable，而該系統也為 predicatable。 ::: 因此該系統不為 predictable ### Predicatable 的條件 1. job 間彼此獨立 2. preemptable with fixed release time 3. one processor 這也就代表著在上述條件下的 priority-driven 容易被 validate，也因為所有 job 的執行行為都是可預測的，因此我們可以忽略 execution time 可能的變動，僅利用 maximum execution time 作為 execution time 來得到 maximum possible response time。反之，只要違反任何一項條件，該系統即為 unpredictable 而不好被 validate。 --- ## Validation algorithm validation algorithm 是一種用來判斷系統中所有的 jobs 是否符合其 timing constraints 的演算法，若該 validation algorithm 判定該 schedule 為可行就真的可行，就其稱為 correct validation algorithm。雖然對於 static system 的 validation algorithm 已經發展的相當成熟，但對於 dynamic, priority-driven systems 還不夠成熟，主要是因為 static 的 job 在執行前就已經確定好，因此相對於其他種，他的變化性與排程的異常現象存在都比較少。 ### 效能指標 validation algorithm 不只要求正確更要求效能上的成果，而效能主要可以由下方三個方面去評斷 * `Complexity` * `Robustness` : 即使 workload model 有一些缺陷(not valid)，該 validation algorithm 仍然能保持 correct，就稱其為 robust。 :::success 一般來說，根據所有在 workload model 中的假設都為 valid，才稱該 algorithm 為 correct。 ::: :::info 不過在給定一些錯誤的 workload model 的情況下，還能得到正確得結果也就意味著該 algorithm 對於 run-time environment 的要求並不是那麼精準。那麼什麼叫做 not valid workload model 呢？假設 job 皆為週期性且執行時間固定，不過現實中卻存在著像 release-time jitters 或 variation in execution time 的微小變化，那該 validation algorithm 可否應付這件事情，也就代表的其 robustness 的指數。 此外我們要衡量時，其實只需要計算出 worst case，若 worst case 為 valid 即所有情況都 valid，至於取 worst case 的方法，通常是取一些變動的極值如 : minimum inter-release time 或 maximum execution time。 ::: * `Accuracy` : 即精確性，當 correct validation algorithm 宣稱該 schedule 不可行時，該 schedule 是否就真的不可行呢？若其實可行，就代表該 validation 雖然為 correct 卻 inaccuracy。這樣的情況發生可能是因為使用的 algorithm 過於嚴謹又或者說是過於悲觀，才導致實際可行的 schedule 被判斷為不可行。過於 inaccurcy 的 algorithm 也被認為是效能差，因為實際可以多接受 job 卻因為錯誤的判斷導致少執行到的這些 jobs。 :::info 若基於 periodic task model，擁有精準的 digit control...等 => well accuracy 基於大範圍變動的 processor-time damends 和 release-time jitter => poor accuracy ::: :::success accuracy 和 robust 間存在負相關 : 給定的條件較鬆散 => robust (上升) accuracy (下降) 給定的條件較嚴謹 => robust (下降) accuracy (上升) ::: 若 validation algorithm 可以在此三項效能評比得到平衡，而不是某項高某項低，那就稱其為 ==good validation algorithm==。 --- ## Online vs Offline scheduling ### Off-line scheduling 在系統開始之前，就已經根據 job 的 release time. processor time. resource requirement 做好相對應的計算與分配，這樣產生的 schedule 就稱為 ==off-line schdule==。若系統的 operation mode 改變，那麼就會採用利用新的 mode 去重新計算出的新的 schedule。 * Disadvantages : off-line scheduling 有個很明顯的缺點，即是 ==inflexibility==。主要是因為系統必須要 deterministic，也就是 job 的 demands 都必須是知道的且不能改變 * Advantages : 演算法所需的時間複雜度就變得不是那麼重要，因為計算都是發生在執行之前 ### On-line scheduling job 的相關資訊(parameters)只在 job release 後才得知，也就是說 scheduler 在排程時，並不需要知道 jobs 的 parameter，而是會根據目前遇到的狀況進行排程。 **An acceptance test** : 系統運行中，已經有既定的 jobs 在執行，那若有一個新的 job 要加入系統，會利用一個測試判斷是否會跟既有的 job 產生 conflict，該測試就稱為 **An acceptance test**。 ### Trade-off 在 workload 是 unpredictable 的情況，通常會採用 on-line scheduling，因為上面提到 on-line scheduling 是可以忍受 job demand 與 resource available 的 dynamic variation，不過 on-line scheduling 並無法對系統得到最佳的 resource 分配，因為她並不知道未來的情況 : Eg: non-preemptive $J_1$ release time = 0, execution time = 1, deadline = 2. * 在 time 0 就進行 schedule $J_1$ 在執行期間加入一個 $J_2$ release time = 0.3, execution time = 0.7, deadline = 1，由於 $J_1$ 為 non-preemptive 因此 $J_2$ 一定會 miss deadline，不過如果預先知道 $J_2$ 的情況，就可以預先做到最佳的排程，也就是讓 $J_2$ 先執行，$J_1$ 則在 time == 1 時再開始執行，藉此就不會 miss deadline * 在 0 < time x < 1 就進行 schedule $J_1$ 假設在 x 時，$J_3$ 剛好被 release, execution time = 1, deadline = 2，那麼在 schedule 時就會不知道該先讓 $J_1 or J_3$ 執行，因為一定無法同時 meet deadline 上述兩個例子也就說明，因為對未來的不可預知(job 的 timing constranints 等)，所以不管採取怎樣的策略都可能造成後面的 jobs miss deadline。 :::info 只要有 job 為 non-preemptable，on-line scheduling alorithm 就無法得到 optimal 的結果，換句話說，就是說只有當 jobs 皆為 preemptable 且 one processor 的情況下 on-line algorithm 才存在 optimal 如 : EDF. LST。 ::: ### System overloaded 指系統無法照著 schedule 執行。因此無論 schedule 多好只要 system overloaded 發生就無法照著預期的情況運行。而當 overload 發生時，最常使用的方式就是直接丟棄某些 job，藉此可以讓其他 job 在 timing constraint 前完成。至於在發生 overload 的情況下，要如何評量一個 scheduling algorithm 的效能呢？那就是在這樣的情況下來能夠排多少的 work(value of a job)，能排越多 work 也就代表該 scheduler 越好。 ```c value_of_job = (job_meet_deadline) ? execution_time : 0 value_of_schedule = sum_of_all_jobs ``` value of schedule 越高，就代表該 scheduler 越好，若該 scheduler 的 value 為 maxmium 的話，又稱該 schedule algorithm 為 optimal。在 system overloaded 的情況下，我們就會使用 maximum possible value 作為 schedule value。 :::info 在 system overload 和沒有 overload 下的 optimal 定義並不相同喔～ ::: ### Competitive factor c c 就代表著 on-line algorithm 的 value of schedule 是 off-line algorithm 的 value of schedule 的多少倍。 $c = \frac{value of schedule(on-line)}{value of schedule(off-line)}$ 因此若是在 `preemptable`. `one processor`. `resource independent`. `system not overload` 的情況下，c = 1; 反之若 system overload， c = 0。 ### Therorem 在 system extremely overload (很嚴重)的情況下，沒有 on-line algorithm 的 competitve factor 可以超過 ==0.25==，即便只是輕微的 overloaded(Slightly overloaded)， competitive factor 最多也無法超過 0.385。 因此若要使用 on-line algorithm 最重要的即時維護系統，防止系統發生 system overloaded，也因此若系統一定要接受和處理大量的 jobs，就必須不斷選擇哪些 job 可以丟棄，不斷的丟棄直到系統不會 overload。至於如何選擇要丟棄的 job，不是看 timing parameter 之類的，而是要根據 job 的重要性，又稱 critical factors，這邊的考量因素其實非常多，包含該 job 是否會影響後續的 job 執行或是目前的執行時間。