Linux操作系統(tǒng)信號量機制的實時化改造

李長松，蔣澤軍

（1.西北工業(yè)大學(xué) 計算機學(xué)院，陜西 西安 710129；2.西北工業(yè)大學(xué) 陜西 西安 710129）

Linux操作系統(tǒng)因其源代碼開放、運行效率高、功能強大、安全性好等特點，在高等院校、銀行、研究機構(gòu)甚至許多商業(yè)領(lǐng)域得到了廣泛的應(yīng)用。隨著嵌入式行業(yè)的發(fā)展，Linux也越來越多的應(yīng)用到一些具有實時性要求的領(lǐng)域。但是，由于Linux操作系統(tǒng)設(shè)計的初衷是通用的分時操作系統(tǒng)，其應(yīng)用于實時系統(tǒng)時仍有諸多的不足之處需要改進[6]。

Linux是一個多用戶多任務(wù)的操作系統(tǒng)，為了避免多個任務(wù)同時進入臨界區(qū)而造成的運行結(jié)果不確定，Linux為用戶提供了信號量[1，7]機制來實現(xiàn)進程間的同步。

本文在對System V信號量機制進行了深入的研究之后，發(fā)現(xiàn)其在應(yīng)用于實時系統(tǒng)時存在的不足之處，并提出了對其進行改進的方法。

1 System V信號量機制

1.1 System V信號量機制

Linux使用System V引入的機制，來支持用戶進程的進程間同步和通信，其中信號量機制用于進程間的同步。System V信號量在ipc/sem.c中實現(xiàn)，對應(yīng)的頭文件是＜sem.h＞。System V的信號量實際上是一個信號量集，其中包含一個或多個信號量。

1.1.1 System V信號量機制重要的數(shù)據(jù)結(jié)構(gòu)

對于系統(tǒng)中的每個信號量集，內(nèi)核維護一個strcut sem_array類型的數(shù)據(jù)結(jié)構(gòu)，其主要成員包括：struct kern_ipc_permsem_perm； struct sem* sem_base； struct list_head sem_pending； int sem_nsems。 其中 kern_ipc_perm 結(jié)構(gòu)中含有當(dāng)前這個特定信號量集的鍵值、訪問權(quán)限等信息；sem_pending指向待決信號量操作鏈表，用于將信號量集與睡眠進程關(guān)聯(lián)起來，該進程申請執(zhí)行信號量的操作，但目前不允許其執(zhí)行；sem_nsems為當(dāng)前信號量集中所包含的信號量數(shù)；sem_base是信號量結(jié)構(gòu)，用于維護信號量集中某個給定信號量的一組值，該數(shù)據(jù)結(jié)構(gòu)中包含3個成員：int semval表示信號量的當(dāng)前實際值，int sempid表示對其值最后一次進行操作的進程ID，struct list_head sem_pending是一個雙向鏈表節(jié)點結(jié)構(gòu)，當(dāng)信號量集中只有一個信號量時，該結(jié)構(gòu)指向待決信號量操作鏈表，用于將信號量與睡眠進程關(guān)聯(lián)起來。

每一個在信號量集上被阻塞的進程對應(yīng)一個struct sem_queue類型的結(jié)構(gòu)，我們稱之為待決信號量操作結(jié)構(gòu)體，其主要成員包括：struct task_struct*sleeper為睡眠進程的進程描述符，int pid為睡眠進程的進程ID，struct sembuf*sops為睡眠進程的待決操作數(shù)組，int nsops為待決操作數(shù)組中元素的數(shù)目，該結(jié)構(gòu)體通過一個list_head型成員被鏈接在相應(yīng)的信號量集上，當(dāng)該信號量集中只有一個信號量時，該結(jié)構(gòu)體通過另一個list_head型成員被鏈接在該信號量的數(shù)據(jù)結(jié)構(gòu)上。

待決操作數(shù)組sops用于描述在信號量上將要執(zhí)行的操作，其數(shù)據(jù)結(jié)構(gòu)的主要成員包括：unsigned short sem_num為信號量在信號量集中的索引，short sem_op為所要進行的操作，short sem_flg為操作標志。

1.1.2 System V信號量相關(guān)的系統(tǒng)調(diào)用

所有對信號量的操作都使用一個名為ipc的系統(tǒng)調(diào)用[2，4]來執(zhí)行。 asmlinkage long sys_ipc （unsigned int call， int first，unsigned long second，unsigned long third，void__user*ptr，long fifth）；該系統(tǒng)調(diào)用不僅用于信號量，也可用于操作消息隊列和共享內(nèi)存，其第一個參數(shù)call用于將實際工作委托給其他函數(shù)，本節(jié)討論用于信號量操作的函數(shù)。Call的值與對應(yīng)所調(diào)用的函數(shù)關(guān)系如表1所示。

表1 函數(shù)調(diào)用對應(yīng)表Tab.1 Function call corresponding table

sys_semctl函數(shù)對一個信號量集執(zhí)行各種控制操作，包括獲取/設(shè)置信號量集中某個/全部信號量的當(dāng)前值，將某個信號量集刪除等。

sys_semget函數(shù)創(chuàng)建一個信號量集或訪問一個已存在的信號量集。

sys_semtimedop函數(shù)對信號量集中的一個或多個信號量進行操作，如果是對多個信號量進行操作，則這些操作要么全做要么一個都不做。

1.2 優(yōu)先級反轉(zhuǎn)現(xiàn)象描述

假設(shè)這樣一種情況：系統(tǒng)中有3個具有不同優(yōu)先級的任務(wù)H，M，L。其中H的優(yōu)先級最高，M次之，L最低。H和L共享同一個由信號量保護的臨界資源R，L最先就緒并獲得臨界資源R的使用權(quán)，這時具有較高優(yōu)先級的任務(wù)H也獲得就緒并申請訪問臨界資源R，但是由于R已經(jīng)被L占有，所以H必須等待。而此時M任務(wù)就緒，并且由于其優(yōu)先級高于正在運行的L而將其搶占。這樣H任務(wù)必須等待優(yōu)先級較低的M任務(wù)運行完畢才有機會獲得運行，就好像是M任務(wù)比H任務(wù)有了更高的優(yōu)先級。這就是所謂的優(yōu)先級反轉(zhuǎn)[3]現(xiàn)象。如果H任務(wù)是一個實時任務(wù)，這一問題將嚴重增加H的延遲時間，降低系統(tǒng)的實時性。

對于System V的信號量集，優(yōu)先級反轉(zhuǎn)的問題更加復(fù)雜，這是因為System V信號量集中可以包含多于一個信號量，并且進程每次對System V信號量所保護資源的申請和釋放都可能多于一個。

System V信號量存在的另外一個問題是，其不對實時進程和普通進程做區(qū)分，當(dāng)請求信號量集的進程無法一次性獲得信號量集中的所有信號量時一律將其插入到sem_pending隊列的尾部，并且喚醒進程的操作是從隊列的頭部選取可以獲得運行的進程。這種情況下，相當(dāng)于在信號量集上阻塞的實時進程和非實時進程有相同的機會獲得信號量集，而與他們的優(yōu)先級大小無關(guān)，這樣勢必會導(dǎo)致實時進程延遲的增加。

2 System V信號量機制的實時化改造

2.1 優(yōu)先級繼承機制簡介

既然優(yōu)先級反轉(zhuǎn)問題會增大實時任務(wù)的延遲時間，我們需要想辦法來避免這一問題。對于優(yōu)先級反轉(zhuǎn)問題一般有優(yōu)先級天花板和優(yōu)先級繼承兩種解決方案。

優(yōu)先級天花板是指，當(dāng)任務(wù)申請訪問某一臨界資源時，立即將其優(yōu)先級提升到能夠申請訪問該資源的任務(wù)中最高的優(yōu)先級。這種方案所存在的問題是優(yōu)先級反轉(zhuǎn)只是在很少情況下才會發(fā)生的事情，如果不進行任何判斷直接將申請訪問臨界資源的任務(wù)優(yōu)先級提高，勢必會為系統(tǒng)增加許多不必要的開銷。而且在實際系統(tǒng)中很難預(yù)測可能訪問臨界資源的任務(wù)集合。因此本文采用優(yōu)先級繼承機制。

優(yōu)先級繼承機制的原理是：當(dāng)較高優(yōu)先級的任務(wù)H試圖獲得臨界資源R時，如果此時R已經(jīng)被較低優(yōu)先級的任務(wù)L占用，那么為了使H能夠盡快獲得調(diào)用運行，而將L的優(yōu)先級臨時提升到和H相同的水平，從而讓L以H的優(yōu)先級參與調(diào)度，盡快讓L執(zhí)行并釋放掉H正在請求的臨界資源R，待L釋放R時再將其優(yōu)先級還原到優(yōu)先級繼承前的水平。

優(yōu)先級繼承的可傳遞性指的是：當(dāng)較高優(yōu)先級的任務(wù)H將優(yōu)先級借給較低優(yōu)先級的任務(wù)L后，L又去申請另外一個臨界資源S，而S已經(jīng)被另外一個較低優(yōu)先級的任務(wù)A占用，這時應(yīng)該同樣將A的優(yōu)先級臨時提升到與H相同的水平，待A釋放資源S后再將其優(yōu)先級還原。

2.2 將優(yōu)先級繼承機制運用于System V信號量

System V信號量功能十分強大，它可以同時保護幾個同種類型或不同類型的臨界資源，但是這也導(dǎo)致了將優(yōu)先級繼承機制運用于System V信號量時有諸多的復(fù)雜之處。

首先System V信號量均采用信號量集的實現(xiàn)形式，在一個信號量集中包含1個或多個信號量，用戶可以同時對信號量集中的一個或多個信號量進行操作。而優(yōu)先級繼承機制是針對某一個信號量的，這就要求在信號量集中的每一個互斥信號量上實現(xiàn)優(yōu)先級繼承機制。其次，System V信號量包括計數(shù)信號量和互斥信號量，優(yōu)先級繼承機制是針對互斥信號量的，對計數(shù)信號量則不做修改?；コ庑盘柫恳话阒钙涑跏贾禐?的信號量，而System V信號量機制規(guī)定，對信號量的申請、釋放即通常所說的P、V操作均不限定于1。這一規(guī)則使我們很難判斷一個System V信號量是否屬于互斥信號量。本文對于這一問題的解決方案是，規(guī)定只將初始值為1的信號量視為互斥信號量，而對于初始值為n申請、釋放單位也為n的情況，視為應(yīng)用程序編程的不規(guī)范，應(yīng)由用戶自己避免。

此外為了讓被阻塞的實時進程盡快得到運行，當(dāng)其申請信號量集失敗時，我們將其按照優(yōu)先級順序插入到待決操作鏈表，而對于非實時進程則直接將其插入到待決操作鏈表的尾部，這樣做可以保證實時進程按照優(yōu)先級由高到低的順序獲得信號量，而非實時進程是FIFO的順序，并且所有實時進程均排在非實時進程前面。這樣做可以有效減少實時進程申請信號量的延遲時間。

2.2.1 對Linux內(nèi)核源碼相關(guān)結(jié)構(gòu)體的修改

首先，需要修改信號量結(jié)構(gòu)體struct sem，增加下列成員：bool if_twovalue；若為互斥信號量此項為1，否則為0；struct task_struct*owner；互斥信號量被某進程持有時，owner指向其進程結(jié)構(gòu)體；int old_prio；記錄進程的原始優(yōu)先級；unsigned long old_policy；記錄進程的原始調(diào)度策略。

2.2.2 函數(shù)體的修改

對Linux源碼函數(shù)體的修改主要包括初始化、申請信號量未成功、申請信號量成功、釋放信號量4個部分。在此分別描述如下：

初始化：在struct sem中新增加if_twovalue、owner兩個成員后，需要在初始化信號量初始值的同時對其進行初始化，為此需要修改函數(shù)static int semctl_main（struct ipc_namespace*ns，int semid，int semnum，int cmd，int version，union semun arg），在該函數(shù)中將owner初始化為NULL，如果信號量的初始值為1，把if_twovalue項初始化為1，否為為0。

申請信號量成功：在進程申請信號量成功的情況下，如果此信號量的if_twovalue項為1，則表示該信號量為互斥信號量，進程在持有該信號量期間有可能發(fā)生優(yōu)先級反轉(zhuǎn)，需要在信號量結(jié)構(gòu)體中記錄進程的進程描述符，以方便在發(fā)生優(yōu)先級反轉(zhuǎn)時，對該進程執(zhí)行優(yōu)先級繼承，為此需要修改函數(shù) staticinttry_atomic_semop（structsem_array*sma，structsembuf*sops，int nsops，struct sem_undo*un，int pid）， 在該函數(shù)中做判斷，如果信號量為二值信號量，則將該進程的進程描述符記錄在信號量的owner項中。如果最后進程沒有成功申請到該信號量集，則需將信號量集中所有信號量結(jié)構(gòu)的owner項還原為NULL。

申請信號量未成功：如果是普通進程申請信號量集，不對其申請過程進行任何修改。而對于實時進程，如果其申請互斥信號量時被阻塞，則將其優(yōu)先級暫時“借給”該信號量當(dāng)前的持有者。然后將其待決操作結(jié)構(gòu)體按優(yōu)先級由高到低的順序插入到信號量集的待決操作鏈表中，如果其只申請了一個信號量，則還需要將其待決操作結(jié)構(gòu)體按優(yōu)先級由高到低的順序插入到相應(yīng)信號量的待決操作鏈表中。為此修改函數(shù)asmlinkagelongsys_semop（intsemid， struct sembuf__user*sops，unsigned nsops）；在該函數(shù)中判斷，如果被阻塞進程為實時進程，則將進程的待決操作結(jié)構(gòu)體按優(yōu)先級由高到低的順序插入到信號量集的待決操作鏈表中，否則將其插入到信號量待決操作鏈表的尾部。如果信號量集中只有一個信號量，還需要將進程的待決信號量操作結(jié)構(gòu)體與該信號量結(jié)構(gòu)體鏈接起來。由于執(zhí)行優(yōu)先級繼承是針對信號量集中的單個信號量的，所以依次對信號量集中的每一個信號量做判斷，如果為互斥信號量、當(dāng)前已被某一進程所持有、信號量操作為-1并且被阻塞進程的優(yōu)先級比持有該信號量的進程優(yōu)先級高，則將持有信號量進程的原始優(yōu)先級和調(diào)度策略保存在信號量結(jié)構(gòu)體中，并用被阻塞進程的優(yōu)先級和調(diào)度策略分別為其賦值。

在執(zhí)行了優(yōu)先級繼承時，還需要保證優(yōu)先級繼承的可傳遞性，考慮這樣一種情況：H、M、L是優(yōu)先級從高到低的3個任務(wù)，R、S是保護某兩個臨界資源的信號量。M已經(jīng)持有R信號量，而L已經(jīng)持有S信號量并且在申請R信號量時被阻塞。此時H任務(wù)就緒并申請S信號量，則按照上面優(yōu)先級繼承的規(guī)則H任務(wù)被阻塞在信號量S上，并將自己的優(yōu)先級繼承給L。但是L此時為阻塞狀態(tài)，所以為了讓L將繼承自H的優(yōu)先級傳遞給M，必須在優(yōu)先級繼承之后，調(diào)用wake_up_process對L執(zhí)行一次喚醒操作，L被喚醒之后會將其繼承到的優(yōu)先級傳遞給M。

釋放信號量：在進程釋放信號量時，將相應(yīng)信號量結(jié)構(gòu)struct sem的owner項重新置為NULL。并且需要判斷該進程是否繼承了其他進程的優(yōu)先級，如果是則需要將其優(yōu)先級還原，為此修改函數(shù)static int try_atomic_semop（struct sem_array*sma，struct sembuf*sops，int nsops，struct sem_undo*un，int pid），在該函數(shù)中做判斷，如果當(dāng)前信號量為互斥信號量且信號量操作為+1時，將信號量結(jié)構(gòu)體的owner項置為NULL，并使用信號量結(jié)構(gòu)體中的old_prio和old_policy兩項將進程的優(yōu)先級和調(diào)度策略還原。

3 改造后的System V信號量性能測試

對System V信號量進行改進后，需要對其進行測試來確定是否達到了預(yù)期的目的，測試的主要指標是實時進程申請信號量的延遲時間受其他進程影響的程度。

為了更好的表現(xiàn)優(yōu)先級繼承后的效果，我們設(shè)計了這樣一組進程：3 個進程 H（High）、M（Middle）、L（Low），其中 H 為實時進程，M、L為普通進程，其優(yōu)先級分別為-5、5（值越低優(yōu)先級越高），H、L競爭一個信號量S，H獲得信號量后計算延遲時間，然后釋放信號量并sleep 230 ms，L在獲得信號量后進行大約500 ms的數(shù)學(xué)計算然后釋放信號量，M則一直在進行數(shù)學(xué)運算。我們測試了只有H、L兩個進程時的延遲時間std作為基準，然后測試了有H、M、L 3個進程且未執(zhí)行優(yōu)先級繼承時的延遲時間orig以及有H、M、L 3個進程且實現(xiàn)了優(yōu)先級繼承時的延遲時間pinh，測試結(jié)果如圖1所示。

圖1 延遲時間對比圖（時間單位：ms）Fig.1 Structure diagram of the delay time comparison

由圖1可以看出，orig要遠高于std，這表明在未實現(xiàn)優(yōu)先級繼承的系統(tǒng)中，M進程的加入極大的增加了H進程申請信號量的延遲時間；而pinh與std相差不大，這表明優(yōu)先級繼承可以讓L盡快的執(zhí)行完并釋放信號量，有效地減小了H的延遲時間。

4 結(jié) 論

信號量是Linux多個進程間實現(xiàn)同步的手段，作為多用戶多任務(wù)的操作系統(tǒng)，信號量對整個操作系統(tǒng)的作用是非常重要的。在將Linux運用于實時應(yīng)用時，需要用優(yōu)先級繼承協(xié)議解決Linux信號量中存在的優(yōu)先級反轉(zhuǎn)問題。這對于提高系統(tǒng)的實時性具有重要意義。

[1]W.Richard Stevens，UNIX網(wǎng)絡(luò)編程第二卷：進程間通信[M].楊繼張譯.北京：清華大學(xué)出版社.

[2]Corbet J，Rubini A.Greg Kroah－Hartman Linux設(shè)備驅(qū)動程序[M].3版.北京:中國電力出版社，2006.

[3]Daniel P.Bovet，Marco Cesati 深入理解Linux內(nèi)核[M].3版.北京：中國電力出版社，2007.

[4]Robert Love Linux內(nèi)核設(shè)計與實現(xiàn)[M].2版.北京:機械工業(yè)出版社，2006.

[5]Intel Corporation IA－32 Intel Architecture Solfware Developer’s Manul Volume 3:System Programming Guide.

[6]Love，Robert.Linux Kernel Development[M].New York:MACMILLAN COMPUTER PUB，2005.

[7]Stevenson W R.Advanced Programming in the Unix Environment[M].Addison－Wesley，1992.