实时调度算法_第1页
实时调度算法_第2页
实时调度算法_第3页
实时调度算法_第4页
实时调度算法_第5页
已阅读5页,还剩18页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

3.4 实时调度算法,实时调度是为了完成实时处理任务而分配计算机处理器的调度方法。实时处理任务要求计算机在用户允许的时限范围内给出计算机的响应信号。实时处理任务可分为 硬实时任务(hard real-time task) 软实时任务(soft real-time task)。 其中,前者要求计算机系统必须在用户给定的时限内完成,后者允许计算机系统在用户给定的时限左右处理完毕。,3.4 实时调度算法, 实现实时调度的基本条件:1提供必要的调度信息,如就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级;2系统处理能力强3调度方式,广泛采用抢占调度方式,特别是在实时要求严格的实时系统;4很快的进程和线程切换速度。,实时调度算法(请同学们看书上P99)(3)对几种调度算法的评述:1 时间片轮转调度算法:这是一种常用于分时系统的调度算法,它只能适用于一般实时信息处理系统,而不能用于实时要求严格的实时控制系统。2 非抢占的优先级调度算法:常用于多道批处理系统的调度算法,也可用于实时要求不太严格的实时控制系统。3 基于时钟中断抢占的优先级调度算法:用于大多数的实时系统中。 4 立即抢占的优先级调度算法:这种算法适用于实时要求比较严格的实时控制系统。,(4) 代表性的实时调度算法:1 时限式调度法(deadline scheduling):是一种以满足用户要求时限为调度原则的算法。有周期性调度和非周期性调度。时限有:处理开始时限(开始截止时间)和处理结束时限(完成截止时间)两种,在实际中可以使用任一种时限。2 频率单调调度(rate monotonic scheduling):是一种被广泛用于多周期性实时处理的调度算法。其基本原理是频率越长(周期越长)的任务优先级越低。,实时调度实例,(EDF算法)在事前能知道各实时任务的开始截止时间,且对调度时延要求不太严格的情况下可以采用最早截止时间优先的非剥夺性调度策略。,1,3,4,2,1,2,3,4,开始截止时间,执行任务,任务到达,t,系统首先调度任务1执行,在任务1执行期间,任务2、3先后到达,由于任务3的截止时间早于任务2的,故系统在任务1后将调度任务3执行。,1,3,4,2,具有完成截止时间的周期性实时任务的调度,例:如果系统中有两个周期性的实时任务A和B,任务A要求每20ms执行一次,执行时间为10ms;任务B要求每50ms执行一次,执行时间为25ms。任务A和B每次的开始截止时间分别为A1、A2、A3和B1、B2、B3见图。为了保证不遗漏任何一次截止时间,应采用最早截止时间优先的剥夺策略。,2. 最低松弛度优先即LLF(Least Laxity First)算法,该算法是根据任务紧急(或松弛)的程度,来确定任务的优先级。任务的紧急程度愈高,为该任务所赋予的优先级就愈高, 以使之优先执行。例如,一个任务在200ms时必须完成,而它本身所需的运行时间就有100ms,因此,调度程序必须在100 ms之前调度执行,该任务的紧急程度(松弛程度)为100 ms。又如,另一任务在400 ms时必须完成,它本身需要运行 150 ms,则其松弛程度为 250 ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列,松弛度最低的任务排在队列最前面,调度程序总是选择就绪队列中的队首任务执行。该算法主要用于可抢占调度方式中。假如在一个实时系统中,有两个周期性实时任务A和B,任务A要求每 20 ms执行一次,执行时间为 10 ms;任务B只要求每50 ms执行一次,执行时间为 25 ms。,图 3-11 A和B任务每次必须完成的时间,在刚开始时(t1=0),A1必须在20ms时完成,而它本身运行又需 10 ms,可算出A1的松弛度为10ms;B1必须在50ms时完成, 而它本身运行就需25 ms,可算出B1的松弛度为25 ms,故调度程序应先调度A1执行。在t2=10 ms时,A2的松弛度可按下式算出: A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms,类似地,可算出B1的松弛度为15ms,故调度程序应选择B2运行。在t3=30 ms时,A2的松弛度已减为0(即40-10-30),而B1的松弛度为15 ms(即50-5-30),于是调度程序应抢占B1的处理机而调度A2运行。在t4=40 ms时,A3的松弛度为10 ms(即60-10-40),而B1的松弛度仅为5 ms(即50-5-40),故又应重新调度B1执行。在t5=45 ms时,B1执行完成,而此时A3的松弛度已减为5 ms(即60-10-45),而B2的松弛度为30 ms(即100-25-45),于是又应调度A3执行。在t6=55ms时,任务A尚未进入第4周期,而任务B已进入第2周期,故再调度B2执行。在t7=70 ms时,A4的松弛度已减至0 ms(即80-10-70),而B2的松弛度为20 ms(即100-10-70),故此时调度又应抢占B2的处理机而调度A4执行。,图 3-12 利用ELLF算法进行调度的情况,什么是多处理机系统 多处理机系统调度策略,3.4 多处理机调度,多处理机系统:是一个具有两个或多个处理机并能相互进行通信以协同一个大的给定问题求解的计算机系统。特点: 1) 有两个或多个处理机2) 共享主存或高速通信网络3) 共享输入输出子系统4) 有单一完整的操作系统5) 各级硬件和软件相互作用,1.什么是多处理机系统,主要功能: 进程分配 更好的利用多机硬件 资源在处理机之间的分配 改善程序的响应时间 处理机的负载平衡 处理机间的协调和同步 因处理机故障引起的系统重组,(1) 多处理机系统与单机调度的区别 多处理机调度与单机调度的主要区别涉及两个资源分配问题: 一是存放程序或数据的存储器分配及如何访问他们的问题。 在多机系统中,由于各进程在物理上也同时执行而不是单机系统那样的交叉执行,这些在物理上同时执行的进程可能同时访问物理存储器的同一地址。处理机对同一存储块的访问必须是顺序的。各进程同时访问物理存储器上的同一地址是不允许的。,多处理机系统调度策略,二是将等待执行的就绪进程分配到哪一个处理机上执行的问题。 在单机系统中,由于只有一个处理机,在调度程序中选取了某个就绪状态的进程之后,不须再选择处理机。而在多机系统中,为了尽量做到让各处理机负荷平衡,可能会将处理机在进程之间进行多次切换。如果被切换进程正在执行其临界区部分或系统中进程数目相当多,这种频繁的上下文转换将会使系统效率大大下降。,为了解决进程对处理机的分配问题,在有的多处理机系统中采用了局部就绪队列的方法限制进程的转移。 局部就绪队列:就是把处于就绪状态的进程分成不同的组,并使每一组进程和一个处理机对应起来。这样,每个处理机只执行以其对应就绪队列中的进程。各个就绪队列中的进程不断发生横向转移。这种方法减少了调度程序的开销。但是,处理机的使用率却因此下降。例如:系统中某个局部就绪队列中因等待进程较多而使得对应的处理机十分繁忙,而另外的处理机则因就绪对列为空而处于空闲状态。,多处理机系统的调度目标是:以最高的可靠性,使用最少的处理机在最短的时间内完成最多的可以并行完成的进程。,多处理机的调度有两种评价模型: 一种是确定性模型,另一种是随机性模性。 确定性模型:进程调度执性之前,估计出这些被调度进程所须要的执行时间,以及这些进程之间的相互关系。 调度程序的目的:是根据给定的执行时间和相互关系,确定出一个最佳的执行顺序。 因此,确定性模型只用来确定给定进程的执行顺序,而随机性模性则常被用来研究动态调度技术。,(2)多处理机的调度评价,一个四道作业的操作系统中,设在一段时间内先后到达6个作业,它们的提交时间和运行时间见表,作业号 提交时间 运行时间,JOB1JOB2JOB3JOB4JOB5JOB6,8:008:208:258:308:358:40,60352025 510,系统采用短作业优先的调度算法,作业被调度进入运行后不再退出,但当一作业进入运行时,可以调整运行的优先次序(抢占)。1 按照所选择的调度算法,请分别给出上述6个作业的执行时间次序2 计算在上述调度算法下作业的平均周转时间,练习:,一个具有两道作业的批处理系统,作业调度采用短作业优先的调度算法,进程调度采用以优先数为基础的抢占式调度算法,如下表的作业序列(表中所有作业优先数即为进程优先数,数值越小优先级越高)。1 列出所有作业进入内存时间及结束时间2 计算平均周转时间,作业的执行时间,作业名 到达时间 估计运算时间 优先数,A 10:00 40分 5B 10:20 30分 3C 10:30 50分 4D 10:50 20分 6,*作业

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论