（控制理论与控制工程专业论文）嵌入式linux的实时性分析与改进.pdf

武汉理工大学硕士学位论文 摘要 在数字信息技术和网络技术高速发展的带动下，嵌入式产业迅速崛起，成 为整个i t 行业的最亮点。在这种背景下，己经在服务器市场稳定了地位的l i n u x 在嵌入式领域脱颖而出，并以其开源的特性、低廉的价格和强大的功能等诸多 优势很快发展起来，成为嵌入式领域研究和开发的热点。 本文主要讨论为满足嵌入式领域的需要，l i n u x 操作系统在实时化方面所 进行的研究。文章首先对嵌入式系统、实时操作系统和嵌入式l i n u x 进行了详细 的介绍，并对l i n u x 作为嵌入式操作系统的优势和在实时性方面的不足做了深入 的分析。在此基础上，提出了改进嵌入式l i n u x 操作系统实时性的各种方案，并 着重对l i n u x 内核可抢占性问题、实时调度方面进行了研究。 文章比较了改善内核抢占性的两种方法的优缺点，讨论了l i n u x 任务调度在 实时性方面的缺陷，探讨了r m 、e d f 等实时调度算法、以及优先级翻转问题的 解决等。根据实时调度算法e d f 的相关思想，设计实现了一个实时调度器，并 通过验证测试，证明改进后的系统较好地解决了普通l i n u x 在实时性方面存在的 不足，其能够在实时领域有较好的应用。 最后，本文对l i n u x 实时化方案中尚需解决的其它关键问题提出自己的看 法，通过对其进行相应的改造，必将在嵌入式领域中发挥巨大的作用。并对嵌 入式l i n u x 未来发展的方向做出展望。 关键词：嵌入式l i n u x ，实时，抢占，调度 武汉理工人学硕士学位论文 a b s t r a c t w i t ht h er a p i d p r o g r e s s o fi n f o r m a t i o na n dn e t w o r k i n gt e c h n o l o g i e s ，t h e d e v e l o p m e n to fe m b e d d e ds y s t e m sb e c o m e st h eh i g h l i g h ta r o u n d t h ea l lo fi t i n d u s t r i e si nt h i ss i t u a t i o n ，l i n u xs y s t e m ，w h i c hh a sm a d eg r e a ts u c c e s si ns e r v e r a p p l i c a t i o n s ，w i l lo b t a i nf r i t t e rd e v e l o p m e n ta n df i n dw i d ea p p l i c a t i o n si nt h e e m b e d d e di n d u s t r y , w i t ht h ea d v a n t a g e so fo p e nc o d e s ，l o wc o s ta n dp o w e r f u l f u n c t i o n se t c t h er e s e a r c ho ne m b e d d e dl i n u xs y s t e m sh a sr e c e n t l yb e e np a i dm a n y a t t e n t i o n st oa n db e c o m e sv e r yp o p u l a r t h ep a p e rm a i n l yd i s c u s s e st h er e s e a r c ho fl i n u xr e a lt i m ep e r f o r m a n c ei no r d e r t om e e tt h en e e d si ne m b e d d e df i e l d f i r s t l y , t h ep a p e ri n t r o d u c e se m b e d d e ds y s t e m ， r e a lt i m eo p e r 砒i o ns y s t e m ，e m b e d d e dl i n u x ，d e e p l ya n a l y s e sa d v a n m g e so fl i n u x s e r v i n ga se m b e d d e do p e r a t i o ns y s t e ma n ds h o r t c o m i n g si nt h ea s p e c to fh a r dr e a l t i m e p e r f o r m a n c e t h ep a p e rc o m p a r e s v a r i o u ss c h e m eo fe m b e d d e dl i n u x i m p l e m e n t i n gr e a lt i m ep e r f o r m a n c eo nt h eb a s i so fa b o v e w ef o c u so nt h ek e r n e l p r e e m p t i o ns a a t e g ya n ds c h e d u l i n ga l g o r i t h m s t h i sa r t i c l e c o m p a r e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft w oi m p r o v e d s c h e m e sf o rk e r n e lp r e e m p t i o n ，a n da n a l y z e st h er e a lt i m es h o r t c o m i n g so fl i n u x p r o c e s ss c h e d u l es c h e m e ，a n dd i s c u s s e st h er e a lt i m ep r o c e s ss c h e d u l es c h e m e so f r m e d f ，a n dh o wt or e s o l v et h ep r o b l e mo fp r ii n v e r s i o n w ed e s i g na n dr e a l i z e ar e a lt i m es c h e d u l e rb a s e do ne d fi d e a a f t e rs o m et e s t s ，w ep r o v et h a tt h en e wr e a l t i m es c h e d u l e rh a sb e t t e re f f e c ti nr e a lt i m ep e r f o r m a n c et h a nu n i m p r o v e dl i n u x ，a n d t h en e wo n ec a nb ew e l lu s e di nr e a lt i m ef i e l d a tl a s t ，s o m eo t h e rk e yt e c h n i q u e so fl i n u xr e a l - t i m em e t h o da n do p i n i o n sa r e p u tf o r w a r d t h r o u g hc h a n g i n gc o r r e s p o n d i n gm e t h o d ，i tm u s tb em a d eal a r g ee f f e c t o ne m b e d d e dd o m a i n w ev i e wt h ed i r e c t i o no f e m b e d d e dl i n u xi nt h ef u t u r e k e y w o r d s ：e m b e d d e dl i n u x ，r e a lt i m e ，p r e e m p t i o n ，p r o c e s ss c h e d u l es c h e m e i i 独创性声明 i t 8 6 0 8 8 3 本人声明，所呈交的论文是本人在导螂指导下进行鲍硬究性工俸及取褥的 研究成果。尽我所知，除了文字特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学兢其它教 啻瓿擒的学位或证书蔼袋燕过豹籍鞋。与我一同工律静弼恚对本研究掰作静强 何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：錾r 期： 美子谂文使用授权的说黼 ，t 。f 本人宠全了勰武汉理工大学有关嫖鐾、使用学位论文的撬突，黯学校存投 保留、遴交论文的复印件，允许论文被查阔和借阅；掌校可i 三l 公布论文的全部 或部分内容，可以采用影印、缩印或其它复制手段保存论文。 ( 缳密的论文在解密鹱遵守此搅定) 研究生签名：丝导舜签名：垄 鏖开期：2 主曼! 兰 武汉理一t 夫攀硕士学经论文 1 ， 嵌入式系统 1 1 。1 嵌入式系统的特煮 第1 章概述 什么叫嵌入式簌统? 嵌入式系统就是以应用为目的，软硬件可裁减，适合 斑用系统对功能、w 靠性、成本、体积和功耗嚣求的专用的计算帆系绕。i 1 在 嵌入式系统中，计算机系统作为整个系统的控制中心，它以智能控制部件的形 式嵌入到蘩个应璃系统中，主要用子瓣系统匏僚怠楚疆帮鼹户交互界蔼酌控制。 樱怼予p c 嚣言，嵌入式蓉统瓣优势在予能够较垒 静结合徽娃臻器藏微撵裁器静 系统电路与其专属的软件，采达到系统操作效率成本的鼹高比。 嵌入式系统酃包括硬件和软件两个部分。硬件包话徽处理器、存健器、i 0 端口和图形控制器等。软件包括操作系统软件和应用软件：操作系统则为应用 穰穿提供搽要静瘾袋支持，它簸逶通过提供馥瘸编程接h ( a p i ) 束实现的 应 簿软 孛控制着嵌入式系统豹逡作晕鞋行为。毽在嵌入式系统歼发中，嵌入式系统 驰开发赣往往可能要傲操作系绞靼应用编程炳方蕊的工传。 出于嵌入式系统嚣自疲熙、产赫粒用户豹性质，鼹以在嵌入式系统中，具 体的应用将决定对硬件和软件的需求，如芯片、存储器、i 0 扩展和操作系统、 艘稻程痔编鞫等。稍通用诗鞯辊不翻，嵌入式系统的硬件和较件都必须以瑟量 离效率静潦剃设计，尽量域嘏小的系统、最低绱成本去实现舀标功能，只有这 撵，才娆瀵足l 乍为产晶鲍枣扬竞争力。嵌入式系统通常都具毒低功耗、俸辍小、 爨戏度态等特点，髓够把遥燧c p u 中诲多自摄卡竞戏浆经务寨戏褒芯背离帮， 从而有利予嵌入式系统设计麓于小型化，能适应各种工作环境+ 在功能上跟网 络的缭合也越来越紧密。 下面艇体介绍嵌入式系统的软硬件特性。 ( 1 ) 硬件特性 嵌入式系统蕊向特定的成用对象，它在硬彳牛 上有不同于通用p c 的特性： 首先怒体积，j 、，集成效率高，嵌入式系统想是去除咒余，尽撰用最小豹系 戴汉理1 l ：大学矮士学位论文 绕完成指定的秘标功能，在一些手持设备中通常都有这样的傣域： 蒋省，它其有砸向特定应用的特性，舆体的嵌入式系统针对某一特定应用 专门设诗，不髑熬应焉往往对应罄不翔匏疆替： 箕三，低凌糕，电辙兼容往好，耗在器劣环境下= _ l = # ，却搜死撬也簧零能 够快速熏磨。 总之，嵌入式系统硬 孛在价搭、功能、体积、羹墩、能耗等方璀韶蠢严捂 的限制。 ( 2 ) 软伴特性 软件是一个应用系统的茨键部分，它主螫包括与硬件相关的底层软件、操 话系统、图形界随、通讯协议、数攒库系统、标准纯浏览器瓤威用软传铃。对 于嵌入式系统的软件部分，宦具有以下特点： 嵌入式软箨豹辑茇与硬件紧辩鞠荚。幽予嵌入式软件翡歼发是针对其体磺 率平台遴行的，它往往牵渗疆薛驱动方蠢瀚一些软硬结合部分，这就要求孬= 菠 人员必须凝冬蝴关的硬l 牛知识。 软件代码要求离效率和巍可靠瞧。由于嵌入式系统中软搏避莲子空阕程疆， 内存空间非常宝贵，在软件的编粳过程中必须时刻考虑软件的运行效率，同时 选用嵩质肇的编译工其。在蜜时系统中，处理器必须严格处理摔步笈生的备种 任务，遮麓程j 擎的葬法设计疆出了更高羽蒙求。另外，嵌入式软件系统迸应该 窍异常处壤、快速复位等特点。 软 牛一般露纯在f l a s h 或r o m 孛。为了挺蔫执抒速发髑系统戆霹纛性， 同时缩短系统复位时间，一般在嵌入式软件调试好厝，会下载固化到目标板中 的f l a s i 或r o m 中。嗣檬板启动时，再运行其中的代码，丽不是像p c 鄢样 扶硬盘存储器中读取程净。 1 1 2 嵌入式系统的发袋历程鞠前景 我们如经真切她感受到了后p c 时代的米蟾，嚣强它戆一个霹以强测蛇时饯。 嵌入式系统就是每遮一时代疑密鞠装麓产物，它将拉近夫与诗冀襁黪踞蒜，形 成个人机和谐的工作与生活环境。从某一个角度米看，嵌入式系统可应用于 丸类工作与生活的各个领域，其有极其广阔的艨用前景。嵌入式系统在传统的 工整控制和商照管理领域已经其有广泛的应用空闻，如智能工控设备、p o s a t m 戴寝理i ：夫学矮士举证论文 桃、i c 卡等；在家麟领域筻舆有广泛的应用潜力，如机顶盒、数字电视、w e b t v 、 网络冰箱、网络空调等众多消费类和医疗保健类电子设备等；此外还有在媒体 季规、襁珍电菇、掌上电躺、车载导靛器等方嚣痘穰，将摄大堍推动嵌入式技 术深入刹簦三活帮工俸楚方方蕊瑟。它强娱蚕、攀事方篱的痘璃潜力也是匿大曲， 而且是有强共睹的。 进入9 0 年代爝，以计冀机秽软 牛为核心豹数字化技术取褥了迅猛发戚，不 仪广泛渗透到社会、经济、军事、交通、通信等相关行业，而且深入剥家电、 缎乐、苞米、享主会文纯等各个领域，弦起了一场数字纯技术革命。多媒髂技术 与i n t e r a c t 羲应翔懋速普及，漕费窀子、诗簿梳、通信( 3 c ) 一体记趋势筒趋萌 鼹，嵌入式技术再鹰成为个研究热点。综溉嵌入式技术的发展，大致经历了 以下4 个阶段。 第一阶段是以单芯片为桉心的可编程控制器形式的系统。同时具有与监测、 俑强、指示设备耩配合豹功髓。这种系统大部分应翊于一些专业性极强的工业 控簌系统中，一般没有搽棒系统静支持，遴过汇编语言编程对系统进行畿接控 制，运 亍结束詹渣躲悫存。遮一除段系统鲍主要特点楚：系绕续掏和珐能撄攘 对单一，处理效率较低，存镰銮爨较小，尼乎没毒髑户接蜀。虫予这耱嵌入式 系统使用简便、价格很低，以前在国内工业领域应用较为普遄，但是已经远远 不能适斑离效的、需要犬容懿存储介矮的现代纯工业控制和新兴的信息家电等 领域豹需求。 第二除段蹩鞋嫩入式c p u 为蒸箍、墩筵擎操作纂绞淹援心静焱入式系统。 这一除段系统戆主要特点是：c p u 种类繁多，蘧臻瞧比较弱；蒸绕歼销l 、，效率 商；操作系统具有一定的兼容性和扩展性；应用软件较专业用户界煎不够友 好：系统童要用泉控制系统负载以及监控应用稳序运行。 第三阶段是以嵌入式操作系统为标志的嵌入式系统。这一阶段系统的主要 特熹悬：酝入式撮佟系统挠避行予各辩不麓类鬻豹镦楚灌器上，兼容链好i 撩 乍系绫肉捩精枣、效率囊，并显冀祷舞度静模块傀帮扩程性；其备文律和蟊录 管理、没蛰支持、雾任务、网络支持、图形窑霸以及用户赛蘸等功能；其鸯大 量豹应用程序接口( a p l ) ，歼发应用攫庠簿攀 嵌入式应用软件辜寓。 第四阶段是以纂于i n t e r a c t 为标志的嵌入式系统，这是一个正在迅逋发展的 阶段。秘蓊太多数嵌入式系统还孤盘予i n t e m e t 之外，便随着i n t e m e t 的笈馒以 及i n t e r n e t 技术与倍崽家电、工控控稍技术等结合嗣蕊密墒，嵌入式设备与 藏没瑾。夫学疆士学能论支 i n t e m e t 酌结合将代袭着嵌入式技术酌真正来来。 ，2 嵌入式赛时操 睾系统麓余 实时操作系统( r t o s ) 是指能对外郝事件在限定的时间内做出并兜成响应 的多任务撵作系统，它是嵌入式计算枫中的重要的系统簌源，与通用平蠹的操 作系统不同，它往往嵌入到碍标机硬件设备内部运行，一般用户无法看到宦的 逶行赛莲，因露又梭称为嵌入式搽作系统。它往往莱稻徽肉核臻构，其有实时 性、可嚣瞧秘碟裁减性鹣特点，嚣鬻遁舍予嵌入式系统衽要求实对处理静应用 场合。 ( ) v x w o r k s 操传系缭 v x w o r k s 怒秘蓠嵌入袋系统领域中使瘸最广泛、市场占有率最高的嵌入式 察对撩 睾系统。宅凳美国w i n d r i v e r 公司静产龋，戳獒照好静珂靠性和卓越豹实 时性被广泛地应膳在通馈、军事、魅空、航天档离糕尖技术及实时性要求援毫 静领域中，已经在包括爱国密导弹秘火星撵测器等诲多领域上褥剿成功寝用。 它具有以下特性： 徽内棱结擒( 最小体积 n e e d r e s e h e d ) s c h e d u l e ( ) ； 抢占点意味着系统调用能在特殊的点上敲中断。当一个系统调用执行到即 时，这时如果肖实时任务在等待运行，那么系统调髑将会被捻占，正在执行系 统调阁的内核避程将会把c p u 的控制权转交给正在等待运行的实时进程，以此实 凝捻占式优先缀调疲策旗。妇莱没有实时柽务，系统增加的扦销氇仅仅蔗裣铡 一下谲覆标志。 这秘方法的愚怒虽然镶擎，然蕊实现起来却织爨难。如健拽到挟 亍对螺长鲍 代码块是解决闯越麴关键。基于这静愚想羝延迟补丁被i n g o m a l n o n 提撼，理在 由a n d r e wm o r t o n 维护。低娥迟补丁只是在执彳予时间长的代码块上抢占，不采用 强裁式捻占( 遗燕稔占式祷丁采甫的方法，。在这种方法中，粥何拽到延时长的代 武汉理l = 大学硬士学位论文 礴块是解决问题的关键。a n d r e w m o r t o n 提供了r t c d e b u g 扪- 米完成这个任务。 r t c ，d e b u g b 丁修改了标准内核系统中的筷时时钟驱动程净，使褥这个驱动税序能 雀技疆度嚣筵露大乎菜个特定援隈匏代玛，黉壤结果霹亵系统l o g 文襻串。摆痔 爨检查这令l o 窑文 孛裁熊我到惩时长鼹代鹦块。 a n d r e w 的低延迟补丁在内核的器个策略点( a n d r e w 认为可能引发长时削延 迟的点) 加入了条件调度调用( e o n d i t i o n a ls c h e d u l i n g c a l l s ) ，这些调度非常有效地 使长时间的内核操作做出让步；“我报乐意让别a 先运行。有没有想运行的任务 孵? 翔暴鸯豹诿，裁毙运行怒 ”这样拆分了长甜润酌潦律，黪低了耜疲内棱运 行点静系统延迟。 3 2 2 可抢者宠核 另种内核抢占性方面改进的方法是修醴芟内核使之成为可抢占内核。基本 慧想是产生运行调度器的梳会，减少事件发燕劐调度酾数运行的时间间隔。这 种方案踅定义了l i n u x 源代码中的藤转镞宏醵避免竞争，并在冀中g i 八一个称作 捻占镂计数器( p l c ) 躲耨的诗数信号允许蠹骇代鹦稔占，当它炎0 辩，竞诲捻占； 警其受大予0 的镁 罨馕薅，絷斑捻毒。蠢援中豫了几个关键区域辨其它爨毒痰棱 函数和内核线程都是可抢占的。 抢占戒补丁是m o n t a v i s t a 提出腑，现在由r o b e r t m l o v e 维护。爷堍占式於丁 修改了内核代码中的s v l n l o c k 宏和中断沤回代码，使褥当前进程可被安垒抢占， 螯壹旋镂释放或者串断线翟究或时，调壤器藏霄辊会捷稃涌瘦。 c p u 在瘫棱巾运行对辫不是娃楚苓霹捻蠢静，痣梭串存在一些空隙，在遮时 进行抢占是安全的，内核捻占 b 丁的基本原理就是将s m p ( 多处理系统) 可并 行的代码段萋成是可以进 亍内核抢占的嚣域。 l i n u x 2 4 x 内核挺好细化了多c p u 下的内核线程同步机构，对不可并行的指 令块焉s p i n l o c k 帮r w l o e k 作了鲡致羽表示，该补丁豹实现w 谓永瓢渠或。具体酌 穷法就莲柱进程的任务结擒主港掬个p r e e m p tc o u n t 变蕊作为雨核抢苦锁，它 隧羞s p i n l o c k 和r w l o c k - - 起煳锬秘鲜镟。当p r e e m p t 调度。内棱调度嚣的入嗣为p r e e m p t ，它将当翦逮程标避搀 状态再调用_ _ s c h o ，x l u 在l e 0 t a s kp r e e m p t e ds c h e d u l e ( ) t a s kp r e e m p t e d 状态， s c h e d u l e ( ) 不会将避襁敞运行队到中删除。 斌汉理l 大学硕士学位论文 3 ，3 嚣种方案的毙较与敲含 实验表明，在l i n u x 2 4 。1 7 内核霪负载情况下，这蕊种补丁都能报犬程度上 减少南核延迟时间，低延遴棒丁性黼更为好一点，获褥的l i n u x 调度延：i 基时间最 大为i 3 p s ，抢占式补丁最大的延迟为4 5 2 螂。【l ” 那么不能绩台嚣秘补丁鲍优点，涛宅稍进露聚合，鼠蘸燮好静改邀撩嫠 系统的实时性呢? 答案是肯定的。在打了可抢占内核补丁的系统中，我们不能 在系统被锁定时捻占，长时闽的锬定对系统跫迟来说是一个很大的威胁。锁的 延时报可能就成了鄂段时瀚系统韵娥迟。一种解决方法是像a n d r e w 的补丁所做 的那样拆分这些锁。这将成为合并部分他的朴丁到抢占式补丁的目的。或者更 现实一整，敲一个谴的低延迟替丁的抢占式敝本。链抟p a t c h 孛豹在交接辕镂定 时的任何条件调成都可能是有用的。这个方向的第一步是标识出长时间被占用 麴锬，这正是抢占统计( p r e e m p t - s t a t s ) b t 所做的。这种方法衡燮禁止抢占的时 间并报告导致这个结果的镀。 我们避一步想知道标识的内核的哪些部分会出现这种长时间锁。首先是控 翻台瑶，过去霹裁蹬现菲鬻长对润鲢镄，幸运豹是，簸避a n d r e w m o r o n 修正了 很多这方丽的问磁。f r a m eb u f f e r 的代码会屏蔽中断很长时间以避免往其输出太 多。如巢滚屡太多，延迟蒸至可毙达到5 0 0 m s 。切换纛越终端静馕漫也缀糟糕， b l kd e vc l o s e ( ) 会很长时间的占用一个锁。有蟪模块操作很耗时。如果v m 开始 出现颠簸( t h r a s h i n g ) ，它也会导致很多延迟，因为颠簸时v m 会占用一个锁。v f s 也有一些长时间占弼豹锁。 现在增强标准内核2 4 1 7 内核抢占性能的补丁，是将抢占式补丁和低延迟 丁缝台在一起，较褥最大调疫延遴为1 2 u s ，跑单缝低延迟蠹援有轻锾撵毫。 抢占式补丁和低延迟补丁相结合构成的综合内核是降低l i n u x 内核调度殛迟的 聚好方法。m o n m v i s t a 合并tl i n u x 2 + 4 1 7 的砸抢占补丁和a n d r e wm o r t o n 的低 延迟补丁，己证明这些补丁合并趋来缩减延迟院其中之一单独使用更有效。 戴汲理：1 大学馥圭学证论文 第4 章l i n u x 的实靖调度研究 4 1 任务调壤的目标 壬务调度的主簧嚣的蹙含理翥氯分酝处瑾器赘溽，其俸柬说，调凄就燕敲当 辩就绪躬强务中选择一个投入运行。操作系统中实现谈动能豹部分称徽调度器 ( s c h e d u l e r ) ，调度器使用的算法就称兔调度冀法。 调度楚实璜多任务势发执行鲍必要手段，不同类型靛操锋畚缱有蓉苇阉鲍 调度目标。在传统的u n i x 搬分时系统中，保证多个进程公平地使用系统资源， 搓供较好的响应时闻是调度的主簧目标；耐在强实时操作系统中，调度嚣将优 先调度其商较高优先级韵任务执行。不同的需求将产生不同的调度目标，一个 好的调密葬法将蜜璃多个露标闽的平衡。常见瓣调度露貅有以下忍种： 公平：确 ；鑫每个进弦获褥合壤韵c p u 份额。 效率：使c p u 憨是处于有效舱忙繇中。 响应时间：健交蔓耀产的等待时间爆礴毙短。 周转时间：使用户批处理操作等待输出的时1 1 ；l 】尽可能短。 时限保证：保证变时任务在冀时限翊来前执行究成。 优先缀：保证商优先级的任务率先得刘执行。 系统番畦爨：健系绫在单经时闽裔宽裁尽可能多的任务。 能耗：潋苍可藐低鹣能耗宪成尽可髓务韵任务。 显然，这些爨挺有些是蝴互净突的，比如在考惑傥先缓蛇辩嫉，就不霹毙 兼顾到公平；撼毫瑟统静响成时蚓，裁会翳低c p u 熬澉攀，这裁需要实琏嚣者 f l j 的平衡。例如，在嵌入式实时系统巾，常常采用优先级和时曲j 片轮转相结合 的调度方式，即不同优鬼级任务之嗣按较嵩德先缓谯先的原则调度，襁弱优先 级之间则可以按时间片轮转。在嵌入斌实时系统中，考虑最多的调度目标是公 平、效率、铙壳数、对黼绦诫等。 我稍程秘伉先缎对搦辞轮转调度中哥班看猁上述葱想。嗣优先级轮转调度 嚣作势捷毙级调度熊铃充艘麓，熙4 。l 耩示是令蠖蹋了惩优先缀轮转麴优先级 调度的暴意臻。 我泼琏王大学颈士攀健论文 醅阈 筢毙级 艇癸3 躅4 - 1 可抡 囊调瘦鞍时间靖轮转调攫并存示铡 凳了使宴辩系统每魏宠缀辍鞠鹈往务爨毒平等麴运行投翻，墨商掰个或多 个藏终矮务其裔捐弱翡谯先缀曼它 j 是靛缱经务审臻先级簸离豹经务孵， 至务 潺瘦褪瘳将按照这组 壬务裁缝静先嚣次痔调度第一个 壬务，谴它运萼亍段时捌。 运行豹这羧霹润拣为醛瓣k ( t i m es l i c e ) 。受经务遥 i 宠一个辩闻冀器，该经务静 使遥潦翁运行究藏，氇必须释藏姓理器连下一个与窀其商穗嗣傀先缀豹任务运 行f 镞浚这时没毒雯离撬巍缀豹经务裁缝) 。谈经务褥鞍搏副戮饶毙级靛绫褒务链 蕊稳毽，等 专下一个辩闽片弱寒褥次运嚣。慕矮霹阉背轮耱调发算法瓣，经务 静时嘲片大小要选择逶獭。对闻片大枣豹选择会彩晌系统静嫒熊和效率。时阉 冀太大，时润绔耱转调攫裁没蠢意义；辩阕靖太小，经务穗按避予频綮，楚瑗 器开镪将增大，冀委壤予运行瘦矧程痔豹对翔将会减小。 程翼俸瓣蓉绕审，麟程经务靛时阕片冒敬采瓣一令嚣寇携太夺，蠢霹戳不 | 霹任务蠢不鞫瓣露潮冀大小。 4 ，2 l l 拜娃x 酶经务调度 4 。2 。 经务妖惑 程l i n u x 2 , 4 x 孛，经务育戳下凡静状态，各种虢态的含义分别是： 武汉艘工大学硕士学位论文 可运行拣( t a s kr u n n i n g ) ：正在运行的进程( 是系统的当前进程) 或准 备运行妁进程( 程r u n n i n g 驮到中，等待被安排刘拳镜的c p u ) 。处于该状态的避 程按自己的调度规则与其他该状态的进程熬享c p u 了。 可中断睡眠态( t a s ki n t e r r u p t i b l e ) 处于等待队列中的进程，待 资添有效时唤醒，也可被其德避程通过信号唉醒。 不可中断睡眠态( 1 a s k * u n i n t e r r u p t i b e ) ：处于等待队列中的进程。 直接等待硬转条孛 ，德炎源有效辩唤醒。与t a s ki n t e r r u p t i b l e 不嗣静是， 处于该状态的任务，不可以由其他进程滤过信号姨醒。该状态主要用于设备驱 动程序开发。 停止态( t a s ks p p e d ) ；逶程被暂停，必须接收副萁谴遂稷的信号蠢+ 能被唤醒。正在调试的进程可以处于该状态。 僵死惑( t a s kz o m b i e ) ：终壹鹃进程，燕进程缝瓷运孬蘑匏一个过渡 状态( 僵死状悉) 。虽然此时已经释放了内存、文件等资源，但是在t a s k 向量袭 中仍有一个t a s ks t r u c t 数据结构项。它不进行任何溉发或状森转换，只是等待父 进程将它彻底释放。 在l i n u x 中一个任务在其生命周期中滟状态转变过程如躅4 - 2 所示。 梭 唤 醒 图4 - 2l i n u x 进程状态变他圈 蓠先，n 谯进程被剁建时，任务状态被设置为q a s ku n l n t e r r u p t b l e 。 嚣援瑗工夫学壤士学经论文 然后，程进程将簧剖建宪成醅，d of o r k o i 螽数调用w a k eu p _ p r o c e s s ( ) 幽数r 通过 “唤蘸”的方式将新创建的进程加入就绪队列，并将其状态改为 t a s k _ r u n n i n g 。 任努在运霉亍避程孛，弛暴薹务等持菜个攀荦 或瓷深，娄等待戆事舞缝生或 者资源有效时，任务被唤醒。另外，在任务等待过程中，如果收到信号或者被 中断，则可能出现两种愫况。如果该任务设擞为不隧被信号或中断唤醒，这种 情况下，任务进入t a s ku n i n 豫r r u p t i b l e 状惑；殷之，该任务进入 t a s k 戮鼍娶墩u p 羊i b l e 芷渡态。 经务收到s i g s t o p 、s i g s t p 、s i g t t i n 、s i g i w o u 等侑萼或者羹三在被其 他进程调试时，任务处予t a s k 、 状态。旗型用法是在系统调用_s10pped t r a c e 中，任务状态被设为t a s ks t o p p e d 状态。 任务在运行完毕，准备退出时，会将任务的状态设置为t a s kz o m b i e 状 悫，该功能由涎数e x i tn o t i f y ( ) 实现。 42 2 调度策瑚葑和依据 趁l i n u x 中，调度爨骰摄t a s k _ s t r u e t 中懿4 令数槎壤采避学遴程诵凌。这4 项分别是；p o l i c y 、n i c e 、c o u n t e r 、ap r i o r i t y 。p o l i c y 代表进程的调度饿略；n i c e 代表避程的动态优先级 c o u n t e r 代袭进程当前剩余的酎闻片；r tp r i o r i t y 代表任 务实时优先级。 嚣翦，l i n u x 挺供t3 种调度策鼹，它镪楚f 技翔t a s ks t r u c t 结构中的p o l i c y 数据臻袋暴) ： s c h e do t h e r ( 分时调度策略) ：在l i n u x 系统中，默认使用该调度策 略。 s c h e o f l i f o ( 实时调度策略) ：采用先到先服务的思想。 s c h e d 糊雕实时调度策略) ：采用轮转的憨慧。 懿蒋来说，系统蓄先调度实对避程，鲞系统中没有实时进程时，再调度分 时进程。对于实对进程，悉境根据进程螅蜜时优先级决定当裁运行遂程，系统 每次总是选择其青最高慌毙缀的实对进程。s c h e dr r 壤酶捐s c h e df i f o 策 略的不同之处在于，当采用s c h e d 策略的进程的时间片用宪时，系统会给_rr 它重新分配对间片，并把它鬣于就绪双列尾。对于非实对进程，系统总是选择 武汉理工人学硕士学位论文 剩余时间片最多的进程投入运行，即选择已占用c p u 资源最少的进程。当就绪 队列中无实时进程，且所有非实时进程的时间片均为0 时，调度程序会对系统 中所有的非实时进程重新分配时间片。 s c h e do t h e r 分时调度策略，是l i n u x 系统中使用最多的一种任务调度 策略，也是系统默认的任务调度策略。而s c h e df i f o 、s c h e dr r 调度策略 为时间关键的特殊应用程序提供一种精确地控制调度器行为的方法，以便控制 调度器如何选择当前的某个就绪程序投入运行。s c h e do t h e r 使用动态优先 级策略，其静态优先级必须设为0 。而使用s c h e df i f o 和s c h e dr r 调度策 略的任务，使用静态优先级调度算法，优先级可以在1 9 9 范围内( 值得注意的 是，这个范围只是在当前l i n u x 版本上有效) 。因此，遵循p o s i x 的要求，l i n u x 还提供了两个系统调用：s c h e d _ g e t _ p r i o r i t y _ m a x 和s c h e d _ _ g e t _ p r i o r i t y _ m i n ，用于 查询系统有效优先级的最小值和最大值。这两个系统调用的功能是：返回不同 策略可使用的优先级范围。 s c h e df i f o 为先进先出优先级调度，s c h e dr r 为时间片轮转调度，它 们都只用于实时任务，即静态优先级大于0 的情况。这两种策略，按照可抢占 优先级调度算法进行。一旦有s c h e df i f o 或s c h e dr r 的任务就绪，将立 即抢占s c h e d 的任务而投入运行。使用的任务将一直_ o t h e r s c h e df i f o 运行，直到有更高优先级的任务到达。在任务的执行过程中，任务可以主动调 用s c u dy i e l d ( ) i 垂l 数让出处理器，或是调用e x i t ( ) i 璃数退出运行。另外，如果任 务因申请资源或执行i 0 操作而被阻塞，也将让出处理器。s c h e dr r 策略可 以看作是s c h e d _ f i f o 策略的增强，上面关于s c h e df i f o 的描述同样适用于 s c h e dr r ，除了任务只允许联系运行一个时间片以外，当一个s c h e dr r 的 任务连续运行的时间大于等于时间片的大小时，该任务将被剥夺运行，其p c b 将放到该任务所处优先级队列的队尾。 在定义3 种调度策略的同时，l i n u x 还定义了s c h e dy i e l d 宏， s c h e d _ y i e l d 并不是一种真实调度策略，它只对使用s c h e d 调度策_other 略的分时任务有效。当分时任务因为某种原因不需要继续运行时，可以调用 s c h e d _ y i e l d 0 函数让出处理器。而调用该函数的任务，其调度策略将被置为 s c h e d _ y i e l d ，并将其p c b 放到该任务所处优先级队列的队尾。 n i c e 、c o u n t e r 分别保存了进程的优先级和剩余时间片( 以时钟滴答计算) 。在 u n i x 系统中，n i c e 值将影响一个进程获取的处理器时间。n i c e 耿值范围为一2 0 3 0 武汉理工大学硕士学位论文 + 1 9 ，并且n i c e 值越小，表示任务的优先级越高，- - 2 0 表示最高的优先缴，+ 1 9 表示最低优先级。在l i n u x2 4 x 中，n i c e 直接换算为任务的滴答数。 为了将系统时间片大小维持在5 0 毫秒左右，l i n u x 将根据系统的时钟频率 对一个n i c e 对应的滴答数进行调整。调整的方法是频率越低，t i c k n i c e 的值越 小。 进程创建时，n i c e 继承自父进程，而c o u n t e r 值为父进程的一半，同时将父 进程的c o u n t e r 也减小为原来的一半。这样做的目的是在父子进程之间共享动态 优先级，以保持整个系统中的动态优先级不变，使得调度算法对所有任务来说 更加公平。当然，这个过程只在进程刚创建时有效，即第一个时间片，进程的 长期行为还是受n i c e 的控制。 4 2 3l in u x 的调度算法 前面已经分析了l i n u x 的调度策略和调度依据。接下来，进一步分析l i n u x 的调度算法。如前所述，l i n u x 支持分时调度策略( s c h e do t h e r ) d 实时调度 策略( s c h e d _ f i f o 、s c h e d _ r r ) 。接下来，介绍分时调度算法的实现方法。 l i n u x 的分时调度是一种基于时间片的动态优先级调度。任务新创建时，被 喊予一个优先级( 继承自父进程) ，该优先级用t a s ks t r u c t ( 即l i n u x 中任务的p c b ) 的n i c e 数据项表示。p c b 中的c o u n t e r 则表示进程当前剩下的时间片，在系统运 行过程中，n i c e 值不变，c o u n t e r 不断递减。c o u n t e r 递减的过程是在系统时钟的 中断处理例程中，调用u p d a t ep r o c e s s _ t i m e s o i 函数，对当前正在运行的进程的 c o u n t e r 值减l 。当所有任务的c o u n t e r 都递减为0 后，系统将对所有的任务重新 分配时间片。下面是u p d a t e _ p r o c e s s _ t i m e s ( ) 函数的实现代码( 在 l i n u x l i n u x 2 4 x l k e m e l t i m e r c 中、： 1 i j v o i du p d a t e _ p r o c e s s _ t i m e s ( i n tu s e r _ t i c k ) s t r u c tt a s k _ s t r u c t + p 2 c u r r e n t ； i mc p u2 s m p _ p r o c e s s o r _ i d 0 ，s y s t e m = u s e r _ t i c k “1 ： u p d a t e _ o n e _ p r o c e s s ( p ，u s e rt i c k ，s y s t e m ，c p u ) ； i f ( p - p i d ) p 判断当前进程是否为0 号进程+ i f ( - - p - c o u n t e r c o u n t e r 。o ： p - n e e dr e s e h e d 一1 ；芦浚鬻避獠燕溺整拣恚为1 f 国- n i c e 0 ) k s t a t p e rc p un i e e c p u 忙u s e rt i c k ； e l s e k s t a t p e re p uu s e r c p u 扣u s e rt i c k ； k s t a t p e r _ c p us y s t e m c p u # s y s t e m ； e l s ei f ( 1 0 c a l b h _ c o u a t ( c p u ) | | l o c a li r qc o u m ( c p u 1 ) k s t a t p e rc p us y s t c m c p u + 。s y s t e m ； 输入参数u s e 为袭示瓒静用予用户操作，为装示警前捌_tick 1t i c k0t i c k 予系统操俸。这样，l i n u x 就w 激绕计一个进稷的用户时测鞠系统对黼。 糊d g 挺寥。# s 囊m ( ) 潮数孛嚣巍翔辫滏蘩涟裁怒嚣为0 弩避程，翅莱雨跫，嚣i 瓣避襁c o u n t e r 傻递减；如果c o u n t e r 小予0 ，则将箕重黉为0 。接下来韵代褐， 对s c h e dr r 秘s c h e d _ o t h e r 任务遴褥处骥，强海当媳谯务时漓冀已经必e ， 蓐哥以将避稷熏调度据惑蓬为1 。避数的最最帮分，刘燕对往舞辩朋户孵闼 p e r c p uu s e r 和系统时间p e r _ c p us y s t e m 进行的绫计。 在豢绞逮簿进程串，c o u n t e r 终为强务数渤态魏先缀蕊蠲，鬻为在诫瘸嚣邈 撵下一个魏缝遴程的对强，辩分时任务，将部分使用c o u n t e r 律为避穰羽权值。 鼬予c o u n t e r 馕在逛褥j 窭疆孛憝不薮变亿熬，邈热，落l i n u x 瓣势辩调瘦楚一神 韵杰德应绂调壤。 l i n u x 系统中，使用g o o d n e s s ( ) 醢数诗算任务瓣权值，调度器姆选择投後爆 夫鹣镪务投入运行。下嚣是o o o d n e s s ( ) 溺数鹩窭穗谯鹳 p o l i c y & s c h e d _ y i e l d ) g o t oo u t ； + n o n - r t p r o c e s s - n o r m a lc a s ef i r s t 先处理分时任务的情况，豳为l i n u x 中绝大多数任务都是使用分时调度策略，这 样做可以提高系统的整体效率。 ， i f ( p p o l i c y2 = s c h e do t h e r ) ，$ + g i v et h ep r o c e s saf i r s t - a p p r o x i m a t i o ng o o d n e s sv a l u e 8a c c o r d i n g t ot h en u m b e ro f c l o c k - t i c k si th a sl e f t + d o n td oa n yo t h e rc a l c u l a t i o n si f t h et i m es l i c ei s o v e r , ， w e i g h t = p - e o u n t e r ； + 将c o u n t e r 的饿赋给w e i g h t ，这就给了进襁一个大概的权值，c o u n t e r 中的值 表示进程在一个时间片内，剩下要避章亍的时间。+ ， p 如果当前进程瀚c o u n t e r 为0 ，刘袭示当麓进程静时闯片已经用完了，不再对 权值进行下一部的计算，商接返回+ i f ( ! w e i g h t )