（计算机应用技术专业论文）空管系统实时调度策略研究及性能评估.pdf

四川大学硕士学位论文空管系统实时调度策略研究及性能评估专业：计算机应用研究生：徐丈清指导教师：扬红雨教授随着我国民航事业的发展，空中交通管制的需求越来越复杂，数据量也越来越大。为了适应巨大的数据量需求，目前的空中交通管制系统的系统结构可能会向集群系统结构发展。由于空中交通管制系统对可靠性和实时性的高要求，若转换成集群体系结构，“调度”势必将成为系统的一个重要的环节。调度策略是否能够满足实时性需求，是否能够满足离可信度需求，等等，都将是其是否适合该系统的关键问题。本文在分析提高系统实时性能方法的基础上，在研究现有实时调度策略的基础上，提出了一种基于三层调度器机制的调度策略。本文主要有以下几点内容：( 1 )分析了目前国内外多种提高实时性能的方法。简要介绍了操作系统的选择、操作系统内核的修改，多线程技术的使用和调度策略的采用这四种提高实时性能的方法。并经过a t c 系统特性的分析，得出：在a t c 系统中，适合在采用多线程方法的基础上，采取合适的实时调度策略。( 2 )分别介绍了现有的单处理机调度策略和多处理机调度策略，为后面提出自己的调度策略打下基础。其中所介绍的单处理机调度策略大部分都已经在作者发表的论文中进行过说明和实验的分析，都是高效的单处理机调度策略；多处理机调度策略都是众多文献认为最经典的几种调度策略。( 3 )在前面介绍的单处理机调度策略和多处理机调度策略的的基础上，提出了一种基于三层调度器机制的调度策略。并对各级调度策略进行了分析和说明，给出了各级调度策略的思路和实现方法。( 4 )探讨了评估系统实时性能的指标，给出了相应的评估方案。作者将三级调度器调度策略进行实验，并在文中所提的评估指标和评估方案的基础上进行了性能评估。证明了算法的低复杂度，高可扩充性，较强的实时性能和容错能力。关键词：a t c ，实时调度策略，处理机调度器，进程调度器，线程调度器，d a g ，优先级，性能评估i l四川大学硕士学位论文r e s e a r c ho fr e a l - t i m es c h e d u l i n gs t r a t e g yf o ra t cs y s t e ma n de v a l u a t i o no fi t sp e r f o r m a n c em a j o r ：c o m p u t e ra p p l i c a t i o ng r a d u a t e ：x uw e n q i n gw i t ht h ed e v e l o p m e n to fa v i a t i o n , t h er e q u i r e m e n to fa 1 阢( s t a n d sf o r a i rt r a f f i cc o n t r o l ) i sb e c o m i n gm o r ea n dm o r ec o m p l e x ，t h er e q u i r e m e n to fi t sc a p a c i t yi sb e c o m i n gl a r g e ra n dl a r g e r m a y b et h ea r c h i t e c t u r eo fc u r r e n ta 陀s y s t e mw i l lb ec h a n g e di n t ot h ed i s t r i b u t i n gc e n t e ra r c h i t e c t u r e i no r d e rt oa d a p tw i t ht h er e q u i r e m e n to ft h eh u g ed a t ac a p a c i t y a st h eh i g hq u a l i t y r e q u i r e m e n to f r e l i a b i l i t ya n dr e a l t i m ep e r f o r m a n c e 。t h es c h e d u l i n gw i l lb ea ni m p o r t a n tt a c h ei fi tc h a n g e si n t ot h ed i s t r i b u t i n gc e n t e ra r c h i t e c t u r e w h e t h e rt h es c h e d u l i n gs t r a t e g yw i l lb em e tw i t h t h er e q u i r e m e n to fr e a l t i m ep e r f o r m a n c e 。w h e t h e ri tw i l lb es a t i s f i e dw i t ht h eh i g hr e l i a b i l i t y t h e yw i l lb et h es t i c k i n g p o i n t st ot h ea 1 眨s y s t e m b a s e do nt h ea n a l y s i so ft h ee x i s t e dm o t h o d so fi m p r o v i n gs y s t e m sr e a l t i m ep e r f o r m a n c e ，a n dt h er e s e a r c ho ft h ee x i s t e dr e a l t i m es c h e d u l i n gs t r a t e g i e sa n da l g o r i t h m s ，t h i sp a p e rg i v e sas c h e d u l i n gs t r a t e g yo ft h r e e - l e v e l b a s e dm e c h a n i s n ti ti sr e l a t e di nt h ef o l l o 霄i n g4p e j ：t s ：( 1 ) a n a l y z e dt h ee x i s t i n gm e t h o d so fi m p r o v i n gt h es y s t e m sr e a l t i m ep e r f o r m a n c e ib r i e f l yi n t r o d u c e df o u rm e t h o d s ：c h o o s eap r o p e r l yo s ，m e d i f yt h ek e r n e lo f0 s ，u s et h em u l t i t h r e a d , a n du s et h es c h e d u l i n gs t r a t e g i e s b a s e do nt h ea n a l y s i so ft h ec h a r a c t e r i s t i c so fa 1 s y s t e m ,ie d u c e dt h a t ：i ti sf i tf o ru s i n gt h ep r o p e r l yr e a l t i m es c h e d u l i n gs t r a t e g yi nt h ea t cs y s t e m , b a s e do nt h eu t i l i t yo fm u l t i t h r e a d ( 2 ) i n t r o d u c e dt h ee x i s t i n g s c h e d u l i n gs t r a t e g i e so fs i n g l e - m a c h i n ea n d1 1 1四川大学硕士学位论文m u l t i - m e c h i n e t h i si st h e f o u n d a t i o n f o rb r i n g i n gf o r w a r dt h en e ws c h e d u l i n gs t r a t e g y t h es i n g l e - m a c h i n es c h e d u l i n gs t r a t e g i e si n t r o d u c e dh e r eh a v ea l m o s ta l lb e e ns p e c i f i e da n de x p e r i m e n t e di nt h ep a p e rt h a tw i l lb ea p p e a r e do nt h et r a n s a c t i o no fs i c h u a no n i v e r s i t y t h e ya r ea lle f f e c t i v e l ys i n g l e - m a c h i n es c h e d u li n gs t r a t e g y t h em u l t i - m a c h i n es c h e d u l i n gs t r a t e g i e si n t r o d u c e dh e r ea r ea 1 1c o n s i d e r e dt ob et h ec l a s s i c a lm u l t i - m a c h i n es c h e d u l i n gs t r a t e g i e s ( 3 ) b a s e do nt h es c h e d u l i n gs t r a t e g i e so fs i n g l e - m a c h i n ea n dm u l t i _ 1 m c h i n et h a ti n t r o d u c e da b o v e 。ib r o u g h tf o r w a r das c h e d u li n gs t r a t e g yo ft h r e e l e v e l b a s e dm e c h a n i s 飓a n a l y z e da n ds p e c i f i e df o ra l ll e v e l s a n dg a v et h et h i n k i n ga n dt h em e t h o do fi m p l e m e n t a t i o nf o ri t ( 4 ) i n t r o d u c e dt h eg u i d e l i n eo fe v a l u a t i n gt h es y s t e m sr e a l t i m ep e r f o r m a n c e ，a n dg a v et h ec o r r e s p o n d i n gs c h e m eo fe v a l u a t i o n ie x p e r i m e n t e dt h et h r e e - l e v e l - b a s e dm e c h a n i s ms c h e d u l i n ga l g o r i t h m , a n de v a l u a t e dt h ep e r f o r m a n c eo fi t ，u s i n gt h eg u i d e l i n et h a tii n t r o d u c e d c o m p a r i n gw i t ht h em e t h o du s e db e f o r e ，w ec o u l df i n dt h a tt h i ss t r a t e g yi so fr e a lu s e 。i tw a sl o wi nc o m p l e x i t y , h i g hi ne x p a n s i o n ，s t r e n g t ho fr e a l t i m ep e r f o r m a n c ea n dh i g h l ys u f f e r a n c eo fe r r o r k e yw o r d s ：a i rt r a f f i cc o n t r o l ，r e a l - t i m es c h e d u l i n gs t r a t e g y ，p r o c e s s o rs c h e d u l e r ，p r o c e s ss c h e d u l e r ，t h r e a ds c h e d u l e r ，d i r e c t e da c y c l i eg r a p h ，p r i o r i t y ，e v a l u a t i o no fp e r f o r m a n c ei v四川大学硕士学位论文1 引言1 1 论文背景1 1 1 实时系统概念所谓“实时”，是表示“及时”、“即时”；实时系统“1 是指系统能及时( 或即时) 响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有的实时任务协调一致地运行。在实时操作系统中必须存在着若干个实时任务，由它们反映或控制某个( 或某些) 外部事件，因而带有某种程度的紧迫性。实时系统产生和发展的动力来源于现实世界的实际需求。近年来，实时系统在航空航天、军事、工业控制、仪器仪表、信息家电等行业得到广泛应用。在实时系统中，系统输出的正确性不仅仅依赖于计算的逻辑结果，而且依赖于结果产生的时间。实时系统一个重要的要求就是系统必须在一个事先定义好的时限内，对外部或内部的事件进行响应和处理，这种事先定义好的时限称为截止期。实时系统中的任务根据对截止期的要求来分，可以分为：硬实时任务和软实时任务。根据任务对截止期的要求，实时系统可以分为硬实时和软实时( h a r dr e a l t i m ea n ds o f tr e a l - t i m e ) 系统。硬实时系统中的硬实时任务在不满足相应时限、响应不及时或反应过早的情况下都会导致灾难性的后果，因此，系统必须及时地对时间做出反应，绝对不能发生硬实时任务错过事件处理或超出截止期的情况。例如控制火箭发射系统、航空航天系统，如果没有对突发事件作出及时的处理，将造成巨大的损失；而在软实时系统中，在不满足相应时限时，系统性能退化，并不会导致灾难性的后果，因而当系统负载较高时允许发生少数事件处理错过截止期的情况，如交换系统。实时系统相对一般系统而言，时间是一个很重要的概念。在实时系统的设计中，必须把握好任务的执行，使之在截止时间之前完成。随着多媒体技术、嵌入式技术、移动计算机技术等的发展，计算机系统越来越需要面对个动态变化与不可预测的环境。如何在这种动态变化和不可预测的环境下，力求在规定的时间内完成事件的处理，并能够控制所有实时设备和实时任务的协调运行，给实时系统带来了前所未有的挑战。四川大学硕士学位论文目前的实时系统主要存在以下几个问题：a 使用于不可预测的环境，实时系统的某些模型参数，如最坏情况资源需求( w o r s t c a s e ) 这个模型参数，导致了系统资源的浪费：b 对于动态系统，假设的一些约束条件，如任务的截止期、周期，并非是已知固定的。因此，导致某些有关实时系统的研究一直处于实验室研究阶段，尚未投入正式应用；c 对于系统过载情况，实时系统性能迅速下降。这些问题的起因，大都与实时系统的调度策略有关。因此，设计大型系统时，有必要进行这方面的研究，以采取有效合理的调度策略，保证系统的实时性能。1 1 2 目前空中交通管制系统的构成空中交通管制的目的是对航空器的空中活动进行有效的管理，维护空中交通秩序，保障空中交通畅通，保证飞行安全和提高飞行效率，防止航空器相撞，防止机场及其附近空域的航空器同障碍物相撞。由于空中交通管制的重要性，国家投入大量资金，研制了空中交通管制系统( a t c ，以下简称a t c 系统) ，并已在国内某些地方投入使用。一个典型的a t c 系统主要包括以下几个子系统：飞行数据处理子系统、雷达数据处理子系统、人机界面子系统和系统监控子系统。其中，飞行数据处理子系统和雷达数据处理子系统是眼务器系统，分别处理飞行数据和雷达数据；人机界面子系统包括飞行数据显示控制席位和雷达数据显示控制席位，是前端显示系统，分别提供飞行数据和雷达数据的显示和操作界面；网络监控管理席位监视和控制着整个系统的网络情况。其基本框架如下：2四川大学硕士学位论文飞行数据显示iil 雷达数据显示操作席位| ifi控制席位( f d d )u l( s d d )飞行数据| | 雷达数据网络监控管理席位( s m p c )l a n飞行数据飞行数据处理服务器( f d p )主从机雷达数据处理服务器( s d p )主从机图i - i 系统基本框架图正如图卜1 中所示，为了保证系统的安全性，经常采用双冗余方式的服务器。两台飞行数据处理服务器，一个主机，一个备机( 或称从机) ，采用双机热备份的方式进行处理；两台雷达数据处理服务器也同样采用的双机热备份方式。这种双冗余备份的方式，是为了增强系统的容错能力，提高系统的可靠性而设置的。在这种双机热备份的服务器方式中，主服务器用于实际进行处理，而备服务器则只是保持与主服务器的同步，只有当主服务器出现故障时，才由备服务器进行实际的处理。也就是说，这种方式下，在一个时刻实际上只有一个服务器工作。因此，这种结构下，往往是主服务器一直相当繁忙，而备服务器则相对非常空闲。1 1 3 为空中交通管制系统选择合理调度策略的必要性近年来我国民航旅客量大幅度增长，民航体制改革取得重大突破。为适应国家经济社会发展的需要和建设民航强国的要求，中国民航总局提出将进一步建立新一代民用航空运输系统，并使中国民航的航空运输不仅在数量上有较大的提升，而且在质量上也有较大的飞跃。然而，在新的航空运输量下，对a t c 系统的数据处理量提出了新的要求。人机界面子系统的需求数量增多，需要处理的飞行数据量和雷达数据量都有相应的增加。双冗余服务器的结构由于实际只有一台机器处于工作状态，因而处理起来将会趋于紧张，甚至可能成为增加数据处理量的瓶颈。因此，有人提出了采用集群服务器的四川大学硕士学位论文方式，建立一个服务器集群体系结构，将飞行数据处理和雷达数据处理服务都分散到各个不同的服务器上进行。具体采用如下图的方式： 飞羹( 箨f d 需d 量) 示山l 雷萎( 蓍s d 墨d 量) 示i l jl 暑( s 篱m 篆p c 蓑) l l jf操作席位| | i控制席位i | ll管理席位| | lrirr】 飞行数据弘达数据礤墓鍪袭酉冒聩黧飞行数据处理和崮崮飞行数据处理和雷达数据处理雷达数据处理服务器( f s d p )服务器( f s d p )图i - 2 的这种集群服务器结构中，多台服务器参与实际的工作，即。将巨大的数据处理量分散到各个服务器上，使得同时有多台服务器同时处理相应的飞行数据或雷达数据，因而能够胜任新的需求下大量的数据信息处理量。并且，在集群服务器模式下，即使以后数据信息量再次增加，也只需要增加服务器数量即可解决。因此，目前看来，这种集群服务器结构的方案能够适应新的数据量的需求，不失为一种可行的解决方法。然而，集群服务器结构毕竟与双机热备份机制有很大的区别，以前的双机热备份基本上是由一台服务器处理数据，而另外一台服务器只需保持同步；现在的集群服务器模式下，所有的服务器都参与数据处理，因而必然会存在服务器之问的通信等诸多与以前不同的问题。它的引入将势必引起整个系统中相应调度策略的调整和变化，而双钆热备份下的调度策略不再适合于集群服务器结构中。因此，有必要对集群方式下整个系统的调度情况进行研究与分析，采用一种合理的调度策略应用到集群服务器结构中。4四川大学硕士学位论文1 2 论文的主要研究工作及其意义在不加任何条件限制的情况下，实时调度策略本身，特别是多处理机系统中的实时调度策略，其处理复杂问题时般都是n p 问题。这方面可做的工作有很多，目前国内外已经有很多关于实时调度策略方面的研究，但是这些研究大部分都停留在实验室的研究阶段，离真正投入应用还有定距离。如果兼顾所有的因素，将使调度问题变得异常复杂，导致失去使用价值。因此，很多调度策略的研究，特别是多处理机调度策略的研究，大都具有一定的针对性，对任务的初始条件等情况进行了一定的限制。由于a t c 系统本身存在极高的可信度要求，并且在已有的多处理机实时调度策略中，有的不适合本系统的情况，有的因为过于通用而相当复杂。因此，有必要对实时调度策略进行研究，针对a 1 系统本身的特性，研究并设计一种适合a t c 系统的实时调度策略，以提高系统的实时性能。一般情况下，实时系统中除了实时性能要求以外，还具有极高的可信度要求。实时系统可信度就是它完成任务所得结果的正确率。容错是当今确保可信度的有效手段，容错的手段主要在于冗余，主要的冗余容错方式有硬件冗余容错、软件冗余容错、时间冗余容错。而冗余的方式需要更多的通信时间和更多的辅助手段来保持信息的同步，这与实时系统对时间的严格要求多少有些冲突。因此，必然需要采取有效的措施，在保证实时系统高可信度的同时。也保证其实时性能。a t c 系统本身就是一个实时系统，并且它对系统的可信度要求很高，主要表现在对逻辑信息的可信度和对时间的可信度两个方面。对于逻辑信息的可信度，可以采用冗余备份方式，防止信息的丢失；采用可靠传输机制，以防信息的错误传输；等等。对于时间的可信度，则需要采用合适的方法提高系统的实时性能，通常的办法是采用合适的实时调度策略。因此，在a t c 系统体系结构发生变化的同时，在保证可信度的基础上，为保证a t c 系统的实时性能，对实时调度策略进行研究并在a t c 系统中加以合理应用不失为一个值得研究和讨论的课题。作者本人在攻读研究生期间，在川大智胜股份有限公司实习2 0 个月，参与了a t c 系统的测试以及飞行数据处理服务( f d p ) 子系统中的开发工作。其中，开发工作主要包括，参与f d p 调度程序的设计，负责译码组报程序的重新设计和开发。本文是作者在参与a t c 系统开发基础上，以飞行数据处理子系统( f d p ) 为实验基础，四川大学硕士学位论文重新对整个系统的调度框架进行探索性研究与实验，希望能适应将来数据量、通信量等越来越大的需求。本文所做的工作是实验性质的，并在f d p 服务器子系统中进行了实验，希望能为新一代的a t c 系统开发工作探寻一些有价值的方法和积累。1 3 论文各部分的安排本文分析了国内外多种解决实时问题的方法，研究了多种实时调度策略，分析了种适合于a t c 系统集群体系结构的实时调度策略。文章的组织分为五个部分，内容安排如下：第一部分为引言。介绍了论文背景和主要研究工作。第二部分，从介绍目前国内外已有的各种提高实时性能的方法入手，分析得出在a t c 系统中，采取合适的实时调度策略是种提高实时性能的有效方法，随后，分析比较了已有的多种单处理机和多处理机实时调度策略。第三部分，在分析本系统特性的基础上，提出了一种基于三级调度机制的实时调度策略，并对各调度层的调度方法进行了分析和阐述。第四部分，根据实时系统的特征，分析了评估调度策略实时性能的指标，提出一种评估方案。并对第三部分所提的三级调度机制的实时调度策略进行仿真试验，并根据本章所提的评估调度策略实时性能的方案，将实验结果与以前的调度方法下的程序运行情况进行分析比较，并给出实验结论。第五部分，对本文进行总结，并分析下一步的主要工作。6四川大学硕士学位论文2 提高系统实时陛能的主要方法目前国内外实时系统研究领域提出了很多用于提高系统的实时性能的方法。作者在老师指导下，研究了多篇论文、相关书籍和其它网上资料，并根据自己的实习经验，综合以前学到的知识，总结得出，提高系统实时性能的方法主要有以下几种：2 1 选择合适的操作系统2 1 1 实时操作系统实时操作系统是指具有实时性，能支持实时控制系统工作的操作系统。实时操作系统的首要任务是调度切可利用的资源完成实时控制任务，其次才是着眼于提高计算机的使用效率，其重要特点是要通过任务调度来满足对于重要事件在规定的时间内作出正确的响应。由于实时系统与一般的分时系统有着明显的区别，因此，在设计实时系统时，选择合适的操作系统是非常重要的。如果选择一个能够较好地支持实时性能的操作系统，在该操作系统上开发实时软件当然是一个保证软件系统实时性能的非常理想的选择。目前世界上比较有影响力的实时操作系统主要有q n x 软件系统有限公司的q n x 、v x w o r k s 、l y n x 实时系统公司的l y n x o s 、集成系统有限公司( i n t e g r a t e ds y s t e m s ，i n c ) 研发的p s o s y s t e m 、以及两种具有代表性的实时l i n u ) 【_ 新墨西哥工学院的r t - l i n u x 和堪萨斯大学的k u r t - l i n u x ：o n x 是g q x 软件系统有限公司开发的分布式、嵌入式，可规模扩展的实时操作系统，它遵循p o s i x 1 a 、p o s i x 1 b 和p o s i x 1 c 标准，并支持抢占式的，基于优先级的调度策略。它提供标准的u n i x 部件：编译器，调试器，x - w i n d o w s ，和t c p i p 。v x w o r k s 是专有的实时操作系统，采用主机目标机方式。一个u n i x 主机用来软件的开发和运行程序的非实时部分。个叫w i n d 的v x w o r k s 内核在目标机上运行实时任务。机器间的通信使用t c p i p 网络连接。它支持多任务、多线程的环境，并支持中断服务程序( i s r ) 。系统本身还提供了很多对任务进行操作和控制的函数，7四川大学硕士学位论文方便对任务的调度。l y n x o s 也是一个分布式、嵌入式、可规模扩展的实时操作系统，它由l y n x 实时系统公司开发，遵循p o s i y 。i ( 程序接口) 和p o s i l2 ( s h e l l 和工具) 、部分遵循p o s i x i b ( 实时扩展) 。目前还不是一个微内核结构的操作系统，支持硬实时优先级调度。p s o s y s t e m 是世界上最早的实时系统之一，也是最早进入中国市场的实时操作系统田。它是一个完全可扩展的嵌入式实时操作系统，包含单处理器支持模块( p s o s + ) ，多处理器支持模块( p s o s + m ) ，文件管理器模块( p h i l e ) ，t c p i p 通讯包( p n a + ) ，流式通讯模块( o p e n ) ，图形界面，j a v a ，h t t p 等。它的功能模块完全独立，开发者可根据应用要求扩展系统功能和存储容量。相比以上几种商业r t 0 s 而言，l i n u x 由于内核可剪裁性好、易于移植、源代码开放等优点而具备更广阔的发展空间。将l i n u x 改造成实时操作系统，是国内外计算机界的研究热点之一嘲。美国的v i c t o ry o d a i k e n 和m i c h a e lb a r a b a n o v 等人最早运用在原有的内核底层加载实时内核的方法实现了l i n u x 实时改造，开发出r t - l i n u x 实时系统，其实时性能达到微秒级，符合硬实时要求。后来p a o l om a n t e g a z z a 又在此基础上设计了实时性能更好的r t a i 。r t - l i n u x 在操作系统之下实现了个简单的实时核心，l i n u x 本身作为一个可抢占的任务在核内运行，其优先级最低，随时会被高优先级任务抢占，其支持基于优先级的抢占式调度和e d f 调度，对实时周期性进程的调度采用单调率算法。但这类双内核实时系统由于不能直接利用l i n u xa p i ，其在p c 机领域的应用前景受到限制，同时这类实时操作系统的可靠性、容错性和可维护性还有待提高。另一种改进方法是以u c l i n u x 为代表的嵌入式l i n u x ，有着极其广阔的应用前景，嵌入式l i n u x 本身并不支持实时调度，可以通过使用r t - l i n u x 的p a t c h 增强实时性能。目前嵌入式l i n u x 在实现过程中。2 i 2 一般州l x 操作系统如果不能采用以上所述的实时操作系统平台。并且所需开发的系统实时性要求不算特别高，则可以适当的选择一个适合于自己的操作系统进行设计。u n i x 操作系统就是一个不错的选择。8四川大学硕士学位论文s o l a r i s 提供了一个复杂环境来进行单处理机或多处理机的多线程实时处理。它对i 靴先级，有临界时间的进程的分配延迟进行了一些优化，使得其调度器非常适合于实时处理。其特征主要有m ：a 抢占式内核；b 多处理机的支持；c 隐式调度：d 优先级逆转；e 优先级继承的实现；f t u m s t i t l e 指针管理线程队列等。d i g i t a lu n i x 有三种调度策略：s 咖r ，s c h e d _ f i f o 和s c h e d r r 同。其中，s c h e d _ o t h e r 是普通的非实时进程，s c 脏d i n 和s r r 是实时进程调度策略。s c h e df i f o 是种简单的先进先出调度算法，它将系统中所有的任务组织成一个队列，先到先服务。可以对其进行修改设置，以选择适合自己的调度策略。传统u n i x 系统中的调度是基于优先级的。而且，进程也分为分时类和实时类。实时类进程使用的优先级比任何个分时进程甚至是内核态进程都高。也就是说，实时进程要在任何内核进程之前调度。一般来说，系统的默认调度策略为分时调度策略，用户可以对它进行配置，将其修改为实时调度策略。但是，在配置和使用实时调度策略时，必须相当谨慎旧。因为，首先，调度机构直接影响系统性能，系统缺省的分时调度策略是经过严格调整的，其性能是可以信赖的，但如果使用实时调度策略，系统的性能和反应时间将完全取决于实时进程本身；其次，在使用实时调度策略时，由于系统的杨心进程无法投入正常运行，所以如果实时进程本身有缺陷，就有可能导致整个系统的瘫痪。另外，在u n i x 操作系统内，也可以采用用户级模式管理线程们。以现有的系统调度管理为基础，本身并不作实际线程运行中的上下文切换等操作，只按照某种调度算法对线程的优先级进行动态设置和调整。然后利用系统固定优先级调度，交由系统管理进行实际调度。因此，这种调度程序运行的频率与系统本身运行的调度程序的频率相同。但是，这种调度方式完全建立在用户级基础之上，它的调度时间特性由系统的调度时间特性所限定，所以只能运用在系统实时性要求不高的软实时情况。9四川大学硕士学位论文2 2 改造操作系统内核如果实时性要求特别高，而q n x 、l y n x o 、r t - l i n u x 这类实时操作系统的基本系统管理功能又不能满足软件系统的需求。则需要对原有的系统线程调度程序进行改写，将实时线程插入到内核中，采用系统级上的线程绑定方式，使线程可以告诉内核它们的实时要求以获得实时响应。在微内核的改造中，主要考虑的问题有：首先，对时钟中断的修改。目前大多系统的时钟中断频率都是l o o h z ，即每l o m s中断一次。而强实时调度经常要求微秒级的性能，l o o h z 的中断频率显然不适合精确的强实时调度。如果实时性要求很高，有必要提高时钟中断的频率，将时钟改为以微秒为单位。但是，时钟中断频率高则中断频繁，也会很大的影响系统的性能。因此，最好的办法是修改时钟中断方式，使其可以在任何需要的时候以微秒级别中断，而一般情况下则仍是每l o m s 或者其它时间值中断一次。文献 8 中提供了一种可以使中断调度得到l 微妙左右的精度而系统开销最小的方式，即，使i n t e l8 3 5 4定时器芯片工作在i n t e r r u p t - o n - t e r m i n a l c o u n t 模式。其次，设计合理的调度方法，并将它集成到一个调度模块上。这样，可以按照应用程序的需求，选择合适的调度方法，由设计的调度程序直接管理系统内部实际的调度。再次，保证系统的可抢占性，确定合适的抢占时机。不仅可以在时钟中断时发生抢占，而且在其它必要的时候也要能够发生抢占目前，对操作系统的实时性改造方面的研究也很多，由于l i n u x 功能强大，源代码开放，支持多种硬件平台，模块化设计，并且函数接口符合国际和工业化标准。很多大学和研究机构提出了基于l i n u x 构建实时操作系统的一些方案和设想“：u n i v e r s i t yo fk a n s a s 计算机及电子工程系信息和远程通信技术中心研制的l ( u r t ( k a n s a su n i v e r s i t yr e a l t i m eo s ) ，它主要对理1i n u x 核心做了两点修改：& 修改时钟中断机制，将时钟粒度细化，并改变了时钟中断的固定频率模式，通过重新设定，使得时钟以微秒为单位，在任何需要的时候产生中断；b 增加新的实时调度模块，i ( u r t 核心有三种调度状态：普通态、实时态和混合态。r t - l i n u x ( 由n e wm e x i c oi n s t i t u t eo ft e c h n o l o g y 计算机系研制开发) 是一个基于t i n u x 的硬实时系统。它是基于通用分时系统核心构造的硬实时操作系统，其1 0四川大学硕士学位论文设计思想是：构造一个简单的硬实时内核，应用的实时部分作为实时进程直接运行在这个硬实时内核之上；原来的常规l i n u x 内核这时作为一个优先级最低的任务，也为这个实时内核所调度，应用的非实时部分作为非实时进程运行在l i n u x 核心之上，从而可以获得l i n u x 核心所提供的切服务。它采用的方式是：a 对l i n u x 核心进行改动，将其与中断控制器隔离，不再允许它任意关中断；b 修改了时钟中断机制；c 提供实时调度；d 实时进程与非实时进程之间进行通信。采用r t l i n u x 和r t a i 的双内核机制的优点是极低的中断延迟和转换时间，而且以种非常简单的方法实现了硬实时支持，使得实时应用程序的运行时间得到保证。美国r e d s o n i c 公司推出的r e d i c e - l i n u x 产品，整合了加州大学欧文分校的开放源码项目r i d - l i n u x 和r t a i 。其中，r e d - l i n u x 支持用户层的实时程序，而r t a l 支持内核层的实时程序。李小群等在l i n u x 核心2 2 1 7 上设计并实现了处理机预留资源、时钟粒度的细化、调度效率的提高、优先级继承协议( p i p ) 的支持、核心可抢占性、s m p 的支持、互斥锁机制的改进等多方面的实时支持功能嘲对l i n u x 的s c h e d u l e o 函数几乎进行了重写。例如，为了提高调度效率，进程就绪队列和实时定时器队列等都采用了堆的数据结构管理。2 3 使用多线程技术代替多进程随着线程技术，特别是多线程技术的产生，很多系统中都采用了多线程的技术。其主要原因在于：首先，传统的进程模型有两个严重的局限性不能较好的支持并行的编程模型：一个进程在某个时刻只能使用一个处理机，不能很好的利用多处理机体系结构m 。线程产生的动机就是为了解决这种传统进程模型的不足。其次，很多实时调度策略，特别是动态调度策略中，一般采用可抢占式调度，因而涉及到较多的上下文切换。由于进程在系统中存储的信息量比较多，进程创建和进程之间切换所需要花费的开销也比较大。如果将每一个任务都设置为一个进程，采用多进程的方式，则上下文的切换将会消耗大量时间和其它资源。而线程则不同，四川大学硕士学位论文它在系统中存储的信息量小。占用资源少，上下文切换快，花费的开销也比较小。因此，可以考虑使用多线程方式代替多进程方式，以减少系统中任务切换时多方面( 包括时间) 的开销。现在很多操作系统都支持线程机制，包括u n i x 和w i n d o w sn t 。也就是说，线程技术的使用基本上不会受到操作系统平台的限制。通常所指的线程( t h r e a d ) 主要有：l w p ( 轻型进程) 、核心线程、用户线程。其中，l w p 是用户请求核态程序生成并管理的线程：核心线程是由0 s 初始化时生成，或其它核心线程请求核态程序生成并管理的只运行核心态程序，只在系统空间访问的线程：用户线程是指使用s v r 4 2 m p 用户线程库所生成并管理的线程。操作系统本身还提供了个线程池，每次调用线程时从线程池中取出即可。有的操作系统又将称之为任务( t a s k ) 。但是它们都提供了对线程或者任务进行操作的函数，可以由用户对这些线程或任务进行合理控制，达到自己需要的效果。但是，采用线程技术必须考虑好共享地址空间的互斥问题，信号的传递和处理问题，以及线程的管理和调度问题等等。如果这些问题处理不好，不仅不能提高实时性能，反而可能影响系统的性能。因此，线程的使用也有很多需要小心和注意的地方。2 4 采用合适的实时调度策略调度程序( 或调度模块) 作为操作系统的一个组成部分，它决定在任给定时刻由哪个进程( 或线程、任务) 去运行。以及这个进程( 或线程、任务) 能运行多长时间。而在软件系统的设计中，为了能够主动控制系统中任务的执行顺序，也应该设计一个调度器，控制任务运行的先后次序和每次运行时间。调度器的描述主要集中在两个方面。方面在于策略，也就是决定运行顺序、每次运行时间及切换规则；另一方面在于实现，也就是实现这种策略的数据结构和算法。调度器的实现般是在调度策略研究和分析的基础上产生的。因而调度策略的研究不仅要考虑到程序本身的调度可行性、调度性能，而且还需要考虑该调度策略实现的可行性。一个再怎么完美的调度策略，如果是不可实现的，那么这个调度策略就是不可行的。现在国内外有很多对调度策略的研究，但是很多都是停留在实验四川大学硕士学位论文室的阶段，并不完全因为这些调度策略都不能解决实际的问题。有些调度策略，很大程度匕，是因为它们的实现过于复杂，考虑到的方面过多，因此不能在实际的程序中实现。调度策略要以系统的需求和系统的特点为依据。不同的系统需求和系统特征，对任务运行顺序、每次运行时间和切换规则的要求有所不同。因此，在设计一个软件系统时，如果没有必要，可以直接采用操作系统本身自带的调度策略；反之，如果有必要，特别是对于设计个实时操作系统而言，则需要设计适合自身的调度策略，以适应系统实时性能等多方面的需求。实时操作系统中都封装了实时系统常用的调度策略。有的实时软件系统设计中，也在原有操作系统的基础上，将适合自己实时软件系统的调度策略库封装成一个调度模块，并将其和系统原有的调度策略起置于操作系统层，或者是将其置于应用程序一级，作为应用程序的个模块。目前已有的实时调度策略有很多种，并且国内外有很多对实时调度策略的研究。包括对原有方法的改进，提出新的调度策略，分析某种调度策略的性能，对某些调度策略作可调度性分析，等等。本文的第三章将对已有的多种调度策略进行描述和分析。2 5a t c 系统提高实时性能的方法由于多线程代替多进程以及设计合适的实时调度策略的方法，都是提高实时性能的有效方法。并且很多实时调度算法中涉及较多的上下文切换，消耗大量时间和资源，而线程的上下文切换快，且线程占用资源少。因此，人们通常将这两种方法结合起来，考虑多个线程之间的调度问题，以提高系统的实时性能。考虑到a t c 系统中，用户对硬件本身及采用的操作系统的规定，加上其它各方面的原因。在a t c 系统中，适合在采用多线程方法的基础上，采取合适的实时调度策略。本文主要针对a t c 系统的特征，对实时调度算法进行研究，采用合适的实时调度算法，以适应a t c 系统在新的需求情况下，新的体系结构中的实时性需求四川大学硕士学位论文3 实时调度策略本文主要是针对a t c 系统，对实时调度算法进行研究和实验，以求找到适合a t c系统集群体系结构的实时调度策略。本章主要是对已有的实时调度策略的研究，根据作者多方面的研究和总结，分析了目前国内外已有的主要的实时调度策略，包括单处理机实时调度策略和多处理机实时调度策略。3 1 实时调度的基本概念实时调度是实时系统的时间确定性和可预测性的保证。实时调度的核心是资源分配，即如何分配资源以保证每个实时任务在正确的时段产生正确的输出n 硼。在这里，资源主要指处理机时间资源，合理地分配时间资源就是合理地安排就绪任务的运行j f 嗫序。本文将要用到的有关实时调度的主要概念，即一个任务的主要参数如下：任务：任务是调度的最小实体。静态地看，任务是实现确定功能的一段代码。动态地看，任务的一次运行，即从就绪到运行结束，被称为一个任务实例。周期：若一个任务的任意两个连续实例的就绪时间的间隔为固定值，则称之为周期任务，该固定值叫做周期任务的周期。时限：每个任务实例的最迟可接受输出时间被称为该实例的时限( 或截止时间、截止期限) 裕度：任务实例从当前时刻到时限时刻，除去估计执行时间以后所剩余的空闲时间；如果裕度小于0 ，那么该任务实例在本次时限内不可完成。估计执行时间：设定的一个估计值，或者动态地采集并更新的个时间值。价值：反应任务的执行与否、成功失败等情况对系统的影响大小。优先级：衡量任务当前执行重要性的一个值，通常情况下，优先级越高的任务越先得到执行。原始优先级：任务初始化时被设定的一个初始优先级。优先级天花板：为了防止优先级反转问题的出现而为每个任务设定的一个优先级值，任务的优先级不能超过该值。1 4四川大学硕士学位论文优先级抢占阈值：为了防止过多的任务间切换而为每个任务设定的一个附加的优先级值，该任务只能被超过该优先级抢占阈值的更高优先级任务抢占。成功率：任务执行成功的次数占总的执行次数的比率。3 2 实时调度策略分类根据实时系统侧重点的不同，实时调度策略有很多种分类方式，以下是一些常见的实时调度：5 1 - 类：3 2 1 单处理机调度和多处理机调度按照实时系统的规模，实时系统调度可以分为：单处理机调度和多处理机调度。其中，多处理机调度又可以分为集中式多处理机调度和分布式调度。单处理机调度需要考虑的因素最少，主要是对独立任务的调度，调度要考虑任务自身的特性，以及任务间的约束。多处理机调度，是指多处理机系统具有处理机间通信