# 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 的示意圖
上圖的 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
* 是一個 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$ 先執行


==time 1==
* $J_2$ 完成執行
* 根據 greedy 並不會允許資源閒置，因此選擇 priority 較高的 job
* 因為 $J_2$ 的完成，使得 $J_3$ 被 release 又 $J_3$ priority 較 $J_5 J_7$ 高，因此先執行 $J_3$


==time 3==
* $J_1 J_3$ 完成
* 目前的 queue 中有 ${J_4, J_7}$
* 因 $J_5$ release 未到，因此還不能被執行


==time 4==
* $J_7$ 未完成但 $J_5$ release，因為是 preemptable 所以需要先執行 $J_5$ 而中斷掉 $J_7$


==time 5==
* $J_4$ 完成，因此開始執行剩下的 $J_7$

==time 6==
* 只剩 {$J_8$, $J_6$} 未被執行
* 但其 precedence $J_7$ 還未完成，因此 idle

==time 8==
* $P_1$ 的 reponse time 為 12
* $P_2$ 的 reponse time 為 9

2. Non-preemptive
* 兩者的差別在於 ==time 4== 時，因為 non-preemptable 的關係 $J_7$ 沒有被換成執行 $J_7$，這也導致了後續的排程不同
* $P_1$ 的 reponse time 為 11
* $P_2$ 的 reponse time 為 8
* 整體的 response time 減少

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$

### 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)$ : 
* 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)$ : 

* 更精準的算法 : 考慮到 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$ 前先執行。

解法 : ==利用 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 的形式。

* $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

這種情況下，$J_k$ 不可能在 $I_1$ 的期間被執行，而這也就代表其排程本來就為 EDF。
2. $J_k$ 在 $I_1$ 之前就被 release

這種情況不符合 EDF。因此利用 ==swap== 來轉成 EDF。
首先利用 $I_1, I_2$ 的大小做區分 :
1. $I_1$ < $I_2$
將 $I_2$ 分成兩份，其中一份與 $I_1$ 相同，並將其移到前面執行。
再將 $J_i$ 的區段移到 $J_k$ 的後面執行。

2. $I_1$ > $I_2$
將 $I_1$ 分成兩份，其中一份與 $I_2$ 相同，並將 $J_k$ 移到 $J_i$ 的前面執行。
再將 $J_i$ 的還沒執行完的區段移到 $I_2$ 執行。

:::info
透過不斷重複上述的 swap，最後就可以得到符合 EDF 的 schedule
:::

因為 priority schedule 是 greedy 且 local optimal，因此不可有 idle 的情況發生，因此需要消除 idle 的部份。
* 將 jobs 往前推
* 尋找符合的 job 插入其中


### NON-OPTIMAL situations
1. Non-preemtable jobs
* 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 : 
:::success
沒 preemptable 無法排出 optimal
:::
另外這組 schedule 其實並無法被任何的 priority-driven algorithm 排程出來，主要是因為 priority-driven 採取 greedy 策略，因此不會排出有 processor idle 的情況

2. Multiple processors
* 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 : 
* 其實只要有 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。

==範例==
* $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$

* `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 - (執行中剩下的執行時間)$

* 範例中，$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
* 四個獨立(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

* 圖 (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:

* 利用 $J_2$ 的 ==execution time 3==
* $J_4$ miss deadline

* 利用 $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 的情況下發生。

* $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。

* 圖 (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)$

* 圖 (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 越好。

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 執行或是目前的執行時間。