李 梅

（西安歐亞學(xué)院 陜西 西安 710065）

Linux是一源代碼公開、功能強(qiáng)大、內(nèi)核模塊化，裁剪方便。Linux支持多種體系結(jié)構(gòu)，適合在嵌入式領(lǐng)域應(yīng)用。作為嵌入式產(chǎn)品的操作系統(tǒng)平臺(tái)，實(shí)時(shí)性是一個(gè)很重要的目標(biāo)。但隨著Linux逐漸應(yīng)用到嵌入式領(lǐng)域，其實(shí)時(shí)性不夠強(qiáng)而一直受到批評(píng)。文中提出了一種提高Linux2.6實(shí)時(shí)性能的O(1)算法。

1 實(shí)時(shí)系統(tǒng)基本概念

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

2 Linux用于實(shí)時(shí)性操作系統(tǒng)的缺點(diǎn)

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

在Linux2.6中,內(nèi)核己經(jīng)可以搶占,因而實(shí)時(shí)性得到了加強(qiáng)"但是內(nèi)核中仍有大量的不可搶占區(qū)域,如由自旋鎖(SPinlock)保護(hù)的臨界區(qū)。

2)時(shí)鐘粒度粗糙

Linux2.6內(nèi)核雖然把時(shí)鐘頻率提高到1 000 赫茲，定時(shí)精度達(dá)到了1 ms，但遠(yuǎn)不能滿足實(shí)時(shí)系統(tǒng)要求的微秒級(jí)定時(shí)精度，如數(shù)控系統(tǒng)要求50μs 的定時(shí)精度。

3)關(guān)閉中斷

系統(tǒng)調(diào)用和中斷服務(wù)程序中，為了保護(hù)臨界區(qū)資源,Linux會(huì)長時(shí)間關(guān)閉中斷"有些系統(tǒng)調(diào)用和中斷服務(wù)程序的時(shí)間還很長,這樣會(huì)加大中斷延遲時(shí)間。

4)缺乏有效的實(shí)時(shí)任務(wù)調(diào)度機(jī)制和調(diào)度算法

Linux系統(tǒng)是按照分時(shí)系統(tǒng)的目標(biāo)設(shè)計(jì)的,以達(dá)到系統(tǒng)較好的平均性能，強(qiáng)調(diào)平衡各進(jìn)程之間的響應(yīng)時(shí)間來保證公平的CPU時(shí)間占用。通常采用固定時(shí)間片的分時(shí)調(diào)度算法，內(nèi)核不能搶占，而實(shí)時(shí)系統(tǒng)的行為更多的取決于復(fù)雜的不可預(yù)知的情況。這些原則不能滿足實(shí)時(shí)系統(tǒng)短的響應(yīng)時(shí)間和確定的執(zhí)行行為的要求。

5)優(yōu)先級(jí)反轉(zhuǎn)的問題

當(dāng)一個(gè)低優(yōu)先級(jí)的進(jìn)程占用了某種資源，導(dǎo)致同樣需要這個(gè)資源的高級(jí)進(jìn)程無法運(yùn)行，并且此時(shí)有一個(gè)優(yōu)先級(jí)在他們之間的就緒進(jìn)程獲得了CPU 的控制權(quán)，這樣就使得高級(jí)別的任務(wù)需要等待比他優(yōu)先級(jí)別低的任務(wù)，這種現(xiàn)象就叫做優(yōu)先級(jí)反轉(zhuǎn)。在Linux中，由于資源是不可搶占的，并且不支持優(yōu)先級(jí)繼承等策略，所以優(yōu)先級(jí)反轉(zhuǎn)現(xiàn)象可能會(huì)發(fā)生，這影響了系統(tǒng)的實(shí)時(shí)性能。

3 Linux 2.6O(1)調(diào)度算法的設(shè)計(jì)

在Linux2.6開始以后，其進(jìn)程調(diào)度程序被重新改寫，以適應(yīng)嵌入式領(lǐng)域的發(fā)展。2.6版本的Linux內(nèi)核使用了新的調(diào)度器算法，稱為O(1)算法，它在高負(fù)載的情況下執(zhí)行得相當(dāng)出色，并且當(dāng)有很多處理器時(shí)也可以很好地?cái)U(kuò)展。O(n)表示算法時(shí)間復(fù)雜度，括號(hào)里的數(shù)字代表最壞情況下算法效率的上限取決于算法涉及到的元素的個(gè)數(shù)，O(1)說明是一個(gè)常數(shù)，在這種情況下，每次調(diào)度的效率是一樣的，與涉及的元素的多少?zèng)]有關(guān)系，O(n)表示算法效率取決于算法涉及元素的個(gè)數(shù)。

3.1 Linux2.6 新的數(shù)據(jù)結(jié)構(gòu)

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

Linux2.6為每個(gè)CPU定義了一個(gè)runqueue.。下面給出runqueue中關(guān)鍵的部分

此結(jié)構(gòu)中最關(guān)鍵的是active和expired指針變量。其中active指針指向時(shí)間片沒用完、當(dāng)前可被調(diào)度的就緒進(jìn)程，即活躍進(jìn)程的優(yōu)先級(jí)數(shù)組，而expired指向時(shí)間片已用完的就緒進(jìn)程，即過期進(jìn)程的優(yōu)先級(jí)數(shù)組。當(dāng)一個(gè)進(jìn)程時(shí)間片用完并且沒有被立刻激活時(shí)，只需重新計(jì)算時(shí)間片，并且將它移入expired指向的優(yōu)先級(jí)數(shù)組即可。在 active指向的數(shù)組為空時(shí)，只要將兩個(gè)指針交換，由于expired指向的數(shù)組中的時(shí)間片都已計(jì)算好，只要放到active的位置立刻可以執(zhí)行，此時(shí)的 active指向的數(shù)組則恰好充當(dāng)新的expired數(shù)組。

active和expired兩者結(jié)構(gòu)相同，均是prio_array 類型，prio_array其定義如下：

typedef struct

{

int nr_active;

unsigned long bitmap[BITMAP_SIZE];

struct list_head queue[MAX_PRIOR];

}priorarray;

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

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

3.2 Linux2.6 O(1)調(diào)度程序的構(gòu)成

整個(gè)調(diào)度程序的實(shí)現(xiàn)由兩部分組成：將進(jìn)程加入到就緒隊(duì)列和檢索優(yōu)先級(jí)最高的進(jìn)程。

1)將進(jìn)程加入到就緒隊(duì)列

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

②調(diào)用函數(shù) _set_bit計(jì)算出該進(jìn)程的優(yōu)先級(jí)值，并將該進(jìn)程優(yōu)先級(jí)值與該進(jìn)程所對(duì)應(yīng)的bitmap中的值相加。

2)檢索優(yōu)先級(jí)最高的進(jìn)程

①獲取當(dāng)前處理器運(yùn)行的任務(wù)隊(duì)列

rq=this_rq();

array=rq-＞active;

②調(diào)用函數(shù)sched_find_first_bit()對(duì)任務(wù)隊(duì)列中的進(jìn)程進(jìn)行檢索。并返回具有最高優(yōu)先級(jí)的那個(gè)進(jìn)程在renqueue中的位置。idx = sched_find_first_bit(array-＞bitmap);

sched_find_first_bit()函數(shù)定義如下：

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);

}

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

③調(diào)用函數(shù)list_entry得到最高優(yōu)先級(jí)進(jìn)程的進(jìn)程控制塊。

queue = array-＞queue + idx;

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

④將此進(jìn)程的next交給處理器執(zhí)行

4 結(jié)束語

在 2.4 版的內(nèi)核里，查找優(yōu)先級(jí)最高的就緒進(jìn)程的過程是在調(diào)度器 schedule() 中進(jìn)行的，每一次調(diào)度都要進(jìn)行一次，這種查找過程與當(dāng)前就緒進(jìn)程的個(gè)數(shù)相關(guān)，因此，查找所耗費(fèi)的時(shí)間是 O(n) 級(jí)的，可見調(diào)度動(dòng)作的執(zhí)行時(shí)間和當(dāng)前系統(tǒng)負(fù)載相關(guān)，這與嵌入式系統(tǒng)實(shí)時(shí)性的要求相違背。

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

最高優(yōu)先級(jí)檢索算法是整個(gè)Linux2.6進(jìn)程調(diào)度算法的重要組成部分，它的時(shí)間復(fù)雜度為O（1），這為整個(gè)Linux2.6進(jìn)程調(diào)度算法的時(shí)間復(fù)雜度為O(1)做出了很大貢獻(xiàn)，從而提高了Linux2.6作為內(nèi)核的嵌入式操作系統(tǒng)的實(shí)時(shí)響應(yīng)能力。

[1] 龍飛.嵌入式Linux系統(tǒng)內(nèi)核實(shí)時(shí)性研究[D].沈陽:沈陽工業(yè)大學(xué),2012.

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

[3] 代玲莉.Linux內(nèi)核分析與實(shí)例應(yīng)用[M].北京:國防工業(yè)出版社,2002.

[4] 毛佳.實(shí)時(shí)系統(tǒng)調(diào)度算法的優(yōu)化設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用，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內(nèi)核進(jìn)程調(diào)度算法的分析、研究與改進(jìn)[D].黑龍江:黑龍江大學(xué),2011.

[6] 張永選，姚遠(yuǎn)耀.Linux2.6內(nèi)核O(1)調(diào)度算法剖析[J].韶關(guān)學(xué)院學(xué)報(bào):自然科學(xué)版,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內(nèi)核分析-對(duì)進(jìn)程調(diào)度機(jī)制的分析[J].長春工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,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.