实时操作系统中的时间车轮算法.pdf

《实时操作系统中的时间车轮算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、万方数据2010年第19卷第2期计算机系统应用摘要：关键词：实时操作系统中的时间车轮算法①顾清山杨顺张亮(辽宁工程技术大学电信学院辽宁葫芦岛125105)操作系统中时间车轮算法被广泛应用，不过其最大调度时间有限，分层时间车轮算法也存在着算法复杂的不足，在二者基础上提出了对时间车轮的改进方法。该算法不但消除了时间车轮计时时限的缺点，而且比分层时间车轮在算法上简单很多，很适用于程序存储空间紧张的嵌入式实时系统。操作系统；最大调度；计时器；时问车轮；分层时间车轮TimeWheelAlgorithminReal-TimeOperatingSystemGUQing-Shah，YANGShun，ZHANG

2、Liang(CollegeofInformationandElectronicEngineering，LiaoningTechnical．University，Huludao125105，China)Abstract：Intheoperatingsystem，thetimewheelalgorithmiswidelyapplied．Butitsbiggestdispatchtimeislimited．Thelaminationtimewheelalgorithmalsohasthealgorithmcomplexinsufficiency．Thisarticleproposesthetimew

3、heel’Scorrectivemethodbasedonthat．Thisalgorithmdoesnotonlyeliminatethetimewheel’Stimelimitation，itisalsoeasierthanscorestratatimewheelalgorithm．Itissuitablefortheprocedurestoragespacetenseembeddedrealtimesystem．Keywords：operatingsystem；biggestdispatch；timer；timewheel；laminationtimewheel1引言嵌入式系统是当今最热

4、门的领域之一，在其系统中，系统任务和用户任务经常需要进行调度和执行相应的任务，实时操作系统中经常需要使用时间轮换调度算法调度同优先级的就绪任务，内核中的任务调度器也必须周期地在相等优先级任务中执行实现设定好的上下文切换，以保证执行的公平性。在嵌入式网络设备中，各种通信协议调度数据进行重新传输和恢复协议的活动，实时操作系统中系统任务的延时、同步和通信等，都需要一个快速准确的计时器11】。实时操作系统一般都提供了时间管理对象完成系统的计时任务。2软件计时器功能模型一个软件计时器的工作模型分为两部分，一部分是系统时钟中断服务处理，一部分是在系统初始化时创建的计时器处理任务，并称其为工作者任务(wor

5、kertask)o工作者任务于系统计时器中断服务连接起来组①收稿时间：2009—06—02成了系统计时服务的功能模型。丁作肯任务准备j岛物系统讨时器所{ftickcm一渊用cickcot=0的定时函数．捌豫uckfnt=0_【厦图1软件计时器的工作模型任务拈起软件计时器的工作模型如图1所示。在系统进入ResearchandDevelopment研究开发53㈨一眦一一啪一懈一一㈨一眦万方数据计算机系统应用2010年第19卷第2期时钟中断服务程序后，系统首先更新系统ticks，记录系统从开始运行到现在的滴答数。然后查询等待某一时间的任务是否等待超时(如任务调用task—sleep是否超时，系统等待

6、某一内核对象是否超时等)。然后激活工作者任务，工作者任务进入就绪状态，工作者任务在处理所有系统计时对象完毕后会马上挂起自身等待下一次时钟中断激活该任务。在中断服务的结尾系统会调用时间轮换调度算法，对与被中断任务同优先级的任务实施分时调度。软计时器应当允许有效的计时器的插入、删除、取消、以及更改。所以一般都用双向链表来链接系统中所有的计时器。由于计时器没有按特定的次序排列，系统维护计时器的所花费的时间是很昂贵的。每个系统滴答工作者任务都需要遍历整个链表并更改每个计时器的倒计数项。如果计时器计数值达到O时还需要调用它的回调函数。典型的解决方案是使用时间车轮方法。3时间车轮原理时对闫槽O计时间隔计时

7、间编嗣槽lH双向链表项H双自链表项卜_时

8、囱J槽2定时回谴函数定时刨调函数埘闻撩j时阕槽4时闫稽5if时间隔计时间隔酵舟槽曲1叫双自链表项l叫双自链表项Ih时阋稽以定时回调函数时向曲．I图2时间车轮框图时间车轮是固定长度数组的结构，其中每个数组项代表一个时间单元【2】，我们称之为时间槽【3】。时间单元代表软件计时器的精度。每次系统滴答时钟拨盘下拨一个时间槽，拨到数组末尾以后折回，每个槽对应一个计时