第二章 实时系统的相关研究
尽管现在的操作系统变得种类繁多，但是UNIX及其兼容的系统仍然是工业和学术领域标准的操作系统。一些非UNIX系统，比如Windows NT，也是与POSIX.1003标准兼容，这个标准无疑是基于UNIX。这个系统的成功是由于它的开放性、稳定性和事实的标准。随着POSIX1003.1b实时扩展标准的发布，UNIX有机会成为分布最广泛的实时处理平台。Linux作为一个类UNIX的系统，凭借其开放源码的优势，获得越来越广泛的应用。
由于以上的原因，在这一章我将集中讨论与Linux相关的实时系统。我将讨论在Linux上进行实时运算的问题，和在一些系统中如何解决这些问题。
2.1 LINUX的分时特性
UNIX最初是作为一个分时系统设计的[17]。LINUX作为UNIX的克隆，很多当前的实现中仍然保留了这些特点。它们力争最优的平均性能。这个目标通常与实时系统的低延迟和高可预言的要求相勃的。为了说明这个问题，让我们考虑一个通过扬声器发声的程序（程序2.1）。
#define DELAY 10000
main()
{
int i;
while (1) {
for (i=0;i
speaker_on();
for (i=0;i
speaker_off();
}
}
程序2.1 简单的发声程序
扬声器的驱动程序假定为只有两种状态on或off。初看起来这个程序可以按给定的周期输出方波，使扬声器正常的发声。然而，当运行一个标准的LINUX程序时，它将不能正确的发声。
我在一个有412MHz Celeron处理器的Linux操作系统上运行这个程序。当在系统没有别的程序在运行时，扬声器发出稳定的声音。每一个滴答声都可以听到。当有按键动作或者移动鼠标时，都会引起声音的断续。在执行磁盘操作或高运算量的程序时，声音将变得严重失真。最后，起动一个大的程序，比如X-Windows，扬声器将持续大约半秒的时间不能发声。假如这个程序是控制步进电机的，而不是使扬声器发声，那么程序将不能使电机稳定地运行。
Linux的设计和实现的原理大体上与UNIX是相同的[12]。它们都是采用分时的调度，低的计时分辨率，非占先式内核，关中断和虚拟内存。我们在细节上来考虑这些问题。
调度程序是内建在操作系统内部的一组策略和机制，它决定哪一项工作将由计算机来完成[4]。
大部分的UNIX操作系统，尤其是Linux操作系统，它们的调度程序追求的是平均响应时间、吞吐量和在进程之间的公平的CPU时间分配[16]。每个进程的优先级是动态的基于进程已经花费的CPU时间，输入/输出强度和别的一些因素来决定。
Linux系统使用固定的时间片(time slices)来调度CPU时间。最开始进程赋予一个高的优先级。如果在某个进程的时间片内，这个进程放弃CPU，它的优先级将不会变，或者变的更高。另一方面，如果一个进程使用完它的时间片，它的优先级将会变低。这种策略关心的是交互式程序，比如说编辑器，由于这类程序更多的把时间花费在等待I/O输入输出的完成。虽然对在终端前的用户来说是有利的。由于程序的执行完全依赖于复杂的、不可预知的系统负荷与别的进程的活动，这种调度方式对于实时进程而言完全没有用。
Linux中加进了POSIX实时扩展部分，引进了实时进程的概念，允许一个进程定义为一个实时进程。Linux区分实时进程和普通进程，采用不同的调度策略。即先来先服务调度(SCHED_FIFO)和时间片轮转调度(SCHED_RR)。在SCHED_RR调度中，任务一旦时间片用完就被移动到优先级队列的队尾，并允许同一优先级的其它任务运行。如果同一优先级没有其它任务，该任务继续运行下一个时间片。SCHED_FIFO是运行直至阻塞的策略。SCHED_FIFO任务按优先级调度，一旦开始就一直运行到结束或阻塞在某种资源上。不像SCHED_RR任务那样共享处理器。
另外还有计时器的精度问题。以前提供给用户进程警报信号和sleep()系统调用只有1秒的精度，如此粗糙的计时精度是不适合大多数的实时进程。当前的版本提供了更高精度的时间间隔，然而，内在的时钟实现限制了计时的正确性。这方面的内容在后面将由更详细的论述。
大部分的Linux的核心进程是不能中断的[10]。换句话说，一旦一个进程进入到核心模式，它将运行到系统调用的完成或者被阻塞为止。假如在这期间有一个更高优先级的实时进程准备好运行了，它将不得不等待。由于不需要考虑内核重入的问题，这种设计的方式使内核的开发更为简单。然而，一个系统调用可能花费很长时间来完成，对于一个实时进程来说长的延迟是不能接受的。
于非占先式内核相关的问题是系统的同步。为了保护数据可能被非同步的操作，比方说中断处理函数，系统设计者通常在临界区代码中选择关中断的方式来处理。比起信号量(semaphores)或者自旋锁(spinlocks)这是更为简单有效的技术。但是，禁止中断是系统能力与系统对外部事件的快速响应的一个折中。这种方法还是不能解决多处理器系统的同步化问题。
Linux系统使用了虚拟内存用于分页[10]。虚拟内存技术只是保护程序在运行部分在RAM中，可以使运行的程序超过系统RAM的容量。这种方式在分时系统中将很好的运行。然而，对于实时系统来说，虚拟内存引起的系统不可确定性达到一个无法忍受的地步。
所有考虑的这些因素来看，显然传统的Linux是不可能用于实时处理。我们需要一些根本的改变。
2.2 Linux性能测试
为了对Linux的性能有一个直观的了解，我对Linux系统进行了测试。测试的内容包括中断延迟时间和上下文切换。对测试的结果进行分析，以寻找提高Linux延时间性能的途径。
2.2.1 中断延迟测试
中断可以分为两种不同类型：同步和非同步中断。对应用程序来说，重要的是非同步中断。非同步中断发生的情况如图2.1所示。中断响应时间是中断发生到中断处理程序开始执行之间的时间差。这个时间差包括直到在运行任务停止和中断分派时间。
图2.1 异步中断和中断响应时间
中断响应时间并不是一个常量。它与操作系统和硬件平台有关。要测量精确的关闭中断的时间，并不是通过上面的定义来进行。因为从中断到来到当前任务停止属于中断延迟时间。在Linux中，内核或驱动程序显式地关/开中断，一般是通过调用__cli()/__sti()来进行操作。中断延迟程序计算一对__cli()/__sti()调用之间的时间。在调用__cli()时，记录系统时间值，读出__sti()被调用时的系统时间值。他们之间的时间差就是关中断时间。Linux下的关中断时间如图2.2所示：
关中断时间测试程序重新写了__cli()/__sti()宏，以允许记录调用它们的文件以及在何处调用。记录这些信息以分析在Linux中那些关中断时间是比较长。（中断测试程序的代码在附录A）
我对Linux进行了大约3个小时的测试，测试的结果如表。在测试中运行一些程序，其中包括一个磁盘循环拷贝程序，打开一些应用程序。可以发现系统负载比较重时，系统的页面调度花了比较多的时间，将近500微秒。表2.1表2.2是统计结果。
图2.2 关中断时间
表2.1 中断关闭时间直方图
表2.2 中断关闭时间概率密度函数直方图
可以看出在我的测试系统中系统中断关闭时间最大达到496微秒，一般中断关闭时间是在250微秒到300微秒左右。这次测试并没有进行所有情况下的测试，从这些结果我们就可以看出： Linux的系统设计人员采用分时的调度、低的计时分辨率、非占先式内核、关中断和虚拟内存是造成系统关中断时间过于长的原因。
2.2.2 上下文切换测试
上下文切换时间是保存一个进程状态，然后恢复另外一个进程状态的时间。我写了一个测试程序来测试这个时间（程序见附录B）。程序运行时，根据输入的参数来决定创建多少个进程。所有的进程用一个环形的UNIX管道连接。程序中实现一个令牌在这些进程之间传递，迫使进行进程间的上下文切换。程序记录在进程间传递令牌2000次所花的时间。每一次令牌的传递有两个开销：上下文切换开销和令牌传递开销。程序首先计算令牌在环形管道中传递的开销，在输出的结果已经除去了这部分开销。
为了计算更真实的切换时间，我加入了人为的数据在里面，进程切换时间包括保存用户级数据状态的时间。测试的结果在表2.3所示，Y轴表示切换时间，X轴表示进程数目，size表示进程的大小。
从结果看，进程的随着进程的大小变化，切换时间在增加，在16k以内增加幅度不大，是因为此时进程的大小还没有超出一级缓存的大小，超过16k时，增加幅度比较大，进程大小达到64k时，切换时间达到300微秒。Linux切换时间过于大的原因是系统保存了过于多的状态。在上下文切换过程中，系统是关中断的，意味着此时的系统关中断时间超过300微秒。对于实时应用来所是不能接受的。
表2.3 上下文切换时间
