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. Qlinux
Qlinux是由AT&T、德州大学分布式多媒体计算实验室和马萨诸塞大学高级系统软件实验室联合开发出来的一种软实时(soft real-time)核心[QLinuxWeb]。它能够为实时多媒体应用提供QoS支持。
QLinux实现了近年来操作系统领域内一些最新的研究成果，包括：
- H-SFQ资源调度算法（Hierarchical Start-time Fair Queuing）[Goyal96]；
- 网络包的延迟处理技术（Lazy Receiver Processing:LRP）[Druschel96]；
- Cello磁盘调度算法[Shenoy98]；
图 3 QLinux系统结构
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磁盘调度
[1] [2] [3] [4] 下一页
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年从剑桥毕业以后，该项目就再没有人维护。跟QLinux一样，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是否很大（这是为了屏蔽一些普通调度流程中对于抢占式调度来说是冗余的那些操作），然后执行抢占式调度。
上一页 [1] [2] [3] [4] 下一页
抢占式内核补丁也修改了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所定义的一个通用的实时调度框架；QLinux所采用的分层式的CPU调度框架，及新颖的调度算法如H-SFQ，以及Cello磁盘调度算法等；SILK所使用的将对一个包的网络处理抽象成PATH，然后在PATH之间进行调度。
对于内核中协议处理以及中断处理的调度，解决办法基本上是一种延迟处理的技术，即到来的协议包在网卡中断处理中仅仅将它拷贝到一个队列中，只有当上层的应用程序请求数据包时才进行协议处理，并将对协议的处理时间记到对应的进程中。另外SILK对于那些网络路由结点，由于路由等的处理并没有对应的上层应用程序，所以SILK在内核的网络处理之间进行明确的调度。
上一页 [1] [2] [3] [4] 下一页
所以，总的来说，从发展方向上来说，实时Linux的发展有如下四个思路：
提供对于硬实时的支持，具体办法有：提高时钟精度，解决封中断和内核态不能被抢占的问题，代表系统RT-Linux、Kurt-Linux，其实大部分实时 Linux都使用了类似与RT-Linux的提高时钟精度和软件中断管理器的思想；总的来说，让内核支持硬实时和使用传统的Linux的丰富的系统调用之间存在着矛盾，以至于像RT-Linux就是单独实现了一个独立的小的硬实时操作系统；但由于软件模拟终端控制器、提高时钟精度、以及可抢占内核等思想的引入，这个矛盾慢慢地得到化解。
提供对于实时多媒体应用的支持，举措：引入新颖的调度算法（网络包调度，进程调度，磁盘调度），代表系统：QLinux、Linux-SRT；
引入新颖的调度框架以及资源管理思想以更好地支持网络系统中的QoS要求，比如SILK中的垂直结构的操作系统调度的思想，QLinux中的分级调度的思想，以及RED-Linux所提出来的一个通用的调度框架和Linux/RK中所使用的资源预留的思想；
方便的任务QoS管理接口函数和管理程序的实现，比如Linux/RK提出的操作系统中各种资源的资源预留的概念；Linux-SRT中为了用户方便地使用新增加的实时调度支持而增加了API，以及提出的reserve的概念等；
在实际的系统中，具体使用那种实时Linux技术，需要根据具体的系统需求而定。如果目标系统是像机床控制或者导弹飞行姿态控制这样的硬实时系统，那基于 RT-Linux是一个不错的方案；如果一个系统对于实时性的要求不是那么严格，但又不是软实时系统，那么可以借鉴Kurt-Linux的想想以及一些为了提高Linux响应速度而提出的可抢占内核的想法；如果目标系统是一个像实时多媒体系统这样的软实时应用，或者一个希望能够在高负载状态下提供更好的吞吐率的服务器系统，那么QLinux和RED-Linux的思想提供了很好的参考；如果是将Linux应用于像路由器这样的网络结点中，可以借鉴SILK 的实现思想。
（出处：http://www.sheup.com）
（出处：http://www.sheup.com/）