越来越多的开发者在基于 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),下面对这三种调度算法逐一进行介绍。
由于 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 的调度程序由两部分组成,其中 Schedule Allocator 初始化到来的job中的属性值;Schedule Dispatcher 根据job的属性值选择一个 job 进行执行;
3.4. Linux /RK
Linux /RK 由卡内基梅隆大学实时和多媒体系统实验室所开发 [RKWeb][ Oikawa98]。它是该实验室资源内核(Resource Kernel)[Rajkumar98] 思想在 Linux 系统中的具体实现。他们最先在 RT-MACH 中实现了资源内核的思想,后来又用资源内核的思想对 Linux 进行了修改。资源内核的概念是网络中资源预留思想在操作系统领域的扩展,应用程序先向操作系统请求预留资源,而操作系统内核在给应用进行资源预留,并能给应用提供有及时的、保证的资源访问。
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 实现了近年来操作系统领域内一些最新的研究成果,包括: