2009年9月17日星期四

抢占式内核

本文译者



康华:计算机硕士,主要从事Linux操作系统内核、Linux技术标准、计算机安全、软件测试等领域的研究与开发工作,现就职于信息产业部软件与集成电路促进中心所属的MII-HP Linux软件实验室。如果需要可以联系通过kanghua151@msn.com联系他。



 



注明:棕色写的内容为译者注。



如果有意义不明之处请参见原文



 



Kevin 将继续他的实时之旅,这次他要着重分析如何通过改造Linux内核来为应用程序带来实时性能。



2002年的1-2月发行的嵌入Linux月刊中,我们探讨了有关实时和Linux的基础问题。而这次我将精力花在改造Linux内核来为应用程序带来实时性能这个主题上。到目前为止,工作的重心集中在提高内核响应速度——通过减少抢占响应时间缩短系统响应时间,因为我们知道抢占响应时间在Linux中耗时较长。



 



通过改进内核——仅仅是剔除一些标准内核的功能——并不去改变或增加内核API,应用程序就可以获得更快的响应速度。这样做优势明显,因为ISVs(独立软件开发商)不需要为不同的实时要求开发不同版本的系统。比如,DVD播放器可以在一个改进过的内核上更稳定的运行,而它不必知道该内核是经过改进的版本。



背景和历史



2.2版本内核发布以来,内核抢占成为一个热门话题。Paul Barton-Davis Benno Senoner曾给Linus
Torvalds
写了一封信(该信后来追加了许多人的签名),请求在2.4版本内核中显著降低抢占延迟时间。



他们需要Linux性能上能满足播放音频、音乐以及MIDI的要求。Senoner开发了一套基准软件benchmarking
software
)测试2.2版本内核(以及后来的2.4版本),在最坏情况下发现抢占延迟高达100毫秒(参考) 对于音频应用程序来说,这么长的延迟时间显然是无法接受的。因为经验显示系统响应时间只有在几毫秒内才能满足音频应用程序的需要。



有两个补丁包为内核提供了相当不错的抢占响应速度提升。Ingo Molnar (来自 Red Hat) Andrew Morton (来自Wollongong大学)
两人都开发了内核补丁,这些补丁为内核中长代码路径片段插入了抢占点。你可以在这里这里发现Ingo Molnar的补丁包 ,或在这里找到Andrew Morton的补丁包。



另外,Morton还提供了测量响应速度的工具,比如测量内核忽视请求时间长度等,有关详细信息在他的快速响应补丁网站上可以找到。



目前,至少有两个组织开发了抢占式内核,为内核抢占问题提供了更基础、更强大的解决途径。



20021-2ELJ上发表的系列文章的第一篇中,我列举了不少希望Linux能够支持的实时功能,它们包括多优先级、用户空间中断处理和DMA、同步机制中的优先级继承(优先级继承可用来解决优先级反转问题。当优先级反转发生时,优先级较低的任务被暂时地提高它的优先级,使得该任务能尽快执行,释放出优先级较高的任务所需要的资源、微妙级的时钟解析度 、全面实现POSIX1003.1b规范要求的功能和调度程序的恒量耗时算法等。我们在本文中也会简要讨论它们。




明白这些性能改进都必须依赖给内核打补丁,但是打补丁后的内核就不再兼容其它标准内核了,比如抢占式内核需要修改自旋锁的代码,这时如果一个驱动程序的二
进制执行文件如果不采用修改过的自旋锁,那么很可能无法正常抢占。所以改造内核时一般都需要内核源代码并重新编译内核代码。值得一提的是,使用模块化的
Linux驱动程序是使得源代码兼容的一个有效方法。我们不赞成仅仅发布驱动程序的已经编译的二进制文件而没有源代码,因为这样作既缺乏兼容性保障也不符合开源精神。



改进



各种各样对内核的改进能够为应用程序透明地提供众多好处。比如,提高内核的抢占性主要通过抢占式内核或是添加抢占点着两个途径。从内核角度进行改进可以使得应用程序不用做修改就能获得高的响应速度。



透明性也应该考虑是否改变对内核来说也是透明的,换句话说就是,是否采用的方法能自动跟踪内核的改变。MolnarMorton提出的插入抢占点的方法需要测量新内核中的调度响应时间,并且在此基础上插入抢占点到合适位置。



    相反,如果在SMP锁定基础上创建抢占式内核,则可以自动、无须修改地过渡到新内核。而且如果在SMP-锁定机制中实现抢占性,则当内核开发者提高SMP锁定粒度(granularity)时,也同时会自动提高抢占粒度。我们会看到SMP锁定将粒度稳步提高,因为SMP不断扩张必定需要不断提高锁定粒度。



正是由于这种新引进的SMP锁,内核抢占才自2.4版本或更新(实际在2.6才正是支持)内核后被正式实现。而早期内核缺乏SMP锁。



抢占式内核的另外一个需要强调的重要优势是它使得代码——但代码不会发觉——可被抢占,比如,驱动程序开发者不必为要使驱动程序可被抢占去编写任何特殊代码,驱动程序的代码能在必要时被抢占,除非驱动程序持有锁。所以在内核其它部分,编写优良的SMP安全代码中不存在多处理器并发访问共享资源的危险)的驱动程序将自动受益于抢占式内核。而另一方面,非SMP安全的驱动程序可能不能和抢占式内核和谐工作。



也许有人会发觉,只要某些驱动程序没有请求锁,内核代码就可以调用它。比如我们使用MontaVista的抢占式内核做简单测试中发现,动态装载的驱动程序中read()write()函数都可以正常被抢占,但是函数init_module()open()close()却不能。这意味着如果一个低优先级的进程执行操作open()close(),那么它有可能被一个新唤醒的高优先级别进程推迟抢占时机。



实际上,开发者最好去测量响应时间,因为即使使用抢占式内核,我们也有可能找到有那些代码片段持有锁的时间超过了应用程序允许的长间。



比如MontaVista, 提供了一个抢占式内核,对那些长期持锁的代码片段插入了抢占点,同时也提供了测量工具,以便开发者可以测量它们实际应用程序和环境的抢占性。



SMP锁的目的是确保内核重入(re-entrance)安全。也就是,如果并行运行的进程需要访问内核资源,那么对这些资源访问必须安全、可靠。越精细的锁定粒度越能保证竞争进程运行的并行巡行能力越强。因为并行能力的提高需要减少堵塞(因为锁的争用),(而细粒度锁可减少阻塞机会)。



上述概念也同样适用于单处理器。对于I/O系统来说,如果将I/O设备看作一个独立的处理器,那么应用程序和I/O活动的并行运行无疑能提高系统吞吐量。提高抢占性,意味着高优先级的I/O范畴进程(I/O-bound process)会更频繁地被唤醒,从而提高了吞吐量。这样以来,虽然可能带来某些负作用,比如我们可能会需要更多的上下文切换和在内核关键路径上执行更多代码(关键路径直那些访问共享资源的代码路径,为了防止竞争条件需要上锁等操作),但是即使如此,我们仍然可以获得更大的系统吞吐量。



允许内核抢占的优势是显而易见的,标准内核迟早会引入抢占功能(目前已经具有)。抢占式内核有些实现中可以提供几微妙的响应时间,而更精确的实现则可把响应时间提高到几十分之一微秒。



环顾嵌入Linux生产商,MontaVista TimeSys提供了抢占式内核;REDSonic使用抢占点;LynuxWorks和红帽子使用RTLinuxLineo
使用RTAIOnCore通过和Linux系统调用兼容的API(和LynuxWorks利用LynuxOs一样)与在他们的抢占式微内核上。



运行一个Linux内核(可抢占的)达到实时目的。



 



抢占点



抢占点的核心思想是在特定点上调用调度程序去检查是否有更高优级的任务做好了运行准备,需要即刻运行。MolnarMorton就是利用该思想,测量内核路径的执行时间,找到时间过长的路径插入调度检查点(等于打断了长路径)。你可以通过抢占补丁代码或是对比打过补丁的内核和先前未达补丁的内核,从中发现那些地方需要插入抢占点。抢占补丁看起来很象if (current ->need_resched) schedule()这是用户空间抢占执行的典型情形;



为了使用Andrew Morton开发的抢占点内核补丁,需要从上面给出的URL下载该补丁,同时还要从kernel.org下载恰当版本的内核源代码。然后内核打上补丁然后重新编译,详细细节可以在这里找到,但要注意这些是为2.4版本老版本内核而言的。另外还请注意你可能需要升级你的开发环境。



   使用Molnar的补丁要做的事情同上。下载补丁、编译新内核,Morton开发了针对2.4多个版本的补丁。而Molnar的补丁针对一些2.2版本内核和早期的2.4版本内核。



 



抢占式内核



抢占式内核使得用户程序在执行系统调用期间可以被抢占,从而使新被唤醒的高优先级进程能够运行。这种抢占并非可以在内核中任意位置都能安全进行,比如在临界区中的代码就不能发生抢占。临界区是指同一时间内不可以有超过一个进程在其中执行的指令序列。在Linux内核中这些部分需要用自旋锁保护。



MontaVista
TimeSys采用类似的方法建立抢占式内核。他们巧妙地将自旋锁的功能加强为也能防止抢占(2.6新内核中自选锁也是这样做的)。依靠该方法,抢占只能发生在未使用自旋锁的其它部分。当一个更高优先级的进程被唤醒,调度程序就能抢占低优先级进程正在执行的系统调用,只要此刻该系统调用代码没有被自旋锁保护——加上自旋锁意味不可抢占。



另外,使用抢占式内核,打断锁(解开再锁上)使得重新调度相比采用抢占点(低响应时间)补丁要简单。因为如果内核释放了一个锁,然后又再获得它,那么当锁被释放时,就会进行抢占检查。内核中有些地方需要上锁——比如一个循环——但不需要一直持有锁,可以每进行一次循环,锁就要被释放,然后再获得。



MontaVista实现抢占主要通过一个计数器(2.6版本中称它为抢占计数,用它可以跟踪锁定嵌套数),当自旋锁被获取时,该计数就增加1。当高优先级别的进程被唤醒,调度程序会检查抢占计数——检查是否为零——判断是否此刻允许抢占(如果为0,就可以发生抢占)。依靠这个计数器,当锁嵌套调用时,抢占机制能很好的工作,但是任何持有自旋锁的临界区域都不允许抢占,即使锁用来保护的是些无关资源。



TimeSys采用一个优先级遗传互斥量(priority inheritance mutex)。利用这种机制,一个高优先级的进程可以抢占一个持有不同资源互斥量的低优先级别的进程。另外因为采用了优先级遗传,所以持有互斥量的低优先级的进程不能无限推迟等待在该互斥量上的高优先级进程。这样以来解决了所谓的优先级翻转问题(Priority Inversion Problem)。



MontaVista公司开发的抢占包可以从SourceForge kpreempt 站点获得。MontaVista公司的开源精神很值得赞赏,他们同时也提供了他们的实时调度程序与高解析度定时器,这些都可以从SourceForge这里这里获得。



SourceForge
kpreempt 项目同时也含有Robert Love开发的抢占式内核的连接(请看20024月和5月出版的Linux杂志,其中介绍了他对内核改进的详细信息)。 另外 MontaVista的补丁也由Love维护(现在Robert Love已经归于MontaVista麾下),虽然MontaVista 也参与维护工作。最新的补丁可在此处下载。



Love最新发布的补丁现在已经可以和Ingo Molnar的恒时(耗时为衡量)调度程序补丁协同工作。Molnar的时间复杂度为O(1)的调度程序可以用于2.4版本内核,并且目前也已经植入了2.5版本的内核中了。TimeSys也将自己的抢占式内核发布在了他们的网站上。抢占式内核需要的补丁包都已经完备。要得到这些补丁,你需要将它们对比2.4.7内核代码数生成diff文件。上述的这些抢占式内核程序都遵守GPL协议。



TimeSys还为实时程序开发者提供了许多额外功能,这些功能不能无偿下载。它们包括实时调度和实时资源分配技术。这些模块填加了额外的系统调用,比如提供对新增功能的访问方法等。



如果那些朋友对这些细节感性趣,可以通过我们提供的许多线索找到想要的信息。自旋锁机制的关键信息包含在文件include/linux/spinlock.h中,MontaVista
TimeSys都对该文件进行了修改。



有趣的是,虽然MontaVista TimeSys都对旧函数改了名字,但是他们仍然使用这些旧函数。以前老的自旋锁函数仍然需要。比如不允许在调度程序执行期间发生抢占内核的行为,否则会带来无穷无尽的递归调用。MontaVista使用象_raw_spin_lock
_raw_read_lock
这样的命名;TimeSys 使用象old_spin_lock
old_spin_lock_irq
这样的命名。



可以在TimeSys发布的代码kernel/include/linux/mutex.h中发现它是利用write_lock() read_lock()函数——他们实现了互斥锁——定义自旋锁的。具体实现函数do_write_lock()可以在文件kernel/kernel/mutex.c中看到,它实现了互斥锁定功能。



其它的内核实时方法



另一个能有效提高实时性的方法是提高时钟的粒度。TimeSys, MontaVista, REDSonic 和其他公司都提高了时钟解析度,比如,TimeSys 在上下文切换期间使用Pentium处理器的时间戳计数器(Stamp Counter)来确保准确地对CPU时间进行记帐,该记帐值要被诸如 getrusage()等函数用到。



许多开发者,也包含作者都认为Linux缺乏对POSIX1003的全面支持是个很重要的缺陷。幸运的是,目前已经有了解决方法,特别是,TimeSys公司已经有了一个不错的实现。



除了对POSIX的贡献外,TimeSys已经开发了一些全新的资源访问控制机制。这些新技术使得实时应用程序可以节约CPU时间或网络带宽。比如结合它们的中断线程模型、抢占式内核和其它功能,能提供高出标准内核23倍的响应速度。



到目前为止,Linux好象还不允许让用户空间应用程序自己注册函数处理中断,该机制称为用户空间中断处理机制,它目前已经在RIXSGI's UNIX等系统中得到使用。



有趣的是,SGILinux中,利用他们的ds1286实时时钟接口,可以从用户空间通过一个实时时钟访问中断。可以在这里.找到相关信息



和用户级别中断处理相关的是用户空间和设备的DMA通讯,提供此功能的补丁可以从这里获得。



保证



显然,没有哪个实时Linux厂商愿意保证响应速度。如果提供保证的话,那么应该类似下面的声明:



使用我们的Linux内核,和所需的硬件与设备等,我们可以保证你的应用程序如果被锁在内存,具有最高优先权。。那么将能够在你实时硬件发出中断信号后的N微妙内被唤醒。如果你无法获得上述能力,我们将视其为一个bug



但是我们从没看到过该类保证,这是为什么呢? 我们认为有如下几种可能。



厂商的这种保证毫无意义,没有客户需要它。但我们认为许多开发者希望获得保证,事实上,硬实时本身就意味着一个保证。




商没有充分测量他们的内核和环境,以至于有能力给出一个保证。这是一个小花招。因为单独测量无法给出另人满意的保证,代码必须在所有环境中被测试而且要在
最坏情况下测试。从厂商的宣称中,看起来它们似乎已经花了大量精力去测量和学习代码,但事实上,对工程师来说可能给出给定环境下的一些数据更能让人放心。



如果考虑所有需要保证的方面,Linux所涉及的方面实在是太多了。这点可能就是问题的所在。开发者希望能够改写他们的内核,他们希望能下载驱动程序并使用。这些行为都超出了厂商的控制,所以如果厂商公开声明一个保证,就有可能仅仅是针对某一个特定系统在一些选定的情况下才有效的。



也许我们会看到某些妥协的保证,例如像“在Pentium
系列的计算机上应用程序响应速度为100ms或更短”另外加上驱动程序花去的时间。驱动程序使用的时间非常重要,因为驱动程序中的中断处理代码往往在响应时间中占主要部分。





没有评论:

发表评论