Linux實時性能優化算法分析與研究

李 梅

（西安歐亞學院 陜西 西安 710065）

Linux是一源代碼公開、功能強大、內核模塊化，裁剪方便。Linux支持多種體系結構，適合在嵌入式領域應用。作為嵌入式產品的操作系統平臺，實時性是一個很重要的目標。但隨著Linux逐漸應用到嵌入式領域，其實時性不夠強而一直受到批評。文中提出了一種提高Linux2.6實時性能的O(1)算法。

1 實時系統基本概念

實時操作系統（RealTime Operation System，RTOS）是指能夠接受外部數據發生并以足夠快的速度進行處理，其處理的結果又能在規定的時間之內來控制生產過程或對處理系統做出快速響應，并控制所有時間協調運行的操作系統[1]。在實時操作系統中，進程的執行結果的正確與否不僅與邏輯運算或數學計算結果的正確性相關，還與進程運行結束得出結果的時間有關，也就是說，如果一個進程的運算結果是正確的，但是由于它完成時間已經超出了系統給定的最后期限，在實時系統中，這個結果就是毫無意義的。所以RTOS的核心是必須在規定的時間內完成系統的指定操作，否則將引起系統性能急劇下降甚至系統崩潰[2]。實時操作系統有“軟實時”和“硬實時”之分[3]。軟實時需要系統盡可能快地完成操作，系統整體吞吐量達或者響應時間快，但特殊的任務在規定時間內不一定完成；硬實時則要求系統務必在規定時間內對時間進行處理。實時操作系統性能優劣可以從調度策略、內存管理、任務切換時間和中斷禁止時間等多方面衡量[4-5]。

2 Linux用于實時性操作系統的缺點

1)Linux中有大量不可搶占的區域

在Linux2.6中,內核己經可以搶占,因而實時性得到了加強"但是內核中仍有大量的不可搶占區域,如由自旋鎖(SPinlock)保護的臨界區。

2)時鐘粒度粗糙

Linux2.6內核雖然把時鐘頻率提高到1 000 赫茲，定時精度達到了1 ms，但遠不能滿足實時系統要求的微秒級定時精度，如數控系統要求50μs 的定時精度。

3)關閉中斷

系統調用和中斷服務程序中，為了保護臨界區資源,Linux會長時間關閉中斷"有些系統調用和中斷服務程序的時間還很長,這樣會加大中斷延遲時間。

4)缺乏有效的實時任務調度機制和調度算法

Linux系統是按照分時系統的目標設計的,以達到系統較好的平均性能，強調平衡各進程之間的響應時間來保證公平的CPU時間占用。通常采用固定時間片的分時調度算法，內核不能搶占，而實時系統的行為更多的取決于復雜的不可預知的情況。這些原則不能滿足實時系統短的響應時間和確定的執行行為的要求。

5)優先級反轉的問題

當一個低優先級的進程占用了某種資源，導致同樣需要這個資源的高級進程無法運行，并且此時有一個優先級在他們之間的就緒進程獲得了CPU 的控制權，這樣就使得高級別的任務需要等待比他優先級別低的任務，這種現象就叫做優先級反轉。在Linux中，由于資源是不可搶占的，并且不支持優先級繼承等策略，所以優先級反轉現象可能會發生，這影響了系統的實時性能。

3 Linux 2.6O(1)調度算法的設計

在Linux2.6開始以后，其進程調度程序被重新改寫，以適應嵌入式領域的發展。2.6版本的Linux內核使用了新的調度器算法，稱為O(1)算法，它在高負載的情況下執行得相當出色，并且當有很多處理器時也可以很好地擴展。O(n)表示算法時間復雜度，括號里的數字代表最壞情況下算法效率的上限取決于算法涉及到的元素的個數，O(1)說明是一個常數，在這種情況下，每次調度的效率是一樣的，與涉及的元素的多少沒有關系，O(n)表示算法效率取決于算法涉及元素的個數。

3.1 Linux2.6 新的數據結構

Linux 2.4 內核中，就緒進程隊列是一個全局的雙向鏈表，整個隊列由一個讀／寫自旋鎖保護著，調度器對它的所有操作都會因全局自旋鎖而導致系統各個處理機之間相互等待，使得就緒隊列成為一個明顯的瓶頸。而在Linux 2.6 中，就緒隊列被定義為一個復雜得多的數據結構 runqueue，并且每個 CPU 都將維護一個自己的就緒隊列，這將大大減小競爭。Linux2.6 的O(1)算法就是以這個數據結構為基礎進行調度的[6-7]。

Linux2.6為每個CPU定義了一個runqueue.。下面給出runqueue中關鍵的部分

此結構中最關鍵的是active和expired指針變量。其中active指針指向時間片沒用完、當前可被調度的就緒進程，即活躍進程的優先級數組，而expired指向時間片已用完的就緒進程，即過期進程的優先級數組。當一個進程時間片用完并且沒有被立刻激活時，只需重新計算時間片，并且將它移入expired指向的優先級數組即可。在 active指向的數組為空時，只要將兩個指針交換，由于expired指向的數組中的時間片都已計算好，只要放到active的位置立刻可以執行，此時的 active指向的數組則恰好充當新的expired數組。

active和expired兩者結構相同，均是prio_array 類型，prio_array其定義如下：

typedef struct

{

int nr_active;

unsigned long bitmap[BITMAP_SIZE];

struct list_head queue[MAX_PRIOR];

}priorarray;

比如說，在教學“以此函數的圖像和性質”時，教師要做好啟發的準備，要讓學生去走進實際知識中。教師可以為學生準備這樣的一個題目，x=（n-1）y-2n是x關于y的一次函數，你可以添加一個適當的條件求出它的解析式嗎？在提問后，教師可以先告訴學生，這個答案是不限制一個的，你們可以嘗試多求出幾個答案。學生在分析這道題中，其思維可以得到有效的釋放，由于答案不限制一項，就算是某些學生算的比較快，其他學生也都能投入到計算中。同時隨著學生們紛紛說出自己的答案，課堂的導向也從教師轉變為學生，學生主體性得到有效的展現，不僅活躍了課堂的氛圍，學生的思維也得到了有效的發散。

其中，nr_active表示當前中active中的進程數量；queue是一個list_head類型的數組；數組的每個元素都指向具有某一類優先級的進程。因為在每個進程控制塊中，都有一個run_list屬性，它是list_head類型數組，queue中的元素與具有某一類優先級的進程，以及具有同一類優先級的進程，都是通過run_list屬性鏈接起來的，比如說：queue[138]表示優先級為139的哪一類進程，這類進程通過各自進程控制中的runl_ist屬性鏈接在一起。當某個進程進入任務隊列時，通過一個名為list_add_tail的函數，將此進程掛到queue[R]所指向的隊列中。當要得到某個具體進程的進程控制塊時，先是通過queue[R]找到具有這類優先級的進程鏈表，然后得到某個具體進程的run_list屬性，再由函數list_entry通過run_list返回整個進程控制塊的結構。Bitmap是位圖數組，該數組中的每個元素都表示優先級在某一范圍內的進程。如：bitmap[0]對應的是優先級范圍為0～31的那些進程，bitmap[1]對應的是優先級范圍在32～63的那些進程，以此類推。正是因為在位圖數組與就緒任務隊列建立了一種映射關系，才使得Linux在高負載情況下，其進程調度的效率也是非常高的。

3.2 Linux2.6 O(1)調度程序的構成

整個調度程序的實現由兩部分組成：將進程加入到就緒隊列和檢索優先級最高的進程。

1)將進程加入到就緒隊列

①用enqueue_task（）將新進程加入到queue[n]所指向的鏈表中，其中n表示某類優先級。

②調用函數 _set_bit計算出該進程的優先級值，并將該進程優先級值與該進程所對應的bitmap中的值相加。

2)檢索優先級最高的進程

①獲取當前處理器運行的任務隊列

rq=this_rq();

array=rq-＞active;

②調用函數sched_find_first_bit()對任務隊列中的進程進行檢索。并返回具有最高優先級的那個進程在renqueue中的位置。idx = sched_find_first_bit(array-＞bitmap);

sched_find_first_bit()函數定義如下：

static inline int sched_find_first_bit(const unsigned long *arr)

{

if(unlikely(array[0]))

return _ffs(array[0]);

if(unlikely(array[1]))

return _ffs(array[1]+32);

if(unlikely(arr[2]))

return _ffs(array[2]+64);

if(unlikely(array[3]))

return _ffs(array[3]+96);

return _ffs(array[4]+128);

}

其中參數array為位圖數組，array[0]表示優先級為0～31的那類進程。函數_ffs()作用是根據數組array中各元素值找出優先級最高的進程。

③調用函數list_entry得到最高優先級進程的進程控制塊。

queue = array-＞queue + idx;

next = list_entry(queue-＞next, task_t, run_list);

④將此進程的next交給處理器執行

4 結束語

在 2.4 版的內核里，查找優先級最高的就緒進程的過程是在調度器 schedule() 中進行的，每一次調度都要進行一次，這種查找過程與當前就緒進程的個數相關，因此，查找所耗費的時間是 O(n) 級的，可見調度動作的執行時間和當前系統負載相關，這與嵌入式系統實時性的要求相違背。

為了加速搜索就緒進程鏈表中優先級最高的進程，2.6 版本用一個位圖數組來對應每一個優先級鏈表，如果該優先級鏈表非空，則對應位為 1，否則為 0。而且還構造了sched_find_first_bit() 函數來執行這一搜索操作，快速定位第一個非空的就緒進程鏈表。將檢索優先級最高的進程過程分解為n步，每一步所耗費的時間都是 O(1) 量級的。

最高優先級檢索算法是整個Linux2.6進程調度算法的重要組成部分，它的時間復雜度為O（1），這為整個Linux2.6進程調度算法的時間復雜度為O(1)做出了很大貢獻，從而提高了Linux2.6作為內核的嵌入式操作系統的實時響應能力。

[1] 龍飛.嵌入式Linux系統內核實時性研究[D].沈陽:沈陽工業大學,2012.

[2] Williams C.Linux Scheduler Lateney[C]//RedHatIne,March 2002.

[3] 代玲莉.Linux內核分析與實例應用[M].北京:國防工業出版社,2002.

[4] 毛佳.實時系統調度算法的優化設計[J].計算機工程與應用，2003,39(15):112-115.MAO Jia.Optimization design of real-time scheduling algorithm[J].Computer Engineering and Applications,2003,39(15):112-115.

[5] 劉磊,Linux內核進程調度算法的分析、研究與改進[D].黑龍江:黑龍江大學,2011.

[6] 張永選，姚遠耀.Linux2.6內核O(1)調度算法剖析[J].韶關學院學報:自然科學版,2009,30(6):5-9.ZHANG Yong-xuan,YAO Yuan-yao.Linux2.6 The kernel O(1)scheduling algorithm[J].Journal of Shaoguan University:Natural Science,2009,30(6):5-9.

[7] 張同光.Linux2.6內核分析-對進程調度機制的分析[J].長春工業大學學報:自然科學版,2006,27(4):333-337.ZHANH Tong-guang.Linux2.6 Kernel analysis- Analysis of the process of scheduling mechanism[J].Journal of Changchun University of Technology:Natural Science,2006,27(4):333-337.