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