# RTOS
## LABs
### RM
* compTime 紀錄執行多久
* OSTimeTick 讓 `compTime --`
* 需要 OSTimeDly 的時間: `period - (end - start)`
* OS_Sched() is called when a task is voluntarily giving up its possession of the CPU
* Complete
* OSIntExit() will manage the scheduling after the system has come back from the calling of ISR
* Preempt
### EDF
* 多加 deadline
* period, compTime, deadline
* OSPrioHighRdy 選擇用 deadline
* OS_Sched() 和 OSIntExit()
* linear seach
### CPP
* Resource priority 實作時假設最高
* OSMutexPend 和 OSMutexPost
* `cpp = (INT8U)(pevent->OSEventCnt >> 8);`
:::warning
* PIP 有 deadline & blocked multiple times 問題
* 但排程時不需先知道 resource usage
:::
___
## Independent Scheduling
### Cyclic Executive
* static schedule(table-driven approach)
* highly deterministic
* hard to modify
* hyper-period(h) : least-common-multiplier of the loop length
* **\[t, t+x\]** is executed => **\[t+h, t+h+x\]** is executed
  p.12 p.13
* A **task(c,p)** is a template of **jobs**
* share nothing but CPU
* computation time is bounded and known a priori
* relative deadline = period
* jobs of the same task may have same or **different** priority
* ready HPT preempts the current task(LPT)
:::warning
schedulable <-> feasible : **universal scheduling algorithm**
:::
___
### RM
Rate-Monotonic Scheduling
* cxtsw overhead : preempting job **+2x** => **(c+2x, p)**
* 短週期 **preempt** 長週期
:::success
**Response time analysis(RMA)**
* **critical instance** : check whether longest response time satisfy its deadline
* recursive compute
* need to test **every** task for schedulability
* pseudo-polynomial time **(high complexity)**
* 適合 offline, 固定工作的 **(not in dynamic systems)**
* **exact schedulability test**
* p.25
:::
:::info
**Liu & Layland Test**
* lowest achievable utilization
* all c/p <= U(n) = n(2^1/n - 1)
* n infinitely large, U(n)->**0.68**
* complexity : O(n)
* **sufficient** condition (but **not necessary**)
* succeed => schedulable, fail=>**we know nothing**
* p.39
:::
* fixed-priority scheduling
* optimal for fixed-priority scheduling
* decide task set's schedulability is costly
* O(1) job insertion is possible (用表記 job 對應 priority 位置)
* Overload survivability : **High and predictable**
* easy implementation
:::warning
**Arbitrary task priority assignment**
* schedulable by **fixed-priority** scheduling with **arbitrary** priority assignment
=> schedulable by **RM**
* **not** applicable of utilization test
* **RMA** still can use
**Harmonical chain**
* **period** 有**倍數**關係
* task period can be divided by shorter task period
* **small n** can use in **U(n)**
* p.71
:::
___
### EDF
Earliest-Deadline-First Scheduling
* priority change from time to time => **urgency / importance**
* no idle time before an overflow
* cxtsw overhead : preempting job **+2x** => **(c+2x, p)**
* 短週期 **preempt** 長週期，長週期 **delay** 短週期
:::info
**Utilization Test**
* schedulable <-> total CPU utilization no more than 1
:::
* ungency of tasks is dynamic
* **universal** for **periodic** and **preemptive** **uni**processor systems
* O(n) for exact schedulability test
* Both job insertion and dispatch take O(log n) time
* Overload survivability : Low and unmanageable
* relatively complicated implementation
:::warning
* EDF is **not** optimal to **non-preemptive** tasks
-- if non-preemptive => critical instance 不存在
* EDF is **not** optimal for **multiprocessor** scheduling (without task migration)
-- **X**分配 by EDF (可分配好後，在uniprocessor排程)
:::
___
### Least-Laxity First(LLF) / Least-Slack-Time
* **laxity** : 目前到deadline時間 - 目前剩餘execute時間
* universal to periodic, preeemptive tasks
* **highly frequent context switches**
* 適合 packet-based scheduling (ATM)
* p.65
___
### Cycle-Based Scheduling (Frame-based scheduling)
* For **I/O** (usb1.1, camera, audio)
* use time frame to service **isochronous** request
* request sizes should not exceed the capacity of one time frame
* **same period** (frame size)
* care about **bandwidth**
  **X** CPU scheduling
  -- context switch overhead 沒考慮
  -- tick(硬體時鐘)有極限
___
## Resource Synchronization Protocols
### Synchronization
* To avoid race condition
* To avoid deadlocks (RTOS必須處理否則會miss deadline)
* To manage priority inversion
* **X** Non-preemptible scheduling
* **X** Cyclic executive or frame-based scheduling
### Resource
  **passive** : busy on the CPU (not suspend on the CPU)
  e.g. semaphore-protected data structure
  active : suspend on the CPU
  e.g. I/O, GPU
  lock attempt may not be granted immediately
  unlock is effective immediately
  critical section : properly nested
  resource contention increase task response time
### Priority inversion
  A high-priority job can not run because of the interference from low-priority jobs
  high priority job tries to lock a resource that is currently locked by low-priority job
* high-priority job is blocked
* low-priority job is preempted
* indirectly blocked : uncontrollable priority inversion
**Timing analomies** (CPU更好，反而miss deadline) p.14
**Deadlock**
___
### NPCS
Non-preemptible Critical Section
  equivalent to interrupt disabling or scheduler locking
  blocking time: max i+1<=k<=n (Sk)
* avoid deadlock
* bounded block time(at most once)
* avoid uncontrollable priority inversion
* no need to know resource usage a priori
* poor response (LPT always blocks HPT)
* HPT may be blocked even if no resource contention
___
### CPP
Ceiling Priority Protocol / highest-locker protocol
  when task lock R, its priority is boosted until it unlock R
  blocking time: boost >= itself, 挑priority小於自己的最大 p.27
* avoid deadlock
* bounded block time(at most once)
* avoid uncontrollable priority inversion
* **need** to know resource usage a priori
* better reponse than NPCS
* HPT may be blocked even if no resource contention (lower degree)
___
### PIP
Priority Inheritance Protocol
  when blocks, inherit priority
  **inheritance** -> no uncontrollable priority inversion
  chain blocking & transitive blocking
  block time : min(v,k); number of required resources & number of LPT
* **deadlock** (hold and wait)
* avoid uncontrollable priority inversion
* multiple blocking
___
### PCP
Priority Ceiling Protocol
  all tasks have unique and fixed priorities (**RM**)
  resource ceiling & system ceiling
  **ceiling** -> no deadlock & only block once
  **lock** (inherit) : **R is not available** or **prio not > system ceiling**
  **postpone a resource request even if available (system ceiling)**
* direct blocking
* priority inheritance blocking
* priority ceiling blocking (avoidance blocking)
  ceiling : manage locking
  priority : manage scheduling
  p.54
  schedulable : c1/p1 + c2/p2 + ... + cn+bn/pn <-> U(n)
  (for NPCS, CPP: 相同但blocking time較長)
  CS=4 if b!=0 / CS=2 if b==0
* avoid deadlock
* bounded block time(at most once)
* avoid uncontrollable priority inversion
* **need** to know resource usage a priori
* a task may be blocked in the middle of execution
* check system ceiling on locking
___
### SRP
Stack Resource Policy
  In **EDF**, shorter period jobs can only be blocked by longer period
  A task cannot **execute** until its preemption level is high than current system ceiling
* preemption level(跟週期呈反比) -> for ceiling
* deadline -> for inheritance & scheduling
  schedulable : b/p + all c/p <= 1
  CS = 2 (**saves up 2 context switches**)
* avoid deadlock
* bounded block time(at most once)
* avoid uncontrollable priority inversion
* response of HPT is bad, compared to PCP
* task will not be blocked once it starts execution
* check system ceiling on scheduling
* LIFO, all tasks can share one execution stack for memory saving
___
## Aperiodic Job Scheduling
### Handling Aperiodic Jobs
**Periodic Tasks :**
**Aperiodic Jobs :**
* Assigned to either ++no deadline++ or ++soft deadline++
* Accept anyway
* Minimal job response times (in a best-effort fashion)
**Sporadic Jobs :**
* assigned to ++hard deadline++
* Accept them if their deadlines can be satisfied, otherwise reject them
* No accepted jobs miss their deadlines
<br>
Server size : a fraction of CPU time reserved for the server
Server budget : a server is ready to execute when budget is nonzero
Backlogged : there are some ready jobs in its queue
Eligible : a server is eligible if it has budget and is backlogged (server is scheduled)
Budget consumption rules :
Budget replenishment rules :
___
### Brute-force methods
**Background execution** : poor response time of aperiodic jobs
**Interrupt execution** : may damage the schedulability of periodic jobs
=>improvement : **Slack Stealing**
easily implemented in **LSF**, hard to implemented in **EDF** or **RM**
___
### Polling Server
* **RM**, **EDF**
* **purely periodic jobs** that serves a queue of aperiodic jobs
* If the queue become **empty**, **suspends immediately** (=> lose all budget)
* p.17
* improvement: Bandwidth-preserving server
___
### Deferrable Server
* **RM**, **EDF**
* Budget is comsumed at a rate of 1 when the server is serving aperiodic jobs
* If server isn't serve, it don't consume the budget
* Budget set to **c~s~** at **k*p~s~**
* p.25, p.26
* **double hit** : interfere low-priority tasks (critical instance 需要考慮它)
* aperiodic task response 很好
* simple consumption/replenishment rules
* complicated schedulability test
:::success
**Response time analysis(RTA)** => for **RM**
* 加上 c~s~ + ceil( R-c~s~ / p~s~ )* c~s~ (考慮 **double hit** )
* p.30
:::
:::info
**Revised Utilization Test** => for **RM** & **EDF**
**RM**
* Test **U(m+1)** with m high-priority tasks and DS first
* low priority 要加上 **c~s~** 個別和 U(m+2)...U(k) 比對
* p.35
**EDF**
* all c/p + **c~s~/p~s~ (1 + p~s~-c~s~ / p~s~)** <= 1
* p.41
:::
___
### Sporadic Server
* **RM**
* never demand processor time more than a periodic task (c, p)
* schedulability test is still **same** => (RTA or U test)
* **preserve budget as long as possible**
* **replenish budget as long as possible**
* simple schedulability test
* complicated consumption/replenishment rules
simple sporadic server
* HPT 執行時 : budget 平的
* server, **LPT**, **idle** 執行時 : budget 下降
* 離開 idle : 補 budget
* 往前到 HPT 到達 : 開始算 period (replenish提前)
* p.50, p.51
* p.52
Sprunt sporadic server
* **LPT**, **idle** 執行時: budget 不下降(平的) => **split**
* 離開 idle : 補滿 budget => **merge**
* p.57
:::warning
**meet deadline?**
* first job: floor( d-r / p~s~ ) * c~s~ - c~1~ >= 0
* others : floor( d-r / p~s~ ) * c~s~ - c~i~ - remaining execution of HPT >= 0
     check LPT (after deadline d~i~) one by one
:::
___
### Priority-Exchange Server
* T~L~ borrows time from T~s~ (借 server priority 執行)
* T~L~ pays its debts to T~s~ (還 T~L~ priority 執行)
* conceptually simple, implement hard
___
### CUS / TBS
Constant utilization server / Total bandwidth server
* **EDF**
* **all density <=1 at any time -> schedulable by EDF**
* open system (applied to VM)
Constant utilization server
* A server comsumes its budget when it is serving budget
* replenish its budget at job deadline (arrival + c /server_size)
* period 不能疊到
* p.72
Total bandwidth server
* A server comsumes its budget when it is serving budget
* replensish its budget when arrival
* job dealine at max(deadline, arrival) + c /server_size
* budget 可以提早補, deadline不變
:::warning
**meet deadline?**
* deadline assigned by server algorithm <= the deadline of sporadic jobs
:::
___
## Multiprocessor Real-Time Scheduling
### Mutilprocessor Model
#### Identical(Homogeneous) processors
* made of the same hardware
* same clock rate
#### Uniform processors
* made of the same hardware
* differnent clock rate (since support DVFS)
#### Unrelated(Heterogeneous) processors
* different ISA (eg. CPU + DSP)
* processor maybe execute one job faster, another job slower than other processors
___
### Global Scheduling
* allow **job migrate** among processors whenever necessary
* global ready queue
* good processor utilization
* unused processor time can be reclaimed during runtime for soft RT tasks
* uni-processors result cannot be extended
* **Scheduling Anomaly**
* Migration overhead (cache re-population & pipeline stall)
:::success
**Scheduling Anomaly**
* relaxing task period (reduce task computation) p.13
* Dhall's Effect (feasible but not schedulable by global-EDF/RM) p.14
:::
For Global-EDF
* use idle processor or preempt farthest deadline => avoid shuffling
:::info
**Schedulability Test**
for M processors using preemptive global-EDF
* all C/T <= M(1- Ck/Tk) + Ck/Tk   where Ck/Tk is the largest utilization
:::
___
### Partitioned Scheduling
* **no task migration** is allowed
* per-processor ready queues
* If all processors' capacity not exceed 100% => schedulable by EDF
* may have **low utilization**, bounded by 50% (worst case 很差)
* cannot reclaim unused processor time
* most uni-processor techniques are applicable
* **first-fit**, **best-fit**, **worst-fit**
For Partitioned EDF-FF
:::info
**Schedulability Test**
for EDF scheduling and First-Fit allocation
* all C/T <= (*beta*\*m+1)/(*beta*+1)   where *beta* = floor(1/u) of largest utilization
:::
___
:::warning
Global v.s. Partitioned => **incomparable**
* {t1=(2,**3**), t2=(2,4), t3=(8,12)}
=> Global能排, Partitioned不能排
* {t1=(2,**4**), t2=(2,4), t3=(8,12)}
=> Partitioned能排, Global不能排
:::
___
### Semi-partitioned Scheduling
* limited on-line job migration
* execution of a split task is only possible in **reserved time window** in time slot
* the rest of time is scheduled by EDF on each individual processor
* reserved time window => 保證 procedure constraint (留了沒使用, utilization損失)
Sign in with Wallet
Connect another wallet