基于新信號量策略的實(shí)時(shí)提升技術(shù)

1 操作系統對實(shí)時(shí)性能的影響

操作系統從誕生發(fā)展到現代經(jīng)歷了批處理系統、分時(shí)系統和實(shí)時(shí)系統等演進(jìn)過(guò)程，具有多樣化特征，派生出不同分支。其中，實(shí)時(shí)性是操作系統的重要特性，它要求在規定的時(shí)間窗口內邏輯正確地完成規定的任務(wù)，具有及時(shí)性、交互性、多路性、獨立性等特點(diǎn)[1]。操作系統的實(shí)時(shí)性主要取決于I/O管理中的異步方式、內存管理中的頁(yè)中斷機制、線(xiàn)程管理中的內核代碼是否可搶占、資源管理中的信號量策略以及中斷延遲和時(shí)鐘精度等硬件支撐結構[2]。由于多線(xiàn)程系統中線(xiàn)程對公共資源的爭奪，資源的有效管理成為提升系統實(shí)時(shí)性能的重要因素，而信號量是管理公共資源的經(jīng)典方式，所以，信號量設計是影響系統實(shí)時(shí)性的基礎設計。本文重點(diǎn)論述信號量策略對實(shí)時(shí)性能的影響，并以NT內核為研究對象和實(shí)現平臺，分析現有幾種信號量策略的優(yōu)、缺點(diǎn)，提出了一種新策略，在保證系統通用性前提下提升了系統實(shí)時(shí)性。

2 信號量策略對實(shí)時(shí)性能的影響

荷蘭科學(xué)家設計的信號量算法為線(xiàn)程使用共享資源提供了有效的同步和互斥機制，NT內核中，信號量（KSEMAPHORE）通過(guò)封裝DISPATCHER_HEADER結構實(shí)現計數器和等待隊列，其數據結構struct _KSEMA-PHORE{DISPATCHER_HEADER Header LONG Limit}在參考文獻[3]中有詳細描述，上述結構可簡(jiǎn)略為：

struct _KSEMAPHORE{LONG SignalState //信號量
計數器變量
LIST_ENTRY WaitList} //線(xiàn)程等待隊列鏈表
它的操作有創(chuàng )建(CreateSemaphore)、刪除(CloseHandle)、請求(WaitForSingleObject)和釋放(ReleaseSemaphore)信號量等。

線(xiàn)程使用資源前需要請求保護該資源的信號量，若信號量計數器減1后小于0，內核阻塞線(xiàn)程并將其排在信號量的線(xiàn)程等待隊列中，同時(shí)啟動(dòng)線(xiàn)程調度程序將計算資源交給等待運行的線(xiàn)程，執行請求操作的線(xiàn)程沒(méi)有陷入“忙等”，而是“讓權等待”。若擁有信號量的線(xiàn)程釋放資源使得計數器加1后還小于等于0，則喚醒線(xiàn)程等待隊列中的等待線(xiàn)程并送線(xiàn)程調度隊列。因此，在資源緊張情況下，請求和釋放信號量會(huì )涉及資源等待隊列和線(xiàn)程調度隊列兩個(gè)隊列。本文討論資源等待隊列，對于資源請求，采用什么策略將線(xiàn)程放入隊列；對于資源釋放，采用什么策略把線(xiàn)程從隊列中取出并放入調度隊列?？紤]放入與取出線(xiàn)程時(shí)同時(shí)采用策略的復雜性，固定取出策略從隊列頭部取出線(xiàn)程，請求時(shí)采取策略將線(xiàn)程放入隊列，目前有以下三種策略[1]：

(1)后進(jìn)先出LIFO(Last In First Out)，線(xiàn)程請求資源后，若信號量計數器小于0，將線(xiàn)程排在線(xiàn)程等待隊列的隊頭。該策略易于實(shí)現，線(xiàn)程等待隊列只需一個(gè)單鏈表即可，這種“后來(lái)先服務(wù)”的方式還可以利用CPU緩存TLB（Tanslation Lookaside Buffer）中存在的剛被掛起線(xiàn)程的頁(yè)表數據，不必更新緩存，提高了運行速度。但是，后進(jìn)先出方式讓最先被掛起的線(xiàn)程鮮有被服務(wù)，若獲得資源的線(xiàn)程高頻率請求資源，會(huì )導致最先請求資源的線(xiàn)程由于長(cháng)時(shí)間處在隊尾得不到服務(wù)導致“餓死”（Starva-tion），使得一些線(xiàn)程頻繁調度，而一些線(xiàn)程很少被調度。

(2)先進(jìn)先出FIFO(First In First Out)，線(xiàn)程請求資源后，若信號量計數器小于0，將線(xiàn)程排在線(xiàn)程等待隊列的隊尾。該策略克服了線(xiàn)程的“餓死”現象，對資源有請求的線(xiàn)程都能公平地占有資源，請求隊列調度均衡化，從策略角度來(lái)看，所有線(xiàn)程都整齊劃一無(wú)差別。這種先來(lái)先服務(wù)的方式?jīng)]有考慮線(xiàn)程的其他因素，例如，對時(shí)間緊要程度的要求不同，有實(shí)時(shí)線(xiàn)程和一般線(xiàn)程之分，如果對實(shí)時(shí)線(xiàn)程和一般線(xiàn)程都采用先進(jìn)先出方式，那么實(shí)時(shí)線(xiàn)程的實(shí)時(shí)性將大幅降低，特別在等待隊列中已有很多線(xiàn)程的情況下，實(shí)時(shí)線(xiàn)程只有等待前面所有線(xiàn)程釋放信號量后才能得到調度，造成不必要的延時(shí)。信號量的數據結構和操作也要復雜一些，需要一個(gè)隊尾指針。

(3)基于優(yōu)先級隊列Priority，線(xiàn)程請求資源后，若信號量計數器小于0，則將線(xiàn)程根據其優(yōu)先級排在線(xiàn)程等待隊列的相應位置。該策略克服了先進(jìn)先出的均衡化調度缺點(diǎn)，使優(yōu)先級高的線(xiàn)程始終處在隊列的隊首，搶占優(yōu)先級低的線(xiàn)程；線(xiàn)程可根據時(shí)間特性來(lái)確定它的優(yōu)先級并排隊，提高了線(xiàn)程的實(shí)時(shí)性。然而這種方式也有其不足，優(yōu)先級低的線(xiàn)程始終得不到調度，同樣會(huì )導致“餓死”。如果系統中有大量線(xiàn)程爭搶稀有資源，排隊過(guò)程還會(huì )引入隊列的搜索時(shí)間。

這就需要一種策略，對于具有很強時(shí)效性的實(shí)時(shí)線(xiàn)程使用優(yōu)先級排隊，對于一般線(xiàn)程按照先進(jìn)先出排隊。由于實(shí)時(shí)線(xiàn)程很少，配合哈希（Hash）表分類(lèi)實(shí)時(shí)線(xiàn)程（如圖1虛直線(xiàn)上部分所示）基本不會(huì )引入搜索時(shí)間。

3 基于Priority和FIFO結合的信號量策略

針對優(yōu)先級隊列過(guò)分強調高優(yōu)先級線(xiàn)程的缺點(diǎn)和先進(jìn)先出隊列過(guò)分強調平均的缺點(diǎn)，本文提出基于優(yōu)先級和先進(jìn)先出隊列結合的排隊策略，同時(shí)兼顧實(shí)時(shí)線(xiàn)程的強實(shí)時(shí)要求和一般線(xiàn)程的公平要求。

NT內核將用戶(hù)線(xiàn)程以一對一方式映射到內核中，并基于優(yōu)先級調度內核線(xiàn)程，內核將優(yōu)先級從低到高分為32級，0～15級為一般線(xiàn)程，16～31級為實(shí)時(shí)線(xiàn)程。本文將這種線(xiàn)程調度隊列的分級方式見(jiàn)之于信號量的等待隊列，如圖1虛直線(xiàn)上部分所示，把線(xiàn)程等待隊列構造成一個(gè)長(cháng)度為17、類(lèi)型為L(cháng)IST_ENTRY的哈希（Hash）指針數組，數組1～16根據優(yōu)先級排列同一級別的實(shí)時(shí)線(xiàn)程，數組0根據先進(jìn)先出排列一般線(xiàn)程。線(xiàn)程請求資源后，若信號量計數器小于0，且線(xiàn)程優(yōu)先級小于16，則將該線(xiàn)程按照先進(jìn)先出策略排在線(xiàn)程等待隊列的隊尾；若線(xiàn)程優(yōu)先級大于等于16，則按照優(yōu)先級排列該線(xiàn)程。當線(xiàn)程釋放資源時(shí)，若信號量計數器小于0，內核應先從優(yōu)先級隊列中搜索掛起線(xiàn)程，再從先進(jìn)先出隊列中搜索掛起線(xiàn)程。


4 新信號量策略在NT內核中的實(shí)現及結果分析

為了兼容操作系統上層軟件，本文僅修改“請求”函數的代碼而不改變現有信號量的數據結構，將圖1虛直線(xiàn)上部分描述的新信號量策略映射到虛直線(xiàn)下，把優(yōu)先級隊列和先進(jìn)先出隊列融合到一個(gè)隊列中，隊列的前半部分是優(yōu)先級隊列，由指針FLINK指定，后半部分為先進(jìn)先出隊列，由指針BLINK指定，這種復合型隊列同時(shí)具備優(yōu)先級和先進(jìn)先出隊列的優(yōu)點(diǎn)，體現了“一個(gè)隊列兩種策略”。線(xiàn)程請求資源后，若信號量計數器小于0，且線(xiàn)程的優(yōu)先級小于16，按照先進(jìn)先出策略將線(xiàn)程排在BLINK指向的先進(jìn)先出隊列隊尾；若線(xiàn)程的優(yōu)先級大于等于16，則將線(xiàn)程按照優(yōu)先級策略在FLINK指向的優(yōu)先級隊列中搜索相應的位置，找到小于優(yōu)先級隊列中的線(xiàn)程并放在該線(xiàn)程之后。當線(xiàn)程釋放資源時(shí)，若信號量計數器小于0，由于線(xiàn)程已經(jīng)根據策略放入恰當的位置，內核只需要從KSEMAPHORE→WaitList→FLINK取出第一個(gè)線(xiàn)程送往線(xiàn)程調度隊列即可。為了最小化修改范圍，用下述代碼替換內核basentoskewait.c文件中KeWaitForSingleObject()函數的部分代碼以實(shí)現新策略：
if (KeQueryPriorityThread(Thread) 16)
{InsertTailList(Objectx->Header.WaitListHead,
WaitBlock->WaitListEntry);}
else {ListHead1 = Objectx->Header.WaitListHead;
WaitEntry1 = ListHead1->Flink;
while(WaitEntry1 != ListHead1) {
WaitBlock1 = CONTAINING_RECORD(WaitEntry1,
KWAIT_BLOCK, WaitListEntry);
if(KeQueryPriorityThread(Thread) >
KeQueryPriorityThread(WaitBlock1->Thread))
{break;}
WaitEntry1 = WaitEntry1->Flink;}
InsertTailList(WaitEntry1, WaitBlock->
WaitListEntry);}

根據C規范[4]設計一個(gè)應用程序測試內核修改后的性能指標，由于NT內核對于一個(gè)特定的進(jìn)程只能有一個(gè)特定的優(yōu)先級類(lèi)，進(jìn)程內的所有線(xiàn)程只能屬于該優(yōu)先級，程序應該第一次進(jìn)程化為實(shí)時(shí)類(lèi)型的主控進(jìn)程，生成信號量和掛在信號量上的實(shí)時(shí)線(xiàn)程，第二次進(jìn)程化為一般類(lèi)型的客戶(hù)進(jìn)程，生成掛在信號量上的一般線(xiàn)程，主線(xiàn)程釋放實(shí)時(shí)線(xiàn)程和一般線(xiàn)程。應用程序中有4個(gè)參量：一般線(xiàn)程數NrTh、實(shí)時(shí)線(xiàn)程數RtTh；信號量Seph及資源爭奪時(shí)間RunT。實(shí)驗中,固定Seph=1，RunT=10 000 ms，改變NrTh和RtTh的值，分別在表1所列的內核上運行，結果如表1所示。

從表1可以看出：1～12行的調度結果和前述分析的各種策略的優(yōu)缺點(diǎn)一致，對于FIFO，無(wú)論不同優(yōu)先級線(xiàn)程的比例是多少，它們被調度的次數幾乎完全相同。對于LIFO，從數據可以看出，兩個(gè)優(yōu)先級為8、一個(gè)優(yōu)先級為6和優(yōu)先級為26、25、24的線(xiàn)程處在等待隊列的前端，而且幾乎每次都是這幾個(gè)線(xiàn)程被調度。對于Priority，無(wú)論是否有實(shí)時(shí)類(lèi)線(xiàn)程，只要優(yōu)先級高，被調度的次數就多。對于新策略（Priority and FIFO），有實(shí)時(shí)線(xiàn)程就按優(yōu)先級調度，若只有一般線(xiàn)程就按照FIFO調度，既有FIFO的特性（比較第2行和第11行）也有Priority的特性（比較第1行和第4行），而其他策略則只具有一種特性。應用程序在其他操作系統測試結果見(jiàn)14～22行，比較可以看出，14～22行的數據與10～12行的數據幾乎完全一致，由此可以推斷Windows 7操作系統的信號量等待隊列也是先進(jìn)先出策略。

研究發(fā)現，提升系統實(shí)時(shí)性應該具備兩個(gè)條件[5]：(1)不同任務(wù)可統一，包括將中斷任務(wù)和線(xiàn)程任務(wù)按不同特征統一映射到一個(gè)優(yōu)先級隊列中，內核根據這個(gè)優(yōu)先級隊列統一調度任務(wù)，中斷線(xiàn)程化為上述兩種任務(wù)的統一提供了可能；(2)所有資源可搶占，計算資源可搶占可行且易實(shí)現，而內存資源和I/O資源可搶占需進(jìn)一步研究，一個(gè)占有共享資源（如臨界區）的低優(yōu)先級線(xiàn)程被一般優(yōu)先級線(xiàn)程搶占計算資源，而該線(xiàn)程又被高優(yōu)先級的線(xiàn)程搶占計算資源，高優(yōu)先級的線(xiàn)程又因請求已被低優(yōu)先級線(xiàn)程占有的資源而掛起，只有等待一般優(yōu)先級線(xiàn)程放棄計算資源后由低優(yōu)先級線(xiàn)程運行并釋放共享資源，才能使高優(yōu)先級線(xiàn)程得以運行，雖然通過(guò)優(yōu)先級繼承避免優(yōu)先級反轉可以提高實(shí)時(shí)性，但若高優(yōu)先級線(xiàn)程能像搶占計算資源那樣搶占線(xiàn)程的其他資源，實(shí)時(shí)性將大幅提升。