---
# System prepended metadata

title: 動態優先權交換 Dynamic Priority Exchange (DPE)
tags: [Embedded System]

---

Spuri, M., & Buttazzo, G. Scheduling Aperiodic Tasks in Dynamic Priority Systems.

本篇論文主要探討關於非週期任務排程，提供五種演算法:
Dynamic Priority Exchange (DPE)
Dynamic Sporadic Server (DSS) 
Total Bandwidth Server (TBS)
Earlier Deadline First with Laxity (EDL)
Improved Priority Exchange (IPE)

非週期性任務的特點就是他的出現沒有規律可循，有可能是較緊急的事件，具有較高的優先級。

---

# **動態優先權交換 Dynamic Priority Exchange (DPE)**
DPE伺服器具有設定的容量與補充週期，每個補充週期時會把容量充滿。
1.非周期性任務會消耗容量進行任務直到完成或是容量耗盡
2.如果沒有非周期性任務，週期性任務會以EDF(最早時間截止優先)的方式進行並且交換伺服器的容量到他身上。
3.如果什麼事都沒有的話，會有閒置時間，容量會消耗直到耗盡。

![image](https://hackmd.io/_uploads/BJauhAmM0.png)

1.在t=14以前遵循著EDF的方式進行排程，週期性任務進來時會消耗容量
2.在t=14後非週期性任務進入後，持續執行
3.t=16~t18回收時間給伺服器，t=18時獲得容量補充
4.容量用盡後，T1與T2截止時間皆為t=24，以FIFO繼續執行T2

 ;
![image](https://hackmd.io/_uploads/Hk5kTR7fC.png)
當伺服器容量在某時刻減少，對應的週期性任務會被推遲執行，直到容量真正減少時才執行。**這種方法展示了在將伺服器視為普通任務時，調度的一致性和可預測性如何得以維持。**


---
# **動態零星伺服器 Dynamic Sporadic Server (DSS)** 
使用狀態機來控制任務的執行，有指定的容量與伺服器週期，但是不會周期性補充容量。
IDLE的時候才會執行週期性任務。

**IDLE->READY:**
有容量可使用時有非週期性任務進入，會進行READY狀態並消耗容量，然後在(當前時間+伺服器週期)後進行容量補充。
**READY->IDLE:**
沒有非週期性任務時。
**READY->EXE:**
伺服器具有高優先權，有非週期性任務時(白話文:有非週期性任務又有新非週期性任務抵達時)，後面來的任務會被延遲，但是會一起同時補充容量。
**EXE->READY:**
伺服器被更高優先度的任務搶占時。
**EXE->IDLE:**
任務都做完時或是伺服器容量耗盡時。

![image](https://hackmd.io/_uploads/S1dU6AQf0.png)
![image](https://hackmd.io/_uploads/B1w_TAXfR.png)


---


# **總帶寬伺服器 Total Bandwidth Server (TBS)**

為每個一個抵達的非週期性任務設定一個截止時間，
再根據EDF演算法進行週期性任務與非週期性任務的共同排程。

**截止時間dk算法:**
![image](https://hackmd.io/_uploads/SkdyR0XzC.png)
![image](https://hackmd.io/_uploads/r1wzRRXzC.png)



---

# **具鬆弛度的最早截止時間優先 Earlier Deadline First with Laxity (EDL)**
# 
在非週期性任務抵達時，把其他週期性任務壓到截止時間計算接下來所有可用的空閒時間，盡可能地讓非週期性任務越快完成提高響應速度。
演算法實際上有點難實現。

![image](https://hackmd.io/_uploads/rkIZJ1NGR.png)
假設非週期性任務在t=8秒時進入，
把後續週期性任務壓到截止時間開始計算可用的空閒時間。

![image](https://hackmd.io/_uploads/r1UNkJNz0.png)
![image](https://hackmd.io/_uploads/ByNGkyVfA.png)

**最後排程結果:**
![image](https://hackmd.io/_uploads/HkgIJ1VfA.png)


---

# **改進的優先權交換 Improved Priority Exchange (IPE)**
因為EDL的方式有點複雜，但是為降低非週期性任務的響應時間，又再提出了IPE的方法。
1.使用EDL的演算法為每個空間時間點來補充容量
2.Server的優先度最高(降低響應時間)
3.可以事先得先算好(偷跑)，存在內存記憶體中(作者的想法)。

![image](https://hackmd.io/_uploads/H17ley4zR.png)



---
平均非週期性負載:平均非週期性服務的時間/到達間隔時間
平均響應時間=T完成-T到達
![image](https://hackmd.io/_uploads/B1K5lJEGC.png)
![image](https://hackmd.io/_uploads/Hk19l1VM0.png)
![image](https://hackmd.io/_uploads/SyXjly4zC.png)
![image](https://hackmd.io/_uploads/SkQ3xJ4zA.png)
