作者 : 张焕强 (zhq@iscas.ac.cn )
中科院软件研究所多媒体通信和网络工程研究中央
越
来越多的研发者在基于 Linux 系统构造嵌入式实时应用，他们迫切地需要一份基于 Linux
系统构造嵌入式实时系统的指南性的文章。考虑到这种需求，本文在介绍了几种基本的实时进程调度算法的基础上，研究了普通的 Linux
操作系统的进程调度，并十分全面地调查了各种实时 Linux 系统为了支持实时特性对普通 Linux 系统所做的改进。文章分析了将 Linux
操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时 Linux
是如何解决这些问题的，最后对于如何将这些已有的研究成果应用和实际的研究和研发工作中作了很好的建议。
第一部分： 实时调度算法介绍
对
于什么是实时系统，POSIX 1003.b 作了这样的定义：指系统能够在限定的响应时间内提供所需水平的服务。而一个由 Donald
Gillies
提出的更加为大家接受的定义是：一个实时系统是指计算的正确性不但取决于程式的逻辑正确性，也取决于结果产生的时间，假如系统的时间约束条件得不到满足，
将会发生系统出错。
实时系统根据其对于实时性需要的不同，能够分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下
的服务时间，即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的任何有实时特性的系统
都能够称之为软实时系统。假如明确地来说，软实时系统就是那些从统计的角度来说，一个任务（在下面的论述中，我们将对任务和进程不作区分）能够得到有确保
的处理时间，到达系统的事件也能够在截止期限到来之前得到处理，但违反截止期限并不会带来致命的错误，像实时多媒体系统就是一种软实时系统。
一
个电脑系统为了提供对于实时性的支持，他的操作系统必须对于 CPU
和其他资源进行有效的调度和管理。在多任务实时系统中，资源的调度和管理更加复杂。本文下面将先从分类的角度对各种实时任务调度算法进行讨论，然后研究普
通的 Linux 操作系统的进程调度连同各种实时 Linux 系统为了支持实时特性对普通 Linux 系统所做的改进。最后分析了将 Linux
操作系统应用于实时领域中时所出现的一些问题，并总结了各种实时 Linux 是如何解决这些问题的。
1. 实时 CPU 调度算法分类
各
种实时操作系统的实时调度算法能够分为如下三种类别 [Wang99][Gopalan01]：基于优先级的调度算法（Priority-driven
scheduling-PD）、基于 CPU 使用比例的共享式的调度算法（Share-driven
scheduling-SD）、连同基于时间的进程调度算法（Time-driven
scheduling-TD），下面对这三种调度算法逐一进行介绍。
1.1. 基于优先级的调度算法
基于优先级的调度算法给每个进程分配一个优先级，在每次进程调度时，调度器总是调度那个具备最高优先级的任务来执行。根据不同的优先级分配方法，基于优先级的调度算法能够分为如下两种类型 [Krishna01][Wang99]：
静态优先级调度算法：
这
种调度算法给那些系统中得到运行的任何进程都静态地分配一个优先级。静态优先级的分配能够根据应用的属性来进行，比如任务的周期，用户优先级，或其他的
预先确定的策略。RM（Rate-Monotonic）调度算法是一种典型的静态优先级调度算法，他根据任务的执行周期的长短来决定调度优先级，那些具备
小的执行周期的任务具备较高的优先级。
动态优先级调度算法：
这种调度算法根据任务的资源需求来动态地分配任务
的优先级，其目的就是在资源分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法，比如短作业优先的调度算法。在实时调度算法中，EDF
算法是使用最多的一种动态优先级调度算法，该算法给就绪队列中的各个任务根据他们的截止期限（Deadline）来分配优先级，具备最近的截止期限的任务
具备最高的优先级。
1.2. 基于比例共享调度算法
虽然基于优先级的调度算法简单而有效，但这种调度算法提供的是一种硬实时的调度，在很多情况下并不适合使用这种调度算法：比如象实时多媒体会议系统这样的软实时应用。对于这种软实时应用，使用一种比例共享式的资源调度算法（SD 算法）更为适合。
比例共享调度算法指基于 CPU 使用比例的共享式的调度算法，其基本思想就是按照一定的权重（比例）对一组需要调度的任务进行调度，让他们的执行时间和他们的权重完全成正比。
我们能够通过两种方法来实现比例共享调度算法 [Nieh01]：第一种方法是调节各个就绪进程出现在调度队列队首的频率，并调度队首的进程执行；第二种做法就是逐次调度就绪队列中的各个进程投入运行，但根据分配的权重调节分配个每个进程的运行时间片。
比例共享调度算法能够分为以下几个类别：轮转法、公平共享、公平队列、彩票调度法（Lottery）等。
比
例共享调度算法的一个问题就是他没有定义任何优先级的概念；任何的任务都根据他们申请的比例共享 CPU
资源，当系统处于过载状态时，任何的任务的执行都会按比例地变慢。所以为了确保系统中实时进程能够获得一定的 CPU
处理时间，一般采用一种动态调节进程权重的方法。
1.3. 基于时间的进程调度算法
对于那些具备稳定、已知输
入的简单系统，能够使用时间驱动（Time-driven:TD）的调度算法，他能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定
下来的离线的静态调度方法。在系统的设计阶段，在明确系统中任何的处理情况下，对于各个任务的开始、转换、连同结束时间等就事先做出明确的安排和设计。这
种调度算法适合于那些很小的嵌入式系统、自控系统、传感器等应用环境。
文章整理：西部数码--专业提供域名注册、虚拟主机服务
http://www.west263.com
以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!
