摘要:本文从实时操作系统的调度功能入手,简单介绍了实时调度算法的分类和种类,
并主要讨论动态优先级调度算法的特点和实现。接下来本文介绍了两类动态优先级调度算法:
截止时间优先调度算法和最短空闲时间优先调度算法的定义及实现方式。然后将静态调度与
动态调度进行比较,突出动态优先级调度的特点,同时指出其可能导致的优先级反转、死锁
等不良后果。然后具体介绍了优先级反转的定义以及解决该问题的两种方案:采用优先级继
承协议与采用优先级天花板协议。
关键词:嵌入式系统 动态优先级 调度算法 优先级反转
在嵌入式的实时操作系统中,调度是一个非常重要的功能,用来确定多任务环境下任务
执行的顺序和在获得 CPU 资源后能够执行的时间长度。
操作系统通过一个调度程序(Scheduler)来实现调度功能。调度程序以函数的形式存在,
用来实现操作系统的调度算法。调度程序本身并不是一个任务,而是一个函数调用,可在内
核的各个部分进行调用。调度程序是影响系统性能(如吞吐率、延迟时间等)的重要部分。
在设计调度程序是、时,通常要综合考虑如下因素:
●CPU 的使用率(CUP utilization);
●输入/输出设备的吞吐率;
●响应时间(responsive time);
●公平性;
这些因素之间具有一定的冲突性。比如可通过让更多的任务处于就绪状态来提高 CPU
的使用率,但这显然会降低系统的响应时间。因此,调度程序的设计需要优先考虑最重要的
需求,然后在各种因素之间进行折中处理。
可以把一个调度算法(Scheduling Algorithms)描述为是在一个特定时刻用来确定将要
运行的任务的一组规则。从 1973 年 Liu 和 Layland 开始关于实时调度算法的研究工作以来
(1973 年,Liu 和 Layland 发表了 一篇名为“Scheduling Algorithms for Multiprogramming in a
Hard Real-Time Environment”的论文),相继出现了许多调度算法和方法。
对于大量的实时调度方法而言,存在着以下几类主要的划分方法:
●离线(off-line)和在线(on-line)调度;
●抢占(preemptive)和非抢占(non-preemptive)调度;