基于新信號量策略的實時提升技術

王 波，崔 喆(中科院成都計算機應用研究所，四川 成都610041)

1 操作系統對實時性能的影響

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

2 信號量策略對實時性能的影響

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

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

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

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

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

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

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

針對優先級隊列過分強調高優先級線程的缺點和先進先出隊列過分強調平均的缺點，本文提出基于優先級和先進先出隊列結合的排隊策略，同時兼顧實時線程的強實時要求和一般線程的公平要求。

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

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

為了兼容操作系統上層軟件，本文僅修改“請求”函數的代碼而不改變現有信號量的數據結構，將圖1虛直線上部分描述的新信號量策略映射到虛直線下，把優先級隊列和先進先出隊列融合到一個隊列中，隊列的前半部分是優先級隊列，由指針FLINK指定，后半部分為先進先出隊列，由指針BLINK指定，這種復合型隊列同時具備優先級和先進先出隊列的優點，體現了“一個隊列兩種策略”。線程請求資源后，若信號量計數器小于0，且線程的優先級小于16，按照先進先出策略將線程排在BLINK指向的先進先出隊列隊尾；若線程的優先級大于等于16，則將線程按照優先級策略在FLINK指向的優先級隊列中搜索相應的位置，找到小于優先級隊列中的線程并放在該線程之后。當線程釋放資源時，若信號量計數器小于0，由于線程已經根據策略放入恰當的位置，內核只需要從KSEMAPHORE→WaitList→FLINK取出第一個線程送往線程調度隊列即可。為了最小化修改范圍，用下述代碼替換內核ase toskewait.c文件中Ke-WaitForSingleObject()函數的部分代碼以實現新策略：

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

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

表1 內核使用不同策略的運行結果

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

[1]湯子瀛，哲鳳屏，湯小丹.計算機操作系統[M].西安：西安電子科技大學出版社，2001.

[2]俸遠楨，閻慧娟，羅克露.計算機組成原理[M].北京：電子工業出版社，1996.

[3]SOLOMON D A，RUSSINOVICH M E.Microsoft Windows Internals Fourth Edition[M].DigitalCopy，Microsoft Press，2004.

[4]KERNIGHAN B W，RITCHIE D M.The C programming language[M].DigitalCopy，Prentice-Hall，1988.

[5]王波，崔喆.基于新 DPC機制的實時提升技術[J].計算機應用研究，2011，28(Z)：110-111.