操作系统最低松弛度优先算法(倪健聪)课件.ppt

文档介绍：该【操作系统最低松弛度优先算法(倪健聪)课件 】是由【yzhlya】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【操作系统最低松弛度优先算法(倪健聪)课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。最低松弛度优先即LLF(LeastLaxityFirst)算法
小组成员:倪建聪、杨贤蹬、阴晓
具体分工:
教案:阴晓
课程讲解:杨贤蹬
学****目标
松弛度的定义
最低松弛度优先即LLF算法的定义
实现条件
特点
实例讲解
不足
松弛度
松弛度就是一种优先级,它反应的是任务的紧急程度。
公式:松弛度=必须完成时间-其本身运行时间-当前时间
例如,此时t=0ms,一个任务在200ms时必须完成,而它本身所需的运行时间就有100ms,因此,调度程序必须在100ms之前调度执行,该任务的松弛度为
200-100-0=100ms
又如,此时t=100ms,一个任务在400ms时必须完成,它本身需要运行150ms,则其松弛度为
400-150-100=150ms
条件
在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列,松弛度最低的任务排在队列最前面,调度程序总是选择就绪队列中的队首任务执行。
特点
①主要用于抢占式调度方式。
②抢占时机:松弛度为零时
③实用于周期性任务的调度。
实例讲解
假如在一个实时系统中,有两个周期性实时任务A和B,任务A要求每20ms执行一次,执行时间为10ms;任务B只要求每50ms执行一次,执行时间为25ms。
A和B任务每次必须完成的时间
t1
t2
t3
t5
t4
t8
t7
t6
0
10
20
30
50
40
60
70
80
时刻
就绪队列
必须完成时间
运行时间
松弛度
t1=0
A1
B1
20
10
10
50
25
25
A1(10)
t2=10
A2
B1
20
25
15
40
10
20
B1(20)
t3=30
A2
B1
40
10
0
50
5
15
A2(10)
t4=40
B1
A3
50
5
5
60
10
10
B1(5)
不足
当多个任务松弛度值接近时,算法造成任务之间的频繁切换或颠簸现象,增大了系统因调度引起的开销,限制了调度算法的实际应用。须寻找合理的任务执行时间片