題目與適用情境
一個單核心、固定優先級、可搶佔的即時系統中有三個任務，優先級數值越大越高：
| 任務 | 優先級 | 行為 | |---|---:|---| | H | 90 | 醒來後需要 bus_mutex，相對截止時間為 10ms | | M | 50 | 不使用該鎖，醒來後需要連續執行 20ms | | L | 10 | 已持有 bus_mutex，臨界區還剩 3ms CPU 工作 |
t=0 時 L 持鎖；H 隨後醒來、搶佔 L、嘗試加鎖並阻塞。H 阻塞 1ms 後，M 變為 runnable。請分別說明普通 mutex 與啟用優先級繼承時的執行順序，計算 H 的鎖等待上界，並回答：
- 什麼才是「無界」優先級反轉；
- 多個 mutex、多個 waiter 和巢狀等待時，優先級如何傳遞與恢復；
- 優先級上限協定與繼承協定有什麼取捨；
- 為什麼不能把普通號誌、縮短時間片或提高 H 優先級當作等價修復；
- 如何用排程軌跡和截止時間指標證明修復有效。
這道題適合嵌入式、RTOS、Linux 即時、機器人、影音、工業控制和系統軟體職位。題中的優先級、3ms、20ms 和 10ms 都是練習條件，不代表特定 RTOS 的優先級範圍或正式環境門檻。
面試官考察重點
第一層是把直接阻塞與無關任務造成的額外延遲分開。H 等待 L 釋放資源，本身就是優先級反轉；真正破壞可預測性的部分，是 M 雖然不使用該資源，卻可以反覆搶佔低優先級持鎖者 L，讓 H 的等待被中優先級工作任意拉長。
第二層是能畫出事件順序，而不只背定義。普通 mutex 下，H 阻塞後 L 雖可執行，卻會在 M 醒來後被搶佔；H 至少等待 M 的 20ms 加上 L 剩餘的 3ms，約 23ms，已經超過 10ms 截止時間。啟用繼承後，H 阻塞的瞬間把有效優先級 90 捐給 L，M 不能搶佔 L；在題目假設下，H 的等待約為 L 剩餘 3ms 加排程開銷。
第三層是理解實作狀態。鎖需要知道 owner 與按優先級排序的 waiter。一個任務同時持有多把鎖時，其有效優先級取基礎優先級與所有相關捐贈中的最高值；最高 waiter 逾時、取消或鎖被釋放後，要重新計算，不能無條件恢復到基礎值。若被提升的 owner 又阻塞在另一把鎖上，捐贈必須沿 PI chain 傳遞。
第四層是機制邊界。繼承減少中優先級任務製造的無界延遲，不能縮短臨界區裡的 I/O、關中斷區、不可搶佔程式碼或硬體操作，也不消除死鎖。優先級上限以預先設定換取更強的阻塞分析；沒有 owner 的計數號誌無法明確提升誰。
最後是驗證能力。強回答會比較鎖等待時長、L 持鎖期間 runnable-but-not-running 的時間、M 是否插入、H 的 deadline miss，以及巢狀鎖和逾時 waiter；只看平均 CPU 或「系統沒有卡死」不足以證明即時邊界。
回答前需要釐清的問題
- 優先級方向與排程策略是什麼？ 本題明確 90 高於 50，且是單核心固定優先級搶佔。不同 RTOS 的數字方向可能相反；普通分時排程也不能直接套用這條時間線。
- 3ms 是牆鐘時間還是實際 CPU 時間？ 本題是 L 在臨界區剩餘的 CPU 執行時間。若其中包含裝置等待或不可搶佔區，PI 不會讓物理操作變快。
- H 的 10ms 從何時起算？ 本題從 H 醒來開始計算相對截止時間。若截止時間從請求到達或週期釋放起算，必須把之前的排隊也加入回應時間。
- 系統中還有優先級高於 90 的任務或中斷嗎？ 題目計算先排除它們。真實上界需要加入更高優先級干擾、關中斷時間、排程開銷和快取影響。
bus_mutex是否真的是帶 owner 的 mutex？ 二元號誌外觀相似，但不一定具有 owner、只能由 owner 釋放或支援 PI。- L 是否還持有其他鎖，或正在等待另一把鎖？ 這決定捐贈是否需要遞迴傳遞，也影響死鎖和阻塞上界分析。
- 目標實作支援哪種協定？ POSIX 可宣告
PTHREADPRIOINHERIT或PTHREADPRIOPROTECT，RTOS 的多鎖、逾時、遞迴鎖和降權語意可能不同，需要查對應版本文件。
30 秒回答框架
「普通 mutex 下，H 在 L 持有 bus_mutex 時阻塞。L 原本可以繼續跑完剩餘 3ms，但 M 在 1ms 後以優先級 50 搶佔優先級 10 的 L，並執行 20ms。M 不碰這把鎖，卻讓優先級 90 的 H 間接等待，所以 H 的鎖等待約為 20+3=23ms，超過 10ms 截止時間。若 M 可以不斷到來，這個額外等待沒有由 L 的臨界區給出上界。
啟用優先級繼承後，H 阻塞時 L 的有效優先級提升到 90。M 醒來後不能搶佔 L；L 用剩餘約 3ms 釋放鎖，再按仍存在的 waiter 和所持 mutex 重新計算優先級，H 隨即獲得鎖。PI 控制的是無關中優先級工作造成的延遲，不保證零阻塞，也不修復長臨界區、死鎖或關中斷。
我會用確定性負載記錄 H 的 block/unblock、L 的 owner 區間、M 的執行區間和每次 deadline miss，比較普通 mutex 與 PI mutex。還要測試巢狀鎖的鏈式捐贈、多個 waiter、waiter 逾時和多鎖逐步釋放，證明提升和降權都正確。」
分步深入解答
第一步：畫出普通 mutex 的無界反轉時間線
將 H 醒來的時刻記為 0ms。L 已持鎖且還需 3ms CPU：
| 相對時間 | 事件 | 結果 | |---|---|---| | 0ms | H 醒來，搶佔 L，申請 bus_mutex | H 因 L 持鎖而阻塞 | | 0–1ms | L 恢復執行 | L 完成 1ms，臨界區還剩 2ms | | 1ms | M 醒來 | M 以優先級 50 搶佔 L | | 1–21ms | M 連續執行 20ms | H 仍等鎖，L runnable 但不能執行 | | 21–23ms | L 跑完剩餘 2ms並解鎖 | H 才解除阻塞 |
從 H 醒來到獲得鎖約 23ms，超過 10ms 截止時間。若 M 在 H 阻塞期間可以持續到來，H 的等待不再由 L 剩餘的 3ms 臨界區限定，這就是這裡的無界反轉。它不表示數學上必然永遠等待，而是目前設計無法從資源臨界區給出有限且可稽核的阻塞上界。
死鎖、飢餓和 CPU 過載要分開：死鎖存在等待環且沒有任務能夠釋放所需資源；飢餓不一定由鎖 owner 造成；CPU 過載會讓很多任務一起錯過截止時間。優先級反轉的證據鏈是 H 等待 L 持有的資源，同時 M 不依賴該資源卻阻止 L 執行。
第二步：加入優先級繼承並重新計算
H 在 0ms 阻塞時，mutex 把最高 waiter 的優先級 90 捐給 owner L。L 的基礎優先級仍為 10，有效優先級暫時為 90：
| 相對時間 | 事件 | 結果 | |---|---|---| | 0ms | H 阻塞在 L 持有的 mutex | L 繼承 90，並立即恢復執行 | | 1ms | M 以優先級 50 醒來 | M 不能搶佔有效優先級 90 的 L | | 0–3ms | L 完成剩餘臨界區並解鎖 | H 的鎖等待約 3ms 加排程開銷 | | 約 3ms | H 取得 mutex | 仍有約 7ms 截止時間預算 |
這個 3ms 結論依賴題目假設：沒有更高優先級任務、長關中斷、不可搶佔區、page fault 或阻塞 I/O，且鎖實作確實支援 PI。真實回應時間還要加入 H 自身執行時間和所有更高優先級干擾。PI 的核心收益是 M 的 20ms 不再進入 H 的這段資源阻塞時間。
提升應是有效優先級的變化，不是永久改寫 L 的基礎優先級。L 解鎖後若沒有其他捐贈，就回到 10；若另一把仍持有的 mutex 上有優先級 80 的 waiter，則只能降到 80，不能直接降回 10。
第三步：處理多個 waiter、多把鎖與 PI chain
假設 L 同時持有 R1、R2，H90 等待 R1，X70 等待 R2。L 的有效優先級為 90。釋放 R1 後，H 不再向 L 捐贈，但 X 仍在等 R2，所以 L 應降到 70；釋放 R2 後才回到基礎優先級 10。最高 waiter 若逾時或被取消，也要立即重新計算。
再假設 L 等待 K 持有的 R3。只提升 L 仍不能釋放 H 需要的鎖，因為 L 自己跑不起來；優先級 90 必須沿 H → R1 → L → R3 → K 傳遞到 K。K 釋放 R3 後，L 才能繼續並最終釋放 R1。Linux rt-mutex 用每把 mutex 的優先級 waiter 集合，以及每個 owner 所持 mutex 的最高 waiter 集合，維護這種提升和降權。
鏈式捐贈沒有消除鎖順序錯誤。若 L 等 K、K 又等 L，PI 只會提升等待環中的任務，資源仍無法釋放。工程上仍要定義全域鎖順序、限制巢狀深度、避免在持鎖時做阻塞 I/O，並為阻塞分析保留可稽核的最壞臨界區時間。
第四步：比較優先級繼承與優先級上限
POSIX mutex 協定可以幫助說明兩者：
PTHREADPRIOINHERIT：只有更高優先級執行緒實際阻塞時，owner 才提升到基礎優先級與所有 waiter 捐贈中的最高值；巢狀等待時遞迴傳遞。PTHREADPRIOPROTECT：執行緒持有 mutex 時，執行優先級至少提升到該 mutex 設定的 priority ceiling，無論是否已有 waiter。
繼承協定按執行期爭用付出簿記與鏈式傳遞成本，不需要提前知道所有使用者的最高優先級。上限協定要求預先知道可能存取資源的任務並正確設定 ceiling，換來更靜態、可分析的阻塞邊界；具體協定能否阻止某類死鎖，還取決於系統是否實作完整的 ceiling admission 規則，不能只看到「ceiling」就宣稱沒有死鎖。
POSIX 初始化示意如下，正式程式碼必須檢查實作支援、回傳值、排程權限和 mutex 生命週期：
pthread_mutexattr_t attr;
int rc = pthread_mutexattr_init(&attr);
if (rc == 0) {
rc = pthread_mutexattr_setprotocol(&attr, PTHREAD_PRIO_INHERIT);
}
if (rc == 0) {
rc = pthread_mutex_init(&bus_mutex, &attr);
}
pthread_mutexattr_destroy(&attr);在 Linux 普通 SCHEDOTHER 執行緒上啟用屬性，不等於獲得硬即時截止時間保證。還要驗證排程類別、即時優先級權限、PREEMPTRT 或目標核心行為，以及應用全部阻塞來源。
第五步：選擇正確的同步原語並縮短臨界區
PI 依賴明確的 owner：高優先級 waiter 阻塞時，核心必須知道要提升誰。因此保護共享資源應使用具備 owner 語意的 mutex，並由 owner 解鎖。計數號誌用於資源計數或通知時可能沒有唯一 owner，無法可靠確定捐贈目標；二元號誌也不能因為值只有 0/1 就自動獲得 mutex 的 PI 語意。
即使使用 PI，也應把臨界區縮到可計算：鎖內只複製必要狀態，把裝置傳輸、日誌、記憶體配置和可能睡眠的呼叫移出鎖；需要序列存取慢裝置時，可考慮專用高優先級服務任務和訊息傳遞。無鎖結構可能減少 mutex 阻塞，卻引入記憶體回收、ABA、重試和更差的最壞執行時間，必須按截止時間而非標籤選擇。
提高 H 的優先級也不解決題目：H 已經是最高任務，阻塞後無法執行；把時間片調短只會讓 M 更頻繁被排程，不能讓優先級 10 的 L 越過 50 的 M；關閉搶佔會擴大所有任務的回應延遲，並把問題移到不可搶佔區。
第六步：用可重現軌跡驗證阻塞上界
建構固定釋放順序：L 先加鎖，屏障確認後釋放 H，再在 H 阻塞 1ms 後釋放 M。分別執行普通 mutex、PI mutex 和 priority-ceiling mutex，多次記錄：
- H 從申請鎖到獲得鎖的分布，以及 10ms deadline miss 數；
- L 持鎖期間處於 runnable 但沒有 running 的累計時間；
- H 阻塞期間 M 的執行區間；
- L 的基礎/有效優先級變化、mutex owner、最高 waiter 和解鎖時刻；
- 排程切換、喚醒、中斷關閉和不可搶佔區時間。
普通 mutex 的軌跡應出現 M 插入並讓 H 等待約 23ms；PI 版本中，M 不應在「H 等待且 L runnable 持鎖」的區間搶佔 L，題目負載下 H 等待應接近 3ms而非 23ms。再加入優先級 70 的第二 waiter、巢狀 mutex、waiter 逾時、L 分步釋放兩把鎖，驗證有效優先級按目前最高捐贈提升和下降。
驗收不能寫成「PI 後永不逾時」。應寫成條件化邊界：在測得的最長臨界區、最高優先級干擾、最大關中斷時間和排程開銷預算內，H 的最壞回應時間小於 10ms；壓力與故障注入後仍滿足同一不等式。
高品質示範回答
「我先固定優先級方向和時間原點：90 最高，H 醒來時開始計算 10ms。普通 mutex 下，H 搶佔 L 後發現 bus_mutex 被持有，於是阻塞。L 恢復執行 1ms 後，優先級 50 的 M 醒來並搶佔 L 20ms。隨後 L 再執行剩餘 2ms 才解鎖，所以 H 從醒來到獲得鎖約等於 23ms，確定錯過截止時間。M 不使用這把鎖，卻間接阻止最高優先級 H 執行；若中優先級工作可持續到來，這段額外阻塞無法由 L 的 3ms 臨界區限定。
啟用 PI 後，H 阻塞的瞬間把優先級 90 捐給 L。L 的基礎優先級仍為 10，有效優先級變為 90；M 在 1ms 時醒來也不能搶佔。L 在約 3ms完成臨界區並釋放鎖，H 獲得鎖，因此題目中的資源阻塞小於 10ms。這個結論不包含更高優先級任務、關中斷和排程開銷，真實回應時間分析必須把它們加回來。
實作不能只保存一個布林值。每把 mutex 要知道 owner 和最高 waiter；每個 owner 要從基礎優先級與其所持所有 mutex 的捐贈中取最高值。若最高 waiter 逾時或一把鎖釋放，就重新計算。L 若又等待 K 的鎖，90 必須沿 PI chain 傳給 K。若存在等待環，提升優先級也不會釋放資源，所以仍要檢查鎖順序與死鎖。
我會用同一釋放順序比較普通 mutex 和 PTHREADPRIOINHERIT mutex，蒐集排程切換、鎖 owner、有效優先級、H block duration 和 deadline miss。PI 通過的直接證據是：H 阻塞且 L runnable 持鎖期間，M 不再執行；H 等待從約 23ms 收斂到 L 剩餘臨界區約 3ms加已計入的系統干擾。最後用第二 waiter、巢狀鎖、逾時和逐把解鎖驗證鏈式提升與正確降權。」
常見錯誤
- 只說「低優先級阻塞高優先級」 → 沒有解釋 M 如何把有限臨界區擴大成無界干擾 → 畫出 H 阻塞、L runnable、M 搶佔的完整時間線。
- 計算成 H 只等待 3ms → 忽略普通 mutex 下 L 被 M 搶佔的 20ms → 按事件順序得到約 23ms，並與 10ms 比較。
- 聲稱 PI 消除所有優先級反轉 → H 仍必須等待 L 的剩餘臨界區 → 表述為消除無關中優先級工作造成的無界延長。
- L 解鎖一把 mutex 就直接恢復到 10 → 另一把鎖上可能仍有高優先級 waiter → 從所有現存捐贈重新計算有效優先級。
- 只提升直接 owner → owner 若阻塞在另一把鎖上仍無法執行 → 沿 PI chain 遞迴傳遞，並限制與觀測鏈深度。
- 把 PI 當作死鎖修復 → 等待環中的任務即使都被提升也沒有可釋放資源的執行路徑 → 繼續使用鎖順序、逾時策略和死鎖偵測。
- 用二元號誌替換 mutex 仍假設有 PI → 號誌可能沒有 owner，系統不知道該提升誰 → 保護資源時選擇明確支援 PI 的 owner mutex。
- 把
PTHREADPRIOINHERIT當作硬即時開關 → 排程類別、權限、核心搶佔、中斷和其他阻塞仍影響截止時間 → 驗證完整平台設定並做最壞回應時間預算。 - 只看平均延遲下降 → 降權、巢狀傳遞或逾時路徑仍可能錯誤 → 同時驗證尾端、deadline miss、有效優先級和多鎖邊界。
追問及應對
追問一：為什麼稱為「無界」，M 明明只執行 20ms？
本題給定一次 M 工作，所以可以算出約 23ms；「無界」描述的是機制沒有用 L 的臨界區替額外延遲設上限。若 M 類任務可連續釋放，L 可以一直 runnable 卻得不到 CPU，H 的等待隨 M 工作增長。PI 把題目中的 M 干擾移出這段阻塞，剩餘上界再由臨界區和更高優先級干擾決定。
追問二：H 等待 L，L 又等待 K 時怎麼辦？
把 H 的 90 先捐給 L，再沿 L 等待的 mutex 捐給 owner K。K 以有效優先級 90 完成臨界區並釋放，L 得以繼續，最後釋放 H 所需的鎖。蒐集軌跡時要看到整條 H → mutex1 → L → mutex2 → K 的提升與反向降權；只看到 L 被提升還不能證明鏈式實作正確。
追問三：多個高優先級 waiter 逾時後，L 應恢復到多少？
取仍然有效的最高需求。若 H90 逾時離開，而 X70 仍等待 L 持有的另一把 mutex，L 從 90 降到 70；只有所有捐贈都消失才回基礎優先級 10。實作需要在 waiter 加入、離開、逾時、取消和每次解鎖時維護優先級有序狀態。
追問四：優先級上限一定比繼承好嗎？
沒有統一答案。上限協定便於在任務集合和資源存取關係穩定時做靜態阻塞分析，但 ceiling 設錯會拒絕合法存取或失去分析保證；繼承按實際爭用提升，設定較少，卻要處理 waiter、鏈式傳遞和動態降權。應根據 RTOS 的具體協定、任務集合穩定性和可接受執行期開銷選擇。
追問五：為什麼 PI 不能修復持鎖 I/O？
提升 owner 只讓它在 runnable 時更早獲得 CPU。若 L 在等待 SPI 傳輸、儲存、page fault 或其他事件，它仍處於 sleeping；若程式關中斷或不可搶佔，排程器也無法介入。修復是把慢操作移出臨界區、改用服務任務或非同步協定，並把硬體最壞完成時間納入預算。
追問六：在 Linux 使用者空間怎樣證明屬性真的生效？
先檢查 pthreadmutexattrsetprotocol 和 pthreadmutexinit 回傳值、系統對 POSIXTHREADPRIOINHERIT 的支援、執行緒實際排程策略與即時優先級權限。再用受控 H/M/L 負載記錄排程與 futex/鎖事件，確認 L 的有效優先級提升、M 沒有插入關鍵區間、解鎖或 waiter 逾時後正確降權。僅憑初始化成功或 p99 偶然下降都不夠。