1 操作系統(tǒng)對實時性能的影響
　　操作系統(tǒng)從誕生發(fā)展到現(xiàn)代經(jīng)歷了批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)等演進過程，具有多樣化特征，派生出不同分支。其中，實時性是操作系統(tǒng)的重要特性，它要求在規(guī)定的時間窗口內(nèi)邏輯正確地完成規(guī)定的任務(wù)，具有及時性、交互性、多路性、獨立性等特點［1］。操作系統(tǒng)的實時性主要取決于I/O管理中的異步方式、內(nèi)存管理中的頁中斷機制、線程管理中的內(nèi)核代碼是否可搶占、資源管理中的信號量策略以及中斷延遲和時鐘精度等硬件支撐結(jié)構(gòu)［2］。由于多線程系統(tǒng)中線程對公共資源的爭奪，資源的有效管理成為提升系統(tǒng)實時性能的重要因素，而信號量是管理公共資源的經(jīng)典方式，所以，信號量設(shè)計是影響系統(tǒng)實時性的基礎(chǔ)設(shè)計。本文重點論述信號量策略對實時性能的影響，并以NT內(nèi)核為研究對象和實現(xiàn)平臺，分析現(xiàn)有幾種信號量策略的優(yōu)、缺點，提出了一種新策略，在保證系統(tǒng)通用性前提下提升了系統(tǒng)實時性。
　　2 信號量策略對實時性能的影響
　　荷蘭科學(xué)家設(shè)計的信號量算法為線程使用共享資源提供了有效的同步和互斥機制，NT內(nèi)核中，信號量（KSEMAPHORE）通過封裝DISPATCHER_HEADER結(jié)構(gòu)實現(xiàn)計數(shù)器和等待隊列，其數(shù)據(jù)結(jié)構(gòu)struct _KSEMA-PHORE{DISPATCHER_HEADER Header LONG Limit}在參考文獻［3］中有詳細描述，上述結(jié)構(gòu)可簡略為：
　　struct _KSEMAPHORE{LONG SignalState //信號量
　　計數(shù)器變量
　　LIST_ENTRY WaitList} //線程等待隊列鏈表
　　它的操作有創(chuàng)建（CreateSemaphore）、刪除（CloseHandle）、請求（WaitForSingleObject）和釋放（ReleaseSemaphore）信號量等。
　　線程使用資源前需要請求保護該資源的信號量，若信號量計數(shù)器減1后小于0，內(nèi)核阻塞線程并將其排在信號量的線程等待隊列中，同時啟動線程調(diào)度程序?qū)⒂嬎阗Y源交給等待運行的線程，執(zhí)行請求操作的線程沒有陷入“忙等”，而是“讓權(quán)等待”。若擁有信號量的線程釋放資源使得計數(shù)器加1后還小于等于0，則喚醒線程等待隊列中的等待線程并送線程調(diào)度隊列。因此，在資源緊張情況下，請求和釋放信號量會涉及資源等待隊列和線程調(diào)度隊列兩個隊列。本文討論資源等待隊列，對于資源請求，采用什么策略將線程放入隊列；對于資源釋放，采用什么策略把線程從隊列中取出并放入調(diào)度隊列。考慮放入與取出線程時同時采用策略的復(fù)雜性，固定取出策略從隊列頭部取出線程，請求時采取策略將線程放入隊列，目前有以下三種策略［1］：
　　（1）后進先出LIFO（Last In First Out），線程請求資源后，若信號量計數(shù)器小于0，將線程排在線程等待隊列的隊頭。該策略易于實現(xiàn)，線程等待隊列只需一個單鏈表即可，這種“后來先服務(wù)”的方式還可以利用CPU緩存TLB（Tanslation Lookaside Buffer）中存在的剛被掛起線程的頁表數(shù)據(jù)，不必更新緩存，提高了運行速度。但是，后進先出方式讓最先被掛起的線程鮮有被服務(wù)，若獲得資源的線程高頻率請求資源，會導(dǎo)致最先請求資源的線程由于長時間處在隊尾得不到服務(wù)導(dǎo)致“餓死”（Starva-tion），使得一些線程頻繁調(diào)度，而一些線程很少被調(diào)度。
　　（2）先進先出FIFO（First In First Out），線程請求資源后，若信號量計數(shù)器小于0，將線程排在線程等待隊列的隊尾。該策略克服了線程的“餓死”現(xiàn)象，對資源有請求的線程都能公平地占有資源，請求隊列調(diào)度均衡化，從策略角度來看，所有線程都整齊劃一無差別。這種先來先服務(wù)的方式?jīng)]有考慮線程的其他因素，例如，對時間緊要程度的要求不同，有實時線程和一般線程之分，如果對實時線程和一般線程都采用先進先出方式，那么實時線程的實時性將大幅降低，特別在等待隊列中已有很多線程的情況下，實時線程只有等待前面所有線程釋放信號量后才能得到調(diào)度，造成不必要的延時。信號量的數(shù)據(jù)結(jié)構(gòu)和操作也要復(fù)雜一些，需要一個隊尾指針。
　　（3）基于優(yōu)先級隊列Priority，線程請求資源后，若信號量計數(shù)器小于0，則將線程根據(jù)其優(yōu)先級排在線程等待隊列的相應(yīng)位置。該策略克服了先進先出的均衡化調(diào)度缺點，使優(yōu)先級高的線程始終處在隊列的隊首，搶占優(yōu)先級低的線程；線程可根據(jù)時間特性來確定它的優(yōu)先級并排隊，提高了線程的實時性。然而這種方式也有其不足，優(yōu)先級低的線程始終得不到調(diào)度，同樣會導(dǎo)致“餓死”。如果系統(tǒng)中有大量線程爭搶稀有資源，排隊過程還會引入隊列的搜索時間。
　　這就需要一種策略，對于具有很強時效性的實時線程使用優(yōu)先級排隊，對于一般線程按照先進先出排隊。由于實時線程很少，配合哈希（Hash）表分類實時線程（如圖1虛直線上部分所示）基本不會引入搜索時間。
　　3 基于Priority和FIFO結(jié)合的信號量策略
　　針對優(yōu)先級隊列過分強調(diào)高優(yōu)先級線程的缺點和先進先出隊列過分強調(diào)平均的缺點，本文提出基于優(yōu)先級和先進先出隊列結(jié)合的排隊策略，同時兼顧實時線程的強實時要求和一般線程的公平要求。
　　NT內(nèi)核將用戶線程以一對一方式映射到內(nèi)核中，并基于優(yōu)先級調(diào)度內(nèi)核線程，內(nèi)核將優(yōu)先級從低到高分為32級，0～15級為一般線程，16～31級為實時線程。本文將這種線程調(diào)度隊列的分級方式見之于信號量的等待隊列，如圖1虛直線上部分所示，把線程等待隊列構(gòu)造成一個長度為17、類型為LIST_ENTRY的哈希（Hash）指針數(shù)組，數(shù)組1～16根據(jù)優(yōu)先級排列同一級別的實時線程，數(shù)組0根據(jù)先進先出排列一般線程。線程請求資源后，若信號量計數(shù)器小于0，且線程優(yōu)先級小于16，則將該線程按照先進先出策略排在線程等待隊列的隊尾；若線程優(yōu)先級大于等于16，則按照優(yōu)先級排列該線程。當(dāng)線程釋放資源時，若信號量計數(shù)器小于0，內(nèi)核應(yīng)先從優(yōu)先級隊列中搜索掛起線程，再從先進先出隊列中搜索掛起線程。
　　
　　4 新信號量策略在NT內(nèi)核中的實現(xiàn)及結(jié)果分析
　　為了兼容操作系統(tǒng)上層軟件，本文僅修改“請求”函數(shù)的代碼而不改變現(xiàn)有信號量的數(shù)據(jù)結(jié)構(gòu)，將圖1虛直線上部分描述的新信號量策略映射到虛直線下，把優(yōu)先級隊列和先進先出隊列融合到一個隊列中，隊列的前半部分是優(yōu)先級隊列，由指針FLINK指定，后半部分為先進先出隊列，由指針BLINK指定，這種復(fù)合型隊列同時具備優(yōu)先級和先進先出隊列的優(yōu)點，體現(xiàn)了“一個隊列兩種策略”。線程請求資源后，若信號量計數(shù)器小于0，且線程的優(yōu)先級小于16，按照先進先出策略將線程排在BLINK指向的先進先出隊列隊尾；若線程的優(yōu)先級大于等于16，則將線程按照優(yōu)先級策略在FLINK指向的優(yōu)先級隊列中搜索相應(yīng)的位置，找到小于優(yōu)先級隊列中的線程并放在該線程之后。當(dāng)線程釋放資源時，若信號量計數(shù)器小于0，由于線程已經(jīng)根據(jù)策略放入恰當(dāng)?shù)奈恢茫瑑?nèi)核只需要從KSEMAPHORE→WaitList→FLINK取出第一個線程送往線程調(diào)度隊列即可