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

1、中國科學技術大學碩士學位論文 OSEK操作系統(tǒng)調(diào)度機制研究作者姓名：馮小天學科專業(yè)：計算機軟件與理論導師姓名：李曦 副教授完成時間：二八年五月一日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中國科學技術大學學位論文原創(chuàng)性和授權使用聲明本人聲明所呈交的學位論文,是本人在導師指導下進行研究工作所取得的成果。除已特別加以標注和致謝的地方外，論文中不包含任何他人已經(jīng)發(fā)表或撰寫過的研究成果。與我一同工作的同志對本研究所做的貢獻均已在論文中作了明確的說明。本人授權中國科學技術大學擁有學位論文的部分使用權，即：學校有權按有關規(guī)定向國家有關部門或機構送交論文的復印件和電子版，允許論文被查閱和借閱，可以將學位論文編入有關數(shù)據(jù)庫進行檢索，可以采用影印、縮印或掃描等復制手段保存、匯編學位論文。保密的學位論文在解密后也遵守此規(guī)定。作者簽名：_年

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

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

5、K操作系統(tǒng)調(diào)度相關的六種系統(tǒng)開銷：激活任務、終止任務、時鐘滴答、切換開銷、獲取資源以及釋放資源。在不考慮系統(tǒng)開銷的調(diào)度分析基礎上，加入了對這些系統(tǒng)開銷的分析，進一步精確了考慮系統(tǒng)開銷的OSEK應用任務集中任務的最壞情況響應時間的計算方法，并提出了考慮系統(tǒng)開銷的情況下，OSEK應用任務集調(diào)度可行性的充分條件，最后通過實驗對比了不考慮系統(tǒng)開銷的任務最壞情況響應時間、考慮系統(tǒng)開銷的任務最壞情況響應時間二者理論值以及實際系統(tǒng)運行的任務響應時間。關鍵詞: OSEK操作系統(tǒng) 實時系統(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標準簡介91.1.1OSEK操作系統(tǒng)標準91.1.2OSEK操作系統(tǒng)任務調(diào)度131.2現(xiàn)有OSEK操作系統(tǒng)141.3論文的主要工作151.4論文組織結構16第 2 章操作系統(tǒng)中的任務調(diào)度172.1背景介紹172.1.1交互式操作系統(tǒng)中的調(diào)度182.1.2多處理器調(diào)度192.1.3實時調(diào)度192.2實時調(diào)度方法202.2.1靜態(tài)循環(huán)調(diào)度202.2.2固定優(yōu)先級調(diào)度212.2.3動態(tài)優(yōu)先級調(diào)度212.3典型實時系統(tǒng)中的任務調(diào)度212.3.1Vxworks222.3.2Micri

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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