QQ客服 官方微博 反馈留言

题名	实时调度算法研究
作者	何军
学位类别	博士
答辩日期	1997
授予单位	中国科学院软件研究所
授予地点	中国科学院软件研究所
关键词	实时系统 实时调度 周期任务 非周期任务 速率单调算法 最后期限驱动算法 带宽保留算法 可延缓时间
学位专业	计算机软件
中文摘要	随着计算机科学的发展，实时计算机系统的应用范围日益扩大。实时环境中常常要考虑实时任务调度、实时任务同步、实时通信、容错等许多问题，本文研究了其中的一个重要问题－实时任务调度。实时任务通常包括周期任务和非周期任务两种类型，其中后者又有软非周期任务和硬非周期之分。文中首先提出了用于提高周期任务可调度性的最优双优先级（ODP）算法。ODP算法沿用了双优先级（DP）法的主要思想，即允许任务有两个优先级，任务在某个阶段内可提高为第二优先级，但它构造第二优先级的方法与DP法不同：ODP将考虑各种第二优先级赋值，直到任务集可调度为止。仿真实验结果证明，与传统的速率单调（RM）算法和DP算法相比，ODP算法大大提高了周期任务集的可调度性。在周期任务负载为1.0的情况下，约有98%的任务集可用ODP算法调度，而RM和DP算法的可调度率仅约为70%和80%；当负载在[0.95, 1.00）之间时，ODP算法的可调度率几乎为100%，而RM和DP算法的可调度仅约为80%和88%。另外，ODP算法增加的额外开销也不算高，与RM算法相比，当周期任务负载为1时，ODP增加的额外开销约为22个百分点，当负载在[0.95, 1.00）之间时，额外开销只增加了约19个百分点。实时环境中常常既包含周期任务，又包含非周期任务，混合任务调度问题是实时系统中的一个重要问题。由于非周期任务中的软非周期任务和硬非周期任务在响应时间上的要求不同，所以两者在调度方法上也存在着较大的差异。软非周期任务调度算法的目标是在不影响周期任务满足最后期限要求的同时，使非周期任务的平均响应时间京可能短。本文以ODP算法为基础提出了一种新的带宽保留算法－基于ODP的PE（ODPPE）算法。ODPPE算法可获得较大的服务器，因此可获得较好的非周期任务响应性能。实验证明，这种新方法在系统总负载超过0.9时，可大大提高平均非周期响应性能，在总负载小于0.9的情况下，它与其它带宽保留算法也是可比的，而且这种性能上的提高不以增加文境切换（context switch）开销为代价，甚至在一些情况下，ODPPE算法的文境切换开销低于其它所有带宽保留算法。本文还讨论了服务器优先级对平均响应的时间的影响，并指出在某些情况下，低优先级服务器有可能带来较好的响应时间。除ODPPE外，本文还提出了另一种利用周期任务的可延缓时间为软非周期任务服务的调度算法。由于固定优先级策略限制了处理机利用率，因此也限制了周期任务的可“挪用”时间。最后期限驱动（DD）算法是一种调度周期任务的动态优先级算法，它可使潜在的处理机利用率达到1.0，本文提出的新算法－ODD算法正是在周期任务的调度中适当引入了DD策略，从而使软非周期任务的响应时间得以缩短。仿真实验的结果表明，这种算法的性能优于已有的所有算法，它的平均非周期响应时间几乎接近理想。与OFP算法相比，它所带来的额外开销并不算高。需要指出的是，从周期任务挪用时间的算法另外可使非周期响应性能好于带宽保留算法，但这类算法的杂度高于后者，文境切换开销相对后者也较高。本文最后研究了基于固定优先级策略的硬非周期任务调度，并提出了自己的算法。此算法是由Ramos-Thuel和Lehoczky提出的算法发展而来的，它利用周期任务的可延缓时间执行硬非周期任务。Ramos-Thuel算法的主要缺点是内存开销较大，本文提出的方法则大大减少了内存需要量。特别是，为了使计算量不至于太大，本文提出了一种新的确定周期任务作业最晚结束时间的方法。理论分析和仿真实验的结果都证明了这种新方法的计算量远远小于Ramos-Thuel的方法。与软非周期任务调度不同，硬非周期任务的目标不是使响应时间尽可能短，而是满足非周期任务的最后期限。当非周期任务到达时，需要对其做接收检测，只有通过了接收测试、最后期限可得到保证的周期任务才应得到处理。本文讨论了各种情况下硬非周期任务的接收条件，包括以最高优先给接收硬非周期任务，以任意优先级接收非周期任务，以及非周期任务重叠的情况。与Ramos-Thuel的方法相比，在判断是否可接收硬非周期任务时，它所需的处理时间量会有所增加。
语种	中文
公开日期	2011-03-17
页码	103
内容类型	学位论文
源URL	[http://ir.iscas.ac.cn/handle/311060/7020]
专题	软件研究所_中科院软件所_中科院软件所
推荐引用方式 GB/T 7714	何军. 实时调度算法研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 1997.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。