Linux操作系統信號量機制的實時化改造

李長松，蔣澤軍

（1.西北工業大學 計算機學院，陜西 西安 710129；2.西北工業大學 陜西 西安 710129）

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

Linux是一個多用戶多任務的操作系統，為了避免多個任務同時進入臨界區而造成的運行結果不確定，Linux為用戶提供了信號量[1，7]機制來實現進程間的同步。

本文在對System V信號量機制進行了深入的研究之后，發現其在應用于實時系統時存在的不足之處，并提出了對其進行改進的方法。

1 System V信號量機制

1.1 System V信號量機制

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

1.1.1 System V信號量機制重要的數據結構

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

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

待決操作數組sops用于描述在信號量上將要執行的操作，其數據結構的主要成員包括：unsigned short sem_num為信號量在信號量集中的索引，short sem_op為所要進行的操作，short sem_flg為操作標志。

1.1.2 System V信號量相關的系統調用

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

表1 函數調用對應表Tab.1 Function call corresponding table

sys_semctl函數對一個信號量集執行各種控制操作，包括獲取/設置信號量集中某個/全部信號量的當前值，將某個信號量集刪除等。

sys_semget函數創建一個信號量集或訪問一個已存在的信號量集。

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

1.2 優先級反轉現象描述

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

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

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

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

2.1 優先級繼承機制簡介

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

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

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

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

2.2 將優先級繼承機制運用于System V信號量

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

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

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

2.2.1 對Linux內核源碼相關結構體的修改

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

2.2.2 函數體的修改

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

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

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

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

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

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

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

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

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

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

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

4 結 論

信號量是Linux多個進程間實現同步的手段，作為多用戶多任務的操作系統，信號量對整個操作系統的作用是非常重要的。在將Linux運用于實時應用時，需要用優先級繼承協議解決Linux信號量中存在的優先級反轉問題。這對于提高系統的實時性具有重要意義。

[1]W.Richard Stevens，UNIX網絡編程第二卷：進程間通信[M].楊繼張譯.北京：清華大學出版社.

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

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

[4]Robert Love Linux內核設計與實現[M].2版.北京:機械工業出版社，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.