一種Minix進(jìn)程調(diào)度的改進(jìn)算法

陳亮強(qiáng)，錢振江，2

（1.常熟理工學(xué)院計算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500；2.南京大學(xué)計算機(jī)科學(xué)與技術(shù)系，江蘇 南京 210023）

一種Minix進(jìn)程調(diào)度的改進(jìn)算法

陳亮強(qiáng)1，錢振江1，2

（1.常熟理工學(xué)院計算機(jī)科學(xué)與工程學(xué)院，江蘇 常熟 215500；2.南京大學(xué)計算機(jī)科學(xué)與技術(shù)系，江蘇 南京 210023）

為了提升Minix進(jìn)程調(diào)度的性能，通過研究和借鑒Linux進(jìn)程調(diào)度算法的思想，提出了一種Minix進(jìn)程調(diào)度的改進(jìn)算法.針對Minix多級隊(duì)列調(diào)度算法的時間片固定的缺點(diǎn)，通過使時間片基于進(jìn)程的優(yōu)先級動態(tài)變化讓Minix調(diào)度器在調(diào)度進(jìn)程時更加體現(xiàn)公平性.

Minix；進(jìn)程調(diào)度；公平性

1 引言

操作系統(tǒng)的發(fā)展經(jīng)歷了漫長的過程，但是真正快速發(fā)展起來是從20世紀(jì)60年代開始的.目前市場上主要被人們認(rèn)可的可以用于實(shí)際生產(chǎn)生活的操作系統(tǒng)數(shù)量并不多，其中Linux占的比重很大，而Minix卻相形見絀.就發(fā)展時間來看，Minix出現(xiàn)的時間要早于Linux，但是后者用戶的基數(shù)與前者不在一個數(shù)量級上. Minix與Linux都是類Unix的操作系統(tǒng)，而Linux當(dāng)中的許多思想也是借鑒于Minix，只是當(dāng)初Minix的開發(fā)者作為大學(xué)教授只想要將該操作系統(tǒng)作為一款學(xué)生學(xué)習(xí)操作系統(tǒng)理念的工具而沒有過多擴(kuò)展其功能［1］，而Linux的發(fā)展是許多人共同努力的結(jié)果.Linux內(nèi)核從最初的版本開始經(jīng)過不斷的改進(jìn)，慢慢適應(yīng)了市場的要求，許多原本有缺陷的地方也在原始開發(fā)者的努力和社區(qū)開發(fā)者們的幫助下逐漸完善.單就調(diào)度器這塊，Linux采用的調(diào)度算法就經(jīng)歷了幾次大的變化，從O（n）調(diào)度算法到O（1）調(diào)度算法再到CFS調(diào)度算法［2］，不僅操作系統(tǒng)的調(diào)度性能提升很大，而且在調(diào)度公平性方面也取得了很好的效果.

為了更好地發(fā)展Minix，目前Minix開發(fā)團(tuán)隊(duì)推出了最新的Minix 3，主要用于小型PC機(jī)和嵌入式系統(tǒng).為了使操作系統(tǒng)變得更加可靠，Minix 3采用了微內(nèi)核的設(shè)計理念，并且越來越模塊化，但是這些特性并不影響對其內(nèi)部某一功能模塊的研究［1］.為了增強(qiáng)Minix的性能，提升其進(jìn)程調(diào)度的效率和公平性是一個很好的切入點(diǎn).通過改進(jìn)Minix進(jìn)程調(diào)度器的調(diào)度算法使Minix的進(jìn)程調(diào)度達(dá)到一個負(fù)載平衡的狀態(tài)，這樣有利于Minix的后續(xù)發(fā)展.既然要對Minix當(dāng)中的進(jìn)程調(diào)度算法進(jìn)行改進(jìn)，那么首先應(yīng)當(dāng)分析它的不足之處，哪些方面還有待提高.在Minix 3中進(jìn)程調(diào)度器采用的是多級隊(duì)列調(diào)度算法，這個算法會在第4節(jié)詳細(xì)介紹.通過對這個算法的過程分析可以發(fā)現(xiàn)，在調(diào)度進(jìn)程時，調(diào)度的公平性并沒有得到很好的保障，未實(shí)現(xiàn)進(jìn)程調(diào)度的相對公平.和Minix具有同樣的情況，Linux 2.6采用的O（1）調(diào)度算法［3］在公平性方面也處理得不是很好，但是到了Linux 2.6.23之后Linux內(nèi)核就改用CFS（完全公平）調(diào)度算法［4］，這時Linux才真正實(shí)現(xiàn)了進(jìn)程調(diào)度的相對公平.O（1）調(diào)度和CFS調(diào)度是目前Linux操作系統(tǒng)用的最多的調(diào)度算法，是操作系統(tǒng)進(jìn)程調(diào)度的前沿.通過研究它們，開發(fā)者對操作系統(tǒng)進(jìn)程管理方面有了更深層的認(rèn)識.并且實(shí)現(xiàn)Minix進(jìn)程間調(diào)度更加公平的改進(jìn)方案，對于現(xiàn)代許多調(diào)度算法來說也有很大的啟迪作用.有些算法可能隨著時代的發(fā)展因?yàn)槟承┓矫娴牟蛔愣惶蕴?，但是通過對這些算法進(jìn)行一些改進(jìn)可能就會有意想不到的效果.

2 相關(guān)工作

Linux之父Linus Torvalds在開發(fā)Linux時借鑒了不少M(fèi)inix的內(nèi)容，現(xiàn)在為了更好的發(fā)展Minix，就需要反過來借鑒Linux成熟的算法.第3節(jié)對O（1）調(diào)度算法和CFS調(diào)度算法進(jìn)行研究，對CFS調(diào)度器取代O（1）調(diào)度器成為當(dāng)前Linux內(nèi)核調(diào)度器的原因進(jìn)行探索［5］.通過對它們的數(shù)據(jù)結(jié)構(gòu)、優(yōu)先級、時間片和工作流程等方面的研究來挖掘出其最本質(zhì)的設(shè)計理念，然后借鑒這些理念可以在公平性方面對Minix的多級隊(duì)列調(diào)度算法［1］進(jìn)行改進(jìn)，讓其調(diào)度器在調(diào)度進(jìn)程時更能達(dá)到進(jìn)程間調(diào)度的相對公平的效果，這樣才更加符合現(xiàn)代操作系統(tǒng)的需要.下面主要研究CFS調(diào)度在O（1）調(diào)度的基礎(chǔ)上如何實(shí)現(xiàn)進(jìn)程間調(diào)度的相對公平，然后從研究的成果中提取出最本質(zhì)的事物，即設(shè)計思想，比如權(quán)重和虛擬運(yùn)行時間的概念等.并通過這些思想，對多級隊(duì)列調(diào)度中已有的優(yōu)先級和時間片進(jìn)行改進(jìn)，也加入權(quán)重和閾值等來對進(jìn)程的時間片進(jìn)行動態(tài)的變化以實(shí)現(xiàn)公平的原則.最后，還需要通過實(shí)驗(yàn)來親自驗(yàn)證這種改進(jìn)方案的可行性.

3 Linux中的調(diào)度思想

在Linux操作系統(tǒng)中，有實(shí)時進(jìn)程和普通進(jìn)程之分，對于這兩種進(jìn)程有3種方式的調(diào)度策略，它們分別為SCHED_FIFO、SCHED_RR和SCHED_NORMAL，前兩個適合于實(shí)時進(jìn)程，而最后一個適合于普通進(jìn)程.對O（1）調(diào)度算法和CFS調(diào)度算法的研究主要圍繞著普通進(jìn)程展開.

3.1 O（1）調(diào)度算法

Linux的O（1）調(diào)度器對可運(yùn)行態(tài)進(jìn)程進(jìn)行調(diào)度主要是通過內(nèi)核源碼中的schedule（）函數(shù)［6］實(shí)現(xiàn)的.該函數(shù)的核心執(zhí)行步驟如下：

步驟1若當(dāng)前處理器的運(yùn)行隊(duì)列上沒有任何可運(yùn)行態(tài)進(jìn)程，那么為了實(shí)現(xiàn)多處理器間的負(fù)載平衡，則從其他處理器上調(diào)一些可運(yùn)行態(tài)進(jìn)程過來.若調(diào)完后當(dāng)前處理器的運(yùn)行隊(duì)列上還是沒有進(jìn)程可運(yùn)行，則在處理器上運(yùn)行idle進(jìn)程來使處理器處于低功耗模式直到有可運(yùn)行態(tài)進(jìn)程出現(xiàn).若運(yùn)行隊(duì)列上有可運(yùn)行態(tài)進(jìn)程則執(zhí)行步驟2；

步驟2判斷active隊(duì)列是否為空.當(dāng)active隊(duì)列為空，即表示所有活動進(jìn)程都運(yùn)行完了，這時就要讓expired隊(duì)列中的過期進(jìn)程再次變?yōu)榛顒舆M(jìn)程.但是并不需要將expired隊(duì)列中的進(jìn)程一個個移進(jìn)active隊(duì)列中去，只需要將active和expired的指針指向的地址互換就行了；

步驟3步驟2執(zhí)行成功后active隊(duì)列中必定存在活動進(jìn)程，這時通過active中的優(yōu)先級位圖bitmap來選擇優(yōu)先級最高且有可運(yùn)行態(tài)進(jìn)程的優(yōu)先級隊(duì)列；

步驟4最后選擇active的bitamp所指向鏈表中的第一個進(jìn)程運(yùn)行即可.

通過以上這4個核心步驟，O（1）調(diào)度器基本完成了對于可運(yùn)行態(tài)進(jìn)程的一次調(diào)度過程，如圖1所示. 3.2CFS調(diào)度算法

圖1 O（1）算法調(diào)度過程

3.2.1 引言

從Linux2.6.23開始，對于普通進(jìn)程的調(diào)度已經(jīng)不再使用O（1）調(diào)度算法了.因?yàn)榭紤]到O（1）調(diào)度的一些不足以及公平性方面的缺陷，所以改用完全公平調(diào)度（CFS）算法.不同于O（1）調(diào)度，CFS調(diào)度基于公平的理念，對進(jìn)程一視同仁，不再對交互式進(jìn)程進(jìn)行區(qū)別，也不再根據(jù)進(jìn)程的平均睡眠時間來確定獎勵bonus并以此來調(diào)整動態(tài)優(yōu)先級.取而代之，CFS通過權(quán)重使每個進(jìn)程都能夠獲得公平的運(yùn)行時間.更為關(guān)鍵的是，CFS調(diào)度算法的設(shè)計和實(shí)現(xiàn)都很簡單，且實(shí)際性能非常優(yōu)越.CFS的主要調(diào)度方式是通過紅黑樹的樹型結(jié)構(gòu)來選擇虛擬運(yùn)行時間最小的進(jìn)程來運(yùn)行，CFS調(diào)度器的整體結(jié)構(gòu)如圖2所示.

圖2 CFS調(diào)度器的整體結(jié)構(gòu)

3.2.2 虛擬運(yùn)行時間

為了實(shí)現(xiàn)公平，開發(fā)者將虛擬運(yùn)行時間引入到CFS調(diào)度中來取代優(yōu)先級對于選擇進(jìn)程運(yùn)行的決定地位，在內(nèi)核源碼中用vruntime字段［7］來表示虛擬運(yùn)行時間.并且在CFS中主要有兩個要素可以決定進(jìn)程的虛擬運(yùn)行時間，它們分別是進(jìn)程的權(quán)重和進(jìn)程實(shí)際運(yùn)行的時間.調(diào)度器總是調(diào)度虛擬運(yùn)行時間最小的進(jìn)程，并且在每一次時鐘中斷到來時，內(nèi)核都要重新計算當(dāng)前進(jìn)程的虛擬運(yùn)行時間.正在運(yùn)行的進(jìn)程的虛擬運(yùn)行時間隨著運(yùn)行時間的增長而增長，當(dāng)它的虛擬運(yùn)行時間不是可運(yùn)行態(tài)進(jìn)程中的最小值時它就會被其他可運(yùn)行態(tài)進(jìn)程搶占，而且能夠看出虛擬運(yùn)行時間與當(dāng)前進(jìn)程運(yùn)行的時間、虛擬運(yùn)行時間與當(dāng)前進(jìn)程的權(quán)重的關(guān)系：虛擬運(yùn)行時間與當(dāng)前進(jìn)程運(yùn)行的時間成正比，與當(dāng)前進(jìn)程的權(quán)重成反比.

由此可見，當(dāng)一個進(jìn)程的優(yōu)先級越高，運(yùn)行的時間越少時，這個進(jìn)程的虛擬運(yùn)行時間就越小，此進(jìn)程就越應(yīng)該被調(diào)度執(zhí)行.

3.2.3 紅黑樹

相比于O（1）調(diào)度，CFS調(diào)度沒有用運(yùn)行隊(duì)列來維護(hù)可運(yùn)行態(tài)進(jìn)程，而是用紅黑樹來組織普通進(jìn)程.紅黑樹［7］本質(zhì)上是一棵二叉查找樹，它具有以下5個特點(diǎn)：

特點(diǎn)1每個葉結(jié)點(diǎn)都是空結(jié)點(diǎn)，并且它們是黑色的；特點(diǎn)2根結(jié)點(diǎn)是黑色的；

特點(diǎn)3紅色結(jié)點(diǎn)的子結(jié)點(diǎn)必定是黑色的；

特點(diǎn)4對于任意結(jié)點(diǎn)而言，其到葉節(jié)點(diǎn)的每條路徑上的黑色結(jié)點(diǎn)的數(shù)目都相同；

特點(diǎn)5每個結(jié)點(diǎn)不是黑色就是紅色.

這些特點(diǎn)決定了紅黑樹是自平衡的，雖然紅黑樹沒有達(dá)到恒定O（1）的時間復(fù)雜度，但是它最差的時間復(fù)雜度也為O（logn），這就決定了它可以在插入和刪除等操作上表現(xiàn)得非常高效.

CFS使用的紅黑樹是以時間為順序的，它的結(jié)點(diǎn)由調(diào)度實(shí)體來描述，關(guān)于調(diào)度實(shí)體的概念將在下一節(jié)組調(diào)度中介紹，而進(jìn)程的虛擬運(yùn)行時間和權(quán)重也存放在這個結(jié)構(gòu)中，圖3描繪了CFS中紅黑樹的結(jié)構(gòu).

內(nèi)核通過紅黑樹來對虛擬運(yùn)行時間進(jìn)行排序，紅黑樹的最左側(cè)結(jié)點(diǎn)的虛擬運(yùn)行時間最少，所以該結(jié)點(diǎn)所表示的進(jìn)程將是下一個要被調(diào)度的進(jìn)程.

3.3 兩種算法的比較

圖3 CFS中紅黑樹的結(jié)構(gòu)

通過對于O（1）調(diào)度和CFS調(diào)度的研究，發(fā)現(xiàn)它們的區(qū)別歸根結(jié)底在于兩者設(shè)計思想的不同.O（1）調(diào)度是通過優(yōu)先級來實(shí)現(xiàn)對時間片的絕對映射，而CFS調(diào)度對于時間片的映射則是通過權(quán)重完成的.CFS調(diào)度相比O（1）調(diào)度的最主要優(yōu)勢在于它實(shí)現(xiàn)了進(jìn)程間調(diào)度的相對公平，而這也是調(diào)度算法設(shè)計中非常重要的一個部分.雖然O（1）調(diào)度的恒定的時間復(fù)雜度O（1）也是一大特色，只是CFS的O（log n）的性能已經(jīng)能夠滿足系統(tǒng)的需要，而且CFS的設(shè)計與實(shí)現(xiàn)簡單，實(shí)際運(yùn)行高效，不像O（1）調(diào)度有那么多的復(fù)雜公式，彌補(bǔ)了O（1）調(diào)度的許多不足之處.所以，這些因素最終決定了CFS調(diào)度要取代O（1）調(diào)度的位置.但是也不能完全否定O（1）調(diào)度算法，它對于以后進(jìn)程調(diào)度算法的發(fā)展還是有許多值得借鑒的地方.

4 改進(jìn)Minix調(diào)度算法

4.1多級隊(duì)列調(diào)度算法

4.1.1 數(shù)據(jù)結(jié)構(gòu)

和O（1）調(diào)度類似，多級隊(duì)列調(diào)度在數(shù)據(jù)結(jié)構(gòu)方面也采用了優(yōu)先級隊(duì)列.在多級隊(duì)列調(diào)度中，一共有16個優(yōu)先級隊(duì)列，每個優(yōu)先級對應(yīng)一個隊(duì)列［1］，其結(jié)構(gòu)如圖4所示.

在優(yōu)先級隊(duì)列中，隊(duì)列0的優(yōu)先級最大，而隊(duì)列15的優(yōu)先級最小.head指針指向隊(duì)首進(jìn)程，而tail指針指向隊(duì)尾進(jìn)程，這樣就可以方便地實(shí)現(xiàn)進(jìn)程的出隊(duì)和入隊(duì)操作.

圖4 初始進(jìn)程隊(duì)列

4.1.2 調(diào)度流程

步驟1調(diào)度器維護(hù)16個隊(duì)列，一個優(yōu)先級級別與一個隊(duì)列相對應(yīng).隊(duì)列的序號越大，優(yōu)先級越低；步驟2隊(duì)列的優(yōu)先級越高，該隊(duì)列分配的時間片越大；步驟3若某一隊(duì)列中進(jìn)程不唯一，則輪到該進(jìn)程運(yùn)行時，它運(yùn)行完了又會回到本隊(duì)列的隊(duì)尾；

步驟4若某一隊(duì)列中進(jìn)程唯一，即輪到該隊(duì)列中進(jìn)程運(yùn)行時本次運(yùn)行的進(jìn)程也是下次要運(yùn)行的進(jìn)程，則在該進(jìn)程連續(xù)兩次運(yùn)行完之后就會被安排到優(yōu)先級更低的隊(duì)列隊(duì)尾，也就是說進(jìn)程被降低了優(yōu)先級，即進(jìn)行優(yōu)先級的數(shù)值+1的懲罰；

步驟5若一個進(jìn)程被降低了優(yōu)先級后，它又阻礙了其他進(jìn)程的運(yùn)行，則會被再次降低優(yōu)先級，但是可降低到的最低優(yōu)先級值為14，即普通進(jìn)程不能和IDLE進(jìn)程同處一個隊(duì)列.若它運(yùn)行完一個時間片后沒有阻礙其他進(jìn)程的運(yùn)行，調(diào)度器將提高它的優(yōu)先級，即進(jìn)行優(yōu)先級值-1的獎勵.對于優(yōu)先級的提高，最高可到達(dá)它所被允許的最大優(yōu)先級為止；

步驟6最低優(yōu)先級隊(duì)列只能由IDLE進(jìn)程使用，它在系統(tǒng)無其他就緒進(jìn)程運(yùn)行時運(yùn)行.用戶進(jìn)程默認(rèn)啟動時的優(yōu)先級要高于IDLE進(jìn)程；

步驟7雖然隊(duì)列內(nèi)的調(diào)度很像時間片輪轉(zhuǎn)調(diào)度，但是又有區(qū)別.如果一個進(jìn)程阻塞時沒有用完本身所擁有的時間片，那么當(dāng)這個進(jìn)程再次變?yōu)榫途w狀態(tài)時，系統(tǒng)就會將它放到它之前所在隊(duì)列的隊(duì)首等待被調(diào)度，而且它運(yùn)行時的時間片是它上次運(yùn)行剩下的時間片.調(diào)度器通過這種方式可以加快I/O調(diào)度；

步驟8系統(tǒng)進(jìn)程的優(yōu)先級高于用戶進(jìn)程的優(yōu)先級，只有在所有系統(tǒng)進(jìn)程都運(yùn)行完后才能運(yùn)行用戶進(jìn)程；

步驟9調(diào)度器調(diào)度進(jìn)程時，總是以隊(duì)列0作為起點(diǎn)，依次檢查該隊(duì)列是否有就緒進(jìn)程存在.若有，則選擇隊(duì)首進(jìn)程運(yùn)行，否則檢查下一個次高優(yōu)先級隊(duì)列.若前15個隊(duì)列都沒有就緒進(jìn)程存在，則運(yùn)行IDLE進(jìn)程使CPU處于低功耗模式，直到系統(tǒng)產(chǎn)生下一個中斷為止.

多級隊(duì)列調(diào)度的流程如圖5所示.

4.2 改進(jìn)方案

4.2.1 調(diào)度的不足

從CFS調(diào)度和多級隊(duì)列調(diào)度中可以看出，雖然兩者都可以防止某一進(jìn)程長時間得不到運(yùn)行的情況，但是CFS調(diào)度在進(jìn)程間調(diào)度公平方面做得更好，而多級隊(duì)列調(diào)度恰恰在這方面有所欠缺.

多級隊(duì)列調(diào)度在數(shù)據(jù)結(jié)構(gòu)方面與O（1）調(diào)度很相似，都采取優(yōu)先級隊(duì)列，當(dāng)一個進(jìn)程長時間占用CPU時，系統(tǒng)就會降低它的優(yōu)先級直到下一個進(jìn)程被調(diào)度運(yùn)行為止.但是在進(jìn)程降低優(yōu)先級的過程中，系統(tǒng)會根據(jù)它所在的優(yōu)先級隊(duì)列分配時間片然后讓其等待運(yùn)行，進(jìn)程被分配的時間片是固定的，這樣就有可能等到其他進(jìn)程有機(jī)會運(yùn)行的時候已經(jīng)過了很長時間，即其他進(jìn)程的等待時間很長，使進(jìn)程調(diào)度不公平.

圖5 多級隊(duì)列調(diào)度

4.2.2 進(jìn)程公平性方面的改進(jìn)

對于多級隊(duì)列調(diào)度算法存在的不足，Linux2.6的O（1）調(diào)度器也存在這樣的問題，但是Linux2.6.23之后的CFS調(diào)度就這樣的問題提出了權(quán)重和虛擬運(yùn)行時間的概念，以此來動態(tài)劃分時間片.基于這些思想，改進(jìn)方案也是對多級隊(duì)列調(diào)度的時間片進(jìn)行動態(tài)劃分，主要提出兩個改進(jìn)的想法，一個是引用權(quán)重的思想來對時間片進(jìn)行動態(tài)的變化，讓長時間占用CPU的進(jìn)程能夠更快被其他進(jìn)程取代；另一個就是通過閾值的設(shè)定防止進(jìn)程所分配的時間片超出最小范圍，因?yàn)闀r間片太小的話會使進(jìn)程切換過度頻繁而浪費(fèi)許多不必要的切換時間.下面就這兩個方面進(jìn)行討論：

（一）通過權(quán)重實(shí)現(xiàn)時間片的動態(tài)劃分

因?yàn)橐粋€進(jìn)程在某個優(yōu)先級隊(duì)列中連續(xù)兩次運(yùn)行后系統(tǒng)就會降低它的優(yōu)先級，然后它的時間片會被系統(tǒng)重新分配，并將它放在優(yōu)先級更低的隊(duì)列中和其他原有的進(jìn)程一起進(jìn)行時間片輪轉(zhuǎn)調(diào)度.改進(jìn)后，采用權(quán)重來對進(jìn)程的時間片進(jìn)行動態(tài)劃分，權(quán)重的計算見公式1.

公式1

其中，weight表示進(jìn)程的權(quán)重，max_priority表示進(jìn)程的最大優(yōu)先級，priority表示進(jìn)程的當(dāng)前優(yōu)先級.

權(quán)重是根據(jù)進(jìn)程優(yōu)先級的降低程度計算出來的，然后由權(quán)重再來計算當(dāng)前進(jìn)程將被分配的時間片大小，具體見公式2．

公式2

其中，now_times表示進(jìn)程當(dāng)前的時間片，times表示進(jìn)程的初始時間片.

通過以上兩個公式就可以動態(tài)改變進(jìn)程的時間片，假如進(jìn)程因?yàn)槌掷m(xù)占用CPU而導(dǎo)致優(yōu)先級降低的話，它本身的時間片也是降低的，并且降低的幅度越大，時間片也就下降得越快，這樣其他優(yōu)先級低的進(jìn)程就有更大的機(jī)會運(yùn)行了，體現(xiàn)了進(jìn)程間調(diào)度的公平性.

（二）利用閥值限定時間片的范圍

若進(jìn)程優(yōu)先級下降幅度太大，就會導(dǎo)致劃分的時間片太小，時間片太小就會使進(jìn)程切換過度頻繁而浪費(fèi)許多不必要的切換時間.為了防止這種情況的發(fā)生，設(shè)定一個固定的閥值來對時間片進(jìn)行檢測.當(dāng)時間片小于這個閥值時，時間片就會按照閥值的大小被分配，具體見公式3.

公式3

其中，threshold表示閥值的大小.

通過以上兩個方法，實(shí)現(xiàn)了在進(jìn)程調(diào)度公平性方面對Minix的多級隊(duì)列調(diào)度算法的改進(jìn).

5 實(shí)驗(yàn)及結(jié)果分析

5.1 實(shí)驗(yàn)設(shè)計

為了驗(yàn)證Minix當(dāng)中的多級隊(duì)列調(diào)度算法改進(jìn)的可行性，可通過具體的實(shí)驗(yàn)來實(shí)現(xiàn).實(shí)驗(yàn)的環(huán)境是minix 3.3.0，并且采用兩種實(shí)驗(yàn)環(huán)境，一個是未修改過內(nèi)核的環(huán)境，另一個是已經(jīng)修改過內(nèi)核并將內(nèi)核重新編譯過的環(huán)境.

圖6 兩次實(shí)驗(yàn)結(jié)果比較

圖7 進(jìn)程運(yùn)行的CPU時間比較

實(shí)驗(yàn)采用了14個C語言程序，分別是從program1到program14.它們都是用來執(zhí)行長時間的運(yùn)算，這樣能夠保證每個C語言程序都需要大量占用CPU時間.為了模擬真實(shí)的多進(jìn)程運(yùn)行，通過Shell腳本程序來靜態(tài)改變這14個進(jìn)程的優(yōu)先級，并且優(yōu)先級越高的進(jìn)程執(zhí)行計算功能的時間越長，即所需要的CPU時間越長.進(jìn)程優(yōu)先級計算見公式4.

公式4

在實(shí)驗(yàn)中，讓這14個程序在系統(tǒng)中同時執(zhí)行.并且通過time命令采集它們的real、sys和user的值，并將其輸出到固定的文件當(dāng)中，然后對文件中的數(shù)據(jù)進(jìn)行分析.為了保證數(shù)據(jù)的準(zhǔn)確性，讓每個程序運(yùn)行10次然后取它們的平均值，這樣就避免了因?yàn)槟硞€數(shù)據(jù)而影響整體的結(jié)果.以上這些實(shí)驗(yàn)步驟先在未修改過內(nèi)核的環(huán)境中執(zhí)行一遍，再在已經(jīng)修改過內(nèi)核的環(huán)境中執(zhí)行一遍，將兩次運(yùn)行的結(jié)果進(jìn)行比對并得出結(jié)論.圖6顯示了實(shí)驗(yàn)后每個進(jìn)程結(jié)束的時間、每個進(jìn)程占用的CPU時間和每個進(jìn)程等待的時間，再通過時間比較的結(jié)果觀察改進(jìn)后的調(diào)度算法是否更加體現(xiàn)了進(jìn)程間調(diào)度的公平性.

5.2 實(shí)驗(yàn)結(jié)果

通過實(shí)驗(yàn)，對實(shí)驗(yàn)采集到的數(shù)據(jù)進(jìn)行分析，繪制出圖7、圖8和圖9這3個折線圖，并根據(jù)這3個圖來觀察改進(jìn)前后進(jìn)程調(diào)度的情況.

圖8 進(jìn)程結(jié)束的時間比較

圖9 進(jìn)程等待的時間比較

從這些圖可以看出，改進(jìn)前后進(jìn)程本身執(zhí)行的時間并沒有受到影響.而改進(jìn)后的進(jìn)程結(jié)束的時間和等待的時間趨向平衡，也就是說優(yōu)先級低但執(zhí)行時間很短的進(jìn)程可以占用到CPU的機(jī)會提前了，而優(yōu)先級高但執(zhí)行時間很長的進(jìn)程也不總占著CPU而讓其他進(jìn)程得不到運(yùn)行，這就成功體現(xiàn)了進(jìn)程間調(diào)度的公平性.所以，對于Minix的多級隊(duì)列調(diào)度算法的改進(jìn)是可行的.

6 結(jié)束語

Minix作為一種適用于小型PC機(jī)和嵌入式系統(tǒng)的操作系統(tǒng)，市場潛力非常巨大，特別是Minix 3采用了微內(nèi)核的設(shè)計理念使得操作系統(tǒng)變得更加可靠.通過不斷提升Minix的性能和可靠性并吸收Linux中一些成功的經(jīng)驗(yàn)與技術(shù)來促進(jìn)Minix在市場上的發(fā)展.Minix 3的內(nèi)核代碼非常短小精煉，對于國產(chǎn)操作系統(tǒng)的自主研發(fā)有很大的幫助.Minix進(jìn)程調(diào)度算法的改進(jìn)中用到的一些方法也對以后操作系統(tǒng)的發(fā)展有一定的推動作用.

［1］TANENBAUM A S,WOODHULL A S.Operating Systems Design and Implementation［M］.3th ed.Prentice Hall,2006:56-57.

［2］BOVET D P,CESATI M.Understanding the Linux Kernel［M］.3th ed.Sebastopol:O’Reilly Media,2005:77-78.

［3］朱永華，沈熠，劉玲.Linux內(nèi)核完全公平調(diào)度器改進(jìn)的研究［J］.計算機(jī)工程與應(yīng)用，2014，50（21）：59-62.

［4］杜慧江，王云光.Linux內(nèi)核2.6.24的CFS調(diào)度器分析［J］.計算機(jī)應(yīng)用與軟件，2010，27（2）：166-168.

［5］曹越，顧乃杰，任開新，等.一種面向多核系統(tǒng)的Linux任務(wù)調(diào)度算法［J］.計算機(jī)工程，2015（2）：36-40.

［6］LOVE R.Linux Kernel Development［M］.2th ed.Novell Press,2005:102-103.

［7］LOVE R.Linux Kernel Development［M］.3th ed.Sebastopol:O’Reilly,2010:111-112.

An Improved Algorithm of Minix Process Scheduling

CHEN Liangqiang1,QIAN Zhenjiang1,2
(1.School of Computer Science and Engineering,Changshu Institute of Technology,Changshu 215500; 2.Department of Computer Science and Technology,Nanjing University,Nanjing210023,China)

In order to improve the performance of Minix process scheduling,an improved algorithm of Minix process scheduling is proposed by studying the algorithm of Linux process scheduling and drawing on some good ideas.For the disadvantage of the fixed time slice in Minix multi-level queue scheduling algorithm,the dynamic change of the time slice based on the priority of the process makes Minix scheduler in scheduling process much fairer.

Minix;process scheduling;fairness

TP316

A

1008-2794（2017）02-0043-06

2016-08-31

國家自然科學(xué)基金項(xiàng)目“小型操作系統(tǒng)內(nèi)核的輕量級形式化設(shè)計和驗(yàn)證方法研究”（61402057）

錢振江，副教授，博士，研究方向：操作系統(tǒng)安全、形式化驗(yàn)證和嵌入式系統(tǒng)，E-mail：qianzj@cslg.cn.