王亞軍 中國人民武裝警察部隊學院

Linux內核優(yōu)先級倒轉分析

王亞軍 中國人民武裝警察部隊學院

Linux對于訪問同一內核臨界區(qū)的多個進程進行同步的有效手段是內核信號量機制。解決Linux內核信號量操作中存在的優(yōu)先級倒轉問題，是將Linux運用于實時系統(tǒng)的重要手段。文中在分析Linux內核信號量操作源代碼的基礎上，結合嵌入式應用深入分析其中存在的優(yōu)先級倒轉問題。

信號量 優(yōu)先級倒轉 嵌入式系統(tǒng) 等待隊列 實時性

1 引言

Linux內核允許多個進程并發(fā)執(zhí)行，從而極大限度地利用了CPU資源。但是為了避免多個進程同時進入臨界區(qū)，Linux內核采取了嚴格的同步機制，信號量就是其中之一。如果一個進程試圖獲得一個已經被占用的信號量，該進程就會被推進一個等待隊列進入“睡眠”狀態(tài)，從而釋放處理器，使處理器可以執(zhí)行其它進程的代碼。當持有信號量的進程釋放信號量以后，在等待隊列中睡眠的進程將被喚醒，并再次試圖獲得該信號量以進入臨界區(qū)。

2 Linux內核優(yōu)先級倒轉分析

在Linux-2.6.10內核中，當有多個進程等待進入一個臨界區(qū)時，當前進程略有優(yōu)勢，然后就是“先來先進”，即先鏈入等待隊列的進程先進入臨界區(qū)，而進程的優(yōu)先級并沒有起作用。也就是說，在這個等待隊列中，如果優(yōu)先級較低的進程排在前面，而優(yōu)先級較高的進程排在后面，那么優(yōu)先級較高的進程就只能等待。Linux內核實現(xiàn)了POSIX.4關于“實時進程”調度的要求，支持執(zhí)行SCHED_FIFO、SCHED_RR和SCHED_OTHER三種不同的調度政策。適用于前兩種政策的進程稱為實時進程，而適用于SCHED_OTHER的則為面向分時應用的普通進程。由于實時進程有較高的實時性要求，所以要將Linux內核用于實時要求較高的嵌入式應用，就應該對等待進入臨界區(qū)的進程鏈表進行優(yōu)化，減少實時進程的等待時間。

從Linux-2.6.10內核代碼中還可以看出，如果一個優(yōu)先級很低的進程A已經進入某個臨界區(qū)，那么當另一個優(yōu)先級很高的進程B也要進入該臨界區(qū)時，由于互斥信號量機制的阻攔而只能睡眠等待。由于互斥信號量所保護的臨界區(qū)內允許進程調度，已經進入某個臨界區(qū)的那個優(yōu)先級很低的進程A一旦受阻進入睡眠，再被喚醒時就很難得到機會運行，因為系統(tǒng)中所有優(yōu)先級比A高但比B低的進程都有可能擠在A的前面得到運行。而進程B盡管優(yōu)先級很高，卻反而只能等待這些進程都交出運行權，然后才能讓正在占用臨界區(qū)的進程A完成其操作而退出臨界區(qū)。為了將Linux內核用于實時要求較高的嵌入式應用，也需要通過修改進程優(yōu)先級的方法來解決優(yōu)先級倒轉問題。

3 Linux內核優(yōu)先級倒轉解決方法

Linux-2.6.10內核調度進程的主要依據(jù)是進程的優(yōu)先級，但又不是單純地按優(yōu)先級調度。普通進程擁有一個初始的優(yōu)先級，即靜態(tài)優(yōu)先級，它從一開始由用戶指定后，就不能改變。而調度程序要用到的動態(tài)優(yōu)先級是通過一個關于靜態(tài)優(yōu)先級和進程交互性的函數(shù)關系計算而來的。而對于實時進程，它們所采用的是實時優(yōu)先級，內核不為它們計算動態(tài)優(yōu)先級，這能保證給定優(yōu)先級別的實時進程總能搶占優(yōu)先級比它低的進程。SCHED_FIFO實現(xiàn)了一種簡單的、先入先出的調度算法，它不使用時間片。SCHED_FIFO級的進程會比任何SCHED_OTHER級的進程都先得到調度。一旦一個SCHED_FIFO級的進程處于可執(zhí)行狀態(tài)，就會一直運行，直到它自己受阻或顯式釋放處理器為止。SCHED_RR則是帶有時間片SCHED_FIFO，當SCHED_RR級的進程耗盡事先分配給它的時間片以后就不能繼續(xù)運行了，這是一種實時輪流調度算法。

為了對等待進入臨界區(qū)的進程鏈表進行改進，減少實時進程的等待時間，需要修改內核中與此相關的源代碼，在將需要等待進入臨界區(qū)的進程鏈入到相應的等待鏈表時，按照進程的優(yōu)先級將其插入到鏈表中的適當位置。由于內核中需要在臨界區(qū)內進行的操作一般都是很短促的，而普通進程又沒有較高的實時要求，所以這種改進只對實時進程來進行。當一個普通進程等待進入臨界區(qū)時，只是按照內核中原來的安排，將其簡單地鏈入等待隊列的尾部。而對于實時進程，則與進程調度的思想相一致，按照實時優(yōu)先級從高到低的順序，將其插入到等待進入臨界區(qū)的進程鏈表之中。對于優(yōu)先級相同的實時進程，仍然按照內核中原來的安排，即先鏈入等待隊列的實時進程先進入臨界區(qū)。為此，需要對內核中的相關源代碼進行修改，將等待隊列分成兩個小的等待隊列。

4 結語

綜上所述，在Linux內核中，信號量及其操作是內核對訪問共享資源的多個進程進行同步的關鍵，對系統(tǒng)的性能具有重要影響。當把linux內核應用于嵌入式系統(tǒng)時，由于嵌入式系統(tǒng)通常具有實時性要求，應該對信號量操作中存在的優(yōu)先級倒轉情況進行改進，以提高內核的實時性，這對于將Linux內核應用于具有實時性要求的嵌入式系統(tǒng)時是有意義的。

[1]毛德操,胡希明.Linux內核源代碼情景分析[M].杭州:浙江大學出版社，2002.

[2]毛德操,胡希明.嵌入式系統(tǒng)[M].杭州:浙江大學出版社，2003.[3]彭曉明、王強編著，《Lniux核心源代碼分析》,北京,人民郵電出版社，2002

河北省科研基金項目支持(HBSZKT-2014143)。

王亞軍，1978年生，男，漢族，籍貫：黑龍江綏化市，單位：中國人民武裝警察部隊學院，副教授，碩士，研究方向：Linux操作系統(tǒng)。