基于多核系统的线程调度

微处理器自诞生以来,性能的提升主要是通过提高主频来实现的,而主频的提升要求大幅度增加晶体管的数量。巨大的晶体管数量则意味着巨大的能耗,随之带来的散热问题也日益凸显。当处理器性能受到半导体工艺限制的时候,研究人员将目光投到了处理器的体系结构,提出了多核处理器的概念。多核处理器已经成为微处理器发展的趋势,使用多核技术可以使微处理器的性能得到极大的提高,但同时也对调度策略提出了更高的要求。 本文首先分析了课题研究的背景和意义,简要介绍了进程、线程和多线程以及在单处理器调度的基本理论知识。介绍了多核处理器硬件相关的主要实现技术,包括同时多线程(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。