《linux内核进程调度算法的分析、研究与改进》由会员分享，可在线阅读，更多相关《linux内核进程调度算法的分析、研究与改进（58页珍藏版）》请在金锄头文库上搜索。
1、 中文摘要 本文分析了L i n u x 2 6 内核源代码，研究了内核的主要数据结构、进程调度原 理及O ( 哟算法。在分析L i n u x 2 6 内核源代码的过程中发现了L i n u x 2 6 内核进程调 度系统在实时应用设计上存在的缺陷。针对L i n u x 2 6 设计缺陷和调度算法上的不 足之处，本文改进了L i n u x 2 6 内核调算法，修改了内核中和调度有关的数据结构， 并将L i n u x 2 6 内核调度算法的时间复杂度从O ( n ) 级改进到0 0 ) 级。分析了实时调 度的原理和主要算法，从硬件和软件两个方面提出了可行的实施性方案，以满足 L i n
2、u x 在实时方面的应用。最后通过实验测试得到的数据证明了改进后的内核进程 调度使系统负载更加均衡。 关键字：L i n u x 内核；进程调度；调度算法分析与改进；实时进程 ；j， A b s t r a c t T h ed i s s e r t a t i o ni n t r o d u c e st h eb a s i ck n o w l e d g eo fL i n u xi n c l u d i n gi t sd e v e l o p m e n t , p r o e v e r s i o na n ds o m ec o n c e p t sa b o u
3、tp r o c e s sa n dd i s p a t c h i n gi nt h eo p e r a t i o ns y s t e m ， w h i c hd e s c r i b e sw h o l ew o r k f l o wa b o u tt h et i m i n g ，s t r a t e g i e sa n ds e h e d u l e ro ft h e p r o c e s ss c h e d u l i n g 1 1 1 ep a p e ra l s os t a t e st h ed i s a d v a n t a g
4、e se x i s t si nt h ed e s i g no f L i n u x 2 6K e r n e lP r o c e s sD i s p a t c h i n gS y s t e m ，a n a l y s e st h ep r i n c i p l e sa n da p p l i c a t i o n so ft h e l a t e s t2 6K e r n e lP r o c e s sD i s p a t c h i n gS y s t e m 田地d i s s e r t a t i o nm a i n l yi n c l u
5、 d e sh o wt o i m p r o v es c h e d u l i n g - p o l i t i c ，i m p r o v e s c h e d u l i n g - a r i t h m e t i c ，i m p r o v e r e a l - t i m e a p p l i c a t i o n L i n u x 2 6k e r n e l a l g o r i t h m ， s i m p l i f yt h et i m ec o m p l e x i t yf r o m0 0 ) t oO ( 1 ) ，m o d i
6、f yt h er e l a t e dd a t as t r u c t u r eo f k e r n e la n ds c h e d u l i n g ，a n dw h i c ha l s oi n t r o d u c e sm o r ea d v a n c e da l g o r i t h m s ，a n a l y s e s t h ep r i n c i p l ea n dm a i na l g o r i t h mo fr e a l - t l m es c h e d u l e T h er e s e a r c hp r o p
7、o s e st w o f l e x i b l eo p e r a t i o np l a n st om e e tt h er e a l - t i m ea p p l i c a t i o n F i n a l l yt h ee x p e r i m e n t c e r t i f i c a t e st h en e wa d o p t e da l g o r i t h m sc o u l dd r o pt h ec o m p l e x i t yf r o mo ( t oo ( 1 ) K e y w o r d s ：L i n u xK
8、 e r n e l ；P r o c e s sS c h e d u l i n g ；D i s p a t c h i n gA l g o r i t h m sA n a l y s i s ； R e a l - t i m eP r o c e s s - 目录 中文摘要。 A B S T R A C T 第1 章绪论 目录 I I I 1 1 1 课题研究的背景与意义1 1 2 国内外研究现状1 1 3 目前存在的问题。2 1 4 本文的主要贡献和论文结构2 第2 章基础知识 4 2 1L I N U X 的起源二。4 2 1 1I 肘系统的出现。4 2 1 2 个人操作系统
9、W i l l d O W S 的出现4 2 1 3 自由软件的兴起4 2 1 4L i n u x 的出现5 2 2L I N V X 的版本6 2 2 1L i n u x 的内核版本。6 2 2 2L i n u x 的发行版本。7 2 3 进程的基本概念8 第3 章内核进程调度算法的分析与研究 1 4 3 1 内核重要数据结构。1 4 3 1 1 就绪队列s t r u c t - r u n q u e u e ：1 4 3 1 2t a s k _ s t m c t 1 4 3 1 3 调度函数s c h e d u l e 0 _ 。1 5 3 2 进程调度算法。：1 6 3
10、2 1L i n u x 的进程调度原理1 6 3 2 2L i n u x 2 6 内核进程调度系统的缺陷1 7 3 3O ( N ) 算法。：。1 7 1 黑龙江大学硕士学位论文 3 4 实时进程2 0 3 4 1 实时系统的调度2 1 3 4 2 实时调度的算法研究。2 2 第4 章内核进程调度算法的改进。 4 1 调度策略的改进。2 3 4 1 1 调度器工作流程2 4 4 1 2 时间片的计算2 4 4 1 3 动态优先级的计算。2 5 4 1 4 负载均衡2 5 4 2 调度算法的改进。2 6 4 2 1 原进程调度算法的局限性一2 6 4 2 2 改进的L i n u x 调度算
11、法。2 6 4 2 3 优先级算法。2 9 4 3O ( 1 ) 算法的实现3 l 4 4 内核数据结构的改进3 7 4 5L I N U X 在实时应用中的改进。3 9 第S 章测试 4 2 5 1 测试环境4 2 5 2H A c r B E N c n 测试4 2 5 3 回归测试。4 3 第6 章结论 参考文献 致谢 独创性声明 4 4 4 5 4 8 4 9 第l 章绪论 第1 章绪论 1 1 课题研究的背景与意义 L i n u x 操作系统目前已经成为世界上主流操作系统之一，其在桌面、工作站、 服务器、网络服务等方面已经占有重要地位。用户可以根据需要定制L i n u x 安装操
12、 作系统，并且可以根据用户需要，修改其内核源代码。由于L i n u x 操作系统加入了 G N U 计划，使之成为F r e ea n dO p e n 的软件，因此在互联网高速发展的今天，有更 多的开源软件的爱好者可以去修改，大量程序通过网络共同完善其内核使之成为更 有发展潜力的主流操作系统之一。系统中调度性能的好坏关系到整个系统的性能， L i n u x 的应用目前主要集中在低端服务器系统和桌面系统，将来很可能向高端服务 器市场和嵌入式系统发展，这就要求调度系统有大的改动。n 1 而L i n u x 2 6 内核调度 系统存在着一定的缺陷而无法满足实时性和高端服务器的需要。主要表现在：第 一，系统为所有进程只设置了一个r e a d y 队列，时间片使用完后的进程被挂起在 r e a d y 队列中，所以时间复杂度是o ( 吣，并且要计算被挂起进程
