文档介绍：四川大学
硕士学位论文
分布式实时系统任务调度算法的设计和实现
姓名:余科军
申请学位级别:硕士
专业:计算机软件与理论
指导教师:洪玫
20060429
分布式实时系统任务调度算法的设计和实现计算祝软件与理论研究生:余科攀指导老师:洪玫随着计算机应用范围的胬┐螅植际绞凳毕低秤τ迷嚼丛焦惴骸F渲校对任务调度的问题是分布式实时系统⋯个关键的问题。合理的分布式实时系统豹任务镄菠舞法对发挥系统豹并行髓能、保证实时任务的可溺凄性、以及傈持网络的负载平衡都具有非常重要的意义。论文在分摄了分布式实时系统任务豹缝季句和常见实时任务调度算法的基硝上,着熏研究了多层分布式系统结构下实时任务的调度算法。论文研究的分布式实时系统任务调度算法采用层次式的任务涸度策略,对分布式系统的调度层次分两级:任务分配和任务调度。任务分配处理选择任务在什么结点上执行,分配决策必须在调度执行决策之自龀觥H挝竦鞫仍蛏婕暗浇谕唤岬愕娜务按怎样的方式进行调度执行。任务分配器设置在中心服务器端。中心服务嚣端响应实时任务请求,并按照加权轮转法分配实时任务到各个执行结点,各执行结点按照速率优先调度算法对本遗实时任务进行调度执行。针对分布式实时任务的多机执行的特点,为了满足任务的合理分配及系统的负载平衡,论文研究了将任务分配到结点的调度方法,提出了基于加权轮转的任务分配机制。根据结点处理能力的不同,采用加权队列的方法在处理能力强的结点上分配更多的任务,而对处理能力弱的结点分配较少的任务,这样可以合理分配任务并使任务得到尽快处理,也解决了结点处理能力不同而造成的负载压力的问题。分布式实时系统在同一结点上有多任务执行的特点,并嚣实时任务具有时靼川大学顺宦畚
限要求,调度实时任务要求每个任务的执行都能够在其截止期限内完成。因此,保证实时任务的可调度性是实时系统调度中的关键问题。单调速率劬算法是实时任务调度的基本算法,论文分析了系统采用速率单调调度算法的任务可调度性,并在结点任务调度上使用速率单调调度算法。关键词:分布式实时系统,任务分配,任务调度,加权轮转调度算法速率单调调度算法四川大学颂十学位论文Ⅱ
—·繵四川大学硕士学位论文::..’簍..Ⅲ篐
琣.,.—癛“.,.—甊甌:琓四川大学硕十学位论文’
髀研究背景随着计算机与自动控制技术的发展,现在,实时系统的应用非常广泛,如数字控制、指挥控制、信号处理以及电信系统等,而这些系统每天都在为我们提供重要的服务。当人们开车上路时,实时系统控制汽车的发动机和刹车闸,并控制交通信号灯;当飞机飞行时,实时系统调度并监控飞机的起飞和降落、控制其飞行、维持其航线,并且使其远离危害;当人们高兴时,还可以借助实时系统玩跳子游戏和调动驾驶来娱乐。计算机和网络上也运行实时系统,不过与个人计算机和工作站上运行的一些非实时系统应用绫嗉骱屯玟榔不同,它们通常是在后台运行的。当实时系统正确运行且状态良好时,总使人们忘记它们的存在。实时系统是能及时响应外部发生的随机事件,并以足够快的速度完成对事件的处理的计算机应用系统。所谓外部事件是指与计算机相连接的设备讲设备、控制对象、键盘等岢龅姆褚G螅缡莶杉⑶楸ḿ焖鳌⒖刂破由此可见,实时系统具有如下特点酝獠渴录南煊Ρ匦朐谝欢ㄊ奔淠谕瓿伞@纾驮鄙舷掳嗯哦哟卡时,计算机须在几秒钟内捕获卡片上的数据,如果在下一张卡片插入时末获取数据,该数据就会丢失。同样,要求的各种输出也必须在一定时间内完成。事实上,数据的获取、处理、已处理数据的输出,都需在特定的时问内完成。这一时间的总和叫做系统的反应时间,其范围一般从几毫秒到几秒,缩短反应时问是设计实时系统的关键。的,有时负荷重,有时负荷轻,甚至有可能大部分时间没有被充分利用,但整个系统必须满足一定的峰值负荷要求。例如,实时雇员考勤系统,早上和晚上上下班时,该系统频繁的工作,从打卡机上捕获和处理数据的能力必须满足雇员上下班记录出勤情况的要求,而该系统在其余大部分时间没有被充分利用。输出等。匦肼阋欢ǖ姆逯蹈汉梢G蟆R桓鍪凳毕低车母汉煽赡苁呛懿痪四川大学碗十学位论文●
胧凳毕低诚喙氐牧硪桓鲋匾N侍馐牵捎谑淙胧萦上低潮旧聿痘瘢因此,该数据只有在系统中才有效,而且只能通过系统来访问。也就是说,在故障发生时,不仅失去由系统执行的功能,而且也会失去有关的数据,使系统不可能恢复工作,因此实时系统可靠性至关重要。实时任务调度算法是实时系统设计和实现的关键。它的好坏,直接影响到系统的吞吐量ノ皇薄喝認内系统可以处理任务的数量⑾低车南煊κ奔洌至是任务能否得以成功调度。由于实时系统的侧重点不同,实时调度亦有多种分类方式。以下是一些常见的实时调度分类—:炊允凳毙阅芤G蟮某潭龋凳比挝窨梢苑治S彩凳和软实时对于硬实时和软实时的定义并不统一,目前比较常用的有郑从任务的结果上