文档介绍：最低松弛度优先算法
贾作文
郝艳伟
田鹏飞
首先了解一下实时系统与实时调度
导弹的制导系统,飞机自动驾驶系统,火车的订票系统等等
一、时间约束性
实时系统的任务具有一定的时间约束(截止时间)。根据截止时间,实时系统的实时性分为“硬实时”和“软实时”。硬实时是指应用的时间需求能够得到完全满足,否则就造成重大安全事故,如在航空航天、军事、核工业等一些关键领域中的应用。软实时是指某些应用虽然提出时间需求,但实时任务偶尔违反这种需求对系统运行及环境不会造成严重影响,如监控系统等和信息采集系统等。
二、可预测性
可预测性是指系统能够对实时任务的执行时间进行判断,确定是否能够满足任务的时限要求。由于实时系统对时间约束要求的严格性,使可预测性成为实时系统的一项重要性能要求
实时系统的特点
三、可靠性
大多数实时系统要求有较高的可靠性。因为任何差错都可能带来巨大的经济损失,甚至无法预料的灾难性后果。
四、与外部环境的交互作用性
实时系统通常运行在一定的环境下,外部环境是实时系统不可缺少的一个组成部分。计算机子系统一般是控制系统,它必须在规定的时间内对外部请求做出反应。
实时系统中的调度
一、实现实时调度的基本条件
实时调度必须满足实时任务对截止时间的要求,因此实时系统必须:
1 提供必要的调度信息:
就绪时间
开始和完成截止时间
处理时间
资源要求
优先级
采用单处理机系统,但须增强其处理能力,以显著地减少对每一个任务的处理时间;
采用多处理机系统。
3. 采用抢占式调度方式
4. 具有快速切换机制
对外部中断的快速响应能力。
快速的任务分派能力。
二、实时调度算法(real-time scheduling Algorithm)
1、非抢占式调度算法
(1)时间片轮转调度算法:响应时间以秒为级别,只适合于一般实时信息处理系统
(2)非抢占优先权调度算法:响应时间可做到以秒或百毫秒为级别。适应于要求不高的实时控制系统。
2、抢占式调度算法
(1)基于时钟中断抢占的优先权调度算法:响应时间可做到几十毫秒至几毫秒。适合大多数实时系统。
(2)立即抢占的优先权调度:一旦外部中断出现,只要当前任务未处于临界区,即能被剥夺处理机,响应时间可做到几毫秒至100微秒。
1,该算法根据任务紧急(或松弛)的程度,确定任务优先级。任务的紧急程度愈高,为该任务所赋予的优先级就愈高, 以使之优先执行。主要用于可抢占调度方式。
2,与任务的完成截止时间密切相关。
最低松弛度优先算法
任务的松弛度的计算公式
任务的松弛度=必须完成时间-其本身的运行时间-当前时间
系统中有一个按松弛度排序的实时任务就绪队列,松弛度最低的任务排在最前面,调度程序总是选择就绪队列中的队首任务执行。