




已阅读5页,还剩59页未读, 继续免费阅读
(控制理论与控制工程专业论文)嵌入式linux的实时性分析与改进.pdf.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 )
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025官方的担保借款协议
- 2025年白酒代理合同范本
- 2025消防设备供应合同范本
- 2025新款电子产品购销合同范本
- 2025-2030年北美电动汽车产业链技术创新与合作机遇报告
- 5G网络下生产设备辅材智能采购及维护服务协议
- 仓储租赁合同补充协议:租金上涨与仓储安全责任
- 离异父母共同监护子女权益保障及抚养费支付合同
- 科技园区内企业知识产权转让及股份制改革合同
- 涉及少数民族的离婚协议书起草与子女抚养合同
- 门窗淋水试验施工方案
- 遥感原理与应用 课件 第7、8章 定量遥感、遥感技术的应用
- 干部履历表模板
- 患者隐私保护培训课件
- 《SolidWorks 2024项目教程》高职全套教学课件
- 儿童肥胖的危害和预防-培训课件
- 加气站气瓶充装质量保证体系手册2024版
- 2025版宝鸡市房地产评估服务合同范本(含保密条款)2篇
- 《集成电路技术导论》课件
- 医疗机构药品管理法
- 弹幕游戏主播培训
评论
0/150
提交评论