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

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

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

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

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

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

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

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