電電俠 ? 科科大大，我最近發(fā)現(xiàn)了并行編程世界中一個(gè)神奇的現(xiàn)象——優(yōu)先級(jí)反轉(zhuǎn)，我一直以為任務(wù)的執(zhí)行順序都是固定的。 ?

是啊。通常情況下，任務(wù)的優(yōu)先級(jí)是根據(jù)其重要性和緊急性來設(shè)定的。但是，在并發(fā)系統(tǒng)或多任務(wù)環(huán)境中，確實(shí)存在一種被稱為“優(yōu)先級(jí)反轉(zhuǎn)”的現(xiàn)象。

科科君 ? 電電俠 ?

什么時(shí)候會(huì)遇到這種現(xiàn)象？

解決資源爭(zhēng)用問題時(shí)。

科科君

死鎖預(yù)防是實(shí)時(shí)系統(tǒng)設(shè)計(jì)中的一個(gè)重要因素。不幸的是,即使使用安全排除技術(shù),這可能也不是困難的終點(diǎn)。在解決資源爭(zhēng)用問題時(shí),可能引入新的優(yōu)先級(jí)翻轉(zhuǎn)問題。

電電俠 ? 能詳細(xì)解釋下優(yōu)先級(jí)反轉(zhuǎn)的原理嗎？ ? 優(yōu)先級(jí)翻轉(zhuǎn)的基本原理可以通過一個(gè)簡單的兩任務(wù)(A 和 B)系統(tǒng)的行為來解釋。 科科君

假設(shè)任務(wù)A 正在使用一個(gè)鎖定的資源,此時(shí)調(diào)度程序決定進(jìn)行任務(wù)交換,新任務(wù)B希望使用 A 持有的資源。在檢查訪問機(jī)制時(shí),發(fā)現(xiàn)資源不可用,因此任務(wù) B 掛起。互斥機(jī)制按計(jì)劃執(zhí)行。但是如果 B的優(yōu)先級(jí)高于 A 呢? 結(jié)果仍然相同,B仍然被阻塞。結(jié)果是低優(yōu)先級(jí)的任務(wù) A 阻塞了高優(yōu)先級(jí)的任務(wù)B;在 A 釋放鎖定資源之前,B不能執(zhí)行。系統(tǒng)的行為表現(xiàn)得好像優(yōu)先級(jí)顛倒了一樣,即優(yōu)先級(jí)翻轉(zhuǎn)。然而,這種行為正是使用互斥時(shí)所期望的,沒什么異常。

電電俠 ? （若有所思）在雙任務(wù)系統(tǒng)中,性能下降可能不是一個(gè)大問題。 ? 但是看下圖的情況。 科科君

這是一個(gè)四任務(wù)系統(tǒng),由任務(wù) A、B、C和 D(按照優(yōu)先級(jí)順序)組成。系統(tǒng)還包括兩個(gè)共享資源 W 和 X。請(qǐng)注意,為了簡化對(duì)系統(tǒng)行為的解釋,做了以下假設(shè)。

(1)上下文切換(重新調(diào)度)僅在滴答(tick)時(shí)間發(fā)生。

(2)任務(wù)可以隨時(shí)掛起。

(3)任務(wù)可以隨時(shí)就緒。

一個(gè)運(yùn)行時(shí)場(chǎng)景

上圖示例的一個(gè)運(yùn)行時(shí)場(chǎng)景,如下圖所示。在t0時(shí)刻,任務(wù) D正在執(zhí)行,其他任務(wù)處于掛起狀態(tài)。在下一個(gè)滴答中斷(t1時(shí)刻)發(fā)生之前,D鎖定資源W。

注意:所有其他任務(wù)都已就緒。

在t1時(shí)刻,任務(wù)A搶占D,任務(wù)D重新進(jìn)入就緒(等待運(yùn)行)狀態(tài)。不久之后,A 試圖使用資源W 但發(fā)現(xiàn)它被鎖定,因此任務(wù)A 掛起。t2時(shí)刻,任務(wù) B被激活,運(yùn)行至完成,然后掛起。在t3時(shí)刻,任務(wù)C運(yùn)行至完成并掛起。然后在t4時(shí)刻,D 再次執(zhí)行。只有當(dāng)任務(wù) D釋放資源鎖時(shí),A 才能執(zhí)行(t5時(shí)刻)。

在此設(shè)計(jì)中,任務(wù)A被賦予最高優(yōu)先級(jí),因?yàn)樗且豁?xiàng)重要的任務(wù)。然而由于互斥機(jī)制鎖,任務(wù)A只能被迫等待所有其他任務(wù)完成后才能執(zhí)行。

電電俠 ? 顯然這種表現(xiàn)是不能接受的, 如何才能防止“連鎖”優(yōu)先級(jí)翻轉(zhuǎn)情況的發(fā)生? ? 這個(gè)問題可以通過兩種方式解決,都涉及臨時(shí)提升任務(wù)優(yōu)先級(jí)。

科科君 01

運(yùn)行任務(wù)的優(yōu)先級(jí)可以提高到通過優(yōu)先繼承技術(shù)獲取的確定值。

為共享資源分配優(yōu)先級(jí),然后將正在運(yùn)行的任務(wù)的優(yōu)先級(jí)提高到資源優(yōu)先級(jí)值,這種方式稱為優(yōu)先級(jí)天花板技術(shù)。

審核編輯：黃飛

?