Linux內核優先級倒轉分析

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

Linux內核優先級倒轉分析

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

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

信號量 優先級倒轉 嵌入式系統 等待隊列 實時性

1 引言

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

2 Linux內核優先級倒轉分析

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

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

3 Linux內核優先級倒轉解決方法

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

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

4 結語

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

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

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

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

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