嵌入式Linux操作系统实时性的分析与研究
宋姜慧
（计算机科学与技术学院，
计算机科学与技术， 04专升本1班，
042230022）
摘要：通过分析嵌入式Linux在实时应用中的不足，从软中断模拟技术、可抢占式内核机制和实时调度策略等方面给出了改善系统实时性能的方法，同时提出了宏观调度结构，拓展了实时系统的应用范围。
关键词：嵌入式系统;
Linux；调度策略；实时性
The Analysis of Real Embedded
Linux Time Capabilities for Operation System
Song Jiang-hui
(computer science and technology
college, computer science and technology, 042230022)
Abstract:
Based on the analysis of the limitation of
Embedded Linux in real time system,the methods to improve the real time
capabilities are proposed.They are soft interrupt control,the kernel
priviledge and the real time scheduling policy.A general scheduling
framework is also proposed to expand it’s application.
Key Words:
Real time Embedded system ; Linux; Scheduling policy
目 录
TOC \o "1-3" \u 1 引言...........................................
PAGEREF _Toc135558958 \h 3
2 Linux在实时方面存在的不足.......................
PAGEREF _Toc135558959 \h 3
3 实时化Linux的实现方案..........................
PAGEREF _Toc135558960 \h 3
4 对Linux内核的内部改造..........................
PAGEREF _Toc135558961 \h 4
4.1
响应时间的分析及解决方法............................................
PAGEREF _Toc135558962 \h 4
4.2
抢占式内核体系结构的设计............................................
PAGEREF _Toc135558963 \h 5
4.3
实时调度的算法研究..................................................
PAGEREF _Toc135558964 \h 6
4.4
经过内部改造后的实时性能测试........................................
PAGEREF _Toc135558965 \h 7
5 对Linux内核的外部实时扩展......................
PAGEREF _Toc135558966 \h 8
5.1
中断处理的修改......................................................
PAGEREF _Toc135558967 \h 8
5.2
实时任务............................................................
PAGEREF _Toc135558968 \h 8
5.3
实时任务调度策略....................................................
PAGEREF _Toc135558969 \h 8
6 Linux实时调度器的实现..........................
PAGEREF _Toc135558970 \h 9
6.1
实时任务的数据结构..................................................
PAGEREF _Toc135558971 \h 9
6.2
实时调度函数与实时调度器...........................................
PAGEREF _Toc135558972 \h 10
6.2.1
实时调度模块的创建.......................................................
PAGEREF _Toc135558973 \h 10
6.2.2
实时任务的建立...........................................................
PAGEREF _Toc135558974 \h 10
6.2.3
实时任务的删除...........................................................
PAGEREF _Toc135558975 \h 10
6.2.4
实时调度函数.............................................................
PAGEREF _Toc135558976 \h 10
6.3
实时程序的编写............................................................................................................
PAGEREF _Toc135558977 \h 11
6.4
经过外部扩展后的实时性能的测试............................................................................
PAGEREF _Toc135558978 \h 11
7 结语..........................................
PAGEREF _Toc135558979 \h 11
参考文献：......................................
PAGEREF _Toc135558980 \h 11
1
引言
Linux本身为分时操作系统，其系统目标为较好的平均响应时间和较高的吞吐量，而实时系统则主要考虑任务的按时完成、尽量减少进程运行的不可预测性等。但与商业嵌入式操作系统相比Linux遵循GPL具有源代码开放，定制方便，支持广泛的计算机硬件等优点，所以近年来嵌入式Linux成为嵌入式系统方向上的一个研究热点。本文首先分析了实时系统的特点和Linux内核在实时应用方面的不足，然后针对影响操作系统实时性能的若干方面进行研究，提出解决方案，最后总结全文。
Linux虽然符合POSIX1003.1b关于实时扩展部分的标准，例如：支持SCHED-FIFO和SCHED-RR实时调度策略，锁内存机制(memory
locking)，实时信号等功能 ，但是由于其最初的设计目标为通用分时操作系统，因此作为一个实时操作系统，Linux仍然存在如下缺陷：
(1)Linux的内核本身是非抢占的。Linux下分用户态和核心态两种模式，当进程运行在用户态时，可被优先级更高的进程抢占，但当它进入核心态时，其他用户态进程优先级再高也不能抢占它。
(2)Linux虽然给实时进程提供了较高的优先级，但是没有加入时间限制。例如：完成的最后期限、应在多长时间内完成、执行周期等等。同时，其他大量的非实时进程也可能对实时进程造成阻塞，无法确保实时进程的响应时间。
(3)时钟粒度粗糙。时钟管理是操作系统的脉搏，任务的执行和中止在很多情况下都是由时钟直接或间接唤起的，它是进程调度的重要依据。Linux的周期模式定时器频率仅为100Hz，远不能精足实时应用的要求。
3
实时化Linux的实现方案
实时化Linux的实现方案可以分为以下两类：(1)对Linux内核的内部改造，即直接修改Linux内核源代码，对它的数据结构、调度函数、中断方式等进行修改使其能处理实时进程。因此这种实时化方法的工作量大，可能会造成系统的稳定性问题，但改造后的系统实时性较好。(2)对Linux内核的外部实时扩展，就是在原有“Linux基础上再设计一个专门用于处理实时进程的内核，即系统有2个内核，普通进程使用原有的内核调度器进行调度，实时进程使用新设计的调度器进行调度，这种双内核系统可以使用实时内核进程获取外部数据，用非实时内核进程处理数据，如以图形方式显示获取的数据。因此这种改造方法有利于系统的稳定，工作量小。该方案的结构如图（1）所示。
图1
Linux实时化方案的详细结构
因此外部实时扩展的方案保留了Linux操作系统所提供的丰富功能，原有的基本内核与实时内核共享CPU，实时内核处理拥有更高优先级别的任务，而基本内核可以看作是实时系统的空闲任务，只是在没有实时处理需求的时候运行。
4
对Linux内核的内部改造
从中断软件模拟、可抢占式内核体系结构、实时任务的调度策略这三个方面对嵌人式Linux内核源代码进行研究并给出了相应的提高实时性的方法。
4.1
响应时间的分析及解决方法
任务的响应时间被定义为一个事件的发生和任务响应这一事件开始执行之间的间隔时间，通常有以下几个因素影响任务的响应时间
J。
(a)中断分配时间IDT(interrupt
dispatch time)：当一个中断产生时，在调用中断处理程序占用CPU以前，操作系统用来保存所有的寄存器中的内容和系统中其他的关于这一任务状态的时间。
(b)中断服务时间IST(interrupt
service time)：中断服务程序用来从硬件设备读取信息或从操作系统收集信息所用的时间。
(c)内核抢占时间KPT(kennel
preemption time)：在操作系统意欲抢占当前进程与抢占实际上发生之间的时间间隔。
(d)调度延迟SD(schedule
delay)：调度程序用来调度另一个线程投入运行的时间。
(e)进程切换时间CST(contest
switching time)：当前线程用束保存寄存器和系统状态的时间与将要运行的线程恢复寄存器中的内容和系统状态的时问总和。
(f)系统调用返回时间RST(return
from system cal1)：处于内核态的线程在它返回用户态之前检查一些状态所用的时间。
以上这些时间中。SD、CST和RST总是固定不变的，如果Linux内核设计得当的话
IDT、IST和KPT可以有效的减少。在实时应用的环境中，若干个中断同时发生的情况是完全可能存在的。这时任务的响应时间最多将包含N（IDT十ISI)，N为中断数。
中断软件模拟被用来解决多个中断同时发生的情形。当一个硬件中断发生时，系统只是简单的在时间表中报告这一时间的发生，然后立即将CPU的控制权返回给操作系统，完全略过查中断向量表并执行相应的中断服务程序。系统在Linux内核之前截获了所有应中断信号，并根据当前实时任务的需要，由软中断模拟机制处理或挂起该中断(例如：IBM
PC中的8259中断控制器)。
采用这个方法，可以减少当多个中断同时发生时任务的响应时间，最长的延迟时间为N*IST’。其中N为中断数。在这里之所以是IST’。而不是IST，是因为采用软中断软件模拟的方法使得在IST时间段内只执行一些简单的操作。
4.2
抢占式内核体系结构的设计
为了解决Linux实现硬实时的最大障碍，使Linux内核成为完全可被抢占实时内核，典型的实现方案是双核结构，使用实时核来运行实时任务。Linux内核来运行非实时任务。例如：对于实时数据采样分析而言，利用实时内核运行一个实时任务来完成数据采集，另一个实时任务完成数据分析和控制输出功能；同时利用Linux内核上运行的界面来进行数据显示。如图（2）所示
图2
双内核结构
在Linux内核和硬件之间加个小的实时核，由它管理中断，提供一些必要的功能，如底层任务创建、中断服务程序，并且为底层任务、ISR和Linux进程之间进行通信排队；而Linux内核本身则成为优先级最低的Idle
task
对实时性要求强的应用编写成实时任务，在实时内核上直接运行。Linux内核可以被优先级更高的实时任务抢占。对于Linux内核的修改主要集中在三方面：(a)在Linux内核中影响实时性的地方增加控制点，使内核在控制点可以被抢占，减少内核抢占延迟；(b)将执行时间较长的系统划分为几个甚至是十几个较小的块分别执行，使实对任务随时中断非实时任务；(c)根据实际需要，增加部分功能。
4.3 实时调度的算法研究
常用的实时调度算法有：基于优先级的调度算法(priority—driven
scheduling，PD)；基于时间驱动的调度算法(time—driven
scheduling，TD)；基于比例共享的调度算法(share—driven
scheduling，SD)。
(1)基于优先级的调度算法。调度器以优先级作为寻求下一个任务执行的依据。可分为如下两种类型：
(a)静态优先级调度算法：该算法给系统中所有进程都静态的分配一个优先级。静态优先级的分配可以根据应用的属性来进行。例如任务的周期、用户优先数或者其他预先确定的策略RM(Rate
Monotonic)是一种典型的静态优先级调度算法，它根据任务执行周转的长短来决定调度优先级执行周期小的任务具有较高的优先级。
(b)动态优先级调度算法：这种算法根据任务的资源需求来动态的分配任务的优先级。EDF(earliest
deadline first)算法是一典型的动态优先级调度算法，该算法根据就绪队列中各个任务的截止期限来分配优先级，具有最近截止期限的任务的优先级最高。
(2)基于时间驱动的调度算法：该算法本质上是一种设计时就确定下来的离线的静态调度方法。在系统的设计阶段。在明确系统中所有处理的情况下，对于各个任务的开始、切换以及结束时间等事先组出明确的安排和设计。
(3)基于比例共享的调度算法。这是一种越来越受到关注的实时调度楼式，基于GPS(general
processor scheduling)的算法，其基本思想就是按照一定的权重(CPU使用的比例)对一组需要调度的任务进行调度，使其执行时问与权重完全成正比。可以通过两种方法来实现比铡共享调度算法：(a)是调节各个就绪进程出现在当前调度队列队首的频率，并调度队首的进程执行；(b)是逐次调度就绪队列中的各个进程投人运行。但根据分配的权重谓节分配给每个进程的运行时间片。比例共享算法包括轮转法、公平共享法、公平队列法和彩票调度法等几类。
每一种调度策略都有自己的优越性和不足。在这里我们提出了一种宏观调度结构，通过设计和构造多属性和多调度器的选择机制，使三种实时两度策略的应用都得到支持，相对于只对单种调度策略提供支持的方案，拓展了系统的可使用范围。宏观调度结构如图（3）所示。
图3
宏观调度结构
我们给每一个实时任务定义了4个调度属性：priority(优先级：限制该任务比相关联的其他任务的优先权)、start_time（起始时间：任务开始执行时间)，finish_time(截止时间：任务停止时间)和budget(预设值：任务允许执行时间)，不同属性的数据对应不同的调度策略。宏观调度结构分为两个模块：属性分配模块和调度器选择模块。属性分配模块给每一个实时任务分配多个属性值，并通过其中的一两个属性值决定哪个属性优先，这样调度器选择模块就可以根据属性的优先级别选择不同的调度器。例如：如果优先级属性优先，则调度器就变成了一个纯粹的PD调度器；如果截止时问优先。那么调度器就作为EDF调度器来工作。
4.4
经过内部改造后的实时性能测试
实验时采用Pentium—II
400处理器 128MB内存。运行环境Linux
2. 0.35(以RED—Linux0.5为补丁)，以RM调度策略为例，分别测量每一次系统请求消耗的时间。数据整理如下：宏观调度结构下属性分配模按消耗的时间大部分不到40
us，平均约3Sus。调度器选择模块平均消耗时间约85us消耗时问总计为118us,约占0.118%的CPU时间；单一调度策略的情况平均消耗时间约为25us，约占0.025%的CPU时间。宏观调度结构的延迟时间为传统调度方式的5倍，对于大多数的嵌入式系统来讲内核的灵活性和可配置性比调度的延时更为重要。而宏观结构和单一调度结构的CPU可用时间分别为99.88%和99.97%，差别极小，符合嵌入式系统实时性要求。
5
对Linux内核的外部实时扩展
本方案将对中断处理、实时任务及实时任务调度做出一些必要的修改，以使增加新的实时调度器后的Linux系统能够发挥最佳性能。
5.1 中断处理的修改
由于中断操作(X86处理器的cli和sti机器指令)会造成不可确定的中断分派延迟。要在普通Linux上增加实时处理能力，需要修改Linux为了达到同步目的使用的关中断方式。为此，本方案通过在Linux内核与中断控制硬件之间增加一个模拟软件来实现。对于实时内核来说，它始终不关闭硬件中断，可接受所有的硬件中断。当中断信号需要实时内核处理时，实时进程将抢占Linux内核。如果中断信号需要原来的Linux来处理，则由实时内核进程传送信号给Linux内核。同时在实时内核中设置一个标志变量，当关中断时，该标志变量置为O，开中断时置为1。只要中断发生，实时内核就检查这个变量。假如这个值是1(Linux中断允许)，则Linux的中断处理程序将立即调用。如果Linux中断是禁止的，实时内核将所有待处理的中断放人到一个队列中，保存所有挂起的中断信息。一旦Linux中断打开，队列中所有挂起的中断被传给Linux内核处理。
5.2 实时任务
实时任务是一个用户设计的程序，它按照在内核控制下的特定调度方式来执行，可将实时任务调度单位设计为以线程为单位。为了提高性能，可利用Linux可装载内核模块的特性使所有的实时任务运行在一个地址空间。每个模块定义了2个例程：Init_module()和Cleanup_module()。Init_module()在模块装载到内核时调用，Cleanup_module()在删除模块时调用。通过使用内核地址空间，减少保护模式变换的系统开销。由于所有的任务在系统的地址空间，任务的切换也更简单。一个上下文切换通过先保存所有寄存器到栈中，然后改变栈的指针指向新的任务就可以了。
5.3 实时任务调度策略
为了是实时化Linux，在普通Linux基础上外加一个实时调度器。该实时调度器是一个基于优先级的抢占式调度器。调度策略是每个任务赋予一个唯一的优先级，只要一个优先级更高的任务就绪，它就可以中断当前较低优先级任务的执行。
根据每个任务的周期和它们的终止时间，可以利用速率单调调度算法(rate monotonic scheduling
algorithm，RMS)决定每个任务的优先级。非周期任务将处理为周期任务，同样赋予一个优先级。调度器把Linux当作一个具有最低优先级的任务。Linux只在没有实时任务运行时运行。
在采用可抢占的优先级调度算法后，为了使优先级相同的任务具有平等的运行权利，还可附加一个时间片循环轮转法，即当有两个或多个就绪任务具有相同的优先级，且它们是就绪任务中优先级最高的任务时，调度程序就选择这组任务中的第一个就绪任务，让它仅运行一段时间(时间片time
slice)。在运行完一个时间片后，该任务即使还没有完成，它也必须释放处理器让下一个与它相同优先级的任务运行(假设这时没有更高优先级的任务就绪)，然后排到同级优先级最后任务的后面，等待再次运行(见图4)。
图4
实时任务调度算法
为此，在任务创建时须为它指定一个优先级(0—255)，系统设计共有256个优先级，优先级数值越大优先级越低，相反数值越小优先级越高，0为最高。处于同一优先级的任务可以有任意多个。
根据以上分析，实时化的Linux需要定义与实时任务调度相关的数据结构，增加实时调度的算法，修改原有的中断处理过程，具体实现方法如下。
6.1 实时任务的数据结构
实时任务调度模块将实时进程分为就绪、运行、等待和僵死4种状态，在给定的时间，实时进程处于以上4种状态中的一种。实时进程的当前状态被记录在struct
RTLthread_struet结构的threadflags成员中。
每一个进程都有一个进程控制块，设计的实时进程控制结构用RTL_thread_struct结构。此外还有一个用来记录当前CPU信息的数据结构RTL_sched_cpu_struct。通过RTL_sched_cpu_struct结构中的RTL_tasks，构造一个实时任务链。
6.2
实时调度函数与实时调度器
6.2.1
实时调度模块的创建
实时调度模块的建立方法和普通Linux内核模块的建立方法一样，通过Init_module函数来实现，实现过程如下：(1)先通过系统调用以SRTLinux—
Scheduler设备名申请一个中断号。这样就把SRTLinux(Small
Real Time Linux，本文所描述实时系统)的进程调度作为普通Linux的一个中断设备来处理，而在普通Linux的进程调度时首先要处理中断，通过这种方法来保证实时进程的优先运行；(2)然后将中断信息保存在变量interrupt_state中，再关中断；(3)接着对系统中的结构RTL_sched_cpu_struct进行初始化。将当前进程指针指向RTL_Linux_task，而RTL_Linux_task就是普通进程，实时调度器模块刚建立时还没有实时进程。同时把普通Linux也作为一个实时进程，链到实时进程队列中；(4)再设置普通Linux的状态，它的优先级赋值为一1(最低优先级)；(5)设置与系统CPU适应的系统时钟，并为时钟设置相应的中断处理函数RTL_
sched— timer_ interrupt，初始化时钟。在RTL_sched_timer_interrupt函数中，系统通过定时器的中断不断调用RTL_schedule()函数进行实时任务调度；(6)最后恢复中断信息，打开中断。
6.2.2
实时任务的建立
为应用程序创建实时进程是通pthread_create(thread，attr，start，arg)函数来实现的。其中thread是一个指向实时进程结构RTL_thread_struct的指针，attr是进程的属性描述，start是进程执行函数的入口，arg是进程执行函数的参数。
该函数完成进程控制块的初始化，关闭中断，将创建的任务加到任务队列的队首，执行任务调度，最后重新打开中断。
6.2.3
实时任务的删除
实时任务运行结束后，通过接口函数pthread_delete_npO将由pthread_create创建的进程删除。
6.2.4
实时调度函数
实时进程可以在创建时用函数pthread_attr_setschedparam
设置或在运行中用pthread_setschedparam
改变其优先级。调度函数将系统的优先级设为一1，而所有实时进程的优先级大于等于0，从而保证实时进程优先执行。调度算法实现过程如下：(1)关闭中断，保存中断字信息；(2)取系统时问；(3)搜索实时任务队列，比较当前精确时间now与恢复执行时间t-〉resume_time，查找到的最高优先级的可运行任务保存在new_task中；(4)如果有新任务且优先级与正在运行的任务相同，则设置调度方式和时问片，停止正在执行的任务并加入到相应优先级队列，切换到新任务。否则直接切换到新任务；(5)如果新任务为空，则从优先级队列中取出高优先级任务执行，最后通过调度将CPU资源交给别的进程；(6)否则，根据当前进程收到的信号调用do_signal()来处理，恢复保存的中断字。
6.3 实时程序的编写
实时应用程序是用户态程序，通常要用到一些内核的API服务函数。Linux内核所提供的两百多个函数以GNU
C程序库的形式提供给用户，也可以在实时应用程序中使用，如fork()、exee()、pipe()等函数。同时实时应用程序还需要POSIX线程的有关调用，如：pthread_create()、pthread
mutex_lock()等 。这些函数的实现规则是基于Linux系统调用的，并最终由Linux内核调度模块来完成。
6.4
经过外部扩展后的实时性能的测试
完成Linux系统改造后，需对其作一定的测试以评估系统是否符合实际应用的需求。实际应用中，应用程序的开发者主要关心的是系统中断延时、时钟精度、上下文切换时间、系统调用的开销以及实时抢占能力。通过使用Andrew
Morton在因特网上提供的测试工具 ，用改造前后的内核分别运行同样的行走机器人数据采集与处理任务。在系统运行8个进程的情况下，该任务从请求到运行完成所需的时间后者比前者减少了2.35
ms，而当系统运行12个进程的情况下则为2.62
ms。系统改造后的性能改进是比较明显的。
7
结语
Linux虽然为分时操作系统，但由于其功能强大、源代码开放以及可移植性强等优势，已成为日益流行的嵌入式实时操作系统的解决方案。本文分析了Linux移植到嵌入式系统并满足实时处理要求的关键技术，通过对Linux内核的内部源代码的改造，提升了普通Linux系统的实时性能，并提出并实现了对Linux内核进行外部改造使之实时化的方法。通过上述改造，解决了普通Linux中的优先级倒置和中断处理时不能处理外部硬件中断而导致响应时间过长的问题，实现了软实时功能，使改造后的Linux可以适应实时应用场合。
骆耀祖.Linux操作系统分析教程[M].北京:清华大学出版社,2004年
Robert
love.Linux内核设计与实现[M].北京:机械工业出版社,2003年
郭玉东,王非非.Linux操作系统结构分析[M].西安:西安电子科技大学出版社,2001年
发表时间
2006－5-9 来源 计算机学院 论文发表
版权声明：文章著作权归作者所有，如侵犯了作者版权，请与我部联系
email xuezizhongguo@163.com