（计算机应用技术专业论文）现代操作系统调度策略研究.pdf

塑塞查兰堡圭堂望鎏茎! 銎垡蓬篷薹鉴篓壅茎堕壁鍪一一一 摘要 传统鹳遂羯操炸系绞恩无法瀵足当懿硬实时、软实射和普通应用并存的要求。 设计对各种痘耀撬供统一支持的调度綮臻成为现代操作系统的磷究热点。 本文对u n i x ，l i n u x 稻w i n d o w s n t 等透感操作系统豹调度掇裂避行分摄，势 指国箕在实露环境下静不是。r t - l i n u x 缒对疆实时痘用提供较好懿支持，本文慰冀 进行箭析，并在既基确上挺甾一种统一调度撬架，该框浆对磋实辩，软安对，数及尽 力u 衙为的斑用进行区分，瓣不葡静应掰按一定静策略分配c p u 帑宽。硬实辩任务敖 在实时内核中处臻，献而傺证它优先执行。对软实对任务控制箕占用c p u 豹时闯魄 例可保证酱通的分时任务不会饥饿，对软实时任务采用接入控制并对其占用c p u 的 时间比例按死线丢失的情况进行修正，从而保证软实时任务的q o s 。 为了验证统一调度框架的有效性，采用u m l 对操作系统中进程调度这一核心 问题构建康拟仿真平台。采用这种基于虚拟与仿真技术的设计和研究方法可以方便 的验证和修改新的策略。本文以虚拟时间为驱动，以任务为调度的基本对象，以随 机数发生器生成系统负载构建了仿真系统。并分蹦对基本的实时调发算法r m a 、分 时调度算法多级反馈循环调度算法进行测试。实验表明，系统负载大于o + 6 9 时，r m a 调度中开她有死线丢失。随繁实验时间的变长，多级反馈循环调度中的任务分得的 c p u 对闯趋囱于一致。对3 3 节巾的调发策赡进露测试，实验表骧：硬实射任务季孽 到了饯先技行，营速强务能获撂一定熬c p u 眩瓣，不会钒饿，弗保证了敦实酵程务 的q o s 要求。 关键谣：软实辩，硬安嚣寸，调度策路，u m l 建禳 塑塑态主堡主望些兰基三一爨签鲎笪墨塑墨蹩整缝塑蔓- a b s t r a c t t h ee l a s s i c a l 鲑1 烨s e0 s b a sn o ts a t i s f i e dt h ed e m a n d o f c o - e x i s t e n c eo f h a r d r e a l _ t i m e a p p 珏c a t i o n s , s o f tr e a l t i m ea p p l i c a t i o n s a n d g e n e r a la p p l i c a t i o n s s od e v i s i n g s c h e d u l i n gp o l i c y w h i c hp r o v i d e su n i v e r s a ls u h s i s t e n c ef o r a l lt y p e so f a p p l i c a t i o n si st h eh o ts p o ti nt h er e s e a r c h o f m o d e r no s t h i sp a p e rs t u d i e st h es c h e d u l i n gm e c h a n i s m so fl i n u x ，u n i xa n dw i n d o w s n to sa n d d o i n t st h e i rs h o r t c o m i n g s a tt h es a m et i m e ，t h ea r t i c l ea n a l y s e sc l a s s i c a lp o l i c ya n ds c h e m e w h i c hs u p p o r tr e a l t i m ea p p l i c a t i o ni no ro u to fc h i n a r t l i n u xp r o v i d e sh a r dr e a l - t i m ef o r p r e f e r a b l es u p p o r t ，t h e a r t i c l ea n a l y z e si ta n df i g u r e so u ta no u t l i n eo f as c h e d u l i n gm e c h a n i s m i td i f f e r e n t i a t e sh a r dr e a l t i m e ，s o f tr e a l t i m ea n d b e s t e f f o r ta p p l i c a t i o n sa n ds u p p l i e sd i f f e r e n t a p p l i c a t i o n sf o rc p u s b a n d 淅d t ha c c o r d i n gt ot h e i ro w np o l i c y h a r dr e a l - t i m ea p p l i c a t i o n sa r e e x e c u t e dw i t hap r i o r i t yb e c a u s eo fi t sp r o c e s s i n gi nr e a l t i m ek e r n e l t h ec o n t r o lo ft i m er a t i o s h a r e db yc p uf o rs o f tr e a l - t i m et a s k sc a nk e e pg e n e r a lt i m e - s h a r i n gt a s kn o tt os t a r v e f u r t h e r , t h ea c c e s sc o n t r o lo fs o f tr e a l t i m et a s k sa n dt h em o d i f i c a t i o no fc p u st i m e s h a r i n gr a t i o a c c o r d i n gt ot h ed r o p p e d d e a d l i n eg u a r a n t e e st h eq o sd e m a n do fs o f tr e a l t i m et a s k t h e r e f o r e ， i te n s b r e st h a tt i l et a s k so fh a r dr e a l - t i m ed on o td r o pd e a d l i n e ，g u a r a n t e e st h eq o sd e m a n do f s o f tr e a l - t i m et a s k sa n dd o e sn o ts t a r v ec o m m o nt a s k s i no r d e rt ov e r i f yt h ev a l i d i t yo f s c h e d u l i n g p o l i c y , w ed e s i g n av i r t u a ls i m u l a t i o n s y s t e mf o r t h ep r o c e s ss c h e d u l i n go fo sb yt h eu s eo fu m lm e t h o d i nt h i sa r t i c l e ，w ed e v i s et h e s i m u l a t i o ns y s t e mt a k i n gv i r t u a lt i m ef o rd r i v e r , t a k i n gt a s kf o rt h et m d e r l y i n gs c h e d u l i n g o b j e c ta n dt a k i n gr a n d o mp r o d u c e rf o rp r o d u c e ro fs y s t e ml o a d 。 s i m u l t a n e o u s l yw e t e s tt h e r v i aa n dr o u n dr o b i nw i t h m u l t i p l ef e e d b a c ki nt h eu n d e r l y i n gr e a l * t i m es c h e d u l i n ga l g o r i t h m w et e s tt h er m aa n dr o u n dr o b i nw i t h m u l t i p l ef e e d b a 呔扭掇es i m u l a t i o ns y s t e m w h e nt h e s y s t e ml o a d o v e r0 6 9 ，t h e r ea r ed e a d l i n e d r o p p i n gi nt h er m as c h e d u l i n g w i t ht h et i m eg o i n g 壤t h et a s k si nt h er o u n dr o b i nw i t hm u l t i p l ef e e d b a c k g e ta p p r o x i m a t et i m e w et e s t s c h e d u l i n gp o l i c yi nt h e3 3 ，t h er e s u l ts h o wt h a tt h es c h e d u l i n gp o l i c yi n3 3e n s u r e st h a tt h e * a s ko fh a r dr e a l - t i m ed o e sn o td r o pd e a d l i n e ，g u a r a n t e e st h eq o sd e m a n do f s o f tr e a l - t i m e t a s k sa n dd o e sn o ts t a l v ec o n 鞠o n t a s k s k e y w o r d s ：s o f tr e e l - t i m e ，h a r d r e a l - t i m e ，s c h e d u l i n gp o l i c y , m o d e l i n gw i t hu m l n 潦惫大学颤士学经论文：现代撵俸笨统调度镱略研究 现代操作系统调度策略研究 硕士生：刘钰峰 指导教师：李仁发教授 ， 专业、年级：计算机科学九九级 摘要 隧着诗舞撬经筑帮可靠牲静不断挺裔，其瘦用已深入到入类丰主会的各个领域。 矮实对、软实对藕酱逶分时任务的并存要求操佟系统能对它稍提供统一的支持。传 统的逶蠲操作系统的设计艨怒是优仡系统的平均功能，这与实时应用的要求响应的 有界性和可预测性辐矛盾。因诧，研究对各种应用旋供统一支持的操作系统成为热 点，两调度策珞更避研究的重点。 本文对u n i x ，l i n u x 和w i n d o w sn t 等通用操作系统的调度机制进行研究， 并指出萁在实时环境下的不足。分析了国内外对实时应用支持的经典策略和方案。 r t l i n u x 能对硬实时应用提供较好的支持，本文对其进行分析，并提出一种调度框 架，利用陵椴架对硬实时，软实时，以及尽力而为的应用进行区分，对不同的应用 按一定的策略分配c p u 带宽。从而保证硬实时任务不会丢失死线，软实时旺乌的 q o s 得到保证，普通任务不会饥饿。用u m l 对实时操作系统中的进程调度这一核 心问题进行建模设计了一个调度策略的仿真平台。研究开发人员可以利用该平台测 试评价调度策略和算法。 第一囊绪论 本章对调度的基本问题进行概要性说明，特别是分绍了在实时调度领域嚣用魄 基于时间的静态表调度、发生率单调算法和最早截止优先算法。并分绍了多媒体滚 的特点及其对调度策略的影响。同时，介缨了在硬实时、软实孵秘普逶分对 ；至务莠= 存的环境下统一调度鲍支持策嚷。 第二耄通用操佟系统调度策略分析 曩蔫遴建躲操佟系绞寿u n i x 、l i n u x 秘w i n d o w sn t 等。本章分车厅这些系统 谖度繁咯她特点及冀对实孵应用黪支持策路。并指爨，遁焉操作系统的应用环境一 般是交互式环境，英设计豹蟊标往往怒优化系统的平均性能，在保证弼户和系统交 互速凌酌萋礁主按公平静琢剐进行调瘫，傈诞系统中的所有用户、所有进程都能按 一定静院例分享c p u 。雨实时迸程要求桶应的有界住和可预浏性，往往要求优化 系统的最环情况。避而指出通鞠操作系统在实时环境中存在的问题。 湖南大学硕十学位论文：现代操作系统调度策略研究 第三章实时调度策略的研究与改进 本章首先介绍了实时调度研究概况。着重分析了r t - l i n u x 对硬实时应用的支 持策略，并在此基础，卜提出了一种新的调度策略，由于采用r t - l i n u x 作为基本系 统，这样能较好地解决硬实时任务优先响应的问题。设置一个随机数发生器，产生 的随机数落入软实时的范围则调度软实时进程，否则调度普通进程，这种方案既能 保证软实时进程所占的比例，又能保证普通进程不会饥饿。并在对软实时进程占用 c p u 份额采用修正方案，这样能在软实时进程丢失死线率增加时增大软实时占用 c p u 的份额，从而减少丢失死线率，从而使软实时任务的q o s 得到保障。 第四章实时操作系统仿真环境的u m l 建模 为了对经典的调度算法及第三章提出的新的调度算法进行测试，采用u m l 对 操作系统中进程调度这一核心问题构建虚拟仿真平台。建模过程中以虚拟时间为驱 动，以任务为调度的基本单位，以随机数发生器生成系统负载构建了个仿真系统。 采用这种基于虚拟与仿真技术的设计和研究方法可以方便的验证和修改新的策略， 而且研究周期短，费用低。 第五章实验结果与分析 本章采用仿真系统分别对基本的实时调度算法r m a 、分时调度算法多级反馈循 环调度算法进行测试。实验表明，系统负载大于0 6 9 时，r m a 调度中开始有死线 丢失，随着实验时间的变长，多级反馈循环调度中的任务分得的c p u 时f b j 趋向于一 致。对3 3 节中的调度策略进行测试，实验表明：硬实时任务得到了优先执行，普 通任务能获得一定的c p u 时间，不会饥饿，并保证了软实时任务的o o s 要求。 结束语( 略) 参考文献( 略) 致谢( 略) 答辩时间：2 0 0 2 年4 月 塑妻奎兰堡主兰些堡苎：墨垡堡堡墨竺塑廛苎堕受塞一 第一章绪论 1 1 引言 随着计算机性能和可靠性的不断提高，其应用已深入到人类社会的各个领域。 从军用高技术装备到信息家电，从通信设备到医疗器械，从工业控制到智能仪器，处 处都需要计算机。随着应用领域不断拓宽，计算机中的应用程序越来越复杂，类型也 越来越多。 在工业控制系统、c i m s 系统和实验仪器的监控管理系统中要求计算机能对各种 外部、异步事件作出立即反应，这一类应用对时间十分敏感，要求系统必须在一定的 时间内作出反应，否则后果不可预测。这一类应用可称为硬实时应用( h a r dr e a l t i m e a p p l i c a t i o n s ) 。 目前，视频压缩和通信技术发展迅速，出现了大量的多媒体应用( 如：音频和视 频会议、远程教育、虚拟现实、v o d 等) ，视频和音频应用要求连续的播放帧，它们 计算结果的正确性与时间相关。因此，这类应用对存储、传输和处理机子系统都有 实时要求。更确切的说，它们要求操作系统以一种可以预测的方式来分配c p u 、网络 带宽、磁盘等资源，从而提供q o s 保证( 如：吞吐量、死线丢失率等) 。与硬实时应 用不同的是，偶尔的帧丢失是可以允许的，它们只要求从概率上保证数据处理在限定 的时间内完成。这一类应用可称为软实时应用( s o f t r e a l - t i m ea p p l i c a t i o n s ) 1 10 除此之外，还有大量的传统应用( 如w w w ，f t p 、t e l n e t 等) 对时间并不敏感，这 一类应用可称为尽力而为的应用( b e s t - e f f o r ta p p l i c a t i o n s ) 。 传统的操作系统的应用环境是多用户多进程的分时环境，其设计原则是公平性， 要求保证系统中的每个任务都能得到相应的份额，即优化系统的平均性能，而实时任 务要求优化系统的最坏情况，两者相矛盾。因此，如何在操作系统中对硬实时，软实 时以及尽力而为的应用程序提供有效支持，并最大限度的利用c p u 资源成为研究热 点。而调度策略更是研究的关键问题。对调度策略的研究主要包括：1 如何提供对硬 实时、软实时和尽力而为应用的统一支持，其研究的重点是如何公平的分配c p u 带宽。 2 如何在提高c p u 利用率的基础上满足软实时进程的q o s ，主要是保证算软实时的 死线丢失率在一定的范围内。3 如何保证硬实时的死线绝对不会丢失以及如何提高操 作系统的响应时间。 塑塑查堂塑主兰些丝塞! 墨垡塑堡墨堕塑鏖苎堕墅壅 1 2 操作系统调度策略研究概况 1 2 1 调度的基本概念 像内存和终端一样，c p u 也是一个共享的资源。系统中的许多进程都争用c p u 。 操作系统必须决定在所有进程之间分配c p u 资源。调度器作为操作系统的一个组成部 分，它决定在任一时刻哪个进程去运行，以及这个进程能运行多长的时间。对调度器 的研究集中在两个方面。第一个是策略，即决定哪个进程运行及什么时候切换到另一 个进程的规则；第二个是实现，即实现这种策略的数据结构和算法1 2 】。 进程调度有非剥夺( n o i l p r e e m p t i v em o d e ) 和剥夺( p r e e m p t i v em o d e ) 两种基本方式 1 3 。非剥夺方式规定，调度器一旦把c p u 分配给进程后便让它一直运行下去，直到进 程完成或发生某事件而阻塞时，才把c p u 分配给另一进程。这种方式的缺点是：1 ： 一个紧急任务到达时，不能立即投入运行，以至耽误时机。2 ：若干个后到的短作业， 须等待长作业运行完毕，导致短作业的周转时间增长。剥夺方式规定，当一个进程正 在运行时，系统可以基于某种原则，剥夺分配给它的c p u ，将之分配给其它进程。剥 夺的原则通常有1 ：优先级原则。2 ：短作业优先原则。3 ：时间片原则。目前，绝大 部分操作系统都采用剥夺方式。 调度策略视c p u 为系统中的种资源，进行调度时应考虑的主要原则有【4 】： 1 公平确保每个进程获得合理的c p u 份额。 2 有效一尽量使c p u 百分之百地忙碌。 3 响应时间使交互用户的响应时间尽可能短。 4 周转时间使批处理用户等待输出的时间尽可能短。 5 吞吐量使单位时间内处理的作业数最多。 而实时系统指的是实时应用程序结果的正确性不仅与计算的逻辑结果有关，而且 与结果产生的时间相关，即数据处理必须在一定的截止期限内完成，否则，实时应用 程序产生的结果是毫无意义的。 因此在实时应用越来越广泛的情况下，调度策略还应考虑： 6 实时性- 保证实时任务在截止期限内完成。 1 2 2 基本的调度策略 基本的调度策略有静态优先权法，动态优先权法，时间片轮转法三种【3 1 。 静态优先权法在进程创建时按进程执行任务的轻重缓急确定每个进程的优先级， 2 塑妻查差婴主兰些堡奎! 墨垡苎堡墨竺塑壅篁堕堡塞一 并且在进程运行过程中不再动态的改变优先级。静态优先权的确定方法通常是：l ： 按进程的内容确定。2 ：按作业要求资源的类型和数量确定。3 ：按作业递交的时间次 序确定。4 ：按用户的类型和要求确定。 静态优先权法实现简单，但是不能反映系统以及进程在运行过程中发生的各种变 化情况。动态优先权法则克服了这种缺陷，在进程运行过程中可以根据变化的情况不 断调整进程的优先级，因此能获得较好的效果。在动态地确定进程优先权时，同样要 考虑前述一般原则，但实施起来可以更加精确。例如，一个进程执行不同的程序段有 轻重缓急之分，动态优先权法可以不断调整该进程的优先级，使之发生相应的高低起 伏。 时间片轮转法规定由各个就绪进程顺次轮流使用c p u ，且每次使用的时间长度一 般为一定值，这种时间长度称为时间片。如果一个进程运行了一个时间片之后还没有 结束，则进入就绪队列末尾，等待下一轮循环。如果由于等待某种事件，进程没有用 完时间片就进入睡眠状态，则当它被唤醒后可按其时间片中未用完部分的值插入就绪 队列的某个位置。这种方法的优点是各进程能比较均衡的共享使用c p u ，因此适用于 分时系统。 1 2 3 基本的实时调度策略 1 2 3 1 基于时间的静态表调度8 在硬实时系统中，任何丢失死线的行为都是不能允许的。因此往往采用静态表调 度。首先对给定任务的时间特性进行分析并产生固定的调度表。任务执行时，根据该 表决定调度任务的执行顺序、执行时间、开始和完成时刻，并且进程执行顺序都是固 定的，不允许抢占。如果任务为t l ，t 2 ，t 3 ，t n ，周期为t 1 ，t 2 ，t 3 ，t n ，表的覆盖长度应 至少为所有任务周期的最小公倍数。如果任务之间非独立，具有前趋、互斥、同步、通 信等约束条件时，则调度是n p 难问题。需要采用启发式算法，通常是采用分支和有界 搜索算法寻找可行的调度 静态调度表的优点是可预测性高，运行时的调度开销小，使用于简单但安全性极 高的系统缺点是在线调度不灵活，所有任务执行顺序必须严格的按事先制订的调度 表来进行。当任务数或任务特性发生改变时，必须修改整个调度表，因此很难处理突 发情形。 1 2 3 2 发生率单调算法( 砌吣 塑堕查兰堡主兰些丝苎! 翌垡塑竺墨丝塑堡茎堕里塞一 r m a 和e d f 是l i u 和l e i l a n d 在1 9 7 3 年提出的基本的实时调度算法【6 】 针对的任 务为t i ( p i ，c i ，d i ) 模型，即任务的周期为p i ，计算时间为c i ，截止时间为d i 。任务在每 个周期起点释放，高优先级任务可抢占低优先级任务执行。 r m a 为每个进程分配一个与事件发生频率成正比的优先级，即任务的周期越小， 优先级越大。例如，周期为2 0 m s 的进程优先级为5 0 ， 而周期为l o o m s 的进程的优 先级为1 0 。运行时，调度程序总是调度优先级最高的就绪进程，必要时可以剥夺当前 进程。 l i u 和l e i l a n d 已证明，如果任务集满足下式，则任务集可调度 c i p i + c 2 p 2 + + c i p i + c n p n p o l i c y ! = ；s c h e d o t h e r ，i l r e t u r n1 0 0 0 + 1 3 - a _ p r i o r i t y ； w e i g h t = p - c o u n t e r ； r e t u m w e i g h t ； 系统遍历可运行队列，用g o o d n e s s o 计算每一个可运行进程的度量值，选择 g o o d n e s s ( ) 返回值最大的进程运行。由于实时进程是1 0 0 0 + p - g _ p r i o r i t y ，总是大于非 实时进程，故保证了实时进程的优先运行，而r t _ p r i o r i t y 起到的是在实时进程之间区 分优先级的大小。 l i n u x 采用了简洁的调度设计，巧妙的保证了实时进程的优先执行，而非实时进程 按公平的原则进行分时调度。这种简单的设计在大多数情况下都能保持较好的性能， 但面对实时任务和普通任务并存的环境，它和s v r 4 存在同样的问题。 2 4w i n d o w sn t 调度分析旺卵 n t 中基本的调度单位是线程，它支持3 2 个线程优先级，0 优先级由系统专用等 待线程使用，l 1 5 给普通线程使用，1 6 3 1 给实时线程使用。 n t 的调度策略较为简单，通过s e t t h r e a d p r i o r i t y ( ) 可以生成线程的初始优先级，初 始优先级落在1 6 3 l 的称为固定优先级线程，初始优先级落在l 1 5 之间的称为可变 优先级线程。处于固定优先级的实时进程无论处在用户态还是内核态都保持优先级不 变。对于处在l 1 5 的可变优先级线程，它在用完时间片时降低优先级，在挂起后又 再次就绪时升高优先级，在内核态运行时也可升高优先级( 但不会超过1 5 ) 。 n t 为每个优先级设置一个就绪队列，新的可运行线程被挂在就绪队列后面，如果 塑塑盔堂堡主兰些丝壅! 墨垡塑笪墨塑翌堕望竺墅型堕一 线程没有用完时间片就被剥夺则仍放在队列前面。调度的规则是选择高优先级的线 程，如果同一优先级的线程有多个，则选择就绪队列最前面的。 与s v r 4 比较，n t 内核中没有设置抢占点，当线程运行在内核中时，如果不产生 硬件中断，高优先级的线程是无法抢占低优先级的进程。因此n t 对实时响应的效果 要比s v r 4 还差。 2 5 通用操作系统在实时环境中的问题 以上分析了几种通用操作系统的调度策略，可知，目前通用操作系统的应用环境 一般是分时和交互式环境，其设计的目标往往是优化系统的平均性能，在保证用户和 系统交互速度的基础上按公平的原则进行调度，保证系统中的所有用户、所有进程都 能按一定的比例分享c p u 。虽然在s v r 4 、l i n u x 和n t 中都实现了对实时进程的支持， 但都是简单地把实时进程的优先级设为最高，优先执行实时任务，这样依然存在许多 问题。 通用操作系统对实时应用的支持主要存在以下问题： l ：没有区分硬实时和软实时应用。硬实时对时间要求苛刻，而软实时允许在一定 概率内丢失死线。如果系统按硬实时定制，会导致浪费大量系统资源。按软实时定制 系统，则硬实时应用也可能丢失死线。因此，应该对硬实时和软实时应用区分对待。 2 ：简单地把实时进程的优先级设为最高将会导致实时进程完全霸占c p u ，造成普 通进程饥饿。例如：2 4 在s v r 4 中进行了一个实验，在系统中并发地运行三个不同 的程序个交互式键入会话，一个批处理作业，一个电影图象演示程序。把电 影图象演示程序设为实时类，结果图象程序本身都不能很好的运行。原因在于播放图 象的x 服务器得不到足够的c p u 时间。如果把图象演示程序和x 服务器都设为实时 类，则图象演示能很好地运行，但交互式作业和批处理作业就几乎停止了，系统不能 响应鼠标和键盘。事实上，实时进程的实时性并不能说明其重要性就一定高于普通进 程。 3 ：一般操作系统的内核是不可抢占的。实时进程有可能阻塞于系统调用，对于硬 实时应用而言，会导致响应时间的不可预测性。同时，在系统中有可能因低优先级拥 有高优先级进程的资源，从而阻塞了高优先级进程的执行。 4 ：内存管理采用虚拟内存方式。如果一个实时任务换出内存，当再次调度它运行 时，必须首先经历一个时间不确定的换入过程，实时任务响应时间不确定。因此，有 必要研究优化实时响应的内存管理方式。 l 湖南大学硕士毕业论文：现代操作系统调度簟略研究 5 ：访问临界区时，中断可被屏蔽。这将影响系统对时间确定性的保证。 本文研究的对象是调度策略，因此，本文的剩余部分主要针对第1 、2 点展开， 对第3 、4 、5 点不作过多讨论。 塑塑查兰堡圭望些丝奎：墨垡堡笪墨竺塑堡苎堕堕壅一 第三章实时调度策略的分析与改进 3 1 引言 通用操作系统无法满足当前实时应用的要求。因此有必要研究新的调度机制，甚 至是新的操作系统体系结构以适应当前硬实时、软实时和普通应用任务并存的环境。 本章首先研究了当前对实时应用支持的一些典型实例，对r t - l i n u x 进行了较为详细的 研究，该系统能对硬实时任务提供较好的支持。并在此基础上提出了一种能对硬实时、 软实时普通应用统一支持的框架，利用该框架，硬实时任务的响应时间短且可预测， 软实时任务能从概率上保证其死线不会丢失，普通进程不会饥饿。 3 2 实时l in u x 专用的实时操作系统能对硬实时提供较好的支持，但它们没有对软实时进行考虑。 并且作为专用系统，往往缺乏足够的应用支持，同时价格也相当昂贵。因此，如何利 用通用的操作系统进行改造，使其能较好地支持硬实时应用成为研究的热点。而l i n u x 又因其源代码开放，具有通用系统的所有功能，应用支持丰富获得人们的青睐。 r y - l i n u x 可以说是所有r e a l t i m el i n u x 的鼻祖。它目前已经发展到3 0 版。这个 系统是由v i c t o r y o d a i k e n 和它的学生m i c h a e lb a r a b a n o v 所完成【2 5 1 【26 1 。r t - l i n u x 在 l i n u x 内核和硬件之间加入一个实时内核，把整个系统分为三个空间，用户空间，l i n u x 内核空间和实时内核空间，实时任务运行在实时内核空间。它的设计思想主要有以下 四点： 1 ：当有实时任务要处理时，实时内核就会运行此实时任务，如果没有实时任务， 则实时内核会调度原有的l i n u x 内核运行，因此，在r t - l i n u x 中，实时任务的优先级 总是高于其它任务。而l i n u x 内核是实时内核的最低优先级的任务，可以被其他实时 任务抢占，这样避免了实时任务因l i n u x 内核运行而造成的不必要的等待。而非实时 任务运行在用户空间，它们的优先级更低。它的调度示意图见图3 1 。 2 ：为了互斥地访问邻界区，l i n u x 在进行临界区操作时屏蔽相应的可屏蔽中断， 这种方法的效率往往高于使用信号量互斥。但同时，屏蔽中断也抑制了系统及时响应 外部事件的能力。为了解决中断延时大的问题，r t - l i n u x 采用在l i n u x 内核和中断控 制硬件之间增加一层仿真软件的办法，将l i n u x 源代码中所有的c i i 、s t i 、i r e t 指令分 1 6 塑妻查堂堡主兰些丝苎! 墨垡苎堡墨竺塑廛堡堕堡壅一 别用仿真宏s _ c l i 、s s t i 、s - i r e t 替换，这样所有的硬件中断都能被实时内核中的 仿真器俘获。在r t - l i n u x 中由实时内核来处理系统的所有中断，实时内核区分实时中 断和非实时中断。如果是实时中断，则转入实时中断句柄进行处理。如果不是实时句 柄或存在的实时句柄要求l i n u x 句柄的参与，则在相应的数据结构中加以标记，当 l i n u x 内核运行时再从相应的数据结构中获取中断信息进行处理。这样，实时任务不 会因为l i n u x 对中断的屏蔽而导致无法及时响应外部事件。 3 ：由于l i n u x 内核和用户进程处在不同的运行级别，用户进程使用系统调用进入 内核时所需的开销太大。对此，r t - l i n u x 利用可调入模块把实时进程的数据采集和工 作调入系统内核，和内核处在同一个地址空间，这样就避免了切换开销太大的问题。 4 ：为了方便实时进程和其它用户进程通讯，实时内核采用简单的f i f o 缓冲区和 用户进程通讯，为了和u n i x 的i p c 机制相区分，可称之为r t - f i f o 。为了避免优先 级翻转问题，r t - l i l o 的读写操作被设计成原子操作从而不能被阻塞。从用户进程的 角度来看，r t - l i l o 缓冲区作为普通的字符设备，可以利用系统调用r t f i f oc r e a t e ( ) ， r t f i f o d e s t r o y ( ) ，r t f i f o g e t ( ) ，r t f i f o _ p u t o 对其进行操作。在r t - l i n u x 中的数据流图如 图3 2 所示。 图3 1r t - l i n u x 图3 2r t - l i n u x 数据流图 根据以上分析，r t - l i n u x 对硬实时能提供较好的支持，事实上，有实验表明1 2 7 1 ， r t - l i n u x 能很好地支持要求响应时间在十毫秒级的硬实时应用，如果把定时芯片如 8 3 4 5 设成终端中断记数方式( i n t e 删p t - o n - t e r m i n a l - c o u n t ) ，则可以达到毫秒级的精度。 其它典型的实时l i n u x 有r t a i 、k u r t 和r e d l i n l l ) 【。 r t a i ( r e a l - t i m e a p p l i c a t i o ni n t e r f a c e ) 是一套可以用来写实时应用程序的界面。它 1 7 塑堕查兰堡圭兰些笙奎! 墨垡塑堡墨竺塑堡丝堕塑茎一 同样直接用可加载式核心模块( 1 0 a d a b l e k e r n e lm o d u l e ) 作为实时进程。每一个实时进 程实际上就是一个可加载式核心模块。r t a i 和r t - l i n u x 最大的不同地方在于它非常 小心的在l i n u x 上定义了一组r t h a l ( r e a l - t i m e h a r d w a r ea b s t r a c t i o nl a y e r ) 。 r t h a l 将r t a i 需要在l i n u x 中修改的部份定义成一组程序界面，r t a l 只使用这组 界面和l i n u x 沟通。这样做的好处在于我们可以将直接修改l i n u x 核心的程序代码减 至最小，这使得将r t h a l 移植到新版l i n u x 的工作量减至最低。由于r t a i 无法直 接使用l i n u x 的系统调用，解决的方法是使用r t - f i f o 将一个r t a i 实时内核模块和 真正的l i n u x 进程连接在一起，由这个进程代理为其呼叫l i n u x 系统调用【2 8 】f 2 9 】。 k u r t 是由k a n s a s 大学所创造的系统，它和r t - l i n u x 及r t a i 有很大的不同。 k u r t 是第一个可以直接使用系统调用的实时l i n u x 。由于k u r t 只是简单的 将l i n u x 的调度器用一个很简单的时间驱动式( t i m ed r i v e n ) 调度器加以取代，实时进程 程的执行很容易受其它非实时进程的影响【2 9 1 。 r e d l i n u x 和k u r t 类似，是一个可以使用l i n u x 系统调用的实时l i n u x 。它的 特点是使用抢占点( p r e e m p t i o np o i n t ) 改善系统的反应速度。k u r t 的最大问题在于它 受限于原有的l i n u x 架构，使得系统的反应时间很难控制。然而在r e d l i n u x 这一点 已经被大大的改善，由在2 0 版的经验得知其反应延迟约在1 0 0u s 左右。r e d l i n u x 非 常有弹性的调度器架构也是其特点之一。它使得r e d l i n u x 可以符合各种不同复杂度 系统的需求。r e d l i n u x 吸取了k u r t 的特点，采用可适应性构架，将优先级、时间 调度和共享调度集成在一个系统框架中，不同的调度方法可以在不同的时间用在同一 应用程序中，这使得r e d l i n u x 能很好的基于应用来重新配置而无须修改复杂的低级 内核调度。基本上，它将调度器分成d i s p a r t c h e r 和a l l o c a t o r 二部份，d i s p a t c h e r 在核 心中执行而a l l o c a t o r 在用户模式执行。a l l o c a t o r 可以是应用程序的一部份，也可以是 一个独立的单位。通常它可能是中间件的一部分，负责将应用程序的资源请求转换成 内核可以了解的格式【2 9 1 1 3 0 1 【3 1 1 。 3 3 实时调度策略的改进 在r t - l i n u x 没有对软实时应用进行优化处理，只是简单的利用了l i n u x 中原有的 策略。而一般的调度策略不能对硬实时提供很好的支持，如 1 4 】【1 5 】在s o l a r i s 2 5 中实 现的d s r t 。在此，我们给出一种新的调度框架，在r t - l i n u x 中提供对硬实时、软实 时和尽力而为的应用的统一支持。调度框架设计的总体目标是：1 ：保证硬实时任务 的优先执行，因为它们的死线不能丢失。2 ：保证软实时任务的q o s 要求，允许在一 1 8 塑壹查堂堡主望兰竺丝塞! 墨垡堡笪墨竺塑堕苎堕堑壅一 定的概率范围内丢失死线。3 ：保证普通任务能获得一定的c p u 时间，不会饥饿： 3 3 1 调度总体框架 调度体系的总体结构如图3 3 所示。 图3 3 调度策略框架 采用分类调度的思想，对不同的应用采用不同的调度策略。系统为硬实时进程、 软实时进程和普通进程分别设置就绪队列。硬实时就绪队列由实时内核进行管理，如 果系统中有新的硬实时进程就绪，系统首先把该进程加入硬实时就绪队列，并把该进 程加入一个可以由实时内核和l i n u x 内核都可以访问的调度记录表，并计算出硬实时 任务总共需要c p u 的处理时间比例。然后由实时内核按e d f 调度硬实时进程。软实 时进程和普通进程的就绪队列由l i n u x 内核进行管理。软实时进程首先向接入服务器 发出申请，接入服务器进行接入控制，如果系统能满足此要求则记入调度记录表，并 计算出软实时任务总共需要的c p u 处理时间比例，同时把该进程加入软实时进程就绪 队列，否则要求用户等待一段时间再进行申请。如果是普通进程，则真接加入普通进 程就绪队列。进程加入就绪队列的分派图如图3 4 所示。 调度表用于记录系统中就绪进程的概况，其中的关键项是硬实时和软实时任务需 要的c p u 时间比例项。调度管理器负责为软实时就绪队列和普通进程就绪队列分派各 自的调度器。而硬实时任务的分派由实时内核完成。 1 9 塑妻查兰堡主兰兰竺丝壅! 墨垡堡笪墨竺塑星兰曼堑墨一 l 图3 4 进程派发图 3 3 2 接入服务器 对软实时任务的第一项工作是进行接入控制，由接入服务器完成。进行接入控制 的理由在于，当系统中的软实时任务太多时，无论使用何种调度算法都无法保证任务 的服务质量，因此，与其让系统中所有的软实时进程的运行质量都变得无法忍受，不 如保证已经就绪进程的运行质量。我们采用简单的接入控制策略。系统启动时由用户 输入软实时任务所能占用c p u 时间的最大比例f s 。然后，每次有软实时任务申请服 务时，首先由接入服务器检查调度表，如果调度表中分配给软实时进程的份额还能满 足此请求，则接受该进程并填写调度表，例如，在图3 5 中，如果分配给软实时的份 额为7 0 ，则还能接受一周期为8 0 毫秒，执行时间为1 0 毫秒的任务，并在调度表中 作记录。如果一个周期为4 0 毫秒，每次执行时间为1 0 毫秒的任务向它请求，由于 5 5 + 1 0 4 0 = 8 0 大于7 5 ，因此q o s 代理拒绝此请求，要求用户过一段时间再请求。 若设第i 个软实时任务的周期为t i ，执行时间为c i ，系统分配给软实时进程的份额为 f s ，系统已分给硬实时的份额为f h 则新的任务能被接受的条件是要满足 m i n ( 1 - f h f s ) c 1 t i + c 2 t 2 + + c i t i 接入服务器以守护进程的方式运行，象其它网络守护进程一样在系统引导时启 动，当有软实时请求时即可唤醒。接入服务器作为一个r o o t 进程运行在动态优先级， 塑妻盔兰堡主兰些堡塞：墨垡塑堡墨丝塑鏖丝堕里塞一 它并不进行实际的调度管理工作，它会在必要时f o r k 一个软实时类的调度管理密，由 调度管理器进行真正的调度管理工作。 3 3 3 调度表 调度表设计成可被实时进程和l i n u x 内核共同访问的共享内存对象。调度表首先 由实时内核来处理，实时内核只记录硬实对进程并计算出硬实时进程占c p u 时间的比 例，因此，我们称之为硬实时内核。l i n u x 内核把剩下的时间片分配给软实时进程和 普通进程，由各自的调度器进行处理。需要注意的是，调度表中记录的是已经就绪的 软实时进程占用c p u 时间的比例，而不是在接入控制中用户预定的软实时任务所能占 用的最大比例。调度表的示例见图3 5 类型实际己占用c p u就绪队列 的比例( )头指针 硬实时】5旧 软实时 5 5 叫互h 互k 普通 厂 厂= _ 厂= 图3 5 调度表示例 调度表中任务特征如下： 进程3 4 5 为硬实时进程，周期为1 0 0 毫秒，每次运行时需要的时间为1 5 毫秒。故 占用c p u 的时间为1 5 。 进程3 4 7 、3 4 8 、3 4 9 为软实时进程，周期分别为1 0 0 毫秒，2 0 0 毫秒，3 0 0 毫秒， 每次运行的时间分别为2 0 毫秒，5 0 毫秒，3 0 毫秒。故软实时进程占用c p u 的时间为 2 0 1 0 0 + 5 0 2 0 0 + 3 0 3 0 0 = 5 5 。如果有新的软实时进程加入就绪队列，例如一个周期为 3 0 0 毫秒，每次运行时间为1 5 毫秒的任务，则此时软实时进程实际占用c p u 时间的 比例应变为5 5 + 1 5