周期性实时任务LLF调度算法改进.pdf

《周期性实时任务LLF调度算法改进.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、周期性实时任务LLF调度算法改进陈自刚．等周期性实时任务LLF调度算法改进mprOvementOfLLFScheduIingAIgorithmfOrPeriodicReaI—timeTaskf9宝白种1朱洛华2(南阳理工学院计算机与信息工程学院1，河南南阳4730014；南阳师范学院计算机与信息技术学院2，河南南阳473061)摘要：为减少松弛度计算和系统调度次数，对周期性实时任务的最低松弛度优先(uF)调度算法进行了改进。在系统处理过程中引入最低松弛度优先队列，当任务松弛度相同时，开始截止时刻早的任务靠

2、近队首。在任务控制块(1℃B)中引入预执行时间，任务被调度以后，如果没有更为紧迫的任务到达，任务执行到预执行时间结束才退出处理器。Matlab仿真试验表明，改进算法有效减少了周期性实时任务的松弛度计算次数和系统调度次数，提高了处理器的利用率。关键词：工作周期调度算法最低松弛度优先队列单处理器实时系统中图分类号：1鸭16+．2文献标志码：AAbstnIct：Inordertoreducethetimsoflax崎caIcllladonaIldsyslem∞hed“Ilg，tllelⅢtl“iIy6BI(LL

3、F)∞hed“Ilga190rithmforpeiodic眦I一Ⅱmet∞k8iBimpmved．TheUJqueueisinm山啪din协tIIe8ystemproce8singpIocedures；whenthelaxityofta8k8i8equal。thetaskwitlI恤eadie8td朗dlineiscI雠协山e呻ofthequeue．m-execu血nti眦iBinⅡoduccdinIo乜skc曲咖lbkk(TcB)，幽rtIletaBki8北hedIIled-ifthe陀ig肿Ⅲo咒ul

4、gentt粕k．1lleexecu面ntaskwitl_如wsh伽tllepmces∞rattheend0ftIlepre-既ecu60n6me．M甜ab8im咖ont嗍8howt壬I址tIIeimprovememofal印dtlIme伍ecbvelyreducestlIetim∞of嫡tycalcu挑onofpeIiodic陀al撕Ⅲet耶ksand吐坶Iim略0f8ygtemschedllling。柚dem删帖eBtIleubh髓籼0fthepr∞e8∞r．Key啪r凼：DuIyperiodicSch

5、edul心al俨刷fIlIlk枷l碰tyfi呲qIle讹Unipl佻e880rReal—d眦8y毗em0引言随着计算机技术的发展，计算机技术的应用日益广泛，实时调度被广泛地应用于实时性强的众多领域，如敏捷制造、电子商务、地铁调度、铁路调度、交通管制、航空航天、自适应容错和机器人等，这些领域都要求计算机在允许的时限范围内给出响应。最低松弛度优先调度算法(1e鹳tIa】【时fir8t，uJF)是一种高效的周期性任务实时调度算法。为完成实时处理任务而合理分配处理器，从而提高处理器的利用率。本文对最低松弛度优先调

6、度算法进行深入分析，并提出改进方案。1系统处理能力和抢占式调度机制1．1系统处理能力虽然计算机技术得到了迅速发展，但任何一个计算机系统的资源都是有限的，其处理能力也必然有限。江西省科技斤支撑计划基金费助项目(编号：2∞9ZDG04100)；河南省科技攻关计划基金资助项目(嫡号：102102210434)；河南省教育厅自然科学基础研究计划基空费助项目(嫡号：2009c520004、20IOc520006、20lOB520020)。修改稿收到日期：20lI—12一07。第一作者陈白刚(1978一)．男，200

7、8年毕业于华中科技大学计算机技术专业．获硕士学位。讲师；主要从事多媒体技术、嵌入式系统应用与开发方面的研究。《自动化仪表》第33卷第7期加12年7月如果处理器的处理能力不够强大。处理器就有可能因为忙不过来，导致某些周期性的实时任务得不到及时处理，从而造成难以预料的后果。假定系统中有m个周期性的实时任务，各任务的系统服务时间为c。，其周期为P。(其中l≤f≤m)，在单处理器情况下，所有周期性实时任务均能正常运行，即系统能够按照某种调度次序正常推进，必须满足下面的限制条件⋯：。C∑吾≤l(1)‘2】r。假设系

8、统中有m个周期性的实时任务，各任务的系统服务时间为c。，其周期为只(其中1≤i≤，，1)，在多处理器情况下，当处理器数量为』v时，所有周期性实时任务均能正常运行，即系统能够按照某种调度次序正常推进，必须满足下面的限制条件：mC善尹≤Ⅳ(2)‘I1．2抢占式调度机制在实时系统中，当一个优先级更高的任务到达时，允许将当前任务暂时挂起，而高优先级任务抢占处理器资源执行，这样才能体现出该实时任务的高优先级特征，这被称为高优先级抢占调度