# Priority Inversion
ref:
A complete guide for RTOS
## 什麼是 Priority Inversion
在 real-time OS 中，由於低優先權任務正在 access shared resource 且高優先權任務也需要該 shared resource，導致 高優先權任務需要等待低優先權任務。

下圖為一個 priority inversion 經典例子:


當 MP 出現前，一切的行為都是正常且符合預期的，然而 MP 的出現就有可能導致 priority inversion
## 影響
1. Missed deadlines: 高優先權任務可能無法在deadline前完成，造成系統效能降低。
2. Reduce system predicatability: 由於高優先權任務無法預期的等待時間，導致整體系統行為較無法預期。
4. Potential system failure: 在 crtical system，延長高優先權任務的等待時間可能導致系統錯誤失敗。

## 怎麼避免 Priority Inversion
下面是幾個常用來避免 priority inversion 的方法，但不保證 100%!.

## Non-preemptible Critical Section(NPCS)
如果一個 task 正在使用 shared resourced, 那它就不會被 preempted(disable interrupte/disable scheduler), 即使沒有 resource conflict.


原本高優先權任務要在第 12 秒才完成，採用 NPCS 後變成在第 10 秒就完成。

### Pros:
* Deadlock 永遠不會發生，因為任何持有共享資源的 task 都不會被 preempted.
* Ease to implement.

### Cons:
* 較低的 concurrency, 因為沒有其他 task 可以打斷.
* Poor responsiveness.

## Prioriy Inheritance Protocol
當 task A 準備要使用 shared resources 時，如果該資源正在被 C 使用，則比較 C 與自己的優先權大小，如果 A 的優先權比 C 大，就把 C 的優先權提升到與 C 相同，等到 C 釋放資源再恢復成原本的優先權。

詳細過程如下圖:


規則:


可能發生 Deadlock

### Pros:
* Simple and high concurrency and responsiveness
### Cons:
* Deallock may happen
* Blocking time is not well managed

## Priority Ceiling Protocol
目的在解決前面 PIP 存在的一些問題。
假設每個 task 的優先權都不同且固定，當一個 task 需要使用 shared resources時，就把該 task 的優先權提升到所有可使用該資源的最高優先權。

同一個 task set 使用 PIP 和 PCP 差異:
PIP:

PCP:

### Pros:
* More efficient than PIP, because priority be changed only one time.
* 不會發生 deadlock

### Cons:
* 比較容易影響其他任務的完成時間，因為優先權一次被提升到最高.

## Others
當任務數量多且每個任務都有不同的優先權，則建議使用 Mutex 替代 binary semaphore. 大部分的 RTOS 中的 Mutex 都有內建 priority inheritance 功能，可避免或降低 priority inversion 的影響。下圖為引入priority inheritance 後的行為:

### Ref:
https://blog.csdn.net/sinat_27421407/article/details/78837425

## 問題與觀念解釋

根據 NPCS，允取 Preemptive 機制下才會發生 Priority Inversion，因為優先權較高的等待低優先權存取的是「資源」而非順序，若需要的資源在 CS 內就不能隨便搶，如果不允取 Preemptive 那麼高優先權的任務就不會等待這麼久。