中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 中科院软件所  > 中科院软件所
题名:
实时调度算法研究
作者: 何军
答辩日期: 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的方法相比,在判断是否可接收硬非周期任务时,它所需的处理时间量会有所增加。
英文摘要: This thesis focuses on a critical issue of real-time systems-real-time task scheduling, and considers the scheduling of hard periodic tasks, soft aperiodic tasks and hard aperiodic tasks. At the beginning of this thesis, Optimal Dual Priority (ODP) algorithm is presented to improve the schedulability of periodic task. ODP algorithm uses the main idea of Dual Priority (DP) method, i.e. allowing a task to increase its priority in a specific phase. But the way to construct phase_2 priorities is different from DP in that ODP continues to consider all the possible phase_2 assignments until it successfully schedules the given task set, allows a task to have two priorities, and the task can increase its priority in certain phases. Experimental results show that, comparing to Rate Monotonic (RM) and DP algorithm, ODP can far improve the schedulability of periodic tasks, while it increases only a small scale of overhead. When the periodic load is 1.0, about 98% of task sets can be scheduled by ODP, while RM and DP can only schedule 70% and 80% of them respectively. when the load is in [0.95, 1.00), the schedulability obtained by ODP is almost 100%, while RM and DP algorithm can only schedule 80% and 88% respectively. The goal of soft aperiodic task scheduling is to minimize the response time of aperiodic tasks without affecting the periodic task to meet their deadlines. Based on ODP algorithm, this thesis presents a new bandwidth preserving algorithm-ODP-based-PE (ODPPE) algorithm. ODPPE can create a larger server than other methods, and thus obtains better aperiodic response time performance. Experimental results show that, when the total system load is above 0.9, the new method offers great improvement over other bandwidth algorithms, and it is comparable with them when the total load is less than 0.9. Another algorithm given in this thesis aims at using the slack time of periodic tasks to service soft aperiodic tasks. The fixed priority scheme limits the processor utilization, therefore limits the slack time of periodic tasks. Deadline Driven (DD) scheme is a dynamic priority algorithm that is used to schedule periodic tasks, its potential utilization is 100%. The new algorithm-ODD algorithm given in this thesis applies the DD scheme to periodic ask scheduling as it needs, and shortens the response time of aperiodic tasks. Simulation results illustrate that the new method provides performance better than any other existing algorithms, and its average aperiodic response time is almost ideal. There is one thing that should be pointed out: although the algorithms that steal slack time from periodic tasks to service aperiodic tasks can provide better performance than bandwidth preserving algorithms, the former is more complex and results in more context switching overhead than the later. This thesis also studies hard aperiodic task scheduling under fixed priority environments and presents its own algorithm. The new algorithm is developed from the slack stealing algorithm introduced by Ramos-Thuel and Lehoczky. The main disadvantage of Ramos-Thuel's method is its high memory consumption. The method given in this thesis curtails the memory consumption greatly. In particular, in order not to bring about too much computation overhead, the thesis presents a new method to determine the latest finish time of a periodic task. Both theoretical analysis and simulation results all prove that the new method needs much less calculation than the Ramos-Thuel's method. When a hard aperiodic task arrives, it must be checked to determine whether it can be accepted or not. This thesis discusses the acceptation condition in various cases. Comparing to Ramos-Thuel's method, the method presented here needs a little more time when deciding whether to accept a hard aperiodic task or not.
语种: 中文
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/7020
Appears in Collections:中科院软件所

Files in This Item:
File Name/ File Size Content Type Version Access License
N98831.pdf(2403KB)----限制开放-- 联系获取全文

Recommended Citation:
何军. 实时调度算法研究[D]. 中国科学院软件研究所. 中国科学院软件研究所. 1997-01-01.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[何军]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[何军]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace