万方数据实时操作系统中的时间车轮算法①Wheelthat．This引言2软件计时器功能模型顾清山亮(辽宁工程技术大学电信学院辽宁葫芦岛1limitation，it0年第1计算机系统应用摘要：关键词：杨顺张05)操作系统中时间车轮算法被广泛应用，不过其最大调度时间有限，分层时间车轮算法也存在着算法复杂的不足，在二者基础上提出了对时间车轮的改进方法。该算法不但消除了时间车轮计时时限的缺点，而且比分层时间车轮在算法上简单很多，很适用于程序存储空间紧张的嵌入式实时系统。操作系统；最大调度；计时器；时问车轮；分层时间车轮TimeAlgorithmReal-TimeOperatingSystemQing-Shah，YANG05，China)1嵌入式系统是当今最热门的领域之一，在其系统中，系统任务和用户任务经常需要进行调度和执行相应的任务，实时操作系统中经常需要使用时间轮换调度算法调度同优先级的就绪任务，内核中的任务调度器也必须周期地在相等优先级任务中执行实现设定好的上下文切换，以保证执行的公平性。在嵌入式网络设备中，各种通信协议调度数据进行重新传输和恢复协议的活动，实时操作系统中系统任务的延时、同步和通信等，都需要一个快速准确的计时器11】。实时操作系统一般都提供了时间管理对象完成系统的计时任务。一个软件计时器的工作模型分为两部分，一部分是系统时钟中断服务处理，一部分是在系统初始化时创建的计时器处理任务，并称其为工作者任务(workertask)o工作者任务于系统计时器中断服务连接起来组成了系统计时服务的功能模型。软件计时器的工作模型软件计时器的工作模型如图1所示。在系统进入9卷第2期25in(CollegeInformationtime①收稿时间：2009—06—02图1㈨一眦一一啪一懈一一㈨一眦201GUShun，ZHANGLiangofandElectronicEngineering，LiaoningTechnical．University，Huludao25Abstract：Intheoperatingsystem，thewheelalgorithmiswidelyapplied．Butitsbiggestdispatchlimited．Thelaminationalsohascomplexinsufficiency．Thisarticleproposeswheel’Scorrectivemethodbaseddoesonlyeliminateeasierthanalgorithm．Itsuitableforprocedurestoragespaceembeddedrealsystem．Keywords：operatingsystem；biggestdispatch；timer；timewheel；lamination准备j岛物系统讨时器定时函数．捌豫任务拈起Development研究开发53notstratatense丁作肯任务所{ftick渊用cickcot=0的uckfnt=0_【厦Researchonscorecm一万方数据54研究开发Re跚ch3时间车轮原理4分层时间车轮原理双自链表项卜_叫双自链表项l叫双自链表项Ih上，要想定时2分3秒500毫秒需要把计时器放到4计算机系统应用0年第1时钟中断服务程序后，系统首先更新系统ticks，记录系统从开始运行到现在的滴答数。然后查询等待某一时间的任务是否等待超时(如任务调用task—sleep是否超时，系统等待某一内核对象是否超时等)。然后激活工作者任务，工作者任务进入就绪状态，工作者任务在处理所有系统计时对象完毕后会马上挂起自身等待下一次时钟中断激活该任务。在中断服务的结尾系统会调用时间轮换调度算法，对与被中断任务同优先级的任务实施分时调度。软计时器应当允许有效的计时器的插入、删除、取消、以及更改。所以一般都用双向链表来链接系统中所有的计时器。由于计时器没有按特定的次序排列，系统维护计时器的所花费的时间是很昂贵的。每个系统滴答工作者任务都需要遍历整个链表并更改每个计时器的倒计数项。如果计时器计数值达到O时还需要调用它的回调函数。典型的解决方案是使用时间车轮方法。嗣槽l图2时间车轮框图时间车轮是固定长度数组的结构，其中每个数组项代表一个时间单元【2】，我们称之为时间槽【3】。时间单元代表软件计时器的精度。每次系统滴答时钟拨盘下拨一个时间槽，拨到数组末尾以后折回，每个槽对应一个计时器链表，该链表中所有计时器具有相同的定时时刻。当时间拨盘指针到达该时间槽后，系统将会调用链表中每一个计时器的回调函数。时间车轮通过固定长度的数组和定时移动的时间盘指针，实现了软计时器的快速安装、删除、修改等操作。时间车轮实现模型如图2所示。图2中时间盘指针指向了时间槽1，这是时间槽1对应的计