# Real-Time CPU scheduling

## Soft real-time system
* 會盡量完成工作，不保證

## Hard real-time system
* 所有工作都要在時間內完成

## 兩種影響效能的延遲

1. Interrupt latency

* 中斷抵達到處理的時間


2. Dispatch latency
* 把目前process移除CPU並載入新process的時間

## conflict phase
* 搶先任何在kernel中執行的process

* 低優先權process釋放高優先權process所需的資源


## Priority-based Scheduling
* 在real-time scheduling中，對優先權做排程是非常重要的

* 只保證soft real-time

* 假設process執行時間: t

* deadline: d

* 週期: p

* 若 0 <= t <= d <= p

* 頻率為1/p


## Rate Montonic Scheduling
* 短周期: 高優先權

* 長週期: 低優先權


* 這個方法有時候會錯過deadline


## Earliest Deadline First Scheduling(EDF)

* deadline越早的優先權越高


1. p1 deadline早，優先權高

2. p1 執行完換p2 執行

3. 到了下一個p1週期，此時p2 deadline = 80-50 = 30 < p1 deadline = 50

4. 因此這裡會給p2高優先權先執行完，接著換p1執行

5. 到了下一個p2週期，此時p1 deadline = 50-30 = 20 < p2 deadline = 80

6. 因此這裡會給p1高優先權先執行完，接著換p2

7. 又到了下一個p1週期 ，此時p1 deadline = 50 < p2 deadline = 80-15 = 65

8. 因此這裡會給p1高優先權先執行完，接著換p2


## 評估最適合的演算法

1. Deterministic Modeling
* 取一組固定的工作量讓每種排程演算法執行
* 最後選擇花費最少時間(waiting time)的
* 但結果只反映了在那些input cases上
* 真實情況不會有一組固定process來讓你決定演算法

2. Queuing Model
* 使用 Little Formula 的統計結果來評估
* 假設一個穩定的系統
> 離開queue的process數量 = 抵達queue的process數量
* 平均queue長度 = 平均抵達率(每秒幾個process到) * 平均 waiting time in queue
* n = λ * W

3. Simulation
* 模擬當時的環境情況並隨機產生數據來測試演算法
* 通常準確度比 Queuing Model 好

4. Implementation
* 實作

---

##### last edit
> [name=dot] [time=Mon, Jan 6, 2020 3:32 PM]

[HOME PAGE](/bKDZoNkrT9SOBnTvY_aj2Q?both) :relieved:

{%hackmd theme-dark %}
###### tags : `OS` `CSIE`