作者 : 张焕强 (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）的调度算法，它能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定下来的离线的静态调度方法。在系统的设计阶段，在明确系统中所有的处理情况下，对于各个任务的开始、切换、以及结束时间等就事先做出明确的安排和设计。这种调度算法适合于那些很小的嵌入式系统、自控系统、传感器等应用环境。
这种调度算法的优点是任务的执行有很好的可预测性，但最大的缺点是缺乏灵活性，并且会出现有任务需要被执行而 CPU 却保持空闲的情况。
2. 通用 Linux 系统中的 CPU 调度
通用 Linux 系统支持实时和非实时两种进程，实时进程相对于普通进程具有绝对的优先级。对应地，实时进程采用 SCHED_FIFO 或者 SCHED_RR 调度策略，普通的进程采用 SCHED_OTHER 调度策略。
在调度算法的实现上，Linux 中的每个任务有四个与调度相关的参数，它们是 rt_priority、policy、priority（nice）、counter。调度程序根据这四个参数进行进程调度。
在 SCHED_OTHER 调度策略中，调度器总是选择那个 priority+counter 值最大的进程来调度执行。从逻辑上分析，SCHED_OTHER 调度策略存在着调度周期（epoch），在每一个调度周期中，一个进程的 priority 和 counter 值的大小影响了当前时刻应该调度哪一个进程来执行，其中 priority 是一个固定不变的值，在进程创建时就已经确定，它代表了该进程的优先级，也代表这该进程在每一个调度周期中能够得到的时间片的多少；counter是一个动态变化的值，它反映了一个进程在当前的调度周期中还剩下的时间片。在每一个调度周期的开始，priority 的值被赋给 counter，然后每次该进程被调度执行时，counter 值都减少。当 counter 值为零时，该进程用完自己在本调度周期中的时间片，不再参与本调度周期的进程调度。当所有进程的时间片都用完时，一个调度周期结束，然后周而复始。另外可以看出 Linux 系统中的调度周期不是静态的，它是一个动态变化的量，比如处于可运行状态的进程的多少和它们 priority 值都可以影响一个 epoch 的长短。值得注意的一点是，在 2.4 以上的内核中，priority 被 nice 所取代，但二者作用类似。
可见 SCHED_OTHER 调度策略本质上是一种比例共享的调度策略，它的这种设计方法能够保证进程调度时的公平性--一个低优先级的进程在每一个 epoch 中也会得到自己应得的那些CPU执行时间，另外它也提供了不同进程的优先级区分，具有高 priority 值的进程能够获得更多的执行时间。
对于实时进程来说，它们使用的是基于实时优先级 rt_priority 的优先级调度策略，但根据不同的调度策略，同一实时优先级的进程之间的调度方法有所不同：
SCHED_FIFO：不同的进程根据静态优先级进行排队，然后在同一优先级的队列中，谁先准备好运行就先调度谁，并且正在运行的进程不会被终止直到以下情况发生：1.被有更高优先级的进程所强占 CPU；2.自己因为资源请求而阻塞；3.自己主动放弃 CPU（调用 sched_yield）；
SCHED_RR：这种调度策略跟上面的 SCHED_FIFO 一模一样，除了它给每个进程分配一个时间片，时间片到了正在执行的进程就放弃执行；时间片的长度可以通过 sched_rr_get_interval 调用得到；
由于 Linux 系统本身是一个面向桌面的系统，所以将它应用于实时应用中时存在如下的一些问题：
Linux 系统中的调度单位为10ms，所以它不能够提供精确的定时；
当一个进程调用系统调用进入内核态运行时，它是不可被抢占的；
Linux 内核实现中使用了大量的封中断操作会造成中断的丢失；
由于使用虚拟内存技术，当发生页出错时，需要从硬盘中读取交换数据，但硬盘读写由于存储位置的随机性会导致随机的读写时间，这在某些情况下会影响一些实时任务的截止期限；
虽然 Linux 进程调度也支持实时优先级，但缺乏有效的实时任务的调度机制和调度算法；它的网络子系统的协议处理和其它设备的中断处理都没有与它对应的进程的调度关联起来，并且它们自身也没有明确的调度机制；
3. 各种实时 Linux 系统
3.1. RT- Linux 和 RTAI
RT- Linux 是新墨西哥科技大学（New Mexico Institute of Technology）的研究成果[RT Linux Web][Barabanov97]。它的基本思想是，为了在 Linux 系统中提供对于硬实时的支持，它实现了一个微内核的小的实时操作系统（我们也称之为 RT- Linux 的实时子系统），而将普通 Linux 系统作为一个该操作系统中的一个低优先级的任务来运行。另外普通 Linux 系统中的任务可以通过 FIFO 和实时任务进行通信。RT- Linux 的框架如图 1所示：
图 1 RT- Linux 结构
RT- Linux 的关键技术是通过软件来模拟硬件的中断控制器。当 Linux 系统要封锁CPU的中断时时，RT- Linux 中的实时子系统会截取到这个请求，把它记录下来，而实际上并不真正封锁硬件中断，这样就避免了由于封中断所造成的系统在一段时间没有响应的情况，从而提高了实时性。当有硬件中断到来时，RT- Linux 截取该中断，并判断是否有实时子系统中的中断例程来处理还是传递给普通的 Linux 内核进行处理。另外，普通 Linux 系统中的最小定时精度由系统中的实时时钟的频率决定，一般 Linux 系统将该时钟设置为每秒来 100 个时钟中断，所以 Linux 系统中一般的定时精度为 10ms，即时钟周期是 10ms，而 RT- Linux 通过将系统的实时时钟设置为单次触发状态，可以提供十几个微秒级的调度粒度。
RT- Linux 实时子系统中的任务调度可以采用 RM、EDF 等优先级驱动的算法，也可以采用其他调度算法。
RT- Linux 对于那些在重负荷下工作的专有系统来说，确实是一个不错的选择，但他仅仅提供了对于 CPU 资源的调度；并且实时系统和普通 Linux 系统关系不是十分密切，这样的话，开发人员不能充分利用 Linux 系统中已经实现的功能，如协议栈等。所以 RT- Linux 适合与工业控制等实时任务功能简单，并且有硬实时要求的环境中，但如果要应用与多媒体处理中还需要做大量的工作。
意大利的 RTAI ( Real-Time Application Interface ) 源于 RT- Linux ，它在设计思想上和 RT- Linux 完全相同。它当初设计目的是为了解决 RT- Linux 难于在不同 Linux 版本之间难于移植的问题，为此，RTAI 在 Linux 上定义了一个实时硬件抽象层，实时任务通过这个抽象层提供的接口和 Linux 系统进行交互，这样在给 Linux 内核中增加实时支持时可以尽可能少地修改 Linux 的内核源代码。
3.2. Kurt- Linux
Kurt- Linux 由 Kansas 大学开发，它可以提供微秒级的实时精度 [KurtWeb] [Srinivasan]。不同于 RT- Linux 单独实现一个实时内核的做法，Kurt - Linux 是在通用 Linux 系统的基础上实现的，它也是第一个可以使用普通 Linux 系统调用的基于 Linux 的实时系统。
Kurt- Linux 将系统分为三种状态：正常态、实时态和混合态，在正常态时它采用普通的 Linux 的调度策略，在实时态只运行实时任务，在混合态实时和非实时任务都可以执行；实时态可以用于对于实时性要求比较严格的情况。
为了提高 Linux 系统的实时特性，必须提高系统所支持的时钟精度。但如果仅仅简单地提高时钟频率，会引起调度负载的增加，从而严重降低系统的性能。为了解决这个矛盾， Kurt- Linux 采用 UTIME 所使用的提高 Linux 系统中的时钟精度的方法 [UTIMEWeb]：它将时钟芯片设置为单次触发状态（One shot mode），即每次给时钟芯片设置一个超时时间，然后到该超时事件发生时在时钟中断处理程序中再次根据需要给时钟芯片设置一个超时时间。它的基本思想是一个精确的定时意味着我们需要时钟中断在我们需要的一个比较精确的时间发生，但并非一定需要系统时钟频率达到此精度。它利用 CPU 的时钟计数器 TSC (Time Stamp Counter) 来提供精度可达 CPU 主频的时间精度。
对于实时任务的调度，Kurt- Linux 采用基于时间（TD）的静态的实时 CPU 调度算法。实时任务在设计阶段就需要明确地说明它们实时事件要发生的时间。这种调度算法对于那些循环执行的任务能够取得较好的调度效果。
Kurt- Linux 相对于 RT- Linux 的一个优点就是可以使用 Linux 系统自身的系统调用，它本来被设计用于提供对硬实时的支持，但由于它在实现上只是简单的将 Linux 调度器用一个简单的时间驱动的调度器所取代，所以它的实时进程的调度很容易受到其它非实时任务的影响，从而在有的情况下会发生实时任务的截止期限不能满足的情况，所以也被称作严格实时系统（Firm Real-time）。目前基于 Kurt- Linux 的应用有：ARTS（ATM Reference Traffic System）、多媒体播放软件等。另外 Kurt- Linux 所采用的这种方法需要频繁地对时钟芯片进行编程设置。
3.3. RED- Linux
RED- Linux 是加州大学Irvine分校开发的实时 Linux 系统 [REDWeb][ Wang99]，它将对实时调度的支持和 Linux 很好地实现在同一个操作系统内核中。它同时支持三种类型的调度算法，即：Time-Driven、Priority-Dirven、Share-Driven。
为了提高系统的调度粒度，RED- Linux 从RT- Linux 那儿借鉴了软件模拟中断管理器的机制，并且提高了时钟中断频率。当有硬件中断到来时，RED- Linux 的中断模拟程序仅仅是简单地将到来的中断放到一个队列中进行排队，并不执行真正的中断处理程序。
另外为了解决 Linux 进程在内核态不能被抢占的问题， RED- Linux 在 Linux 内核的很多函数中插入了抢占点原语，使得进程在内核态时，也可以在一定程度上被抢占。通过这种方法提高了内核的实时特性。
RED- Linux 的设计目标就是提供一个可以支持各种调度算法的通用的调度框架，该系统给每个任务增加了如下几项属性，并将它们作为进程调度的依据：
Priority：作业的优先级；
Start-Time：作业的开始时间；
Finish-Time：作业的结束时间；
Budget：作业在运行期间所要使用的资源的多少；
通过调整这些属性的取值及调度程序按照什么样的优先顺序来使用这些属性值，几乎可以实现所有的调度算法。这样的话，可以将三种不同的调度算法无缝、统一地结合到了一起。
RED- Linux 调度程序的框架结构如图 2 所示：
图 2 RED- Linux 调度框架
RED- Linux 的调度程序由两部分组成，其中 Schedule Allocator 初始化到来的job中的属性值；Schedule Dispatcher 根据job的属性值选择一个 job 进行执行；
3.4. Linux /RK
Linux /RK 由卡内基梅隆大学实时和多媒体系统实验室所开发 [RKWeb][ Oikawa98]。它是该实验室资源内核（Resource Kernel）[Rajkumar98] 思想在 Linux 系统中的具体实现。他们最先在 RT-MACH 中实现了资源内核的思想，后来又用资源内核的思想对 Linux 进行了修改。资源内核的概念是网络中资源预留思想在操作系统领域的扩展，应用程序先向操作系统请求预留资源，而操作系统内核在给应用进行资源预留，并能给应用提供有及时的、保证的资源访问。
资源内核中有两个基本的概念：资源预留和资源集。一个资源预留代表一份计算资源，这个资源可以是 CPU、内存、磁盘、网络带宽等。在内核中，一个资源预留有对应的描述它的数据结构，而一个资源集指一组资源预留的集合。一般情况下我们将某一个应用程序所请求的所有资源预留组合在一起组成一个资源集，这样方便管理和分配。
Linux /RK 增强了普通 Linux 内核的功能，从而使 Linux 内核可以提供对于系统中各种计算资源的准入控制、资源预留和统计管理。 Linux /RK 由两部分组成：普通的 Linux 内核以及可移植的资源内核；这两个部分之间通过回调钩子函数（Callback hooks）进行交互。类似于 RT- Linux ，为了防止 Linux 内核中的封中操作以及提高调度精度， Linux /RK 也截取系统中的中断，并提高了系统时钟频率，只有在需要的时侯才将中断送给 Linux 内核。另外它使用 Proc 文件系统来显示资源预留和使用的情况；
3.5. Q Linux
Q Linux 是由 AT&T、德州大学分布式多媒体计算实验室和马萨诸塞大学高级系统软件实验室联合开发出来的一种软实时 (soft real-time) 核心[Q Linux Web]。它能够为实时多媒体应用提供 QoS 支持。
Q Linux 实现了近年来操作系统领域内一些最新的研究成果，包括：
- H-SFQ 资源调度算法（Hierarchical Start-time Fair Queuing）[Goyal96]；
- 网络包的延迟处理技术（Lazy Receiver Processing:LRP）[Druschel96]；
- Cello 磁盘调度算法 [Shenoy98]；
图 3 Q Linux 系统结构
H-SFQ 资源调度算法由由德州大学的 Pawan Goyal 等人提出，它采用了一种分级调度的思想，先将资源在不同的应用类别之间进行按比例分配，并在应用类别之间提供对于资源使用的隔离，同时在每一个应用类别中还可以使用不同的资源调度算法。这样做的目的是为了在多媒体系统中提供 QoS 支持。
LRP 技术是一种新颖的设计 OS 网络子系统的思想，它由 Rice 大学计算机系的 Peter Druschel 等人提出，其目的是为了解决普通 Unix 和类 Unix 系统中网络包接收的问题。
传统的 Unix 系统没有对到来的网络包的协议处理的显式调度，它们一般采用中断驱动的机制。当网卡有中断时，CPU 就立刻进行一系列由网卡中断程序启动的包接收和协议处理操作，将最终的数据送给等待接收的进程，并唤醒该进程。但这种处理方式会影响应用程序资源调度的性能，并在系统处于过载状态时可能会引起一些应用层任务的饥饿，降低网络吞吐率，甚至会让系统没有响应。为了解决这些问题，LRP 的核心思想就是每一个 Socket 有一个 IP 包的队列，只有当上层应用程序请求数据时才进行协议处理，同时对协议处理操作以请求数据的应用的优先级进行显式的调度。通过这种途径增强了资源调度的公平性，能够提供一定程度的流量隔离，同时能够提高系统过载状态时的吞吐量。
Cello 磁盘调度算法由德州大学 Prashant J. Shenoy 等人提出。它能够支持多种应用类别，比如：交互式尽力而为应用、大吞吐量尽力而为应用、以及软实时应用等类别，并公平地给各个类别的应用分配磁盘访问带宽。
在结构上 Cello 磁盘调度采用的是一种两级式的调度方式，它由多个与应用类别相关的调度器以及一个与应用类别无关的调度器组成（如图 4所示）。
图 4 Cello 磁盘调度
Cello调度算法中应用类别无关的调度器管理时间上粗粒度的磁盘的调度，而应用相关的调度器控制着小粒度上磁盘调度。如上图中有n个应用类别，Cello使用一个应用无关的调度器C和n个类别相关的调度器 ，系统中有n+1个调度队列。类别无关的调度器C决定你了何时以及多少磁盘请求被从等待队列（pending queue）移到调度队列（scheduled queue）；类别相关的调度器Si对等待队列中的请求进行排序，并根据调度队列的状态来决定磁盘请求被插入到调度队列的什么位置。
3.6. Linux -SRT
Linux -SRT是剑桥大学David Ingram的博士论文项目 [SRTWeb][Ingram00]，基本上是一个实验性的东西，自从 Ingram 在 2000 年从剑桥毕业以后，该项目就再没有人维护。跟 Q Linux 一样， Linux -SRT 属于软实时的 Linux。
在 Linux -SRT 中可以给一个任务分配一定百分比的 CPU 时间，它通过 RM 算法实现了一种基于速率的调度机制来保证给所有多媒体应用的 QoS 需求；另外由于 CPU 并非唯一影响多媒体应用的资源，对于那些做图形显示的应用，X 服务器中的资源调度也十分关键，所以 Linux -SRT 对 XFree86 最了扩展，让 X 服务器可以对来自不同X客户的图形显示请求进行优先级排序；另外为了方便用户管理各个进程的 CPU 分配情况， Linux -SRT 提供了一个图形界面的程序。下面对于 Linux -SRT 对于普通 Linux 所作的修改做一具体说明。
Linux -SRT 也提高了系统的定时精度。但它并没有采用惯用的将时钟芯片置于单次触发模式的做法，而是简单地修改了 Linux 内核中HZ的定义，将 Linux 的时钟频率由每秒 100 次提高到了 1024。
另外 Linux -SRT 在原有的 Linux 系统中的 SCHED_OTHER、SCHED_FIFO、SCHED_RR 这三个调度策略的基础上，给 Linux 增加了一些新的调度策略：SCHED_PAUSE、SCHED_IDLE、SCHED_QOS、SCHED_VAR；策略为 SCHED_PAUSE 的进程在调度时被调度程序忽略，不参与调度执行；使用 SCHED_QOS 调度策略的进程能够得到有保证的 CPU 执行时间；使用 SCHED_IDLE 策略的进程优先级最低，它被分配给那些只在系统空闲时才能够被调度执行的进程，比如一些批处理程序；SCHED_VAR 是一个可变优先级的策略，它被用于解决由于临界资源访问时所产生的优先级倒置问题，即一个高优先级的任务等待低优先级任务占用的某种临界资源，但低优先级任务又得不到CPU处理时间所造成的死锁问题；这时通过该调度策略将低优先级任务的优先级置为等待资源的高优先级任务的优先级（优先级继承）来解决死锁问题。
对于使用 SCHED_QOS 调度策略的实时任务，采用RM静态优先级调度算法进行调度；另外在进行调度时，它还采用了一种双调度策略的方案，即当一个实时任务在当前的调度周期中用完自己所有的时间片之后，在下次调度周期到来之前，并非简单地不调度执行它，而是使用它进程属性中的 Fallback policy 所定义的调度策略来调度它，让它以该策略参与本轮的剩余时间的调度。
Linux -SRT 按照 POSIX 推荐的方式扩展了传统的几个用户设置进程调度属性的系统调度，让用户或者编程人员可以在后向兼容的情况下使用这些新添加的调度特性。另外为了使用的方便，它还提出了 reserve 的概念，一个 reserve 在 /proc 文件系统中有一个结点，它包含有关资源分配的情况；reserve 独立与进程，一个进程可以通过新增加的 reserve 相关的系统调用申请加入（使用）或退出一个 reserve。
3.7. Hard-hat Linux
Hardhat Linux 是 MontaVista 公司所发布的一款主要面向各种嵌入式应用的 Linux 发布 [HardHatWeb][Morgan01]。Hard-hat Linux 最大的贡献在于：为了解决 Linux 在内核态不可被抢占的问题，它开发了一种抢占式（Preemptible）的内核，有人认为它的这种方法充其量也就是一种能够被抢占（Preemptable）的内核。
其基本思想就是让调度程序获得更多的执行机会，从而减少了从一个事件发生到调度程序被执行的时间间隔。可抢占内核的补丁包修改了 spinlock 的宏定义以及中断返回处理代码，当当前进程可以被"安全"地抢占并且有一个等待处理的重新调度请求，系统就会调用调度程序进行进程调度。
那么什么情况下可以认为一个进程可以被 "安全" 地抢占？最早的 Linux 内核代码认为，一旦进入内核态执行，不管是由于陷入（trap）还是中断处理，当前执行进程都不会被切换，直到内核认为可以安全地进行重新调度为止。这种思想可以使得内核代码对一些数据结构进行操作时比较简单，即不需要使用互斥原语（比如旋转锁 spinlock）进行数据的修改保护就可以安全地存取数据。但随着内核源代码的发展，不使用保护机制的内核数据访问代码越来越少，所以在抢占式内核中，认为如果内核不是在一个中断处理程序中，并且不再 spinlock 保护的代码中，就认为可以"安全"地进行进程切换。
抢占式内核对普通 Linux 内核作了如下的一些修改：
抢占式内核给task struct数据结构增加了一个数据项：preempt_count。该数据项由宏 preempt_disable()、preempt_enable()、以及 preempt_enable_no_resched() 所使用。preempt_disable 对 preempt_count 计数进行递增，preempt_enable 对 preempt_count 进行递减。preempt_enable 宏查看当前进程的 preempt_count和need_resched 域的内容，如果 preempt_count 为 0 并且 need_resched 为 1，则调用 preempt_schedule() 函数。该函数将给当前进程的 preempt_count 项增加一个很大的值（比如让 preempt_counter=preempt_counter + 0x4000000），然后调用进程调度函数 schedule()，在schedule函数返回后从该进程 preempt_count 中再减去该值。可抢占内核也修改了 schedule 函数，它检测进程的 preempt_counter 是否很大（这是为了屏蔽一些普通调度流程中对于抢占式调度来说是冗余的那些操作），然后执行抢占式调度。
抢占式内核补丁也修改了 spinlock 的代码。在 spin_lock() 和 spin_try_lock 中增加了对于 preempt_disable 的调用，在 spin_unlock() 中增加了对于 preempt_enable 的调用。
另外抢占式内核补丁还修改了中断返回的代码，在其中增加了对于 preempt_enable 的调用。
所以我们根据上面的三个修改可以看出，内核的抢占式调度发生在如下情况：在释放 spinlock 时，或者当中断返回时，如果当前执行进程的 need_resched 被标记，则进行抢占式调度。
3.8. SILK
SILK 代表 SCOUT In Linux Kernel，它是普林斯顿大学支持 PATH 调度的垂直结构操作系统 SCOUT 在 Linux 中的一个实现[SILKWeb][Bavier01]。它将 SCOUT 操作系统作为 Linux 的一个模块来实现。
SILK 系统的主要目的就是为一些网络 QoS 提供支持，它支持对于网络包处理的显式的调度，并且这个调度是以 PATH 为单位进行的。PATH 概念的新颖之处在于，不像传统的基于任务的调度方式，它从另外一个角度进行系统的资源调度，即以网络的数据流及其处理为单位进行调度。详细来说，一个 PATH 由一串当数据流流经系统时进行数据处理或者数据转换的代码模块组成，并且对应的数据流所消耗的资源也归该 PATH。研究表明，PATH 这种体系结构特别适用于有 QoS 要求的分布式多媒体系统以及软件路由设备中。下图对于什么是 PATH 作了一个图示，它说明了一个 TCP PATH：
图 5 一个TCP PATH
在实现上，SILK 系统将 Linux 系统中的网络子系统替换成了自己的协议栈。 Linux 应用程序通过 Socket 来创建和使用 PATHs，几乎不用对应用程序本身作任何修改。
图 6 说明了 SILK 系统的结构。在图的左半部分，SILK 模块和网络设备驱动、SOCKET 接口层、以及包过滤接口 netfilter 通过标准的方式交换数据。SILK 还修改了 Linux 任务的调度参数，以便影响 Linux 进程调度程序的调度决策。图的右半部分示意了 SILK 中的两个 PATH。SILK 模块有自己的CPU调度器，它和 Linux 系统中的 CPU 调度器进行合作和协调。这个合作由图中的 Linux thread 代表，通过执行这个线程，SILK 将控制转给 Linux 调度程序。
图 6 SILK 系统结构示意图
SILK 在操作系统中提供了一个新的 SOCKET 协议族以便上层应用程序调用下层的 SCOUT PATH。为了在 Linux 进行网络包处理之前截获 IP 包，SILK 通过 Linux 2.4 内核的 netfilter 接口插入了一个 netfilter hook，所有到来的IP包会被重定向到该 hook 上，如果SILK找到一个对应于该网络包的 PATH，就让 Linux 内核丢弃该包，而由 SILK 对包进行处理。
关于 CPU 调度，SILK 有着自己的CPU调度程序和线程包，它们和 Linux 系统的调度程序并存，在有 SILK 的 Linux 系统中，我们一般把由 SILK 调度的归属于某个 PATH 的处理叫做 SILK 线程（thread），而普通的由 Linux 调度程序调度的东西都叫做任务（task）；SILK 在一个 Linux 内核任务的基础上实现它的线程调度，这个内核任务当 SILK 进行初始化的时候创建，并且将该内核任务的优先级设为优先级最高的实时任务，所以 SILK 的内核任务几乎是只要它就绪就可以投入运行，并且只有当该内核任务主动初让 CPU 时 Linux 系统中的其他普通任务才能够得以运行。SILK 将 CPU 出让给普通的 Linux 任务是通过调度 SILK thread 中的一个叫做 Linux thread 的线程来实现的，该 Linux thread 本质上就是在 SILK 的调度空间中代表 Linux 的普通调度程序。SILK 在调用 Linux thread 之后，代表SILK的内核任务就被 Linux 的进程调度程序设置为非就绪状态，直到它运行一个其他的进程之后，高优先级得 SILK 内核任务就又得到 CPU。所以这种实现机制可以让 SILK在调度 Linux thread 时，Linux 调度程序可以有机会调度一个其他的进程执行。
4. 实时 Linux 实现方案的总结
总结上述的各种实时 Linux 的实现，它们针对不同的设计目标，从不同的侧重点解决了通用 Linux 操作系统对实时性支持的问题。
针对 Linux 系统定时粒度过大的问题，一般的解决办法都是将实时时钟编程为单次触发的状态，然后利用 CPU 的时钟计数寄存器提供高达 CPU 时钟频率的定时精度。像 RT- Linux 和 Kurt- Linux 采用的就是这种方法。
对于 Linux 进程在进入内核态时不能被抢占的问题，目前的解决办法有 RED- Linux 在内核函数中插入抢占点的方法，另外 Hardhat 也通过修改 spinlock 的宏定义以及中断返回处理代码，实现了一种可抢占的内核；
对于 Linux 驱动程序中的封中断的方法，RT- Linux 所使用的软件模拟中断控制器的方法可以有效地解决这个问题；
对于 Linux 系统中缺乏实时调度机制和调度算法的问题，目前有很多新颖的操作系统调度框架和调度算法都有 Linux 实现，比如 RED- Linux 所定义的一个通用的实时调度框架；Q Linux 所采用的分层式的 CPU 调度框架，及新颖的调度算法如 H-SFQ，以及 Cello 磁盘调度算法等；SILK 所使用的将对一个包的网络处理抽象成 PATH，然后在 PATH 之间进行调度。
对于内核中协议处理以及中断处理的调度，解决办法基本上是一种延迟处理的技术，即到来的协议包在网卡中断处理中仅仅将它拷贝到一个队列中，只有当上层的应用程序请求数据包时才进行协议处理，并将对协议的处理时间记到对应的进程中。另外SILK对于那些网络路由结点，由于路由等的处理并没有对应的上层应用程序，所以SILK在内核的网络处理之间进行明确的调度。
所以，总的来说，从发展方向上来说，实时 Linux 的发展有如下四个思路：
提供对于硬实时的支持，具体办法有：提高时钟精度，解决封中断和内核态不能被抢占的问题，代表系统 RT- Linux 、Kurt- Linux ，其实大部分实时 Linux 都使用了类似与 RT- Linux 的提高时钟精度和软件中断管理器的思想；总的来说，让内核支持硬实时和使用传统的 Linux 的丰富的系统调用之间存在着矛盾，以至于像 RT- Linux 就是单独实现了一个独立的小的硬实时操作系统；但由于软件模拟终端控制器、提高时钟精度、以及可抢占内核等思想的引入，这个矛盾慢慢地得到化解。
提供对于实时多媒体应用的支持，举措：引入新颖的调度算法（网络包调度，进程调度，磁盘调度），代表系统：Q Linux 、 Linux -SRT；
引入新颖的调度框架以及资源管理思想以更好地支持网络系统中的 QoS 要求，比如SILK中的垂直结构的操作系统调度的思想，Q Linux 中的分级调度的思想，以及 RED- Linux 所提出来的一个通用的调度框架和 Linux /RK 中所使用的资源预留的思想；
方便的任务 QoS 管理接口函数和管理程序的实现，比如 Linux /RK 提出的操作系统中各种资源的资源预留的概念； Linux -SRT 中为了用户方便地使用新增加的实时调度支持而增加了 API，以及提出的 reserve 的概念等；
在实际的系统中，具体使用那种实时 Linux 技术，需要根据具体的系统需求而定。如果目标系统是像机床控制或者导弹飞行姿态控制这样的硬实时系统，那基于 RT- Linux 是一个不错的方案；如果一个系统对于实时性的要求不是那么严格，但又不是软实时系统，那么可以借鉴 Kurt- Linux 的想想以及一些为了提高 Linux 响应速度而提出的可抢占内核的想法；如果目标系统是一个像实时多媒体系统这样的软实时应用，或者一个希望能够在高负载状态下提供更好的吞吐率的服务器系统，那么 Q Linux 和 RED- Linux 的思想提供了很好的参考；如果是将 Linux 应用于像路由器这样的网络结点中，可以借鉴 SILK 的实现思想。
参考文献
[Wang99]
Yu-Chung Wang and Kwei-Jay Lin, Implementing a General Real-Time Scheduling Framework in the RED- Linux Real-Time Kernel, IEEE Real-Time Systems Symposium, 1999
[Gopalan01]
Kartik Gopalan, Real-Time Support in General Purpose Operating Systems, Tech Report, 2001
[Krishna01]
C.M.Krishna, Kang G.Shin, Real-time Systems, Tsinghua Press, 2001
[Nieh01]
Jason Nieh, Chris Vaill, Hua Zhong, Virtual-Time Round-Robin: An O(1) Proportional Share Scheduler, Proceedings of the 2001 USENIX Annual Technical Conference, 2001
[RT Linux Web]
http://www.rt Linux .org/ or http://fsmlabs.com/
[Barabanov97]
Michael Barabanov, A Linux -based Real-Time Operating System, A Master Thesis, New Mexico Institute of Mining and Technology, Socorro, New Mexico, 1997
[KurtWeb]
[Srinivasan]
Balaji Srinivasan, A Firm Real-Time System Implementation using Commercial Off-The-Shelf Hardware and Free Software, Master Thesis, Department of Electrical Engineering and Computer Science, University of Kansas, Feb, 1998
[REDWeb]
http:// Linux .ece.uci.edu/RED- Linux/
[RKWeb]
http://www-2.cs.cmu.edu/~rajkumar/ Linux -rk.html
[Rajkumar98]
Raj Rajkumar, Kanaka Juvva, Anastasio Molano and Shui Oikawa, Resource Kernels: A Resource-Centric Approach to Real-Time Systems, In Proceedings of the SPIE/ACM Conference on Multimedia Computing and Networking January 1998
[Oikawa98]
Shui Oikawa and Raj Rajkumar, Linux /RK: A Portable Resource Kernel in Linux , In IEEE Real-Time Systems Symposium Work-In-Progress, Madrid, December 1998
[Q Linux Web]
http://lass.cs.umass.edu/software/qLinux/
[Goyal96]
P. Goyal and X. Guo and H.M. Vin, A Hierarchical CPU Scheduler for Multimedia Operating Systems, Proceedings of 2nd Symposium on Operating System Design and Implementation (OSDI'96), Seattle, WA, pages 107-122, October 1996.
[Druschel96]
Peter Druschel, Gaurav Banga, Lazy Receiver Processing(LRP): A Network Subsystem Architecture for Server Systems, Proceedings of the 2nd Symposium on Operating System Design and Implementation (OSDI'96), Seattle, WA, Pages 261-275, October 1996
[Shenoy98]
P Shenoy and H M. Vin, Cello: A Disk Scheduling Framework for Next Generation Operating Systems, Proceedings of ACM SIGMETRICS Conference, Madison, WI, pages 44-55, June 1998.
[SRTWeb]
http://www.srcf.ucam.org/~dmi1000/ Linux -srt/
[Ingram00]
David Ingram, Integrated Quality of Service Management, Ph.D. Thesis, Jesus College, University of Cambridge, 2000
[HardHatWeb]
http://www.montavista.com/
[Morgan01]
Kevin Morgan, Preemptible Linux : A Reality Check, MontaVista White Paper, 2001
[SILKWeb]
http://www.cs.princeton.edu/nsg/scout/
[Bavier01]
Andy Bavier, Thiemo Voigt, Mike Wawrzoniak, Larry Peterson, SILK: Scout Paths in the Linux Kernel, Technical Report, Nov 2001
[UTIMEWeb]
作者信息
张焕强，男，中国科学院软件研究所多媒体通信和网络工程研究中心博士，研究兴趣为家庭网络、实时系统、视频会议等。通过 zhq@iscas.ac.cn 可以和他联系。
全文出自 : IBM DeveloperWorks 中国网站
