基于 Linux 的实时系统_MySql_学习笔记★闵涛★计算机学习电脑编程软硬件技巧


	转至繁体中文版	\| 网站首页 \| 图文教程 \| 资源下载 \| 站长博客 \| 图片素材 \| 武汉seo \| 武汉网站优化 \|

基于 Linux 的实时系统

作者：闵涛文章来源：闵涛的学习笔记点击数：1743 更新时间：2009/4/22 20:45:30

作者 : 张焕强 (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所示）。