Chinaunix首页 | 论坛 | 博客
  • 博客访问: 150064
  • 博文数量: 38
  • 博客积分: 687
  • 博客等级: 上士
  • 技术积分: 426
  • 用 户 组: 普通用户
  • 注册时间: 2009-11-09 10:48
文章分类

全部博文(38)

文章存档

2019年(1)

2016年(1)

2014年(5)

2013年(1)

2012年(8)

2011年(17)

2010年(2)

2009年(3)

我的朋友

分类: 嵌入式

2012-03-12 10:37:56

这两个东西不是很新的东西,大概有50年的历史了。
Rate-Monotonic scheduling
因为RMS有一系列的假设,所以实用性不强。
===
任何一个结论都有一个模型假设, 让我们先列出这里的假设:
  (A1) 所有的任务请求都是周期性的,必须在限定的时限内完成;
  (A2) 任务的作业必须在该任务的下一个作业发生之前完成, 这样避免了考虑队列问题; 在这里, 我们对任务和作业不作特别的区分, 因为一个任务请求就是一个作业。
  (A3) 任务之间都是独立的,每个任务的请求不依赖于其他任务请求的开始或完成;
  (A4) 每个任务的运行时间是不变的,这里任务的运行时间是指处理器在无中断情况下用于处理该任务的时间;
  (A5) 所有的非周期性任务都在特殊的情况下运行,比如系统初始化或系统非正常紧急处理程序。
  (A6) 其它一些假设, 比如, 单处理器, 可抢占调度, 任务切换的时间忽略不计等等。
===
RMS的特点
1, 每个任务都是周期性的。
2, 任务的deadline等于任务的周期。
3, 任务的执行时间小于任务的周期
4, 优先级静态固定分配。优先级与周期成反比, 周期越短优先级越高。
===
问题描述:假设一任务集S={t1,t2,t3,...,tn},周期分别是T1,T2,...,Tn,执行时间为c1,c2,...,cn,deadline为D1,D2,...,Dn,Di=Ti。任务ti可以被抢占。
  CPU利用率用U=sum(ci/Ti)来表示。对于单处理器,U<=1是S可调度的前提条件,否则S不可调度。
===

Deadline-monotonic scheduling
===
This priority assignment policy is optimal for a set of periodic or
sporadic tasks which comply with the following restrictive system model:
All tasks have deadlines less than or equal to their minimum inter-arrival times (or periods).
All tasks have worst-case execution times (WCET) that are less than or equal to their deadlines.
All tasks are independent and so do not block each others' execution (for example by accessing mutually exclusive shared resources).
No task voluntarily suspends itself.
There is some point in time, referred to as a critical instant, where all of the tasks become ready to execute simultaneously.
Scheduling overheads (switching from one task to another) are zero.
All tasks have zero release jitter (the time from the task arriving to it becoming ready to execute).
===
与RMS不同的是
1,任务的deadline可以小于任务的周期
2,优先级不是按周期静态分配,而是按deadline到来时间动态分配,越短的deadline优先级越高。

RTEMS上实现了RMS,其他的RTOS没听说。

参考资料
%E6%8E%92%E7%A8%8B



阅读(3760) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~