|
|
知识路径： > 嵌入式系统软件基础知识 > 嵌入式操作系统基础知识 > 处理器管理 >
|
|
相关知识点：38个
|
|
|
|
|
许多嵌入式操作系统都是实时操作系统，对于RTOS调度器来说，任务之间的公平性并不是最重要的，它追求的是实时性，即要让每个任务都在其最终时间期限之前完成。
|
|
|
|
大多数RTOS调度器都采用了基于优先级的可抢占调度算法，但是在具体实现上，需要考虑几个方面的问题，例如，如何设定各个任务的优先级？优先级是静态设置的还是动态可变的？算法的性能如何，能否满足实时要求？
|
|
|
|
|
|
考虑实时系统中常用的任务模型，即周期性任务模型。所谓的周期任务，就是该任务每隔固定的一段时间，就会运行一次。
|
|
|
|
|
|
.启动时间r（i，j）：第i个任务的第j次执行的开始时间；
|
|
|
|
.时间期限D（i）：第i个任务所允许的最大响应时间（从任务启动到运行结束所需的时间）；
|
|
|
|
.周期P（i）：第i个任务的连续两次运行之间的最小时间间隔；
|
|
|
|
.执行时间E（i）：对于第i个任务，当它所需要的资源都已具备时，其执行所需要的最长时间。
|
|
|
|
在任务模型中，每一个任务用一个三元组来表示（执行时间、周期、时间期限），一般来说，一个任务的周期时间同时也是它的时间期限，因为该任务必须在它的下一个周期开始之前，完成此次运行。另外，任务可以在一个周期内的任何时刻被启动，但必须在它的时间期限之前完成，如下图所示。
|
|
|
|
|
|
|
|
|
|
单调速率调度算法（Rate Monotonic Scheduling，RMS）是一种静态优先级调度算法，也是最常用的一种确定任务优先级的算法。RMS算法是基于以下的几个假设条件。
|
|
|
|
|
|
|
|
|
|
|
|
（5）任务可以在任何位置被抢占，不存在临界区的问题。
|
|
|
|
RMS算法的基本思路：任务的优先级与它的周期表现为单调函数的关系，任务的周期越短，优先级越高；任务的周期越长，优先级越低。
|
|
|
|
RMS算法是一种最优调度算法：如果存在一种基于静态优先级的调度顺序，使得每个任务都能在其期限时间内完成，那么RMS算法总能找到这样的一种可行的调度方案。当然，对于具体的某一组任务而言，这种调度方案并不一定存在。但只要存在，就能通过RMS算法进行调度。
|
|
|
为了判断一组任务的可调度性，可以计算CPU的使用率： 。如前所述，Ei是第i个任务的执行时间，Pi是它的周期。
|
|
|
|
.如果U>1，则RMS调度方案不存在（处理器不可能一天工作25个小时）；
|
|
|
|
.如果U≤n（21/n-1），n为任务的个数，则RMS调度方案一定存在；
|
|
|
|
.如果n（21/n-1）<U≤1，则RMS调度方案可能存在也可能不存在。
|
|
|
|
令T=n（21/n-1），表示可调度上限。例如，当n=1时，T=1；当n=2时，T=0.83；当n趋向于无穷大时，T=1n2=0.69。
|
|
|
|
例如，如下表所示，有两个任务T1和T2。T1的执行时间为2，周期和时间期限为5；T2的执行时间为4，周期和时间期限为7。由于T1的周期更短，因此它的优先级要高于T2。另外，在该系统当中，CPU的使用率U=2/5+4/7=0.97，而RMS的可调度上限T=0.83，因此，在这种情形下，RMS无法保证能够找到合适的调度顺序，使得每个任务都能在自己的时间期限之前完成。
|
|
|
|
|
|
|
|
|
|
最早期限优先（Earliest Deadline First，EDF）调度算法是一种动态优先级调度算法，它能根据需要动态地修改各个任务的优先级，是目前性能较好的一种调度算法。
|
|
|
|
EDF算法的基本思路是：根据任务的截止时间来确定其优先级，对于时间期限最近的任务，分配最高的优先级。当有一个新的任务处于就绪状态时，各个任务的优先级就有可能要进行调整。与RMS算法一样，EDF算法的分析也是在一系列假设的基础上进行的，它不要求系统中的任务都必须是周期任务，其他的假设条件与RMS相同。
|
|
|
|
EDF算法是最优的单处理器动态调度算法，其可调度上限为100%。对于给定的一组任务，只要它们的CPU使用率小于或等于1，EDF就能找到合适的调度顺序，使得每个任务都能在自己的时间期限内完成。反之，如果EDF不能满足这组任务的调度要求，则其他的调度算法也不行。
|
|
|
|
仍以上表当中的系统为例，在RMS方式下，任务T2会发生超时的现象。但如果采用EDF算法，则可以避免这个问题。
|
|
|
