OSEK操作系統(tǒng)調(diào)度機(jī)制研究

1、中國(guó)科學(xué)技術(shù)大學(xué)碩士學(xué)位論文 OSEK操作系統(tǒng)調(diào)度機(jī)制研究作者姓名：馮小天學(xué)科專業(yè)：計(jì)算機(jī)軟件與理論導(dǎo)師姓名：李曦 副教授完成時(shí)間：二八年五月一日Research of Scheduling Mechanism In OSEK Operating System University of Science and Technology of ChinaA dissertation for masters degreeAuthors Name：Xiaotian FengSpeciality：Computer Software TheorySupervisor：Associate Prof. Xi

2、Li Finished Time：May 1st, 2008中國(guó)科學(xué)技術(shù)大學(xué)學(xué)位論文原創(chuàng)性和授權(quán)使用聲明本人聲明所呈交的學(xué)位論文,是本人在導(dǎo)師指導(dǎo)下進(jìn)行研究工作所取得的成果。除已特別加以標(biāo)注和致謝的地方外，論文中不包含任何他人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果。與我一同工作的同志對(duì)本研究所做的貢獻(xiàn)均已在論文中作了明確的說(shuō)明。本人授權(quán)中國(guó)科學(xué)技術(shù)大學(xué)擁有學(xué)位論文的部分使用權(quán)，即：學(xué)校有權(quán)按有關(guān)規(guī)定向國(guó)家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文被查閱和借閱，可以將學(xué)位論文編入有關(guān)數(shù)據(jù)庫(kù)進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存、匯編學(xué)位論文。保密的學(xué)位論文在解密后也遵守此規(guī)定。作者簽名：_年

3、 月 日摘 要摘 要OSEK操作系統(tǒng)標(biāo)準(zhǔn)是針對(duì)汽車電子領(lǐng)域嵌入式系統(tǒng)制定的工業(yè)標(biāo)準(zhǔn)，在汽車工業(yè)界有著廣泛的應(yīng)用。調(diào)度是多任務(wù)系統(tǒng)正確運(yùn)行的保證，而OSEK操作系統(tǒng)作為硬實(shí)時(shí)系統(tǒng)，其調(diào)度有著特殊的需求，因此研究OSEK操作系統(tǒng)的調(diào)度是OSEK操作系統(tǒng)設(shè)計(jì)中最為核心的部分。本文主要針對(duì)OSEK操作系統(tǒng)調(diào)度機(jī)制進(jìn)行研究。主要包括以下兩個(gè)方面：1) OSEK操作系統(tǒng)調(diào)度機(jī)制分析及實(shí)現(xiàn)本文深入分析OSEK操作系統(tǒng)標(biāo)準(zhǔn)，給出滿足OSEK操作系統(tǒng)支持優(yōu)先級(jí)天花板協(xié)議的固定優(yōu)先級(jí)任務(wù)調(diào)度機(jī)制的實(shí)現(xiàn)方法。（1）將OSEK任務(wù)調(diào)度分為三個(gè)部分：判斷何時(shí)發(fā)生調(diào)度、查找最高優(yōu)先級(jí)就緒任務(wù)以及任務(wù)切換機(jī)制；（2）通過(guò)分

4、析OSEK操作系統(tǒng)的重調(diào)度點(diǎn)，解決了OSEK操作系統(tǒng)何時(shí)才會(huì)發(fā)生重調(diào)度的問(wèn)題；（3）根據(jù)OSEK操作系統(tǒng)就緒隊(duì)列的特性，提出了OSEK操作系統(tǒng)中優(yōu)就緒任務(wù)優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)方法；（4）通過(guò)分析OSEK操作系統(tǒng)任務(wù)特征以及任務(wù)切換機(jī)制，提出了針對(duì)OSEK操作系統(tǒng)的任務(wù)堆棧優(yōu)化方法。2) OSEK應(yīng)用任務(wù)集可調(diào)度性分析實(shí)時(shí)系統(tǒng)調(diào)度分析理論中，需要考慮每個(gè)任務(wù)的最壞情況響應(yīng)時(shí)間是否滿足其時(shí)間約束，本文通過(guò)對(duì)OSEK操作系統(tǒng)中的任務(wù)調(diào)度簡(jiǎn)化抽象，首先給出了不考慮系統(tǒng)開(kāi)銷的任務(wù)最壞情況響應(yīng)時(shí)間計(jì)算方法以及任務(wù)集可行性條件，分析給出OSEK操作系統(tǒng)任務(wù)調(diào)度的一些本質(zhì)特性。 本文根據(jù)OSEK應(yīng)用，提出了OSE

5、K操作系統(tǒng)調(diào)度相關(guān)的六種系統(tǒng)開(kāi)銷：激活任務(wù)、終止任務(wù)、時(shí)鐘滴答、切換開(kāi)銷、獲取資源以及釋放資源。在不考慮系統(tǒng)開(kāi)銷的調(diào)度分析基礎(chǔ)上，加入了對(duì)這些系統(tǒng)開(kāi)銷的分析，進(jìn)一步精確了考慮系統(tǒng)開(kāi)銷的OSEK應(yīng)用任務(wù)集中任務(wù)的最壞情況響應(yīng)時(shí)間的計(jì)算方法，并提出了考慮系統(tǒng)開(kāi)銷的情況下，OSEK應(yīng)用任務(wù)集調(diào)度可行性的充分條件，最后通過(guò)實(shí)驗(yàn)對(duì)比了不考慮系統(tǒng)開(kāi)銷的任務(wù)最壞情況響應(yīng)時(shí)間、考慮系統(tǒng)開(kāi)銷的任務(wù)最壞情況響應(yīng)時(shí)間二者理論值以及實(shí)際系統(tǒng)運(yùn)行的任務(wù)響應(yīng)時(shí)間。關(guān)鍵詞: OSEK操作系統(tǒng) 實(shí)時(shí)系統(tǒng) 調(diào)度算法 調(diào)度分析理論VIIAbstractOSEK operating system standard is an in

6、dustrial standard for automotive embedded system, and there are many applications for OSEK standards.Scheduling is the very important part in multi-task systems. OSEK operating systems are hard real-time systems; the scheduling mechanism has special demand for OSEK operating systems. So the research

7、 of OSEK operating system scheduling is key part of OSEK operating system design.This paper is focus on the research of OSEK operating system scheduling mechanism. There are mainly about two parts:1) OSEK operating system scheduling mechanism analyze and implementThis paper, deeply analyzes the OSEK

8、 operating system standards, presents the essence of OSEK operating system scheduling mechanismfixed priority scheduling with OSEK priority ceiling protocol support, and give the implementation of OSEK operating system scheduling mechanism. (1) This paper divide OSEK task scheduling into three part:

9、 determine when to schedule、find the ready task with highest priority and the task switch mechanism;(2) This paper solves determining when the systems will reschedule by analyzing the rescheduling point of OSEK operating system; (3) This paper presents a highly optimization implementation method of

10、ready task queue based on the ready task specification in OSEK operating systems;(4) Finally this paper gives an optimization method for OSEK operating system task stacktask stack sharing. 2) Scheduling analyze of OSEK application task setBased on the modern scheduling analyze theory, this paper pre

11、sents the scheduling analyze methods for OSEK application task set with OSEK operating system characterize. We give the OSEK application task model and hypothesis under our model; present the calculating method of worst case response time for tasks in OSEK application task set ignoring the system ov

12、erheads; finally prove the feasible scheduling condition for OSEK application task.According to the OSEK applications, we present six system overheads related to OSEK operating system scheduling: Active task overhead、Terminate task overhead、Tick time overhead、switching overhead、get and release resou

13、rce overhead. We add the consideration of these system overheads under the former scheduling analyze method. Moreover, we give the calculating method of worst case response time for tasks in OSEK application task set with these system overheads, also present the feasible scheduling condition for OSE

14、K application task set. Finally we compare the worst case response time ignoring system overheads、worst case response time with system overheads and the actual response time in Trampoline system and give the conclusion.Keywords: OSEK Operating System，Real Time Systems，Scheduling Algorithm，Scheduling

15、 Analyze Theory插圖目錄目 錄摘 要IAbstractII第 1 章緒論91.1背景介紹91.1.1OSEK標(biāo)準(zhǔn)簡(jiǎn)介91.1.1OSEK操作系統(tǒng)標(biāo)準(zhǔn)91.1.2OSEK操作系統(tǒng)任務(wù)調(diào)度131.2現(xiàn)有OSEK操作系統(tǒng)141.3論文的主要工作151.4論文組織結(jié)構(gòu)16第 2 章操作系統(tǒng)中的任務(wù)調(diào)度172.1背景介紹172.1.1交互式操作系統(tǒng)中的調(diào)度182.1.2多處理器調(diào)度192.1.3實(shí)時(shí)調(diào)度192.2實(shí)時(shí)調(diào)度方法202.2.1靜態(tài)循環(huán)調(diào)度202.2.2固定優(yōu)先級(jí)調(diào)度212.2.3動(dòng)態(tài)優(yōu)先級(jí)調(diào)度212.3典型實(shí)時(shí)系統(tǒng)中的任務(wù)調(diào)度212.3.1Vxworks222.3.2Micri

16、um222.3.3Linux232.3.4Trampoline232.4本章小結(jié)24第 3 章OSEK操作系統(tǒng)任務(wù)調(diào)度機(jī)制253.1OSEK操作系統(tǒng)任務(wù)調(diào)度機(jī)制253.1.1OSEK操作系統(tǒng)任務(wù)管理機(jī)制253.1.2OSEK任務(wù)調(diào)度機(jī)制實(shí)現(xiàn)293.2實(shí)驗(yàn)數(shù)據(jù)353.2.1實(shí)驗(yàn)環(huán)境介紹363.2.2實(shí)驗(yàn)結(jié)果及分析363.3本章小結(jié)37第 4 章OSEK應(yīng)用任務(wù)集可調(diào)度性分析384.1任務(wù)調(diào)度模型與相關(guān)定義384.1.1相關(guān)工作384.1.2周期任務(wù)調(diào)度模型404.1.3相關(guān)假定404.2無(wú)系統(tǒng)開(kāi)銷的調(diào)度分析424.2.1計(jì)算阻塞時(shí)間434.2.2第q次激活任務(wù)的開(kāi)始時(shí)刻444.2.3第q次激活任

17、務(wù)的結(jié)束時(shí)刻454.2.4最壞情況響應(yīng)時(shí)間454.2.5可行性條件454.2.6OSEK操作系統(tǒng)任務(wù)調(diào)度特征464.3考慮系統(tǒng)開(kāi)銷的調(diào)度分析484.3.1系統(tǒng)開(kāi)銷分析484.3.2考慮系統(tǒng)開(kāi)銷的調(diào)度分析494.3.3考慮系統(tǒng)開(kāi)銷的可行性條件514.4實(shí)驗(yàn)結(jié)果514.5本章小結(jié)52第 5 章總結(jié)與展望545.1本文的主要工作545.2進(jìn)一步工作展望55參考文獻(xiàn)57在讀期間發(fā)表的學(xué)術(shù)論文與取得的研究成果62致 謝63插圖目錄圖 2.1 Trampoline原優(yōu)先級(jí)隊(duì)列結(jié)構(gòu)圖24圖 3.1 擴(kuò)展任務(wù)狀態(tài)轉(zhuǎn)換圖26圖 3.2 基本任務(wù)狀態(tài)轉(zhuǎn)換圖26圖 3.3 優(yōu)先級(jí)反轉(zhuǎn)示意圖27圖 3.4 優(yōu)先級(jí)天花

18、板協(xié)議示意圖28圖 3.5 空就緒任務(wù)隊(duì)列30圖 3.6 多次激活就緒任務(wù)隊(duì)列30圖 3.7 資源優(yōu)先級(jí)就緒任務(wù)隊(duì)列31圖 3.8 實(shí)時(shí)系統(tǒng)任務(wù)結(jié)構(gòu)圖33表格目錄表1.1 OSEK操作系統(tǒng)一致類10表 3.1 擴(kuò)展任務(wù)狀態(tài)及其轉(zhuǎn)換26表 3.2 擴(kuò)展任務(wù)狀態(tài)及其轉(zhuǎn)換27表3.3 Trampoline原調(diào)度算法下ActiveTask的執(zhí)行時(shí)間36表3.4 新調(diào)度算法下ActiveTask的執(zhí)行時(shí)間36表4.1 測(cè)試任務(wù)集數(shù)據(jù)52表4.2 系統(tǒng)開(kāi)銷最壞情況運(yùn)行時(shí)間52表4.3 任務(wù)最壞情況響應(yīng)時(shí)間理論與實(shí)驗(yàn)值對(duì)比52總結(jié)與展望 第 1 章 緒論1.1 背景介紹1.1.1 OSEK標(biāo)準(zhǔn)簡(jiǎn)介隨著汽車安

19、全、環(huán)保、舒適和經(jīng)濟(jì)等性能要求的不斷提高，汽車電控單元(electronic control unit，ECU)的數(shù)量越來(lái)越多，其復(fù)雜性也急劇上升。大量ECU的使用和復(fù)雜的控制程序給汽車制造商帶來(lái)了巨大的成本壓力，因此，開(kāi)發(fā)經(jīng)濟(jì)、高效的ECU內(nèi)存和處理器資源的操作系統(tǒng)已變得十分迫切。傳統(tǒng)的實(shí)時(shí)操作系統(tǒng)太大，功能過(guò)多，已難以適應(yīng)ECU數(shù)量大而內(nèi)存小的現(xiàn)代汽車控制系統(tǒng)。為滿足日益龐大復(fù)雜的汽車電子控制軟件的開(kāi)發(fā)需要，實(shí)現(xiàn)應(yīng)用軟件的可移植性和不同廠商的控制模塊間的可兼容性，德國(guó)汽車工業(yè)協(xié)會(huì)于1993年提出OSEK標(biāo)準(zhǔn)(德語(yǔ)“汽車電子設(shè)備開(kāi)放式構(gòu)架及其接口規(guī)范”的簡(jiǎn)稱)，旨在建立一個(gè)用于汽車電子分布式

20、控制系統(tǒng)的開(kāi)放式結(jié)構(gòu)體系，1994年法國(guó)汽車電子規(guī)范VDX(Vehicle Distributed eXecutive)并入OSEK標(biāo)準(zhǔn)。OSEK標(biāo)準(zhǔn)更名為OSEK/VDX（本文簡(jiǎn)稱OSEK），并在1995年發(fā)布了它的第一個(gè)正式版本。目前OSEK標(biāo)準(zhǔn)已經(jīng)加入ISO國(guó)際標(biāo)準(zhǔn)。OSEK標(biāo)準(zhǔn)包含OS(OSEK操作系統(tǒng)標(biāo)準(zhǔn))1,2,3、COM(OSEK通信服務(wù)標(biāo)準(zhǔn))4、NM(OSEK網(wǎng)絡(luò)管理標(biāo)準(zhǔn))5以及OIL(OSEK實(shí)現(xiàn)語(yǔ)言標(biāo)準(zhǔn))6等部分，對(duì)汽車電子控制軟件的開(kāi)發(fā)平臺(tái)作了較為全面的定義與規(guī)定。OSEK標(biāo)準(zhǔn)發(fā)布至今，國(guó)外著名汽車制造商如：寶馬、博世、戴姆勒奔馳、歐寶、西門子、大眾、標(biāo)致和雷諾等，其產(chǎn)品

21、中使用的嵌入式操作系統(tǒng)均支持OSEK標(biāo)準(zhǔn)。1.1.1 OSEK操作系統(tǒng)標(biāo)準(zhǔn)OSEK操作系統(tǒng)標(biāo)準(zhǔn)1,2,3旨在為汽車控制單元的應(yīng)用程序提供一個(gè)高效利用資源的統(tǒng)一平臺(tái)。OSEK操作系統(tǒng)是一種單處理器的操作系統(tǒng)，用于分布式ECU(電子控制單元)。OSEK應(yīng)用中所有對(duì)象均是靜態(tài)的，它們?cè)趹?yīng)用程序啟動(dòng)之前就已經(jīng)創(chuàng)建，并且啟動(dòng)后不會(huì)被刪除。OSEK操作系統(tǒng)具有可配置性、可移植性、標(biāo)準(zhǔn)化接口、實(shí)時(shí)性以及可靠性等特點(diǎn)。OSEK操作系統(tǒng)標(biāo)準(zhǔn)要求操作系統(tǒng)具有任務(wù)管理、資源管理、時(shí)鐘管理、中斷管理和錯(cuò)誤處理等功能，并且操作系統(tǒng)給處理器帶來(lái)的負(fù)擔(dān)不應(yīng)超過(guò)5%，操作系統(tǒng)的代碼應(yīng)高度優(yōu)化以減少內(nèi)存消耗量。1.1.1.1

22、任務(wù)管理OSEK操作系統(tǒng)標(biāo)準(zhǔn)提供了兩種不同的任務(wù)類型：基本任務(wù)和擴(kuò)展任務(wù)。一方面，基本任務(wù)是不會(huì)被阻塞的順序代碼。其同步點(diǎn)只在任務(wù)的開(kāi)始和結(jié)束時(shí)，基本任務(wù)只在任務(wù)終止、內(nèi)核切換到更高優(yōu)先級(jí)的任務(wù)時(shí)或中斷時(shí)釋放處理器；另一方面，擴(kuò)展任務(wù)可以看作是由可導(dǎo)致等待狀態(tài)的操作系統(tǒng)服務(wù)分隔開(kāi)的若干代碼段。擴(kuò)展任務(wù)與基本任務(wù)相比，引入了等待狀態(tài)，擴(kuò)展任務(wù)可以阻塞自身進(jìn)入等待狀態(tài)，直到某個(gè)事件發(fā)生再進(jìn)入就緒狀態(tài)。而事件的觸發(fā)可以通過(guò)任務(wù)或者中斷來(lái)設(shè)置，等待事件并不會(huì)超時(shí)，也就是說(shuō)，擴(kuò)展任務(wù)可以無(wú)限期的阻塞自己。任務(wù)執(zhí)行結(jié)束后進(jìn)入掛起狀態(tài)，處于該狀態(tài)的任務(wù)可以被再次激活。OSEK操作系統(tǒng)中，管理擴(kuò)展任務(wù)比管理基

23、本任務(wù)開(kāi)銷更大。OSEK操作系統(tǒng)中的任務(wù)在系統(tǒng)生成時(shí)靜態(tài)創(chuàng)建。1.1.1.2 一致類OSEK操作系統(tǒng)標(biāo)準(zhǔn)中的一致類定義了四種實(shí)時(shí)內(nèi)核的版本，用來(lái)滿足不同的應(yīng)用需求。它們由三種主要屬性來(lái)區(qū)別：任務(wù)類型、對(duì)基本任務(wù)的多次激活請(qǐng)求的記錄以及每個(gè)優(yōu)先級(jí)對(duì)應(yīng)的任務(wù)數(shù)。這四個(gè)一致類分別是BCC1、BCC2、ECC1和ECC2，如表1.1所示表1.1 OSEK操作系統(tǒng)一致類一致類BCC1 BCC2 ECC1 ECC2基本任務(wù)的多次激活請(qǐng)求 不支持 支持 不支持 支持任務(wù)類型 基本 基本 擴(kuò)展/基本 擴(kuò)展/基本每個(gè)優(yōu)先級(jí)是否對(duì)應(yīng)多個(gè)任務(wù)否 是 否 是非掛起狀態(tài)任務(wù)數(shù)8 8 16 16每個(gè)任務(wù)事件數(shù)無(wú) 無(wú) 8

24、8任務(wù)優(yōu)先級(jí)數(shù)8 8 16 16 資源數(shù)調(diào)度器 8 8 8顯然，BCC2和ECC2一致類中，需要支持對(duì)基本任務(wù)的多次激活，每個(gè)優(yōu)先級(jí)可能與多個(gè)任務(wù)對(duì)應(yīng)，調(diào)度行為更為復(fù)雜。而ECC1和ECC2一致類中，需要對(duì)擴(kuò)展任務(wù)以及事件機(jī)制提供支持。1.1.1.3 調(diào)度策略任務(wù)的優(yōu)先級(jí)由用戶通過(guò)OIL文件靜態(tài)指定，采用“最高優(yōu)先級(jí)就緒任務(wù)最先運(yùn)行”的策略，而在BCC2和ECC2中，由于每個(gè)優(yōu)先級(jí)可能有多個(gè)任務(wù)，相同優(yōu)先級(jí)的任務(wù)需要按照FIFO原則來(lái)進(jìn)行調(diào)度。OSEK操作系統(tǒng)中支持四種調(diào)度策略：1) 完全可搶占調(diào)度該調(diào)度策略下，在任務(wù)的任何位置都可能發(fā)生重調(diào)度，只要有更高優(yōu)先級(jí)的任務(wù)就緒，就會(huì)搶占當(dāng)前任務(wù)運(yùn)行

25、。完全可搶占調(diào)度策略下系統(tǒng)用于保存任務(wù)上下文的開(kāi)銷最大，任務(wù)需同步訪問(wèn)共享資源，系統(tǒng)復(fù)雜度最大。2) 無(wú)搶占調(diào)度無(wú)搶占調(diào)度策略下，通過(guò)用戶通過(guò)系統(tǒng)服務(wù)設(shè)置重調(diào)度點(diǎn)，基本任務(wù)一旦運(yùn)行就會(huì)一直運(yùn)行直到其運(yùn)行結(jié)束，而擴(kuò)展任務(wù)可能進(jìn)入等待狀態(tài)。3) 混合搶占調(diào)度可搶占任務(wù)和非搶占任務(wù)共存于一個(gè)系統(tǒng)中時(shí)，使用混合搶占調(diào)度策略，系統(tǒng)調(diào)度依賴于正在運(yùn)行的任務(wù)的搶占特性。如果當(dāng)前運(yùn)行的任務(wù)是非搶占的，其它任務(wù)只有在該任務(wù)結(jié)束或者進(jìn)入等待狀態(tài)時(shí)才能運(yùn)行；如果當(dāng)前運(yùn)行的任務(wù)是可搶占的，執(zhí)行可搶占調(diào)度策略。如果應(yīng)用中包含較長(zhǎng)運(yùn)行時(shí)間的并行任務(wù)，選擇可搶占調(diào)度更為合適；而應(yīng)用中包含較多短執(zhí)行時(shí)間的任務(wù)時(shí)，無(wú)搶占調(diào)度更

26、適合，為了實(shí)現(xiàn)性能和效率的折衷，可以使用混合搶占調(diào)度策略。4) 任務(wù)組通過(guò)任務(wù)組，OSEK操作系統(tǒng)能使多個(gè)任務(wù)同時(shí)具有可搶占和無(wú)搶占調(diào)度特性。如果任務(wù)的優(yōu)先級(jí)等于或者小于某組中優(yōu)先級(jí)最高的任務(wù)，那么該任務(wù)對(duì)于組中的任務(wù)是不可搶占的。反之，組中的任務(wù)是可搶占的。OSEK應(yīng)用開(kāi)發(fā)者，通過(guò)配置任務(wù)優(yōu)先級(jí)以及搶占屬性來(lái)定義任務(wù)執(zhí)行順序，OSEK操作系統(tǒng)的任務(wù)類型獨(dú)立于調(diào)度策略。1.1.1.4 任務(wù)同步任務(wù)同步(擴(kuò)展任務(wù))是基于私有事件機(jī)制：只有事件的擁有者才能等待該事件的發(fā)生。設(shè)置事件可以通過(guò)任務(wù)或者ISR(中斷處理例程)完成，等待事件不會(huì)超時(shí)。事件只用于擴(kuò)展任務(wù)，傳遞二進(jìn)制信息，其具體含義通過(guò)應(yīng)用決

27、定。事件是擴(kuò)展任務(wù)從等待狀態(tài)進(jìn)入就緒狀態(tài)的標(biāo)志。OSEK操作系統(tǒng)不允許擁有資源的擴(kuò)展任務(wù)進(jìn)入等待狀態(tài)。1.1.1.5 資源管理資源管理用于協(xié)調(diào)優(yōu)先級(jí)不同的任務(wù)和中斷服務(wù)例程對(duì)資源進(jìn)行并發(fā)訪問(wèn)。共享資源包括：調(diào)度程序、程序代碼、內(nèi)存或硬件資源等。所謂資源，就是臨界區(qū)，OSEK操作系統(tǒng)禁止訪問(wèn)共享資源時(shí)進(jìn)入等待狀態(tài)，同時(shí)也禁止對(duì)同一資源的嵌套訪問(wèn)。協(xié)調(diào)任務(wù)和中斷時(shí)，OSEK操作系統(tǒng)需確保所有需要的資源均釋放后，才執(zhí)行中斷服務(wù)例程。OSEK操作系統(tǒng)標(biāo)準(zhǔn)規(guī)定了對(duì)共享資源的并發(fā)訪問(wèn)機(jī)制OSEK-PCP(優(yōu)先級(jí)天花板)協(xié)議，也稱作IPCP(立即優(yōu)先級(jí)天花板協(xié)議)。當(dāng)一個(gè)任務(wù)獲取一個(gè)資源后，該任務(wù)的優(yōu)先級(jí)立

28、即提升到資源的優(yōu)先級(jí)，資源的優(yōu)先級(jí)等于共享該資源的任務(wù)中的最高優(yōu)先級(jí)。這樣，就可以避免優(yōu)先級(jí)反轉(zhuǎn)的問(wèn)題。由于資源共享允許發(fā)生在任務(wù)和中斷服務(wù)例程之間或者中斷服務(wù)例程之間，需要為每個(gè)中斷分配一個(gè)虛擬的優(yōu)先級(jí)來(lái)實(shí)現(xiàn)擴(kuò)展到中斷級(jí)的OSEK-PCP協(xié)議。在系統(tǒng)初始化階段，根據(jù)來(lái)自O(shè)IL配置的先驗(yàn)知識(shí)，為每一資源靜態(tài)分配天花板優(yōu)先級(jí)。1.1.1.6 中斷管理OSEK操作系統(tǒng)中，將中斷服務(wù)例程分為兩類：第一類中斷，不使用OSEK系統(tǒng)調(diào)用的中斷服務(wù)例程。中斷結(jié)束后，處理器從被中斷的指令處繼續(xù)運(yùn)行，即第一類中斷對(duì)任務(wù)調(diào)度沒(méi)有影響。此類中斷系統(tǒng)開(kāi)銷最小。而第二類中斷，操作系統(tǒng)需要提供中斷服務(wù)例程處理框架，為其提

29、供運(yùn)行環(huán)境，系統(tǒng)初始化時(shí)，需要將第二類中斷處理例程注冊(cè)到相應(yīng)中斷。OSEK操作系統(tǒng)不允許第二類中斷執(zhí)行中進(jìn)入調(diào)度內(nèi)核。即使在第二類中斷中激活了某任務(wù)，也要在退出中斷后，再去執(zhí)行調(diào)度。1.1.1.7 警報(bào)和計(jì)數(shù)器警報(bào)和計(jì)數(shù)器管理周期性任務(wù)以及看門狗定時(shí)器，用來(lái)監(jiān)測(cè)各種情況(等待事件發(fā)生、發(fā)送接收消息等)。警報(bào)用于處理周期性事件，這些事件可以來(lái)自定期提供中斷的定時(shí)器，也可以來(lái)自其它定期感應(yīng)的傳感器。計(jì)數(shù)器用一個(gè)計(jì)數(shù)值表示，按系統(tǒng)滴答頻率計(jì)數(shù)，警報(bào)需要與具體的計(jì)數(shù)器相關(guān)聯(lián)。當(dāng)警報(bào)相關(guān)計(jì)數(shù)器達(dá)到了警報(bào)預(yù)設(shè)的值時(shí)，警報(bào)可以有三種行為：激活相關(guān)任務(wù)、設(shè)置相關(guān)任務(wù)的事件或者執(zhí)行回調(diào)函數(shù)。警報(bào)可以設(shè)置成一次性

30、或者周期性的以滿足不同應(yīng)用要求，多個(gè)警報(bào)可以依附于同一計(jì)數(shù)器。1.1.1.8 通信OSEK操作系統(tǒng)中，任務(wù)之間通過(guò)消息實(shí)現(xiàn)通信。消息是應(yīng)用數(shù)據(jù)的容器，只是一個(gè)發(fā)送者，但可以有多個(gè)接收者。消息類型在系統(tǒng)創(chuàng)建時(shí)定義，不能在運(yùn)行時(shí)增加和刪除消息。OSEK操作系統(tǒng)中有兩類消息：可排隊(duì)消息和不可排隊(duì)消息。前者是靜態(tài)長(zhǎng)度消息，可以被消息接收程序移走，實(shí)現(xiàn)時(shí)使用FIFO隊(duì)列來(lái)管理；不可排隊(duì)消息類似黑板模式，即消息不斷刷新，不能被消息接收程序移走。1.1.1.9 錯(cuò)誤處理OSEK操作系統(tǒng)提供了系統(tǒng)專用鉤子程序，以便在操作系統(tǒng)內(nèi)部操作時(shí)執(zhí)行用戶定義的函數(shù)。特點(diǎn)是：依賴于操作系統(tǒng)實(shí)現(xiàn)，在特定現(xiàn)場(chǎng)被操作系統(tǒng)調(diào)用；比

31、所有任務(wù)的優(yōu)先級(jí)都高；不能被第二類中斷服務(wù)例程中斷；是操作系統(tǒng)的一部分；接口被標(biāo)準(zhǔn)化，但功能（包括執(zhí)行環(huán)境和處理程序的行為）沒(méi)有被標(biāo)準(zhǔn)化。鉤子程序通常是不可移植的，為了減小系統(tǒng)復(fù)雜性，只允許使用系統(tǒng)服務(wù)例程的一個(gè)子集。鉤子程序可用于：系統(tǒng)啟動(dòng)，相應(yīng)鉤子程序在操作系統(tǒng)啟動(dòng)后，進(jìn)入調(diào)度程序之前執(zhí)行；系統(tǒng)關(guān)閉，相應(yīng)鉤子程序在應(yīng)用或操作系統(tǒng)（此時(shí)發(fā)生嚴(yán)重錯(cuò)誤）請(qǐng)求系統(tǒng)停止運(yùn)行時(shí)執(zhí)行；跟蹤、調(diào)試應(yīng)用以及現(xiàn)場(chǎng)切換時(shí)調(diào)用用戶定義的擴(kuò)展程序；錯(cuò)誤處理。1.1.1.10 OSEK執(zhí)行語(yǔ)言O(shè)SEK執(zhí)行語(yǔ)言（OIL）2,3,6主要是配置在特定處理器上的OSEK應(yīng)用程序。所有的OSEK系統(tǒng)對(duì)象都在OIL文件中定義，包

32、括任務(wù)優(yōu)先級(jí)、資源優(yōu)先級(jí)等信息。通過(guò)用戶定義OIL文件，整個(gè)OSEK操作系統(tǒng)是完全靜態(tài)配置的。1.1.2 OSEK操作系統(tǒng)任務(wù)調(diào)度OSEK操作系統(tǒng)標(biāo)準(zhǔn)只定義了調(diào)度策略，并且規(guī)定了OSEK操作系統(tǒng)中的調(diào)度選擇當(dāng)前優(yōu)先級(jí)最高的任務(wù)運(yùn)行，任務(wù)的當(dāng)前優(yōu)先級(jí)通過(guò)任務(wù)的基本優(yōu)先級(jí)以及此刻用戶的資源優(yōu)先級(jí)共同決定。該標(biāo)準(zhǔn)并未提出如何實(shí)現(xiàn)OSEK操作系統(tǒng)的調(diào)度機(jī)制，因此實(shí)現(xiàn)OSEK操作系統(tǒng)調(diào)度機(jī)制是本文的研究目標(biāo)之一。OSEK操作系統(tǒng)標(biāo)準(zhǔn)中規(guī)定了任務(wù)的基本優(yōu)先級(jí)由用戶靜態(tài)指定，用戶可能為不同的應(yīng)用設(shè)計(jì)不同的任務(wù)集，用戶需要關(guān)注自己設(shè)計(jì)的任務(wù)集能否滿足應(yīng)用的時(shí)間限制，而在實(shí)際應(yīng)用中驗(yàn)證需時(shí)較長(zhǎng)、成本要求較高，因

33、此通過(guò)對(duì)OSEK操作系統(tǒng)調(diào)度機(jī)制進(jìn)行理論分析，計(jì)算每個(gè)任務(wù)的最壞情況響應(yīng)時(shí)間，判斷該時(shí)間是否滿足最終期限要求，是本文的另一研究目標(biāo)。1.2 現(xiàn)有OSEK操作系統(tǒng)OSEK操作系統(tǒng)主要應(yīng)用于汽車電子領(lǐng)域，目前已知的支持OSEK操作系統(tǒng)的標(biāo)準(zhǔn)大多是商業(yè)系統(tǒng)。德國(guó)3Soft公司從1996開(kāi)始開(kāi)發(fā)OSEK操作系統(tǒng)，1997年發(fā)布了第一個(gè)商業(yè)化的OSEK操作系統(tǒng)proOSEK1.0，已經(jīng)為BMW提供了基于OSEK的軟件開(kāi)發(fā)平臺(tái)，為VW/Audi開(kāi)發(fā)了OSEK軟件開(kāi)發(fā)平臺(tái)，同時(shí)為DaimlerChrysler提供了首個(gè)基于OSEK項(xiàng)目的軟件平臺(tái)，此外提供了各種硬件平臺(tái)的Bootloader、HIS實(shí)現(xiàn)7。F

34、reescale公司開(kāi)發(fā)的OSEKTurbo是目前市場(chǎng)上使用最為廣泛的OSEK操作系統(tǒng)之一8。德國(guó)Vector公司開(kāi)發(fā)了具有CANopen協(xié)議棧的OSEK操作系統(tǒng)osCAN，支持多處理器以及不同的CAN通信協(xié)議。此外德國(guó)的ETAS公司、英國(guó)的LiveDevices公司開(kāi)發(fā)了支持OSEK標(biāo)準(zhǔn)的嵌入式產(chǎn)品RTA-OSEK9,10。美國(guó)Wind River公司也在其產(chǎn)品VxWorks的基礎(chǔ)上擴(kuò)展開(kāi)發(fā)了OSEKWorks以支持OSEK標(biāo)準(zhǔn)11。目前國(guó)內(nèi)也有許多基于OSEK標(biāo)準(zhǔn)的嵌入式操作系統(tǒng)。北京西曼公司與清華大學(xué)智能技術(shù)與系統(tǒng)實(shí)驗(yàn)室合作，自主研發(fā)了支持OSEK標(biāo)準(zhǔn)的嵌入式操作系統(tǒng)PowerOSEK1

35、0。浙江大學(xué)嵌入式系統(tǒng)工程中心也自主研發(fā)了面向汽車電控領(lǐng)域的嵌入式軟件開(kāi)發(fā)平臺(tái)SmartOSEK13,14,15。相關(guān)的研究論文中，大多是對(duì)已有的嵌入式操作系統(tǒng)例如Micrium、Linux等進(jìn)行擴(kuò)展，以支持OSEK標(biāo)準(zhǔn)16,17,18,19,20,21,22。而在開(kāi)源嵌入式操作系統(tǒng)領(lǐng)域，openOSEK23和Trampoline24均為基于OSEK標(biāo)準(zhǔn)的嵌入式操作系統(tǒng)。其中openOSEK并未發(fā)布成熟運(yùn)行版本，Trampoline已經(jīng)可以在多個(gè)平臺(tái)上運(yùn)行。Trampoline嵌入式操作系統(tǒng)的設(shè)計(jì)出發(fā)點(diǎn)是良好的平臺(tái)移植性以及低內(nèi)存消耗，整體可分為三個(gè)部分：1) Goil：OIL解析器。以O(shè)IL

36、文件為輸入文件，生成系統(tǒng)配置相關(guān)的頭文件(與平臺(tái)相關(guān))。目前支持Infineon C167、PowerPC以及x86平臺(tái)。2) Viper：虛擬處理器仿真器(Virtual Processor Emulator)。用于在類UNIX平臺(tái)之上對(duì)目標(biāo)平臺(tái)進(jìn)行仿真，Viper監(jiān)控定時(shí)器、中斷以及警報(bào)，通過(guò)共享內(nèi)存以及異步POSIX信號(hào)與OSEK進(jìn)程通信。3) Kernel：OSEK內(nèi)核。支持ECC2和BCC2一致類中的標(biāo)準(zhǔn)中規(guī)定的系統(tǒng)調(diào)用。在已有系統(tǒng)上對(duì)OSEK/VDX進(jìn)行擴(kuò)展的系統(tǒng)僅僅是部分支持OSEK標(biāo)準(zhǔn)，并且其調(diào)度算法并非針對(duì)OSEK操作系統(tǒng)專門設(shè)計(jì)，可能帶來(lái)不必要的開(kāi)銷。而Trampoline

37、是專門針對(duì)OSEK標(biāo)準(zhǔn)設(shè)計(jì)的嵌入式實(shí)時(shí)操作系統(tǒng)，平臺(tái)移植性好、內(nèi)存消耗較低，但是其調(diào)度開(kāi)銷可能隨著任務(wù)增多而加劇。1.3 論文的主要工作本文主要針對(duì)OSEK操作系統(tǒng)調(diào)度機(jī)制進(jìn)行研究。主要包括以下兩個(gè)方面：1) OSEK操作系統(tǒng)調(diào)度機(jī)制分析及實(shí)現(xiàn)本文在深入分析OSEK操作系統(tǒng)標(biāo)準(zhǔn)的基礎(chǔ)上，結(jié)合實(shí)時(shí)系統(tǒng)調(diào)度機(jī)制現(xiàn)有研究，分析了OSEK操作系統(tǒng)調(diào)度機(jī)制的實(shí)質(zhì)支持優(yōu)先級(jí)天花板協(xié)議的固定優(yōu)先級(jí)調(diào)度，進(jìn)而提出了滿足OSEK特殊需求的調(diào)度機(jī)制的實(shí)現(xiàn)方法。將OSEK任務(wù)調(diào)度分為三個(gè)部分：判斷何時(shí)發(fā)生調(diào)度、查找最高優(yōu)先級(jí)就緒任務(wù)以及任務(wù)切換機(jī)制。通過(guò)分析OSEK操作系統(tǒng)的重調(diào)度點(diǎn)，解決了OSEK操作系統(tǒng)何時(shí)才會(huì)

38、發(fā)生重調(diào)度的問(wèn)題；根據(jù)OSEK操作系統(tǒng)就緒隊(duì)列的特性，提出了針對(duì)OSEK操作系統(tǒng)的高度優(yōu)化的就緒任務(wù)隊(duì)列的實(shí)現(xiàn)方法；通過(guò)分析OSEK操作系統(tǒng)任務(wù)特征以及任務(wù)切換機(jī)制，提出了針對(duì)OSEK操作系統(tǒng)的任務(wù)堆棧優(yōu)化方法。在Trampoline原有算法的基礎(chǔ)上實(shí)現(xiàn)了本文提出的算法，對(duì)二者運(yùn)行時(shí)間進(jìn)行對(duì)比分析。2) OSEK應(yīng)用任務(wù)集可調(diào)度性分析本文在實(shí)時(shí)現(xiàn)有調(diào)度分析理論的基礎(chǔ)上，結(jié)合OSEK操作系統(tǒng)特征，提出了針對(duì)OSEK應(yīng)用任務(wù)集的調(diào)度分析方法，給出了OSEK應(yīng)用任務(wù)模型，并在該模型基礎(chǔ)上做出相關(guān)假定，給出了不考慮系統(tǒng)開(kāi)銷情況下OSEK應(yīng)用任務(wù)集中任務(wù)的最壞情況響應(yīng)時(shí)間的計(jì)算方法，進(jìn)一步提出了OSEK

39、應(yīng)用任務(wù)集調(diào)度可行性的充分條件。根據(jù)OSEK應(yīng)用，提出了OSEK操作系統(tǒng)調(diào)度相關(guān)的六種系統(tǒng)開(kāi)銷：激活任務(wù)、終止任務(wù)、時(shí)鐘滴答、切換開(kāi)銷、獲取資源以及釋放資源。在不考慮系統(tǒng)開(kāi)銷的調(diào)度分析基礎(chǔ)上，加入了對(duì)這些系統(tǒng)開(kāi)銷的分析，進(jìn)一步給出了考慮系統(tǒng)開(kāi)銷的OSEK應(yīng)用任務(wù)集中任務(wù)的最壞情況響應(yīng)時(shí)間的計(jì)算方法，并提出了考慮系統(tǒng)開(kāi)銷的情況下，OSEK應(yīng)用任務(wù)集調(diào)度可行性的充分條件，最后通過(guò)實(shí)驗(yàn)對(duì)比了不考慮系統(tǒng)開(kāi)銷的任務(wù)最壞情況響應(yīng)時(shí)間、考慮系統(tǒng)開(kāi)銷的任務(wù)最壞情況響應(yīng)時(shí)間二者理論值以及實(shí)際系統(tǒng)運(yùn)行的任務(wù)響應(yīng)時(shí)間。本文工作的創(chuàng)新點(diǎn)在于：1) 目前已有的OSEK操作系統(tǒng)絕大多數(shù)均為商業(yè)系統(tǒng)，本文在深入分析OSEK

40、操作系統(tǒng)的調(diào)度機(jī)制基礎(chǔ)上，給出一種更適合OSEK操作系統(tǒng)的調(diào)度實(shí)現(xiàn)方案。2) 已有的調(diào)度分析理論主要針對(duì)通用的調(diào)度策略，本文在此基礎(chǔ)上，提出了針對(duì)OSEK應(yīng)用任務(wù)集的調(diào)度分析方法。1.4 論文組織結(jié)構(gòu)本文緒論主要對(duì)OSEK相關(guān)標(biāo)準(zhǔn)進(jìn)行介紹，并針對(duì)OSEK操作系統(tǒng)中任務(wù)調(diào)度的問(wèn)題加以分析，提出了本文需要解決的問(wèn)題。本文第二章介紹了多任務(wù)系統(tǒng)的分類，分析不同類別多任務(wù)系統(tǒng)的調(diào)度需求，介紹了相關(guān)調(diào)度算法，著重介紹了實(shí)時(shí)系統(tǒng)中調(diào)度所受的約束，以及實(shí)時(shí)系統(tǒng)中的常用調(diào)度方法。本文第三章是OSEK操作系統(tǒng)任務(wù)調(diào)度機(jī)制，首先介紹了OSEK操作系統(tǒng)中的任務(wù)概念，在此基礎(chǔ)上分析了OSEK操作系統(tǒng)中的任務(wù)調(diào)度機(jī)制，

41、給出適合OSEK操作系統(tǒng)的調(diào)度算法及其實(shí)現(xiàn)，從調(diào)度角度分析并給出了對(duì)任務(wù)堆棧的優(yōu)化方法。在第三章結(jié)尾，通過(guò)實(shí)驗(yàn)驗(yàn)證本文提出的調(diào)度算法。本文第四章對(duì)OSEK應(yīng)用進(jìn)行調(diào)度分析，首先提出了OSEK操作系統(tǒng)中的任務(wù)模型以及相關(guān)概念假設(shè)，在此基礎(chǔ)上對(duì)OSEK應(yīng)用任務(wù)集進(jìn)行調(diào)度分析，進(jìn)而在分析基礎(chǔ)上加入對(duì)系統(tǒng)開(kāi)銷的考慮，最后通過(guò)實(shí)驗(yàn)對(duì)比了不考慮系統(tǒng)開(kāi)銷的任務(wù)最壞情況響應(yīng)時(shí)間、考慮系統(tǒng)開(kāi)銷的任務(wù)最壞情況響應(yīng)時(shí)間二者理論值以及實(shí)際系統(tǒng)運(yùn)行的任務(wù)響應(yīng)時(shí)間。文章最后總結(jié)全文，并對(duì)進(jìn)一步工作進(jìn)行展望。第 2 章 操作系統(tǒng)中的任務(wù)調(diào)度通常操作系統(tǒng)中的調(diào)度可以分為交互式操作系統(tǒng)調(diào)度、多處理器調(diào)度以及實(shí)時(shí)調(diào)度三類。調(diào)度算

42、法需要考慮系統(tǒng)多個(gè)方面的需求，不可能使這些需求都達(dá)到最優(yōu)，例如，提供較好的響應(yīng)時(shí)間可能需要調(diào)度算法在任務(wù)間頻繁的切換，增加了系統(tǒng)開(kāi)銷，降低了吞吐量。因此，設(shè)計(jì)一個(gè)調(diào)度算法需要在互相競(jìng)爭(zhēng)的各個(gè)條件之間進(jìn)行折衷，根據(jù)系統(tǒng)的本質(zhì)和使用情況，給各種要求設(shè)定相對(duì)權(quán)值。2.1 背景介紹操作系統(tǒng)中必須為多個(gè)任務(wù)可能有競(jìng)爭(zhēng)的請(qǐng)求分配計(jì)算機(jī)資源。對(duì)處理器而言，可分配的資源是在處理器上的執(zhí)行時(shí)間，分配的途徑是任務(wù)調(diào)度。調(diào)度功能必須設(shè)計(jì)成可以滿足多個(gè)目標(biāo)，包括公平、任何進(jìn)程都不會(huì)餓死、有效的使用處理器時(shí)間和低開(kāi)銷。此外，調(diào)度功能可能需要為某些進(jìn)程的啟動(dòng)或者結(jié)束考慮不同優(yōu)先級(jí)和實(shí)時(shí)最終期限。近年來(lái)，調(diào)度已經(jīng)成為深入研

43、究的焦點(diǎn)，并且已經(jīng)實(shí)現(xiàn)了許多不同的算法。選擇函數(shù)確定在就緒進(jìn)程中選擇哪一個(gè)在下一次運(yùn)行，該函數(shù)可以是基于優(yōu)先級(jí)、資源需求或者任務(wù)的執(zhí)行特性。調(diào)度模式通?？煞譃椋嚎蓳屨寂c不可搶占的6。不可搶占型內(nèi)核要求每個(gè)任務(wù)自我放棄處理器的所有權(quán)。不可搶占型調(diào)度法也稱作合作型多任務(wù)，各個(gè)任務(wù)彼此合作共享一個(gè)處理器。異步事件還是由中斷服務(wù)來(lái)處理。中斷服務(wù)可以使一個(gè)高優(yōu)先級(jí)的任務(wù)由掛起狀態(tài)變?yōu)榫途w狀態(tài)。但中斷服務(wù)以后控制權(quán)還是回到原來(lái)被中斷了的那個(gè)任務(wù)，直到該任務(wù)主動(dòng)放棄處理器的使用權(quán)時(shí)不可剝奪型內(nèi)核的最大缺陷在于其響應(yīng)時(shí)間。高優(yōu)先級(jí)的任務(wù)已經(jīng)進(jìn)入就緒態(tài)，但還不能運(yùn)行，要等，也許要等很長(zhǎng)時(shí)間，直到當(dāng)前運(yùn)行著的任務(wù)

44、釋放處理器。不可搶占型內(nèi)核的優(yōu)點(diǎn)是響應(yīng)中斷快、幾乎不需要使用信號(hào)量保護(hù)共享數(shù)據(jù)。不可搶占型內(nèi)核的任務(wù)響應(yīng)時(shí)間是不確定的，不知道什么時(shí)候最高優(yōu)先級(jí)的任務(wù)才能拿到處理器的控制權(quán)，完全取決于應(yīng)用程序什么時(shí)候釋放處理器。，那個(gè)高優(yōu)先級(jí)的任務(wù)才能獲得處理器的使用權(quán)。當(dāng)系統(tǒng)響應(yīng)時(shí)間很重要時(shí)，要使用可搶占型內(nèi)核。因此，絕大多數(shù)商業(yè)上銷售的實(shí)時(shí)內(nèi)核都是可搶占型內(nèi)核。最高優(yōu)先級(jí)的任務(wù)一旦就緒，總能得到處理器的控制權(quán)。當(dāng)一個(gè)運(yùn)行著的任務(wù)使一個(gè)比它優(yōu)先級(jí)高的任務(wù)進(jìn)入了就緒態(tài)，當(dāng)前任務(wù)的處理器使用權(quán)就被剝奪了，或者說(shuō)被掛起了，那個(gè)高優(yōu)先級(jí)的任務(wù)立刻得到了處理器的控制權(quán)。如果是中斷服務(wù)子程序使一個(gè)高優(yōu)先級(jí)的任務(wù)進(jìn)入就緒

45、態(tài)，中斷完成時(shí)，中斷了的任務(wù)被掛起，優(yōu)先級(jí)高的那個(gè)任務(wù)開(kāi)始運(yùn)行。使用可剝奪型內(nèi)核，最高優(yōu)先級(jí)的任務(wù)什么時(shí)候可以執(zhí)行，可以得到處理器的控制權(quán)是可知的。使用可搶占型內(nèi)核使得任務(wù)響應(yīng)時(shí)間得以最優(yōu)化。使用可搶占型內(nèi)核時(shí)，應(yīng)用程序不應(yīng)直接使用不可重入型函數(shù)。調(diào)用不可重入型函數(shù)時(shí)，要滿足互斥條件，這一點(diǎn)可以用互斥型信號(hào)量來(lái)實(shí)現(xiàn)。如果調(diào)用不可重入型函數(shù)時(shí)，低優(yōu)先級(jí)的任務(wù)處理器的使用權(quán)被高優(yōu)先級(jí)任務(wù)搶占，不可重入型函數(shù)中的數(shù)據(jù)有可能被破壞。綜上所述，可搶占型內(nèi)核總是讓就緒態(tài)的高優(yōu)先級(jí)的任務(wù)先運(yùn)行，中斷服務(wù)程序可以搶占處理器，到中斷服務(wù)完成時(shí)，內(nèi)核選擇此時(shí)優(yōu)先級(jí)最高的任務(wù)運(yùn)行（不一定是那個(gè)被中斷了的任務(wù)）。任務(wù)

46、系統(tǒng)響應(yīng)時(shí)間得到了最優(yōu)化，且是可知的。2.1.1 交互式操作系統(tǒng)中的調(diào)度交互式操作系統(tǒng)中，通常為單處理器，任務(wù)之間共享一個(gè)處理器，處理器通過(guò)執(zhí)行某個(gè)任務(wù)而保持忙狀態(tài)，而此時(shí)其它任務(wù)處于等待狀態(tài)。交互式操作系統(tǒng)中，由于需要與用戶進(jìn)行交互，需要為用戶提供適當(dāng)?shù)捻憫?yīng)時(shí)間，考慮用戶使用的需求。常見(jiàn)的交互式操作系統(tǒng)中的調(diào)度算法有以下幾類25：1) 先來(lái)先服務(wù)(FCFS)也稱作先進(jìn)先出(FIFO)，當(dāng)每個(gè)任務(wù)就緒后，加入就緒隊(duì)列，當(dāng)前任務(wù)停止運(yùn)行時(shí)，選擇就緒隊(duì)列中最早的任務(wù)運(yùn)行。2) 時(shí)間片以固定的時(shí)間間隔周期性產(chǎn)生時(shí)鐘中斷，當(dāng)中斷發(fā)生時(shí)，當(dāng)前任務(wù)被置于就緒狀態(tài)，然后基于FIFO選擇下一個(gè)就緒任務(wù)運(yùn)行。3

47、) 最短任務(wù)優(yōu)先最短任務(wù)優(yōu)先屬于不可搶占調(diào)度，其原則是選擇所需時(shí)間最短的任務(wù)，可能導(dǎo)致長(zhǎng)任務(wù)被餓死的情況。4) 最短剩余時(shí)間調(diào)度程序總是選擇預(yù)期剩余時(shí)間最短的任務(wù)，可能導(dǎo)致長(zhǎng)任務(wù)被餓死的情況。5) 反饋隊(duì)列當(dāng)一個(gè)任務(wù)第一次進(jìn)入系統(tǒng)中時(shí)，將其放在最高優(yōu)先級(jí)的隊(duì)列中，在隨后時(shí)間，每當(dāng)它被搶占時(shí)，就被降級(jí)到下一個(gè)低優(yōu)先級(jí)的隊(duì)列中。隊(duì)列內(nèi)使用FIFO來(lái)選擇任務(wù)?？梢钥闯觯换ナ较到y(tǒng)需要考慮用戶與系統(tǒng)之間的交互，需要平衡各個(gè)任務(wù)的公平執(zhí)行，對(duì)運(yùn)行時(shí)間要求不是很高。2.1.2 多處理器調(diào)度當(dāng)一個(gè)計(jì)算機(jī)系統(tǒng)中包含多個(gè)處理器時(shí)，在設(shè)計(jì)調(diào)度功能時(shí)就會(huì)產(chǎn)生一些新的問(wèn)題，主要包括以下兩個(gè)方面25：1) 任務(wù)分配到處

48、理器通常系統(tǒng)維護(hù)一個(gè)公共隊(duì)列，任務(wù)就緒時(shí)加入該隊(duì)列，然后調(diào)度選擇到可用的處理器上運(yùn)行。2) 任務(wù)的實(shí)際分派任務(wù)被分配到具體的處理器后，問(wèn)題就變成了該任務(wù)在單處理器系統(tǒng)中的調(diào)度。多處理器調(diào)度中，通常將任務(wù)劃分為一組線程，這些線程可以在同一地址空間內(nèi)協(xié)作和并發(fā)的執(zhí)行，線程調(diào)度常用的幾種方法有：1) 負(fù)載分配任務(wù)不是分配到一個(gè)特定的處理器，而是維護(hù)一個(gè)就緒任務(wù)的全局隊(duì)列，每個(gè)處理器只要空閑就從隊(duì)列中選擇一個(gè)任務(wù)。2) 成組調(diào)度一組相關(guān)的線程基于一對(duì)一的原則，同時(shí)調(diào)度到一組處理器上運(yùn)行。3) 專用處理器分配與負(fù)載分配方法相反，它通過(guò)把線程指定到處理器來(lái)定義隱式的調(diào)度。在任務(wù)執(zhí)行過(guò)程中，每個(gè)任務(wù)被分配給

49、一組處理器，處理器的數(shù)目與任務(wù)中線程數(shù)目相等。當(dāng)任務(wù)終止時(shí)，處理器返回到總的處理器池中，可供分配給另一個(gè)任務(wù)。4) 動(dòng)態(tài)調(diào)度在執(zhí)行過(guò)程中，任務(wù)內(nèi)線程數(shù)目可變。顯然，多處理器系統(tǒng)中，會(huì)對(duì)多個(gè)處理器間的協(xié)同工作以及負(fù)載平衡予以較多考慮。2.1.3 實(shí)時(shí)調(diào)度實(shí)時(shí)系統(tǒng)中的調(diào)度根據(jù)實(shí)時(shí)性要求分為硬實(shí)時(shí)調(diào)度和軟實(shí)時(shí)調(diào)度。其中硬實(shí)時(shí)調(diào)度是所有的任務(wù)必須在其最終期限內(nèi)完成，而軟實(shí)時(shí)調(diào)度允許有部分延遲。任務(wù)調(diào)度算法設(shè)計(jì)的好壞直接決定了實(shí)時(shí)系統(tǒng)能否成功運(yùn)行，實(shí)時(shí)系統(tǒng)中的任務(wù)調(diào)度算法必須是高度優(yōu)化、高效、對(duì)資源占用盡可能少的。實(shí)時(shí)系統(tǒng)中任務(wù)的另一個(gè)特征就可以是周期的也可以是非周期的。實(shí)時(shí)系統(tǒng)的設(shè)計(jì)目標(biāo)是盡可能快速的

50、啟動(dòng)實(shí)時(shí)任務(wù)，因此強(qiáng)調(diào)快速中斷處理和任務(wù)分派。通常，實(shí)時(shí)系統(tǒng)中的任務(wù)調(diào)度可以分為三個(gè)部分：離線配置、運(yùn)行時(shí)分派以及優(yōu)先級(jí)分析26。離線配置主要用來(lái)為系統(tǒng)運(yùn)行生成靜態(tài)配置信息。在某些調(diào)度方法中，配置信息由表組成，這些表指示了哪個(gè)任務(wù)將被運(yùn)行以及何時(shí)運(yùn)行。而在另一類調(diào)度算法中，這些離線配置信息非常少，甚至沒(méi)有，調(diào)度器使用實(shí)時(shí)信息(如最終期限)來(lái)選擇哪個(gè)任務(wù)將被運(yùn)行。運(yùn)行時(shí)分派用來(lái)處理計(jì)算系統(tǒng)運(yùn)行中不同事務(wù)所發(fā)生的切換。絕大多數(shù)的調(diào)度方法都是基于處理器上的任務(wù)系統(tǒng)。實(shí)時(shí)調(diào)度算法通過(guò)當(dāng)前系統(tǒng)信息(例如當(dāng)前系統(tǒng)時(shí)間)以及離線配置信息(例如任務(wù)優(yōu)先級(jí))來(lái)確定何時(shí)發(fā)生任務(wù)切換。任務(wù)切換有兩種策略：可搶占的和

51、不可搶占的?？蓳屨记袚Q需要停止當(dāng)前正在運(yùn)行的任務(wù)，切換到另外的任務(wù)，后面需要再切換回被中止的任務(wù)繼續(xù)執(zhí)行。而不可搶占中斷中，任務(wù)一旦開(kāi)始運(yùn)行，就需要等待其運(yùn)行結(jié)束才能繼續(xù)運(yùn)行其它任務(wù)。運(yùn)行時(shí)的調(diào)度算法并不能保證所有的任務(wù)都能在其最終期限內(nèi)完成，而優(yōu)先級(jí)分析主要是在系統(tǒng)運(yùn)行前分析是否能滿足時(shí)間要求。分析需要清楚的知道離線配置信息以及運(yùn)行時(shí)調(diào)度算法的具體行為。當(dāng)優(yōu)先級(jí)分析得出調(diào)度可行的結(jié)論時(shí)，所有最終期限條件都滿足，此時(shí)稱該分析是必要的。而當(dāng)優(yōu)先級(jí)分析得出調(diào)度不可行時(shí)，必定有某個(gè)任務(wù)的最終期限不會(huì)被滿足，稱該分析是充分的。同時(shí)滿足充分和必要的分析稱為嚴(yán)格的。近三十年來(lái)，調(diào)度分析理論不斷發(fā)展，針對(duì)固

52、定優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)調(diào)度策略均有相關(guān)，而在每種調(diào)度策略中，關(guān)于調(diào)度分析的理論可以分為調(diào)度最佳性條件、任務(wù)最壞情況響應(yīng)時(shí)間以及調(diào)度可行性充分條件三個(gè)部分。2.2 實(shí)時(shí)調(diào)度方法2.2.1 靜態(tài)循環(huán)調(diào)度靜態(tài)循環(huán)調(diào)度27,28是實(shí)時(shí)系統(tǒng)中早期使用的一種調(diào)度方法，它是一種離線方法。任務(wù)運(yùn)行模式由配置算法計(jì)算得出，該運(yùn)行模式存儲(chǔ)在一個(gè)表中(通常被稱作Calendar)，運(yùn)行時(shí)調(diào)度器遵循來(lái)自該表的信息。表通過(guò)當(dāng)前時(shí)間模除表長(zhǎng)來(lái)進(jìn)行索引，其運(yùn)行模式是重復(fù)循環(huán)的，因此得名。該調(diào)度方法非常簡(jiǎn)單，對(duì)其調(diào)度行為的分析也就沒(méi)有太大的意義：只需要循環(huán)遍歷該表即可得出最終期限是否滿足。靜態(tài)優(yōu)先級(jí)調(diào)度有著極大的局限性：不能處

53、理由外部事務(wù)調(diào)用的任務(wù)，所有外部事務(wù)只能通過(guò)輪詢來(lái)處理；表的大小不能過(guò)大等。在現(xiàn)有實(shí)時(shí)系統(tǒng)中已經(jīng)很少有其應(yīng)用。2.2.2 固定優(yōu)先級(jí)調(diào)度應(yīng)用程序執(zhí)行過(guò)程中任務(wù)優(yōu)先級(jí)不變，則稱之為固定優(yōu)先級(jí)。在固定優(yōu)先級(jí)系統(tǒng)26中，任務(wù)以及它們的時(shí)間約束在程序編譯時(shí)是已知的。固定優(yōu)先級(jí)調(diào)度包括可搶占和不可搶占兩種，系統(tǒng)運(yùn)行過(guò)程中，任務(wù)的優(yōu)先級(jí)不會(huì)發(fā)生改變。在可搶占固定優(yōu)先級(jí)調(diào)度中，調(diào)度器需要時(shí)刻確保最高優(yōu)先級(jí)的可運(yùn)行任務(wù)在實(shí)際運(yùn)行。低優(yōu)先級(jí)任務(wù)運(yùn)行過(guò)程中，如果有高優(yōu)先級(jí)的任務(wù)觸發(fā)，那么調(diào)度器需要掛起低優(yōu)先級(jí)任務(wù)，轉(zhuǎn)去執(zhí)行高優(yōu)先級(jí)的任務(wù)。而不可搶占固定優(yōu)先級(jí)調(diào)度中，在任務(wù)執(zhí)行過(guò)程中不會(huì)發(fā)生任務(wù)搶占。固定優(yōu)先級(jí)調(diào)度

54、系統(tǒng)行為簡(jiǎn)單，實(shí)現(xiàn)較容易，運(yùn)行時(shí)系統(tǒng)開(kāi)銷較低，因此在實(shí)時(shí)系統(tǒng)領(lǐng)域應(yīng)用廣泛。2.2.3 動(dòng)態(tài)優(yōu)先級(jí)調(diào)度動(dòng)態(tài)優(yōu)先級(jí)調(diào)度是指系統(tǒng)運(yùn)行過(guò)程中，任務(wù)的優(yōu)先級(jí)會(huì)根據(jù)具體情況發(fā)生改變26。主要包括最早最終期限優(yōu)先(EDF)、先進(jìn)先出(FIFO)、后進(jìn)先出(LIFO)等。其中EDF算法時(shí)刻保證最接近最終期限的任務(wù)優(yōu)先運(yùn)行，F(xiàn)IFO算法時(shí)刻保證最先就緒的任務(wù)優(yōu)先運(yùn)行，而LIFO算法保證最后進(jìn)入就緒狀態(tài)的任務(wù)優(yōu)先運(yùn)行。與固定優(yōu)先級(jí)調(diào)度相比，動(dòng)態(tài)優(yōu)先級(jí)調(diào)度實(shí)現(xiàn)更為復(fù)雜，對(duì)系統(tǒng)資源的消耗較大。2.3 典型實(shí)時(shí)系統(tǒng)中的任務(wù)調(diào)度本節(jié)主要分析了典型實(shí)時(shí)系統(tǒng)Vxworks、Micrium、實(shí)時(shí)Linux以及Trampolin

55、e的任務(wù)調(diào)度機(jī)制，通常實(shí)時(shí)系統(tǒng)調(diào)度主要包括查找最高優(yōu)先級(jí)就緒任務(wù)以及任務(wù)切換兩個(gè)部分，由于任務(wù)切換通常與具體硬件平臺(tái)相關(guān)，操作系統(tǒng)設(shè)計(jì)無(wú)法影響這部分。因此實(shí)時(shí)系統(tǒng)調(diào)度中，最關(guān)鍵的就是如何查找最高優(yōu)先級(jí)就緒任務(wù)。2.3.1 VxworksVxworks是美國(guó)Wind River公司開(kāi)發(fā)的嵌入式實(shí)時(shí)操作系統(tǒng)29,30，其內(nèi)核稱為Wind。Wind內(nèi)核缺省調(diào)度機(jī)制為基于優(yōu)先級(jí)的搶占式調(diào)度。采用這種機(jī)制時(shí)，系統(tǒng)把處理器分配給優(yōu)先級(jí)最高的進(jìn)程，使之執(zhí)行。一旦出現(xiàn)了另一個(gè)優(yōu)先級(jí)更高的進(jìn)程時(shí)，進(jìn)程調(diào)度程序剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給高優(yōu)先級(jí)任務(wù)而在相同優(yōu)先級(jí)的多個(gè)任務(wù)之間。也可以采用時(shí)間片輪轉(zhuǎn)調(diào)度機(jī)制

56、，采用這種機(jī)制時(shí)，當(dāng)一個(gè)任務(wù)到達(dá)時(shí)，它被排在輪轉(zhuǎn)隊(duì)列的后面，等待分配給自己的時(shí)間片的到來(lái)，如果在時(shí)間片內(nèi)沒(méi)有結(jié)束，則再等待屬于自己的時(shí)間片的到來(lái)，直到任務(wù)完成。 采用基于優(yōu)先級(jí)的搶占式調(diào)度，系統(tǒng)中每個(gè)任務(wù)都有一個(gè)介于最高0到最低 255之間的優(yōu)先級(jí)。任一時(shí)刻，系統(tǒng)內(nèi)核一旦發(fā)現(xiàn)一個(gè)優(yōu)先級(jí)更高的任務(wù)轉(zhuǎn)變?yōu)榫途w態(tài)，內(nèi)核就保存當(dāng)前任務(wù)的上下文并把當(dāng)前任務(wù)狀態(tài)轉(zhuǎn)換為阻塞態(tài)，同時(shí)切換到這個(gè)高優(yōu)先級(jí)任務(wù)的上下文執(zhí)行。采用輪轉(zhuǎn)調(diào)度算法，系統(tǒng)讓處于就緒態(tài)的優(yōu)先級(jí)相同的一組任務(wù)依次輪流執(zhí)行預(yù)先確定長(zhǎng)度的時(shí)間片。這是一種處理機(jī)平均分配的方法。如果不使用輪轉(zhuǎn)調(diào)度算法，優(yōu)先級(jí)相同的一組任務(wù)中第一個(gè)獲得處理機(jī)的任務(wù)將不會(huì)被阻塞而獨(dú)占處理機(jī)，如果沒(méi)有阻塞或其他情況發(fā)生，它不會(huì)放棄處理機(jī)的使用權(quán)?；趦?yōu)先級(jí)的搶占式調(diào)度可與輪轉(zhuǎn)調(diào)度相結(jié)合。當(dāng)優(yōu)先級(jí)相同的一組任務(wù)依次輪流平均分配處理機(jī)時(shí)，若有高優(yōu)先級(jí)的任務(wù)轉(zhuǎn)變?yōu)榫途w態(tài)就可以搶占該組任務(wù)。直到再一次符合執(zhí)行條件時(shí)，該組任務(wù)才可再次共享處理機(jī)。為了任務(wù)控制的靈活性 ，Wind內(nèi)核還提供了動(dòng)態(tài)優(yōu)先級(jí)機(jī)制，任務(wù)的優(yōu)先級(jí)在運(yùn)行期間可動(dòng)態(tài)地變化。同時(shí)，為了防止優(yōu)先級(jí)反轉(zhuǎn)，還