车载嵌入式操作系统调度算法分析与改进

作者：刘建伟焦风川牛涛齐建德　　章节　　随着现场总线技术、嵌入式微控制技术的发展，现代列车的过程控制已从集中型的必要数字控制系统发展沦为基于网络的分布式控制系统。高速列车以健汪旅客乘车安全性与舒适度为基础，必需对车辆的制动器、减震、车门、供电及空调等设备分别展开掌控、检测和临床；各设备分别由适当的车载微机展开掌控，包含各个子系统；子系统之间通过现场总线网络，构成仅有列车的网络控制系统。

实际情况下，车载微机必须对多点的压力、温度以及许多其他的状态参量展开收集与监测．单一编程更为简单，省辖市用嵌入式实时操作系统来已完成这些任务。任务中有些必须按时间片展开调度，天内已完成各个任务；而现有的源码对外开放的嵌入式实时操作系统一般都是守住式多任务内核，因此必须对现有实时操作系统的任务调度机制展开改建，从而符合车载操作系统的实际市场需求。　　1调度算法分析　　调度算法是所指在受限的处理单元上对具备某些未知特征的任务集继续执行顺序的设计。在嵌入式实时系统中，任务的继续执行要面临两种容许：时间容许和资源容许。

动态任务拒绝系统有较好的响应时间以符合累计时间，在嵌入式系统中只有受限的RAM和CPU等资源，所以调度的优劣在相当大程度上要求了系统的性能。　　1．1RMS调度算法　　RMS算法脚在1973年由C．L.Liu和J．Layland明确提出的。

该算法是基于统计资料任务继续执行频率的一种任务调度方法。RMS算法将最低优先级彰显最低继续执行频率的任务，以单调的顺序对余下的任务分配优先级。

分析中，RMS算法不作了以下假设：　　◇所有任务都是周期性的；　　◇任务间不必须实时，没共亨资源，没任务间数据交换等问题；　　◇CPU必需总是继续执行优先级最低且正处于准备就绪态的任务，即须用可褫夺型内核调度法。　　由于使用守住式的凋度方式，低优先级的任务准备就绪后立刻守住正在运营的较低优先级的任务。

另设系统中有n项有所不同的任务，由于RMS算法拒绝调度的独立国家的周期性任务总能符合其累计时间，即拒绝系统中的所有任务必需符合软动态条件，于是有下列不等式正式成立：　　式中：Uk为任务k最久继续执行时间，Tk是任务k的继续执行周期，Vk／Tk即任务k所需的CPU时间利用率。当系统中的任务数n渐趋无穷大时，S(n)的值为Ln2，即0．693。

于是，若要使所有的任务都符合软动态拒绝，则有：　　亦即所有有时间容许的任务的总CPU时间利用率不应高于70％。只不过，系统设计中，使CPU的时间利用率超过100％并很差。如果那样，程序就没改动的余地了，也无法减少新的功能。

实际情况下，CPU的时间利用率不应在60％～70％以下。RMS算法的优点是灵活性强劲、支出小、可调度件测试非常简单。

但在某些情况下．继续执行频率最低的任务并非最重要的任务。　　1．2EDF调度算法　　守住式EDF调度算法是一种动态优先级驱动的调度算法，其中分配给每个任务的优先级根据它们当前对最后累计时问的拒绝而以定。当前催促的累计时间最近的任务具备最低的优先级，而催促累计时间更远的任务被分配最低优先级。这个算法需要确保在经常出现某个任务的累计时回答无法符合之前，不不存在处理器的空闲时间。

　　C．L．Liu和J．Layland证明了对于一个具备n个任务的子集，累计时间驱动的调度算法的不切实际条件为：　　任务的最久响应时间Tr是有界的，需符合Tr大于累计时间，任务才能被调度。对于Tr能用下式传达：　　式中；Trun_i为任务i的继续执行时间；Tlok_i为任务i的枪机时间；Tspd_i为任务i的调度支出时间；Trdy_j为任务j再度准备就绪的时间；max{Tr/Trdy_j}·Trun_j为低优先级任务i被低优先级任务j褫夺后，低优先级任务闲置的总时间。

　　守住式EDF调度算法仅次于的优势在于，当系统的阻抗比较较低时十分有效地，对于任何等价的任务集，只要处理器的利用率不多达100%，就需要确保它的可调度性。EDF的劣势在于无法解决问题短路问题，当系统阻抗较轻时，有可能引发大量任务错失累计时间，造成CPU的时间大量花费在调度上，这时系统的性能很低。

本文来源：米兰体育-www.cnhjx.com