linux嵌入式实时调度原理

1、仅供个人参考不得用于商业用途实时调度资料摘自 清华大学自动化系ARM 培训教材实时系统逐渐成为人们研究的热点。而其中的操作系统或者更确切的说，操作系统中 的调度部分是实时系统的重中之重。小到实验室设备，大到航空航天，实时系统得到了广 泛的应用。For pers onal use only in study and research; not for commercial use那么什么是实时系统呢？人们一般认为，实时的特征有两点，那就是系统不仅需要给 出合乎逻辑的计算结果， 而且其处理时间还需要满足一定的要求， 比如说不能超过某个截 For pers onal use only in stud

2、y andresearch; not for commercial use止时间等等。我们可以把实时系统分为两类，一类是硬实时(Hard Real-Time);另外一类则是软实时(Soft Real-Time)。所谓硬实时是指如果系统对某个实时任务的处理未能在某个截止时间开始或者结束的话，最终的结果将是灾难性的，这就意味着即便是处理结果合 乎逻辑但是仍然毫无意义；而在软实时系统中，处理任务启动或者结束的截止时间只是一 个期望值，并不见得必须满足；即便是处理时间超过了截止时间，也是有意义的。另外我们还可以按照处理任务的特点将实时系统划分为周期性(Periodic)和非周期性(Aperiodic

3、)两种。一个非周期性的任务启动或者结束有一个截止时间必须要满足；而周 期性任务则是指处理任务需要在某个时间周期里面完成处理。Z 实时操作系统特点实时操作系统与普通操作系统的区别主要表现在五个方面，这就是其任务处理的确定性、 响应灵敏度、用户参与控制、可靠性以及故障保护措施上。实时操作系统应当能够做到这一点：实时任务处理的开始时间和结束时间应当是确定 的、可预测的、这在实时处理上显得非常重要。从这方面来讲，在实时操作系统中，系统 的吞吐量和确定的任务处理相比，要次要的多，实时操作系统的任务处理具备一定的确定 性。衡量系统的确定性有一个比较好的指标，就是系统从接到要求处理的中断和对应的处 理任务启

4、动这两个事件发生的时间间隔。一般操作系统这个时间参数很大，而且可能会有 几个数量级的变动。而在实时操作系统中，它应当很小，并且比较稳定，有一个上限值。和系统的确定性相关联的是系统的响应灵敏度，它可以定义为系统响应请求的时间。 它所关心的是，系统在确认任务请求之后，需要花费多长时间来处理完相关的计算任务。 不难看出，系统的确定性和系统仅供个人参考不得用于商业用途的响应灵敏度共同构成了系统对外界时间的反应时间。用户参与控制是实时操作系统不同于一般操作系统的又一重要特点。在一般操作系统 中，用户所能做的至多只能是希望系统如何如何，而最后系统完成的如何，那就看系统自 己的了。而实时操作系统就不同了：当

5、用户发出控制指令后，系统应严格按照指令办事， 并且用户可以实现对系统尽可能多的控制，甚至于到系统的调度算法上。实时操作系统为了完成一些对处理时间敏感的计算任务，必须要强调可靠性。对于一 般的系统而言，某个运行错误可能导致的系统重启或者处理能力下降等问题对系统本身影 响并不大。而在实时系统中，这样的错误可能是灾难性的。计算机系统在运行过程中，难免会出现某些运行故障。由于这些突发故障可能会带来 灾难性后果，我们就更关心一旦故障发生之后，应该怎么办的问题。一般实时系统都有比 较完备的故障保护措施， 用于在系统发生运行故障之后， 尽可能多地保护系统的运行结果， 从而为系统的再恢复打下基础。另外，有些系

6、统会有冗余设计，从而降低系统运行的故障 率。z 实时调度( Real-Time Scheduling)在考察实时调度算法时，我们可以从三个角度对各种各样的调度算法进行分类：首先 看系统是否做调度分析；如果有的话，然后就看是静态分析还是动态分析；最后看这个分 析结果是否直接影响到进程的实时分派。据此，我们可以将各种实时调度算法大体上分为 四类，即 ST 类、SPP 类、DP 类、DBE 类。静态表驱动调度ST (Static Table-driven)类调度算法就是根据相关信息做出一个切实可行的实时调度 计划表，并在系统实时运行时严格按照这个表来调度进程。这类方法比较适合周期性任务。 调度分析所

7、需要的信息包括周期性到达时间、执行时间、周期性结束截止时间以及各个任 务的优先级等。 调度算法希望能够制定出一个进程调度计划表来满足所有周期任务的要求。这个方法是确定性的，可以预测实际运行效果，但是却不灵活。并且如果某个任务的特征 有所改变的话，就需要整个调度计划表重新编制。静态优先级驱动调度SPP( Static Priority-driven Preemptive )类调度算法也是需要做出一个静态调度计划表 来，但是这么一个表只是在赋予各个任务优先级的时候提供参考，在系统实际运行时，按 赋予任务的优先级来进行抢占式调度。这类调度算法的典型代表就是后面要讲到的RMS调度算法。动态规划调度在

8、DP( Dynamic Planning-based )类调度算法中，一个实际有效的调度计划不是在系 统运行之前制定的，而是在运行中动态规划的；一个新的计算任务只有当它提出的要求能 够被满足时才会被系统接受并处理，调度算法将决定何时会分派该任务。动态最优调度DBE (Dynamic Best Effort )类调度算法中，不需要做任何调度分析，系统竭力去满足 所有计算任务所提出的要求，并且会毫不留情地将不可能满足要求的进程丢弃掉，即便这 样的进程已经被启动了。这类算法是很多商业化实时操作系统所广泛应用的，比较容易实现。但是有一个缺点，就是对任务的截止时间等参数无法预知，这样就会在一些没法满足

9、条件的任务身上花费不必要的处理器时间。z 时限调度( Deadline Scheduling)目前大多数的实时操作系统都有一个相同的设计目标，那就是获得尽可能快的中断处 理和任务分派速度。事实上，这对实时操作系统的性能并不见得有益。实时仅供个人参考不得用于商业用途操作系统更关 心的是能否在规定的时间完成处理任务，而不会受系统负荷变化的干扰。 近些年来有一些很好的实时调度算法出现，只是这些算法需要提供关于任务本身的更 多的信息，这其中包括：(1)任务准备运行时的时间；(2)任务开始处理的时间上限；(3)任务完成处理的时间上限；(4)任务处理所耗费的时间；(5)资源需求；(6)任务的优先级；(7)

10、一个计算任务最好能够分成两个子任务：一个是迫切需要尽快处理的部分，这部 分一般有一个硬性的时限规定；一个是有更多选择余地的部分。进行实时调度时，如果考虑各种时间上限的话，我们就需要认真回答几个问题，比如 说，下一个供调度的任务是谁？我们选择何种抢占方式？对于第一个问题的回答，我们给出一个不仅是在单处理器系统而且在多处理器系统中 都成立的一个结论，这就是，下一个供调度的任务其时间上限与调度时刻离得越近，最终 未能满足时间上限要求的任务所占的比例就越少。另一个问题是关于抢占方式的选择。如果我们强调的是任务开始处理的时间上限，那 么一个非抢占式的调度方法就很有效。在这种情况下，获得处理器控制权的任务

11、可以在它 处理完自己迫切需要尽快处理掉的部分之后进入阻塞状态，从而使得其它任务得以尽快启 动。z RMS 调度( Rate Monotonic Scheduling)RMS 调度算法前面已经提过， 它采用静态调度法赋予各个任务在实时运行时所需要的 优先级，各个任务在实际运行依照这个优先级来实现运行时调度。而优先级的指定是以任 务的周期时间为基础的。显而易见， RMS 方法是面向周期性处理任务的。图 2.11 给出了周期性任务的相关参数。一个周期性任务的任务周期是指这样一个任务 相邻两次重复处理的开始时间的间隔；对应的处理频度(赫兹)则是这个周期的倒数(周 期单位取秒) 。其中处理时间是指周期性

12、任务的实际处理所占用的时间。第个循坏周期第二个循环周期处理屮宪闲处理中字闲处理屮赴理时何4- -任群周期图 2U 周期性任务时间鑫数图 2.11.周期性任务时间参数在 RMS 调度算法中，任务的优先级的高低与其任务周期的长短成反比，也就是说， 一个任务的任务周期越短，它的优先级就越高。按照优先级的规定，如果有多个任务等待 处理，那么总是任务周期最短的那个先开始处理。仅供个人参考不得用于商业用途一个判别周期性调度算法是否有效的判据就是看是否所有的硬性截止时间要求都被满 足了。假设有 n 个周期性任务，每一个都有一个固定的周期和一个固定的执行时间。如果 要使这个判据可能成立的前提就是下面这个不等式

13、必须成立：其中，k C 是第 k 个任务的处理时间，k T 是第 k 个任务的任务周期， n k , , 2 , 1 L =。也就是说如果一个周期性调度算法能够满足所有的硬性截止时间的要求，那么所有任务对处理器的利用率的总和应该不会超过1 这个上限，而对于一个具体的算法而言，这个上限会更低一些。比如说，对于 RMS，就有下面这个不等式成立：三+1 +乞0航2宀-)1iJ1不等式中各个变量和下标的意义与上同。Linux 的调度机制谈到 Linux 的调度机制，我们一般指的是Linux 普通版本的调度机制。事实上，由于Linux 的开放源码，更多的调度机制得以方便的引入，并与Linux 的一般调度

14、机制和谐共存，这里值得一提的就是在Linux 上实现了实时调度机制的RT-Linux 的双内核机制。我们首先阐述 Linux 的一般调度机制，而后对RT-Linux 的实时调度机制给予详细阐述。z Linux 的一般调度机制Linux 属于典型的多用户多任务操作系统。 它采用分时技术， 进程交替执行， 实现所 谓的“假并行” 。它主要有三种调度算法， 一个是基于优先级的循环执行法， 二是 FIFO 算 法，三是传统的基于优先级的循环执行法。前两种调度算法都是软实时的，而第三种则并 非实时的。Linux 进程的优先级是动态变化的。调度程序周期性地检查进程的工作状态并对其优 先级进行修改。这样，

15、一个长时间没有取得处理器控制权的进程将会被赋予较高的优先级， 而对一个长时间占用处理器时间的则赋给较低的优先级，从而让各进程在计算资源的占用 方面获得平衡。Linux 进程分为实时和普通两种。由于 Linux 同时对这两种进程进行调度。为了保证 实时进程总是先于普通进程执行，实时进程总是赋给更高的优先级。普通进程的优先级赋 值是 0-999 ，而实时进程则至少是 1000。需要特别指明的是 Linux 核心是非抢占式的， 只能实现软实时，普通的 Linux 内核是 不适合硬实时应用。z RT-Linux为了保持原有 Linux 的强大功能，这其中包括，网络连接、用户界面等，同时又能够 满足硬实

16、时应用的要求，新墨西哥州立大学的 FSM 实验室提出了用虚拟机( Virtual Machine )技术改造 Linux 内核的思想。具体做法是，运行一个简单的实时调度模块，将 Linux 内核作为这个模块控制下的一个任务，而其它仅供个人参考不得用于商业用途用户级别的实时任务具有比 Linux 内 核更高的优先级。实时调度模块的调度算法是基于优先级的抢占式调度方法，速度快，系 统在满足硬实时应用方面有很好的效果。1) RT-Linux 的双内核架构在 RT-Linux 中，Linux 内核作为一个任务运行在一个小的实时内核之上的(图 2.12)。事实上，对这个实时内核而言， Linux 只是在

17、没有实时任务运行的前提下才获得处理器控 制权的。 Linux任务不能阻塞中断，对自己的运行与否没有决定权。所有这些实现的核心 技术就是在 RT-Linux 中实现了一个硬件控制设备的软件模拟器，即采用了所谓的虚拟机技术。当 Linux 发出中断禁止请求时，实时就会截获这个请求，记录下来，并假装对这个请 求做出回应，而实际上 Linux 禁止硬件中断的请求是不被实际硬件理会的。 不管 Linux 的 内部状态如何，它都要为实时任务的处理让路。当一个中断信号到来的时候，实时内核会 截获这个中断，并作相应的处理：如果有一个与该中断对应的实时中断处理例程的话，该 例程即被激活；如果该例程希望这个中断能

18、和 Linux 内核共享，或者根本就没有这样一个 实时处理例程的话，中断就会被挂起。当 Linux 请求该中断时，一个对应的软件模拟的中 断信号就会送给 Linux 内核，同时，相应的硬件中断重新使能。仅供个人参考不得用于商业用途RT-Linux图2.12. RT-Linux的双内核架构从这里实现的虚拟机技术我们可看出，不管Linux 的工作状态如何，不管它是否对实际硬件中断设备发出了禁止或者使能请求，这些都不会影响 RT-Linux 实时内核对中断控制设备的控制。原因只有一个，因为，Linux 只是和一个由实时内核虚拟出来的硬件中断设备打交道。而真正和这些硬件设备打交道的只是RT-Linux 的实时内核。2) RT-Linux 的实时调度算法RT-Linux 的设计是高度模块化的。实时调度算法的实现也不例外。系统提供缺省的实 时调度模块，比如说实时FIFO 调度算法。如果这个算法不能满足具体要求，我们可以很方便地将它替换成满足要求的调度模块。现在，RT-Linux 有两个可供选择的实时调度算法：一个是 EDF 算法，即最早达到截止时间的实时进程最早运行；另外一个就是RMS 算法。仅供个人用于学习、研究；不得用于商业用途For personal use only in study and research; not for commercial u