嵌入式系统算法综述

1、嵌入式系统论文专业：通信工程班级：0904班姓名：周晨学号：U200913881嵌入式实时操作系统中实时调度算法综述率单调算法引言实时调度是指在有限的系统资源下，为一系列任务决定何时运行，并分配任务运行除 CPU之外的资源，以保证其时间约束、时序约束和资源约束得到满足。一个实时系统可以由 单处理器系统来实现，也可以用多处理器系统来实现。实时调度算法是保障实时系统时限性 和高可靠性的最重要手段之一。凶。，概述对一般的程序来说，大多数是考虑指令执行的逻辑顺序，指令何时执行并不重要。而对 实时应用系统的程序就不一样，当外部某激励出现时，系统必须以一定的方式和在限定的时 间内响应它，如果已超时，那怕执

2、行结果是正确的，系统也认为是失效的。实时操作系统通 常被分为软实时操作系统和硬实时操作系统。前者意味着偶尔错过时限是可以容忍的；后者 意味着执行过程不但必须正确而且必须准时。在实时操作系统中，系统将程序分成许多任务 （或进程），而每个任务的行为都预先可知，或者是有明确的功能，系统根据一定的调度原则， 决定谁可取得执行权，这就是RTOS的核心所在。速率单调算法速率单调算法是一个经典的算法，它是针对那些响应和处理周期性事件的实时任务的。 它事先为每个这样的实时任务，分配一个与事件频率成正比的优先级。例如，周期为20ms 的实时任务，优先级为50;而周期为100ms的实时任务，优先级为10。运行时，

3、调度程序总 是调度优先级最高的就绪任务。必要时抢占当前正在运行的任务。根据进程执行周期的长短来决定进程的优先级别，适合 于周期性实时任务.prio fc(l/ T) Jt：系数:进fit先级 T:任务周期实现时，就绪队列中的所有任务，按优先级Priority排队，优先级最高的任务排在队 首。当处于运行态的任务，由于某种原因而挂起时，只要把就绪队列的首元素，从就绪队列 中取下，使运行指针pRunTask指向该元素即可。如果是处于其他状态的任务变为就绪状态， 而挂起就绪队列时，则必须对运行任务和就绪队列首元素的任务进行比较，优先级高的任务 占有CPU。为了区分这两种方式，定义一个枚举型变量MODE

4、: Enum MODESUSPEND 一 XIT， READY同时，在内核中设置两个全局变量sehedulerFlag和sehedulerMode: BOOLEAN SehedulerFlag Enum MODE SchedulerMode;前者确定调度程序是否应该进行调度，后者确定按何种方式进行调度。内核在处理系统调用命令或处理其他中断的过程中，有些任务的状态可能发生变化，也 可能没有发生什么变化。如果发生变化，就需要就行调度，相应的处理函数将把内核中的全 局变量SchedulerFlag置为TRUE;而在调度程序处理完毕后，重新把它置为FALSE。这样， 调度程序就可以根据sehedule

5、rFlag，确定是否对任务进行实际的调度。当运行的任务被挂起，或者退出运行而引起调度时，把schedulerMode置为susPEND 一 xIT;当某个任务的状态由其他状态变为就绪，而引起调度时，把SehedulerMode置为 READY0于是，调度程序Sehedule;的实现，就可说明如下，其程序为： voidScheduler(intPoliey) if(SehedulerFlag=TRUE) if(SehedulerMode=SUSpENDesEXIT) GetRunTask(Poliey);/取就绪队列第一个元素作为运行任务 EISe Taskswiteh(Policy);/就绪队

6、列第一个任务和运行任务互相切换 SehedulerFlag=False;其流程图为:图 3-1 $cheduler()iift 程图其中，函数GetRunTask按所规定的策略，取就绪队列第一个元素作为运行任务。此时， 原运行任务的TCB，在该任务状态变化时，己插入挂起队列或静止队列。在此情况下， GetRUNTask的实现过程如下，其中，常数SRF表示数率优先策略。VOidGetRunTask(intPolicy)switeh(policy)easeSRF:PRunTask=GetReadyTask(NULL);/取就绪队列首元素SetTasktstate(PRunTask，RUN);/设置

7、任务状态Break;当SchedulerMode为READY时，这是某个任务的状态由其他状态变为就绪，而引起调度， 这时，任务的TCB已按优先级插入就绪队列。所以，函数Taskswitch按Poficy所规定的策 略，如果就绪队列的第一个任务的优先级高于当前运行的任务的优先级，就使就绪队列的第 一个任务和运行任务互相切换。实现过程示意如下：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;这个算法