分類： linux內(nèi)核 2012-06-29 08:46 613人閱讀 收藏 舉報 AbStract
In this paper．diferences in task scheduling mechanism between the two multi-tasks operating systems Linux and Vx。
Works are analyzed．The two are compared with aspects of task control block，the standard of scheduling and the policy of
scheduling．Further more．The implementati***** of task scheduling in POSIX 1003．1b specification are analyzed both in Linux
and VxWorks．
Keywords：Linux．VxWorks．task scheduling，scheduling policy，priority
摘要
分析了Linux和VxWorks兩種多任務(wù)操作系統(tǒng)任務(wù)調(diào)度機制的異同，從任務(wù)控制塊、調(diào)度的時機、調(diào)度的優(yōu)先級和調(diào)度
的策略方面進行了詳細的分析和對比。分析了VxWorks和Linux在POSIX1003．1b調(diào)度標(biāo)準(zhǔn)實現(xiàn)上的差異。
關(guān)鍵詞：Linux．VxWorks，任務(wù)調(diào)度，調(diào)度策略，優(yōu)先級
通用的分時操作系統(tǒng)面向多用戶的不同任務(wù)，意在追求系統(tǒng)整體運行的效率和資源的均衡利用，軟件的執(zhí)行在時間上要求并不嚴(yán)格。實時操作系統(tǒng)不同于分時操作系統(tǒng)，它主要是對任務(wù)進行實時的處理，要求任務(wù)的運行具有可確定性和可預(yù)測性，提供即時響應(yīng)和高可靠性。由此導(dǎo)致通用分時系統(tǒng)和實時操作系統(tǒng)的內(nèi)核在任務(wù)調(diào)度機制方面的不同。本文以Linux(2.4)版本內(nèi)核)和VxWorks(5.4版本)為代表，著重分析二者任務(wù)調(diào)度機制的異同。
1 進程(任務(wù))控制塊
進程是一個具有獨立功能的程序?qū)δ硞€數(shù)據(jù)集在處理機上的執(zhí)行過程和分配資源的基本單位。進程是一個動態(tài)概念，具有并行特征，表現(xiàn)為獨立性和異步性。在Linux中，進程和任務(wù)的概念是等價的。VxWorks中把每個相互獨立的程序稱為任務(wù)，任務(wù)是VxWorks資源分配的單位，也是處理器調(diào)度的基本單位。
每個任務(wù)擁有各自的上下文，即擁有各自的CPU環(huán)境和系統(tǒng)資源。上下文切換時，Linux進程上下文保存在進程控制塊中(PCB)中，VxWorks任務(wù)的上下文保存在任務(wù)控制塊(TCB)中，二者的上下文內(nèi)容有很大的區(qū)別。
作為通用操作系統(tǒng)的Linux，其進程所使用(管理)的資源比嵌入式實時操作系統(tǒng)VxWorks要多的多，就任務(wù)控制塊來說，二者的差異還是比較大的，典型的區(qū)別分析如下：
1)多用戶性。Linux是多用戶操作系統(tǒng)，它使用用戶和組標(biāo)識符來控制進程對系統(tǒng)中文件和映像以及其他資源的訪問權(quán)限。task_struct中有四對進程和組標(biāo)識符：進程uid和gid、有效uid和gid、文件系統(tǒng)uid和gid、保留的uid和gid。而VxWorks是單用戶的操作系統(tǒng)，任務(wù)控制塊結(jié)構(gòu)windTcb中沒有與用戶相關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu)。
2)文件打開表。Linux的每個進程都擁有一個文件打開表，以記錄該進程使用文件的情況， 對應(yīng)于task_struct中file_ struct 類型的files成員。當(dāng)進程退出時，內(nèi)核會自動檢查并關(guān)閉進程已打開但未顯式調(diào)用close()關(guān)閉的文件。VxWorks的整個系統(tǒng)共用一個文件打開表，每個任務(wù)控制塊中沒有記錄該任務(wù)已打開的文件信息，因此當(dāng)某個任務(wù)退出時，其已打開的文件自然不會被自動關(guān)閉。
3)任務(wù)之間的親屬性。Linux的每個進程都不是孤立地存在于系統(tǒng)中，新的進程白創(chuàng)建起就置于一種表示“宗族”和“家譜”的樹型組織中，初始化進程init是所有進程的祖先進程。在task_ struct結(jié)構(gòu)中有一組task_struct 類型的指針結(jié)構(gòu)成員，其中P_opptr和P_pptr指向父進程，p_cptr指向最“年輕”的子進程，P_Ysptr和P_osptr則分別指向其“哥哥”和“弟弟”。而Vx-Works的任務(wù)間沒有類似的親屬關(guān)系，每一個任務(wù)都是平等而獨立的，即使一個任務(wù)創(chuàng)建并激活一個新的任務(wù)，兩者之間也不存在父子關(guān)系。
另外，Linux的進程控制塊和VxWorks任務(wù)控制塊的差別還有許多，比如Linux的task_struct中保存的進程雜湊隊列的鏈人指針、線程信息、虛擬內(nèi)存信息等。
2.1 VxWorks的任務(wù)調(diào)度
2.1.1 VxWorks任務(wù)調(diào)度時機
VxWorks中任務(wù)調(diào)度的時機可分以下兩種情況：
1)同步任務(wù)切換，引起的原因是當(dāng)前運行的任務(wù)執(zhí)行下列操作：①進行阻塞、延遲、掛起的調(diào)用；②使更高優(yōu)先級任務(wù)就緒而發(fā)生優(yōu)先級搶占；③降低自身優(yōu)先級或者退出。
2)異步任務(wù)切換，通常由中斷服務(wù)使高優(yōu)先級任務(wù)就緒引起。VxWorks的Wind微內(nèi)核基于優(yōu)先級搶占調(diào)度。并采取單一實地址空間模式，上述引發(fā)任務(wù)調(diào)度的情況發(fā)生時，VxWorks內(nèi)核立即進行任務(wù)的調(diào)度切換。
2.1.2 VxWorks任務(wù)調(diào)度策略
多任務(wù)運行時需要一個調(diào)度算法，將CPU分配給就緒的任務(wù)。Wind內(nèi)核默認采用基于優(yōu)先級的搶占式調(diào)度(Priority-based preemptive scheduling)算法，同時也可以選用輪轉(zhuǎn)(Round-robin)調(diào)度算法。
1)基于優(yōu)先級搶占的任務(wù)調(diào)度：指每個進程被賦予一個優(yōu)先級，優(yōu)先級最高的就緒進程率先執(zhí)行 可搶占調(diào)度(preemptive scheduling)是指允許將邏輯上可運行的進程暫時掛起的策略。VxWorks采用基于優(yōu)先級搶占的調(diào)度算法，系統(tǒng)中的每個任務(wù)都擁有一個優(yōu)先級，內(nèi)核將CPU分配給處于就緒狀態(tài)的優(yōu)先級最高的任務(wù)。如果系統(tǒng)內(nèi)核一旦發(fā)現(xiàn)有一個優(yōu)先級比當(dāng)前任務(wù)的優(yōu)先級高的任務(wù)轉(zhuǎn)變到就緒狀態(tài)，內(nèi)核立即保存當(dāng)前任務(wù)的上下文，當(dāng)前任務(wù)狀態(tài)切換到就緒狀態(tài)并按優(yōu)先級插入到相應(yīng)任務(wù)隊列的隊尾，然后內(nèi)核切換到這個高優(yōu)先級任務(wù)的上下文中執(zhí)行。
Wind內(nèi)核有256個優(yōu)先級，編號是0-255，0的優(yōu)先級最高，255最低。任務(wù)的優(yōu)先級可以在創(chuàng)建時設(shè)定，系統(tǒng)默認的任務(wù)優(yōu)先級為100。VxWorks允許任務(wù)動態(tài)改變自己的優(yōu)先級，當(dāng)任務(wù)執(zhí)行時，它可以調(diào)用taskPrioritySet()改變自己的優(yōu)先級。
2)輪轉(zhuǎn)調(diào)度：VxWorks中，基于優(yōu)先級搶占的調(diào)度可以與輪轉(zhuǎn)調(diào)度相結(jié)合。輪轉(zhuǎn)調(diào)度算法試圖讓優(yōu)先級相同的、處于就緒狀態(tài)的任務(wù)公平地分享使用CPU資源。如果不使用輪轉(zhuǎn)調(diào)度，當(dāng)系統(tǒng)中存在多個相同優(yōu)先級的任務(wù)時，第一個獲得CPU的任務(wù)將會獨占CPU，如果沒有阻塞或其它情況出現(xiàn)，其它相同優(yōu)先級的任務(wù)將得不到運行的機會。
使用輪轉(zhuǎn)調(diào)度時，每個任務(wù)被分配一個時間段，稱作它的時間片(quantum)，即該任務(wù)允許運行的時間。在VxWorks系統(tǒng)中，可以調(diào)用函數(shù)kernelTimeSlice0來選用輪轉(zhuǎn)調(diào)度策略，其參數(shù)是時間片的長度，該時間片是每一個任務(wù)在放棄CPU給另一個相同優(yōu)先級任務(wù)之前，系統(tǒng)允許它運行的時間長度。如果任務(wù)在它的時間片中被高優(yōu)先級的任務(wù)搶占，調(diào)度器保存它的運行時間計數(shù)器，當(dāng)它再一次符合執(zhí)行條件的時候，調(diào)度器恢復(fù)運行時間計數(shù)器。
2.1.3 搶占上鎖與中斷上鎖
由于所有VxWorks任務(wù)共存于單一的線性地址空間，當(dāng)多個任務(wù)共享全局的數(shù)據(jù)結(jié)構(gòu)時，需要提供對臨界區(qū)的互斥訪問機制。使用信號量對資源上鎖是一種比較通用的互斥手段，如POSIX有名信號燈或無名信號燈和System V的信號量集。VxWorks提供了三種類型的信號量：二進制信號量、互斥信號量和計數(shù)器信號量。此外，VxWorks在任務(wù)調(diào)度層次上提供了互斥訪問保護的機制：在I臨界區(qū)內(nèi)禁止任務(wù)的搶占調(diào)度，這在VxWorks中稱為搶占上鎖，具體互斥的實現(xiàn)是將臨界區(qū)代碼包括在兩個函數(shù)taskLock()和taskUnlock()之間。
在VxWorks中，不僅任務(wù)與任務(wù)之間需要考慮互斥，同時任務(wù)與中斷之間也要考慮互斥。因為中斷的優(yōu)先級高于任何任務(wù)，所以搶占上鎖雖然保證了任務(wù)與任務(wù)間的互斥，但并沒有保證任務(wù)與中斷服務(wù)程序?qū)臨界區(qū)的互斥訪問。VxWorks的中斷上鎖則提供了最強有力的互斥，將臨界區(qū)代碼保護在intLock()和intUnlock()兩個函數(shù)之間。中斷上鎖實現(xiàn)的是中斷級互斥，在互斥期間，即使外部事件產(chǎn)生而引發(fā)相應(yīng)的中斷，系統(tǒng)也不會切換到相應(yīng)的中斷服務(wù)程序(iSR)。
因此，VxWorks的搶占上鎖和中斷上鎖是通過禁止任務(wù)搶占或禁止切換到中斷服務(wù)程序來保護臨界區(qū)的。同時，這種靈活的互斥手段在臨界區(qū)中也會影響VxWorks任務(wù)的原始調(diào)度原則，比如低優(yōu)先級任務(wù)搶占上鎖時，就緒任務(wù)隊列上具有較高優(yōu)先級的任務(wù)卻不能即時占有處理機。
2.2 Linux的進程調(diào)度
2.2.1 Linux進程調(diào)度的時機
Linux進程的調(diào)度時機大致分為兩種情況：一種是進程自愿調(diào)度；另一種是發(fā)生強制性調(diào)度。首先，自愿的調(diào)度隨時都可以進行。在內(nèi)核空間中，進程可以通過schedule()啟動一次調(diào)度；在用戶空間中，可以通過系統(tǒng)調(diào)用pause()達到同樣的目的。如果要為自愿的暫停行為加上時間限制，在內(nèi)核中使用schedule_timeout()，而在用戶空間則使用nanosleep()系統(tǒng)調(diào)用。Linux中，強制性的調(diào)度發(fā)生在每次從系統(tǒng)調(diào)用返回的前夕，以及每次中斷或異常處理返回用戶空間的前夕。應(yīng)注意的是，從內(nèi)核態(tài)返回到用戶態(tài)是進程調(diào)度發(fā)生的必要條件，而不是充分條件，還要取決于當(dāng)前進程task_struct結(jié)構(gòu)中的need_resched是否為1。單CPU條件下，有三種情況可以使當(dāng)始終比所有的非實時進程都要大，這就保證了實時進程的優(yōu)先運行。實時進程的counter與nice都與其優(yōu)先級權(quán)值無關(guān)，這和普通進程是有區(qū)別的， 實時進程task_struct中的nice和counter只與SCHED—RR調(diào)度策略進程的時間片計數(shù)相關(guān)；而對于SCHED—FIFO調(diào)度策略的實時進程沒有調(diào)度的參考意義。
3 POSlX調(diào)度接口
POSIX1003．1b實時擴展標(biāo)準(zhǔn)定義了進程調(diào)度的標(biāo)準(zhǔn)函數(shù)接El形式，VxWorks的任務(wù)調(diào)度和Linux中實時進程的調(diào)度都支持POSIX1003．1b標(biāo)準(zhǔn)，但二者在該標(biāo)準(zhǔn)的實現(xiàn)上差異較大，列出如下。
1)實時優(yōu)先級數(shù)。VxWorks任務(wù)的優(yōu)先級為0-255，Wind內(nèi)核默認為數(shù)值越大，任務(wù)優(yōu)先級越低。Unux實時進程優(yōu)先級為1～99，數(shù)值越大，進程優(yōu)先級越高。
2)調(diào)度策略的種類。Linux支持SCHED—RR、SCHED—FIFO和SCHED—OTHER的調(diào)度策略，而VxWorks只支持前兩種策略，不支持SCHED_OTHER策略。另外Linux實時進程和普通進程可以互相轉(zhuǎn)換， 通過SCHED_OTHER 參數(shù)調(diào)用sched_ setscheduler()函數(shù)，可以將Linux實時進程轉(zhuǎn)化為普通進程。通過以SCHEDl-RR或SCHED FIFO 為參數(shù)調(diào)用sched_ setscheduler()也可以將普通進程轉(zhuǎn)為實時進程。
3)調(diào)度策略所基于的對象。VxWorks的任務(wù)調(diào)度策略不是基于某個任務(wù)的，而是針對整個系統(tǒng)的所有任務(wù)。VxWorks下不能通過sched—setscheduler()來改變內(nèi)核當(dāng)前的任務(wù)調(diào)度策略，VxWorks下改變調(diào)度策略的唯一手段是通過kernelTimeSlice()函數(shù)設(shè)置輪轉(zhuǎn)調(diào)度的時間片長度來實現(xiàn)的，該時間片長度設(shè)為0時。即取消了SCHED—RR策略。Linux中的調(diào)度策略是基于進程的，某個進程調(diào)度策略的設(shè)置不影響其他進程。
4 結(jié)束語
VxWorks作為嵌入式實時操作系統(tǒng)，Linux作為通用分時操作系統(tǒng)，二者在任務(wù)調(diào)度機制方面差異較大，包括任務(wù)上下文內(nèi)容、任務(wù)的優(yōu)先級、調(diào)度的時機、調(diào)度的策略等。二者在兼容POSI×10o3．1b進程調(diào)度標(biāo)準(zhǔn)的同時其具體實現(xiàn)又有差異。本文通過分析與比較Linux和VxWorks任務(wù)(進程)調(diào)度機制的異同，有助于理解實時內(nèi)核和通用分時內(nèi)核在任務(wù)調(diào)度機制實現(xiàn)層次上的差異，并基于它們更有針對性地開發(fā)相應(yīng)的應(yīng)用，同時對基于通用操作系統(tǒng)Linux的一些實時化改造工作也提供參
考借鑒作用。
參考文獻
張堯?qū)W，史美林．計算機操作系統(tǒng)教程(第2版)．清華大學(xué)出版社，2OO1
李方敏．VxWorks高級程序設(shè)計．清華大學(xué)出版社，2004
Andrew S．Tanenbaum．現(xiàn)代操作系統(tǒng)．機械工業(yè)出版社，2000
代玲莉，歐陽勁．Linux內(nèi)核分析與實例應(yīng)用 國防工業(yè)出版社，20o2
毛德操，胡希明．Linux內(nèi)核源代碼情景分析．浙江大學(xué)出版社，2001
本站僅提供存儲服務(wù)，所有內(nèi)容均由用戶發(fā)布，如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請
點擊舉報。
