Embedded 版 (精华区)

发信人: Thinkpad (船 长), 信区: Embedded_system
标  题: 关于提高Ｌｉｎｕｘ核心实时处理能力的讨论
发信站: 哈工大紫丁香 (2001年11月09日11:53:14 星期五), 站内信件

　　                 关于提高Ｌｉｎｕｘ核心实时处理能力的讨论
             曹计昌,余　隽(华中科技大学计算机科学与技术学院,湖北武汉430074)

摘　要:Ｌｉｎｕｘ已经成为一个流行的ＵＮＩＸ操作系统。如何将Ｌｉｎｕｘ改造为实
时操作系统,许多人做了许多探讨和研究。这篇文章,我们通过引入三种新的内核机制来
提高Ｌｉｎｕｘ的实时性。把微定时器引入内核,并且在Ｌｉｎｕｘ核心中采用和完善了
时间驱动的调度算法。最后,通过提高内核的可抢占性来减少实时任务的响应时间。

关键词:实时操作系统;可抢占性;Ｌｉｎｕｘ;内核

中图分类号:ＴＰ316.81　　文献标识码:Ａ

1　引言
    到目前为止,有三种类型的ＯＳ应用于实时系统之中:嵌入式微内核(例如:ＱＮＸ,Ｐ
ＳＯＳ);实时操作系统(例如:Ｌｙｎｘ,ＲＴ-ｌｉｎｕｘ);在传统的操作系统之上做了
一些实时性扩展的(例如:ＷｉｎｄｏｗｓＮＴ,Ｓｏｌａｒｉｓ)。嵌入式微内核对于实
时调度只能给出有限的支持,其他一些实时性要求只能通过别的方法实现。做了一些实时
性扩展的非实时性操作系统虽然可以满足一定的实时功能的要求,但是它本身的设计是基
于非实时性构架的,所以常常会表现出一些功能上的缺陷。对于实时操作系统当然是满足
实时应用要求的最佳选择,但是高昂的售价让许多项目策划人望而止步。所以我们试图设
计一种开放式的ＲＴＯＳ。
    我们想到了Ｌｉｎｕｘ,这是一种公开源代码的类ＵＮＩＸ操作系统。但是早期的Ｌ
ｉｎｕｘ内核是一个非抢占式系统,并不是很适合于实时应用。虽然Ｌｉｎｕｘ在1.3版
之后提供了有限的ＰＯＳＩＸ实时支持,采取了基于时间轮换片的优先级调度,它可以将
一个进程指定为一个实时进程,调度程序给实时进程赋一个高的优先权,以满足该进程的
实时性要求。但是Ｌｉｎｕｘ并没有加入对时间的限制,例如对一个实时进程应完成的最
后期限的限制,应在多长时间内完成,执行的周期等。而且,Ｌｉｎｕｘ不能保证对实时任
务的及时响应。例如大量的非实时性事件可能阻塞实时任务的执行。实时系统的主要性
能指标是:中断响应时间(ＩｎｔｅｒｒｕｐｔＲｅｓｐｏｎｓｅ)、进程切换时间(Ｃｏ
ｎｔｅｘｔＳｗｉｔｃｈｉｎｇＴｉｍｅ)、确定性(一个实时任务要在确定的时间内完
成)。
    所以,我们必须根据以上三条性能指标要求对Ｌｉｎｕｘ内核做一些改造,使它能满
足实时系统的要求。
2　实时内核的特性
    一个实时系统的典型例子是:当一个或多个外部物理设备向计算机发出处理请求,计
算机必须在一个限定的时间内做出合适的响应。
   我们把实时系统分为硬实时系统和软实时系统。硬实时系统中实时内核必须对所有的
外部实时请求在要求时间内做出及时响应;软实时系统则可以偶尔对某些实时请求做出非
实时响应。这两种实时系统中,所有的实时任务都是由它们的时间特性来进行定义的,例
如:周期性(一个外部实时事件在固定的时间间隔发生)、执行的最后期限等。操作系统就
要按照这些实时任务的时间特性来进行尽量可能精确的调度。
   要使一个内核具备实时性,必须具备以下几个特性:
   微定时器
   任何一个实时内核中都必须要具备一个精确的定时器。在一个时间共享的系统中,一
个操作系统采用一个周期性的定时器来将ＣＰＵ的时间分配给每一个任务。选择一个合
适的时间频率(也就是我们通常所说的时间轮换片),可以使在进程切换与任务响应之间达
到一个十分良好的平衡。依照不同的系统结构,定时器的间隔时间通常设定为1ｍｓ到20
ｍｓ之间。然而,对于大多数实时应用来说,这种解决方案并不是很好。为了使调度程序
对以下情况有足够的响应时间(例如:进程什么时候开始,什么时候结束它们的执行过程)
,实时应用程序通常需要一个微秒级的定时器。
   任务响应时间
   除了定时器外,一个ＲＴ核心还需要确保短任务的响应时间。任务的响应时间被定义
为一个事件发生和任务响应这一事件开始执行之间的间隔时间。
   通常有以下几个因数影响任务的响应时间:
   ａ)中断分配时间(ＩＤＴ):当一个中断产生时,在调用中断处理程序占用ＣＰＵ以前
,操作系统用来保存所有的寄存器中的内容和系统中其他的关于这一任务状态的时间。
   ｂ)中断服务时间(ＩＳＴ):中断服务程序用来从硬件设备读取信息或从操作系统收集
信息所用的时间。
   ｃ)内核抢占时间(ＫＰＴ):在操作系统意欲抢占当前进程与抢占实际上发生之间的时
间间隔。这一时间依赖于当前运行的线程所处的模式。如果一个线程运行于用户态时,并
且抢占立刻发生的话,ＫＰＴ为零。如果当前运行的线程处于核态,那么ＫＰＴ就有可能
长到该运行线程结束其核态时为止。
   ｄ)调度延迟时间(ＳＤ):调度程序用来调度另一个线程投入运行的时间。
   ｅ)进程切换时间(ＣＳＴ):当前线程用来保存寄存器和系统状态的时间与将要运行的
线程恢复寄存器中的内容和系统状态的时间总和。
   ｆ)从系统调用中返回的时间(ＲＳＴ):处于内核态的线程在它返回用户态之前检查一
些状态所用的时间。例如:内核检查是否有悬挂信号给某个线程,如果要是有的话,那么就
将该进程挂起,而不是进行进程切换。
    在以上这些时间中,ＳＤ,ＣＳＴ和ＲＳＴ总是固定不变的,不能够减少。如果Ｌｉｎ
ｕｘ内核设计得当的话,ＩＤＴ,ＩＳＴ和ＫＰＴ可以有效地减少。其中ＩＳＴ通常比Ｉ
ＤＴ要长,而且当ＩＳＴ是用来表示执行一些复杂任务的花销时间时,对于非实时系统中
的实时任务来说,它是很长的。所以,在对Ｌｉｎｕｘ核心进行改造时,必须要使用某种技
术来减少ＩＳＴ。而且,在一个实时系统中几个中断可能同时发生,这样的话,一个任务的
响应时间可能包括几个ＩＳＴ和ＩＤＴ。从理论上来说,任务的响应时间可能无限长,因
为在同一时间可能有无数多个中断产生。因此,在非实时内核中,任务的响应时间应该是
:Ｎ (ＩＤＴ+ＩＳＴ),其中Ｎ是中断的个数。
   从这个公式来看,在实时系统的内核中必须要选择合适的Ｎ值。从ＫＰＴ的定义来看
,我们可以通过调整时间轮换片的大小来使ＫＰＴ的值尽可能地小。在Ｌｉｎｕｘ中一个
进程是不能抢占一个正运行在核态的进程的。只有当后一个进程离开了核态,那么前一个
进程才能占用ＣＰＵ。这样我们可以选择合适的时间轮换片,使得处于核态的进程的运行
时间满足实时系统的要求。
3　提高Ｌｉｎｕｘ核心实时性的改造方案
    一个实时系统有可能要对多个周期性的事件流做出响应。依照每一事件进行处理所
需要的时间不同,实时系统有可能不能对它们全部进行处理。例如:如果有ｍ个周期性事
件,其中有ｉ个事件以时间间隔Ｐｉ来发生,并且处理每一个事件需要Ｃｉ秒的ＣＰＵ时
间。那么只有当:∑ｍｉ=1ＣｉＰｉ 1时,一个实时系统才能处理全部事件。满足这一条
件的实时系统称为可调度的实时系统。
   我们以下所做的改造方案,均假设满足以上可调度条件的前提下来完成的。
   为了提高Ｌｉｎｕｘ核心的实时性,我们引入了三个组件到Ｌｉｎｕｘ核心中:微定时
器、减少内核阻塞的调度和中断软件模拟。
   在改进后的Ｌｉｎｕｘ核心中,每一个实时进程都以一个普通的用户进程出现,然后通
过ｓｒｔ—ｓｅｔｓｃｈｅｄｕｌｅｒ()系统函数来指定它的ＱｏＳ参数。这个系统调
用将会返回一个布尔类型的值来判断该进程的ＱｏＳ是否被接受。如果接受的话,该进程
就成功地成为一个实时进程;否则的话,它将会改变ＱｏＳ值,重新进行提交。以下我们着
重讨论一下具体的实施措施:
   3.1　中断软件模拟
    软件中断模拟被用来解决多个中断同时发生的情形。解决的方法是:当一个硬件中断
发生时,系统只是简单地在事件表中报告这一事件的发生,然后立即将对ＣＰＵ的控制权
返回给操作系统,而不是象一般的Ｌｉｎｕｘ核心那样去查中断向量表并执行相应的中断
服务程序。我们用中断的软件模拟来代替相应的硬件处理(例如:ＩＢＭＰＣ中的8259中
断控制器)。用软件的方法来检查每个中断事件的状态和紧迫程度(即优先权),来决定选
择哪一个进程投入运行。
   采用这种方法,可以减少当多个中断同时发生时任务的响应时间长度。最长的延迟时
间为Ｎ ＩＳＴ′,其中Ｎ为中断数。在这里之所以是ＩＳＴ′,而不是ＩＳＴ,是因为采
用中断软件模拟的方法使得在ＩＳＴ时间段内只执行一些简单的操作。但是软件的处理
也有它的缺点,就是有可能导致某些硬件中断被挂起的时间过长,而影响实时性,因为软件
的处理速度要比硬件的处理慢。
  3.2　减少内核阻塞的调度算法
  在大多数ＵＮＩＸ系统中,每一个系统调用都是一个自动的操作。没有一个任务可以中
断一个系统调用的执行,除非在系统调用的执行过程中因为缺乏资源而自动让出ＣＰＵ。
一个单独的系统调用执行时间可以从几十毫秒(例如:给一个进程赋优先级)到几秒(例如
:从磁盘上读大块的数据)。所以,假如有一个很长时间的系统调用被一个非实时进程调用
时,一个实时进程的响应时间可能很长。事实上,在Ｌｉｎｕｘ中任务的响应时间并不会
象我们以上分析的那么长,因为一个较长的系统调用被划分成几个较小的块来执行。例如
ｒｅａｄ()系统调用,它的执行过程如下所示:ｓｙｓ—ｒｅａｄ：发读请求给磁盘休眠
、进入等待队列，直到磁盘将数据准备好为止读磁盘数据的一个块读磁盘数据的一个块
读磁盘数据的一个块发另外一个读请求给磁盘休眠、进入等待队列，直到磁盘将数据准
备好为止读磁盘数据的一个块读磁盘数据的一个块读磁盘数据的一个块  进程调度程序
在前一个进程进入休眠状态之后,可以调度另一个进程投入运行,以尽量减少进程的等待
时间。但是,就算是这样,一个代码块的执行时间仍然会从10到30ｍｓ不等,这对于许多实
时进程来说还是长了一点。那么我们就必须对Ｌｉｎｕｘ内核进行改造,以满足系统的实
时性要求。
    解决方案是:将系统调用的执行过程再进行细分,使得每一个小块的执行时间都相当
短。在每一小块执行完之后,系统内核都要检查在可运行队列中是否有高优先级的实时进
程等待运行,如果有的话,那么将前一个进程挂起,而将该进程投入运行。
   以上我们所讨论的两种模型都是在一个线程处于核态的时候允许其他优先级更高的进
程抢占执行,中断软件模拟模型属于完全抢占模型、减少内核的阻塞的模型属于合作型抢
占模型。以上两种模型在抢占时都会有一些延迟。抢占前调度程序的执行框架为:
   ｂｅｇｉｎ：
   ｐ=ｈｅａｄｅｒ—ｏｆ—ｂｌｏｃｋ—ｌｉｓｔ；
   ｄｏ｛
   ｉｆ（ｐｉｓｔｈｅｂｌｏｃｋｗｅｗａｎｔ）
     ｂｒｅａｋ；
      ｉｆ（需要抢占）｛
      ｓｃｈｅｄｕｌｅｒ（）；
        ｇｏｔｏｂｅｇｉｎ；
      ｝
   ｐ=ｔｈｅｎｅｘｔｂｌｏｃｋｉｎｌｉｓｔ；
  ｝ｗｈｉｌｅ（ｐｉｓｎｏｔｔｈｅｌａｓｔｏｎｅｏｆｌｉｓｔ）；
   在我们参照以上模型,设计内核中的调度算法的时候,必须考虑到以下情况:当一个进
程要抢占一个正在执行的进程,并且可能要使用并改变一些正在执行的进程所使用的资源
时,我们是不能抢占该执行进程的。例如用以上程序框架调度时,如果碰上一个很长的进
程可运行队列要查询时,那么延迟时间会很长。所以以上的调度算法改善后可以写为:
    ｂｅｇｉｎ：
    ｐ=ｈｅａｄｅｒ—ｏｆ—ｂｌｏｃｋ—ｌｉｓｔ；
    ｄｏ｛
     ｉｆ（ｐｉｓｔｈｅｂｌｏｃｋｗｅｗａｎｔ）
         ｂｒｅａｋ；
         ｉｆ（需要抢占）｛
          ａｄｄ—ｗａｉｔ—ｑｕｅｕｅ（＆ｃｏｎｔｒｏｌ—ｏｆ—ＣＰＵ，＆ｗ
ａｉｔ）；
           ｓｃｈｅｄｕｌｅｒ（）；
           ｒｅｍｏｖｅ—ｗａｉｔ—ｑｕｅｕｅ（＆ｃｏｎｔｒｏｌ—ｏｆ—ＣＰＵ
，＆ｗａｉｔ）；
             ｇｏｔｏｂｅｇｉｎ：
          ｝
         ｐ=ｔｈｅ—ｎｅｘｔ—ｂｌｏｃｋ—ｉｎ—ｌｉｓｔ；
     ｝ｗｈｉｌｅ（ｐｉｓｎｏｔｔｈｅｌａｓｔｏｎｅｏｆｌｉｓｔｓ）；
4　总结
     以上我们在硬实时系统的构架基础上,提出了对Ｌｉｎｕｘ核心的实时化改造方案
。一个典型的实时操作系统不同于一般非实时系统的最大特点就是严格的时间限制,所以
,我们对一个非实时系统的改造,主要的思路就是尽量提高实时任务的响应速度,一般来说
响应的时间范围在10-3秒到10-6秒之间。
参考文献
［1］　Ｋｗｅｉ-ＪａｙＬｉｎ，ＡｎｓｇａｒＨｅｒｋｅｒｔ．ＪｉｔｔｅｒＣｏｎ
ｔｒｏｌｉｎＴｉｍｅ-ｔｒｉｇｇｅｒｅｄＳｙｓｔｅｍｓ［Ａ］．Ｐｒｏｃ．29ｔｈ
ＨａｗａｉｉＣｏｎｆｅｒｅｎｃｅｏｎＳｙｓｔｅｍＳｃｉｅｎｃｅｓ［Ｃ］．Ｍａ
ｕｉ，Ｈａｗａｉｉ，Ｊａｎｕａｒｙ1996
［2］　Ｂ．Ｓｒｉｎｉｖａｓａｎ，ｅｔａｌ．ＡＦｉｒｍＲｅａｌ-ｔｉｍｅＳｙｓ
ｔｅｍＩｍｐｌｅｍｅｎｔａｔｉｏｎＵｓｉｎｇＣｏｍｍｅｒｃｉａｌｏｆｆｔｈｅ
ＳｈｅｌｆＨａｒｄｗａｒｅａｎｄＦｒｅｅＳｏｆｔｗａｒｅ［Ａ］．Ｐｒｏｃ，Ｉ
ＥＥＥＲｅａｌ-ＴｉｍｅＴｅｃｈｎｏｌｏｇｙａｎｄＡｐｐｌｉｃａｔｉｏｎＳｙｍ
ｐｏｓｉｕｍ［Ｃ］，Ｊｕｎｅ1998．
［3］　ＡｎｄｒｅｗＳ．Ｔａｎｅｎｂａｕｍ，ＡｌｂｅｒｔＳ．Ｗｏｏｄｈｕｌｌ．
ＯｐｅｒａｔｉｎｇＳｙｓｔｅｍＤｅｓｉｇｎａｎｄＩｍｐｌｅｍｅｎｔａｔｉｏｎ
（ＳｅｃｏｎｄＥｄｉｔｉｏｎ）［Ｍ］．北京：清华大学出版社，1998
［4］　程莉君．Ｌｉｎｕｘ操作系统内核分析［Ｍ］．北京：人民邮电出版社，

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.239.147]