基于多核系统的线程调度

被引:0
作者
覃中
机构
[1] 电子科技大学
关键词
多核处理器; 对称多处理; Linux进程调度; O(1)调度算法; 负载均衡;
D O I
暂无
年度学位
2009
学位类型
硕士
导师
摘要
微处理器自诞生以来,性能的提升主要是通过提高主频来实现的,而主频的提升要求大幅度增加晶体管的数量。巨大的晶体管数量则意味着巨大的能耗,随之带来的散热问题也日益凸显。当处理器性能受到半导体工艺限制的时候,研究人员将目光投到了处理器的体系结构,提出了多核处理器的概念。多核处理器已经成为微处理器发展的趋势,使用多核技术可以使微处理器的性能得到极大的提高,但同时也对调度策略提出了更高的要求。 本文首先分析了课题研究的背景和意义,简要介绍了进程、线程和多线程以及在单处理器调度的基本理论知识。介绍了多核处理器硬件相关的主要实现技术,包括同时多线程(Simultaneous Multithreading,SMT ),片上多处理器(Chip MultiProcessor,CMP),片上多线程(Chip Multiple Threading, CMT);并分析了目前多核线程调度的研究现状。 其次,本文详细研究了Linux2.6内核的O(1)调度算法及其具体实现。O(1)调度器中增加了数据结构runqueue,就绪队列被分成活动队列和过期队列,结合bitmap[]不必遍历整个就绪队列,查找next进程的时间复杂度降为O(1),进程运行时间片的重新分配更及时;动态优先级的计算过程更简单。详细分析了在Linux中的SMP的具体实现,着重讨论了Linux负载均衡系统。然后指出了Linux2.6调度算法的不足:1.因为在处理器间迁移不同进程的代价是不尽相同的,所以在迁移进程的时候,应该适当考虑进程的特点。2.调度器给处理器分配进程的时候应该考虑进程的相关性。3.当系统的负载不平衡且很轻微的时候,不一定需要平衡负载。 最后,提出一种负载均衡的通用模型,使用四元组来表示。然后根据该模型的各个因子对Linux的负载均衡系统进行剖析,着重分析了Linux的负载评价因子L和调度策略因子S。针对Linux调度器不考虑进程迁移代价的不足提出了基于资源利用率的负载均衡算法,通过计算进程的CPU利用率和内存利用率来选择迁移进程,然后通过统计系统中的过载CPU和轻载CPU,根据Donor或者Reciever算法来匹配源CPU和目的CPU。
引用
收藏
页数:80
共 23 条
[1]
现代体系结构上的UNIX系统.[M].(美)CurtSchimmel著;张辉译;.人民邮电出版社.2003,
[2]
计算机操作系统.[M].汤子瀛等著;.西安电子科技大学出版社.1996,
[3]
Exploiting process lifetime distributions for dynamic load balancing [J].
HarcholBalter, M ;
Downey, AB .
ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1997, 15 (03) :253-285
[4]
On-line predicting behaviors of jobs in dynamic load balancing.[J].Jiubin Ju;Gaochao Xu;Kun Yang.Journal of Computer Science and Technology.1996, 1
[5]
基于多核处理器的实时操作系统的扩展 [D]. 
章承科 .
电子科技大学,
2006
[6]
基于Linux的进程调度算法的改进与实现 [D]. 
邹治锋 .
江南大学,
2006
[7]
多处理机系统的负载平衡模型设计附视频 [J].
王力生 ;
毛昀波 .
单片机与嵌入式系统应用, 2008, (04) :10-13
[8]
基于公平调度算法的分布式系统负载均衡研究 [J].
梁根 ;
郭小雪 ;
秦勇 .
计算机工程与设计, 2008, (06) :1362-1363+1400
[9]
多核多线程结构线程调度策略研究 [J].
王晶 ;
樊晓桠 ;
张盛兵 ;
王海 .
计算机科学, 2007, (09) :256-258+289
[10]
多核处理器的结构设计研究 [J].
何军 ;
王飙 .
计算机工程, 2007, (16) :208-210