Real-Time Embedded System 心得(1): Priority Inversion

以前雖然有接觸過 RTOS，但僅限於紙上談兵、淺嘗則止的階段，這兩年朝夕相處總算有了些實戰經驗(作到產品可以送樣出貨)。未來可能不再碰這方面的東西了，趁印象鮮明時趕緊寫幾篇文章紀錄一下心得。

Priority Inversion

中譯為優先權反轉或優先權倒置，在 MicroC/OS-II The Real-Time Kernel 2nd - 2.16 Priority Inversions 開頭就很清楚的告訴讀者：

Priority Inversion is a problem in real-time systems and occurs mostly when you use a real-time kernel.

甚至連科幻小說火星任務也拿來當梗：

「我們檢視了拓荒者號的軟體，將它複製到電腦上，進行了一點測試，就是他們之前用來測試計畫卻差點毀掉任務的那幾台電腦。其實很有趣，原來逗留者號作業系統的執行緒管理是採用優先權倒置機制...」

另外不能忘了提大神 jserv - Priority inversion 簡介

所以 Priority Inversion  說是 RTOS 中最重要的觀念也不為過。這邊筆者直接借用書中 Page.46 Figure 2.7 講解:

 

註：Task 1(H) priority >  Task 2(M) > Task 3(L)

(1) Task 3 正在執行，而 Task1,2 正在等待某個事件發生(例如 semaphore, event flag, timer...)。

(2) Task 3 為了存取共享資源，必須先獲取 (binary) semaphore(也可想成 mutex)。

(3) Task 3 使用共享資源(灰色的部份)。

(4) Task 1 等待的事件發生了(最簡單的事件如 delay n ticks, 而 delay 結束了)，OS kernel 暫停 Task 3 改執行 Task 1，因為 Task 1 有更高的 priority。

(5)(6) Task 1 執行一段時間直到他試圖存取與 Task 3 共享的資源，但 semaphore 已經被 Task 3 取走了，Task 1 只能等待 Task 3 釋出 semaphore。

(7)(8) Task 3 恢復執行，直到 Task 2 因為某事件被喚醒(如(4) Task 3)

(9)(10) Task 2 收工後，將 CPU 讓回給 Task 3

(11)(12) Task 3 用完共享資源後釋放 semaphore。OS kernel 知道還有一個更高 priority 的 task(Task 1)正在等待此 semaphore，執行 context switch 切換到 Task1。

(13) Task 1 取得 smaphore，開始存取共享資源。

Task 1 原本應該是 priority 最高，但這麼一折騰下降到跟 Task 3 一樣的水平，看起來反到是 Task 2,3 priority 比較高，priority 被顛倒了，這就是 Priority Inversion(優先權反轉)的由來。

Priority Inversion 案例

Priority Inversion 會有什麼嚴重影響?這邊舉一個具體案例，筆者之前曾經發表過一篇 "SPI to Ethernet Driver for RTOS"，當時 IP packet 傳送給 Ethernet Task 是採用 IPC 的方式：

看起來用 FIFO(ring buffer) 是聰明選擇，但在很多 time critical 應用中，FIFO 會變成延遲跟不確定性的來源(這需要另外寫一篇說明,只能說FIFO水很深...)。另外這種 IPC 的方式通常慢於直接對硬體讀寫(因為還要 OS 介入進行 context switch)。

如果我們要直接寫入硬體，比方說上面的 Tx Ethernet Frame 直接透過 SPI 寫到 ENC28J60 內的緩衝區裡，那就必須把 SPI bus 當成共享資源，用 binary semaphore or mutex 加以保護，否則就會與原本的 SPI to Ethernet Driver Task 衝突：

然後就很有可能重演前面 Task 1-3 發生的事件：

比方說有一個要馬上處理的 Rx Ethernet Frame 送到了 SPI to Ethernet Driver Task，但因為 Priority Inversion 被擱置了，那就有可能發生硬體緩衝區爆掉、系統總是時好時壞，然後 code 怎麼修改客人都說有問題。

另外，lwIP 2.0 也直接在 source code 中強調了這一點：

避免 Priority Inversion

修正這個問題的方式如下：

1. Task 3 取得 semaphore
2. 將 Task 3 priority 提高至大於 Task 1
3. Task 3 用完資源，釋放 semaphore，降回原本的 priority。

這如果要 RD 手動添加很容易出錯，甚至有時根本不可行，所以有些 RTOS 支援 priority inheritance(優先權繼承)，uC/OS-II 不支援這種方式，必須空出一個沒有 Task 使用，優先權高過 Task 1 的 priroity，然後在初始化 mutex 時(OSMutexCreate) 將此 priority 填入。

這種方式顯然很有問題，因為 uC/OS-II 只支援 64 個 task，priority 還不能重複，沒兩下就用光了，所以到後面的 uC/OS-III 就在內部解掉了，但了解 Priority Inversion 還是非常重要，即使你是使用 FreeRTOS 等其他 RTOS。

接下來看 priority inheritance 如何運作(取自書中 Page.47 OSMutexCreate 也十分類似):

(1)(2) 與之前範例相同，Task 3 取得 mutex。

(3)(4)(5) Task 3 存取資源時被 Task 1 搶先(preempte)。

(6) Task 1 試圖取得 mutex。OS kernel 看到 Task 1 擁有 mutex 而 Task 3 priority 低於 Task 1，於是將 Task 3 priority 提升到與 Task 1 一樣。

(7) OS kernel 讓 Task 3 恢復執行，Task 1 繼續等待。

(8) Task 3 用畢資源，釋放 mutex，OS kernel 將 Task 3 恢復成原本的 priority，恢復 Task 1 執行。

(9)(10) Task 1 用畢資源，釋放 mutex

(11) Task 1 釋出 CPU(例如呼叫 OSTimeDly 睡一會)，Task 2 取得 CPU 控制權。注意 Task 2 不像未修改前成為程咬金。

書中也強調

Some level of priority inversion can not be avoided but far less is present than in the previous scenario.

某些場景還是會發生，但已經遠少於之前的情況了。

尾聲

筆者在日常工作時，赫然發現這些運作多年的 code，居然都沒有處理這個問題，如果說是因為筆者的同事人人都是高手，所以閃開了這個"最常發生的問題"，那從客戶的反應來看似乎也不是這樣。

某天筆者修好了 Priority Inversion，同事跑來問我這是幹麻的，筆者心想這大概不是只有你不知道，可能很多人都不知道，當下除了直接給他看 uC/OS-II 原作者的權威說明，也覺得可以寫篇文章充實一下 blog。

怪的是 uC/OS-III 把 uC/OS-II 原本第二章全部刪除，但這些知識放到現今也不會過時。

下筆至此，筆者想起以前搞過的那個 8 核心 MCU - FxxA，就記憶所及，當時他們並沒有考慮到這個問題，事隔多年後 8 核心也變成了單核心，大概也不用去管什麼 priority inversion 了，哈哈哈~