RM和EDF算法原论文翻译.docx
《RM和EDF算法原论文翻译.docx》由会员分享,可在线阅读,更多相关《RM和EDF算法原论文翻译.docx(20页珍藏版)》请在咨信网上搜索。
1、RM和EDF算法原论文翻译 作者: 日期:2 RM和EDF硬实时环境下多线程的调度算法摘要:单处理器的多线程调度问题的研究范围已经从它本身的特征拓展到程序运行的可靠性。研究表明最佳固定优先级调度在大型任务序列集的情况下的最大调度利用率仅为70%。此外,根据当前任务序列截止期动态分配优先级可以使调度率利用率等于1。本文还讨论了将两种调度方法结合起来的算法。1 引言近年来,运用计算机来控制和监测工业生产过程已得到广泛应用和不断扩展,并且在未来很可能得到更大的拓展。此类应用的多数情况下,计算机由一定数目的时限监控程序和一批非时限任务流所共用。然而,在其他的应用中,非时限作业不存在且计算机的有效利用只
2、能通过谨慎调度时限监测程序来达到。后者被称为“纯过程控制”且为本文呈现的组合调度分析提供了理论背景。本文研究了此类程序设计中的两种调度算法,这两种均为可抢断优先级驱动算法,这意味着正在处理的任务可被任何高优先级任务中断。第一个算法用一个固定优先级分配能使处理器利用率到达约70%甚至更大。第二个算法通过动态分配优先级可以达到处理器的全利用。此外,本文还讨论了两个算法的结合。2 背景一个程序控制计算机执行一个或更多的监控程序。追踪航天器运行轨迹的天线尖端就是此类监控程序的一个例子。每个程序与一系列任务序列集相联且共同被执行。此类任务中的一些任务是为了响应计算机监控的设备所发生的事件。这些任务不能先
3、于事件执行。每个任务都必须在事件按要求释放后的固定时间内执行完毕。在此时间段内的服务都需确保稳定性。将运行环境分类为“硬实时”1是为了在可接受的响应时间统计分布上与“软实时”相对应。多数现有多程序设计文献是针对商业分时系统的统计数据分析(文献2包含了详细的参考书目)。也有文献针对更有意思的方面,比如调度批量处理设备或是混合批量分时设备,这些调度通常是在如文献3-8中多处理器配置环境下。仅有少数论文直接讨论如何攻克“硬实时”程序设计的难关。Manacher1提出了硬实时环境下的任务的调度的算法,但它的结果受到一个不现实情况的限制,比如对所有任务只有一个请求时间,即便将多截止时间考虑在内。Lamp
4、son9概括性的讨论了软件调度问题并且提出了一套ALGOL多程序设计步骤,这些步骤可以通过软件执行或是设计成用于特殊目的的调度器。对于资源的配置、优先级分配及时序,他提出了一个计算估计的响应时间的程序,此程序是基于针对需要可靠性保证的程序所提供的时间信息。然而,它并没有描述这个程序所必须使用的算法。Martin10的文章描述了“实时”系统的范围且有条理的讨论了编程过程中遇到的难题。Martin提出在实时软件研发期间必须保持严格的工程管理控制,他的这一论述得到了Jarauch11的自动结账软件系统论文的强烈回应。这些研讨旨在强调软件设计中运用更为系统的方法的重要性。3 环境为了得到硬实时环境下程
5、序运行的分析结果,必须对运行环境作出一些假设。并不是所有的这些假设都是绝对必要的,在后面的章节中会讨论放宽假设条件后的影响。(A1) 存在硬截止期的所有任务的请求是周期性的,且请求可被经常的中断。(A2) 截止期仅由运行能力的限制组成,也就是说,每个任务必须在下一个请求发生前完成。(A3) 请求中的任务是互相独立的,某个任务不依赖于这个请求中其他任务是否初始化或已经完成。(A4) 每个任务的运行时间不变且不随时间变化。运行时间是指处理器无中断地执行任务所需要的时间。(A5) 系统中的所有非周期任务都是特殊的,它们是初始和故障恢复程序,它们可以在自身运行时取代周期性任务,并且没有硬、关键截止期。
6、假设(A1)与Martin12形成对比,但显得对纯过程控制更加有效。假设(A2)消除了单个任务的排队问题。对于假设(A2)而言,每个外设功能必须拥有少量但可能至关重要的缓冲硬件。任何计算机内部结束的控制跳转都必须允许至少一个单元的采样延迟。注意到假设(A3)并不排除任务的出现只能遵循任务的出现次数,此数为固定的,即为。这种情况可以通过选择任务和的周期来建模,以便使的周期是的倍,并且次请求会与1次请求一致等等。假设(A4)的运行时间作为最大任务处理时间且可以被中断。通过这种方法,请求继承者所需的时间和抢占代价也能被考虑在内。因为有大容量的主存,而且主存和辅助存储设备之间的数据传输相互重叠,程序在
7、现代计算机系统环境下运行,因此假设(A4)是一个很好的近似,即使它并不确切。这些假设使得一个任务的完成特征有以下两个指标:它的请求周期和它的运行时间。除非另有说明,在本文中我们用来表示个周期任务,且它们的请求周期是,运行时间各为。任务的请求速率是其请求时间的倒数。一个调度算法是一套决定在特定时刻所执行的任务的规则。本文研究的调度算法是优先级驱动的可抢断算法。也就是说,任何时刻,具有最高优先级别的任务总是最先得到执行。如果当前有其他的较低优先级任务正在执行,则该较低优先级任务被抢占,让位给具有最高优先级的任务执行,直至就需队列中没有高于该任务优先级的任务时,该任务恢复执行。如此一来,此算法等价于
8、分配任务优先级的方法。若分配给任务的优先级是不变的,我们称之为“静态”调度算法。静态调度算法又称“固定”优先级调度算法。若分配给任务的优先级可能随请求的不同而不同,我们称之为“动态”调度算法。如果某些任务优先级是固定的而其余是变动的,则该算法称为“混合调度算法”。4 固定优先级调度算法图1 在的请求之间执行本节我们得到一个优先级分配规则,该规则源于静态调度算法。决定该规则的一个很重要的方面是一个任务的“关键时刻”。一个任务请求的截止期定义为同一任务的下一次请求的时间间隔。根据一些调度算法,对于任务序列集的调度,若是一个未完成请求的截止时刻,则我们说时刻发生了溢出。对于给定的任务序列集,一个调度
9、算法是可行的当所有任务都能调度完毕且未发生溢出。我们定义任务请求的响应时间为请求发出时刻与响应该请求结束时刻之间的时间段。任务的“关键时刻”是指在该时刻的任务请求有最长的响应时间。任务的“关键时间域”是指关键时刻和响应任务请求结束时刻之间的时间间隔。我们提出如下定理:定理1任务的关键时刻均发生在同时请求它和比其优先级高的任务时。证明 用表示一系列按优先级顺序排列的任务,的优先级最低。若使在时刻对任务发出请求,假定在与之间发出了对任务的再一次请求,而任务的请求发生在时刻,如图1所示。显然,对的抢断会对完成任务造成一定延迟,任务的请求是在时刻发出的,直至任务在时刻之前完成。此外,从图1我们可以直观
10、的看到提前请求时间并不会加速任务的完成。提前请求时间既不会改变也不会延迟任务的完成时间。因此,当与重合时,完成任务的延迟时间最长。对于所有任务,同理可知,故定理得证。图2 两个任务的调度这个结论的价值在于通过简单的计算就可以决定一个给定的任务优先级是否能产生一个可行的调度算法。特别的,如果所有发生在其关键时刻的任务请求都能在它们各自的截止期之前完成,则此调度算法是可行的。例如,任务的请求周期分别为,运行时间为。的优先级高于,从图2(a)中我们可以看出优先级分配是可行的。此外,从图2(b)中可看出的值最大可增至2。另一方面,若使。的优先级高于,如图2(c)所示,则的值都不得超过1。定理1也得到了
11、一个最佳优先级分配算法,我们会在定理2中做阐述。让我们进一步对调度任务的一般结论做扩展。的请求周期分别为,且。若的优先级更高,则根据定理1,必须满足不等式: (1)若得优先级更高,则必须满足不等式: (2)由于:故(1)已包含(2)。也就是说,在的情况下,无论何时,只要的优先级高于,则任务可调度,而当的优先级高于时,任务也能被调度。因此,更一般的来说,优先级分配的一个合理的规则似乎是根据任务的请求速率来分配优先级而不去管它们的运行时间。特别的,任务的请求速率越高,优先级越大。这种优先级分配方法称为“单调速率优先级分配”。结果表明,当不能被RM算法调度的任务序列集同样也不能被其他固定优先级分配规
12、则调度时,RM算法是最优的。定理2 对于一个任务序列集,若存在可行的优先级分配,则对于此任务序列集,RM算法是可行的。证明 为一个包含个任务的序列集,且存在可行的优先级分配算法。和的优先级相邻且的优先级较高。设。交换和的优先级后,不难发现所得到的优先级分配仍是可行的。对于一个已排序的任务序列集,依照上述方法对相邻优先级的一对任务进行重新排序,即可得到RM算法,因此定理2得证。5 可达到的处理器利用率目前,对于固定优先级系统,已有可判定处理器利用率上确界的工具。定义“(处理器)利用率因子”为:执行任务序列集的过程中,处理器耗费时间的间隔。换句话说,利用率因子等价于1减去处理器空余时间的间隔。由于
13、是处理器执行任务的时间间隔,对于个任务,利用率因子为:尽管可通过增大或减小的值来提升处理器利用率,但由于所有任务在其关键时刻必须满足截止期的要求,故利用率的上界受到限制。研究处理器利用率因子的最小值显然是没有乐趣的。若优先级分配是可行的且增大任何任务的运行时间都会使得此优先级分配不可行,则称任务序列集完全利用了处理器。对于一个给定的固定优先级调度算法,利用率因子的上确界为完全利用处理器的任务序列集中利用率因子的最小值。对于所有处理器利用率因子低于这个确界的所有任务,存在一个可行的固定优先级分配算法。另一方面,当且仅当任务的彼此关联适当,才能达到高于这个上确界的利用率。由于RM算法是最优的,对于
14、给定的任务序列集而言,它的利用率因子大于或等于其他优先级分配算法。因此,RM算法利遍及任务所有的请求周期和运行时间的用率因子的下确界即为所要确定的上确界。这个确界起初由两个任务组成,然后扩充为任意数量的任务。定理3 对于固定优先级的两个任务,处理器利用率因子的上确界为。证明 任务和的周期和运行时间分别为和。设。根据RM算法,的优先级高于。在的关键时间域内,有个任务的请求。我们通过调整的值使得在关键时间域内能使处理器得到完全利用。有以下两种情况:情况1 运行时间足够小,使得在的关键时间域内所有的请求都能在下一个请求之前完成。即:因此,的最大值为相应的处理器利用率因子为在此情况下,处理器利用率因子
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- RM EDF 算法 论文 翻译
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。