嵌入式系統(tǒng)算法綜述

1、嵌入式系統(tǒng)論文專業(yè)：通信工程班級：0904班姓名：周晨學號：U200913881嵌入式實時操作系統(tǒng)中實時調(diào)度算法綜述率單調(diào)算法引言實時調(diào)度是指在有限的系統(tǒng)資源下，為一系列任務決定何時運行，并分配任務運行除 CPU之外的資源，以保證其時間約束、時序約束和資源約束得到滿足。一個實時系統(tǒng)可以由 單處理器系統(tǒng)來實現(xiàn)，也可以用多處理器系統(tǒng)來實現(xiàn)。實時調(diào)度算法是保障實時系統(tǒng)時限性 和高可靠性的最重要手段之一。兇。，概述對一般的程序來說，大多數(shù)是考慮指令執(zhí)行的邏輯順序，指令何時執(zhí)行并不重要。而對 實時應用系統(tǒng)的程序就不一樣，當外部某激勵出現(xiàn)時，系統(tǒng)必須以一定的方式和在限定的時 間內(nèi)響應它，如果已超時，那怕執(zhí)

2、行結(jié)果是正確的，系統(tǒng)也認為是失效的。實時操作系統(tǒng)通 常被分為軟實時操作系統(tǒng)和硬實時操作系統(tǒng)。前者意味著偶爾錯過時限是可以容忍的；后者 意味著執(zhí)行過程不但必須正確而且必須準時。在實時操作系統(tǒng)中，系統(tǒng)將程序分成許多任務 （或進程），而每個任務的行為都預先可知，或者是有明確的功能，系統(tǒng)根據(jù)一定的調(diào)度原則， 決定誰可取得執(zhí)行權(quán)，這就是RTOS的核心所在。速率單調(diào)算法速率單調(diào)算法是一個經(jīng)典的算法，它是針對那些響應和處理周期性事件的實時任務的。 它事先為每個這樣的實時任務，分配一個與事件頻率成正比的優(yōu)先級。例如，周期為20ms 的實時任務，優(yōu)先級為50;而周期為100ms的實時任務，優(yōu)先級為10。運行時，

3、調(diào)度程序總 是調(diào)度優(yōu)先級最高的就緒任務。必要時搶占當前正在運行的任務。根據(jù)進程執(zhí)行周期的長短來決定進程的優(yōu)先級別，適合 于周期性實時任務.prio fc(l/ T) Jt：系數(shù):進fit先級 T:任務周期實現(xiàn)時，就緒隊列中的所有任務，按優(yōu)先級Priority排隊，優(yōu)先級最高的任務排在隊 首。當處于運行態(tài)的任務，由于某種原因而掛起時，只要把就緒隊列的首元素，從就緒隊列 中取下，使運行指針pRunTask指向該元素即可。如果是處于其他狀態(tài)的任務變?yōu)榫途w狀態(tài)， 而掛起就緒隊列時，則必須對運行任務和就緒隊列首元素的任務進行比較，優(yōu)先級高的任務 占有CPU。為了區(qū)分這兩種方式，定義一個枚舉型變量MODE

4、: Enum MODESUSPEND 一 XIT， READY同時，在內(nèi)核中設置兩個全局變量sehedulerFlag和sehedulerMode: BOOLEAN SehedulerFlag Enum MODE SchedulerMode;前者確定調(diào)度程序是否應該進行調(diào)度，后者確定按何種方式進行調(diào)度。內(nèi)核在處理系統(tǒng)調(diào)用命令或處理其他中斷的過程中，有些任務的狀態(tài)可能發(fā)生變化，也 可能沒有發(fā)生什么變化。如果發(fā)生變化，就需要就行調(diào)度，相應的處理函數(shù)將把內(nèi)核中的全 局變量SchedulerFlag置為TRUE;而在調(diào)度程序處理完畢后，重新把它置為FALSE。這樣， 調(diào)度程序就可以根據(jù)sehedule

5、rFlag，確定是否對任務進行實際的調(diào)度。當運行的任務被掛起，或者退出運行而引起調(diào)度時，把schedulerMode置為susPEND 一 xIT;當某個任務的狀態(tài)由其他狀態(tài)變?yōu)榫途w，而引起調(diào)度時，把SehedulerMode置為 READY0于是，調(diào)度程序Sehedule;的實現(xiàn)，就可說明如下，其程序為： voidScheduler(intPoliey) if(SehedulerFlag=TRUE) if(SehedulerMode=SUSpENDesEXIT) GetRunTask(Poliey);/取就緒隊列第一個元素作為運行任務 EISe Taskswiteh(Policy);/就緒隊

6、列第一個任務和運行任務互相切換 SehedulerFlag=False;其流程圖為:圖 3-1 $cheduler()iift 程圖其中，函數(shù)GetRunTask按所規(guī)定的策略，取就緒隊列第一個元素作為運行任務。此時， 原運行任務的TCB，在該任務狀態(tài)變化時，己插入掛起隊列或靜止隊列。在此情況下， GetRUNTask的實現(xiàn)過程如下，其中，常數(shù)SRF表示數(shù)率優(yōu)先策略。VOidGetRunTask(intPolicy)switeh(policy)easeSRF:PRunTask=GetReadyTask(NULL);/取就緒隊列首元素SetTasktstate(PRunTask，RUN);/設置

7、任務狀態(tài)Break;當SchedulerMode為READY時，這是某個任務的狀態(tài)由其他狀態(tài)變?yōu)榫途w，而引起調(diào)度， 這時，任務的TCB已按優(yōu)先級插入就緒隊列。所以，函數(shù)Taskswitch按Poficy所規(guī)定的策 略，如果就緒隊列的第一個任務的優(yōu)先級高于當前運行的任務的優(yōu)先級，就使就緒隊列的第 一個任務和運行任務互相切換。實現(xiàn)過程示意如下：Taskswiteh(intPolicy)TCB *PTask=GetReadyTask(NULL);switch(poliey)Case SRF:If(pTask PriorityPRunTask Priority)SetTaskstate(PTask， RUN);SetTaskstate(PRunTask， policy);PutReadyTadk(PRunTask，Poliey);/將任務按 Poliey 策略放回就緒隊列PRunTask=PTask:elseputReadyTadk(PTask， Poliey);Break;這個算法