|
|
知识路径： > 嵌入式系统软件基础知识 > 嵌入式操作系统基础知识 > 处理器管理 > 实时系统调度 >
|
|
相关知识点：3个
|
|
|
|
|
单调速率调度算法（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无法保证能够找到合适的调度顺序，使得每个任务都能在自己的时间期限之前完成。
|
|
|
|
|
|
|
