基于多核系统的线程调度

发布时间：2020-03-27 06:13

【摘要】： 微处理器自诞生以来,性能的提升主要是通过提高主频来实现的,而主频的提升要求大幅度增加晶体管的数量。巨大的晶体管数量则意味着巨大的能耗,随之带来的散热问题也日益凸显。当处理器性能受到半导体工艺限制的时候,研究人员将目光投到了处理器的体系结构,提出了多核处理器的概念。多核处理器已经成为微处理器发展的趋势,使用多核技术可以使微处理器的性能得到极大的提高,但同时也对调度策略提出了更高的要求。本文首先分析了课题研究的背景和意义,简要介绍了进程、线程和多线程以及在单处理器调度的基本理论知识。介绍了多核处理器硬件相关的主要实现技术,包括同时多线程(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.当系统的负载不平衡且很轻微的时候,不一定需要平衡负载。最后,提出一种负载均衡的通用模型,使用四元组E,T,L,S来表示。然后根据该模型的各个因子对Linux的负载均衡系统进行剖析,着重分析了Linux的负载评价因子L和调度策略因子S。针对Linux调度器不考虑进程迁移代价的不足提出了基于资源利用率的负载均衡算法,通过计算进程的CPU利用率和内存利用率来选择迁移进程,然后通过统计系统中的过载CPU和轻载CPU,根据Donor或者Reciever算法来匹配源CPU和目的CPU。
【图文】：

时间片,进程,剩余时间,调度程序

3. 最短进程减少 FCFS 固有的对长进程的偏爱的另一种方法是最短进程（S，SPN）策略。这是一个非剥夺的策略，其原则是下一次选择所进程。因此，短进程将会越过长作业，跳到队列头。SPN 的风险在于只要持续不断地提供更短的进程，长进程就有方面，尽管 SPN 减少了对长作业的偏爱，但是由于缺少剥夺机或事务处理环境仍然不理想。4. 最短剩余时间最短剩余时间（Shortest Remaining Time，SRT）是对 SPN 增加。在这种调度机制下，调度程序总是选择预期剩余时间最短的进个进程加入就绪队列时，它可能比当前运行的进程具有更短的只要新进程就绪，调度程序就剥夺当前进程并使新进程运行。和程序在执行选择函数时必须包含对处理时间的估计，并且存在险。5. 最高响应比根据排队模型，周转时间（turnaround time，TAT）就是驻留时

组织结构图,组织结构图

Intel 公司所实现的 SMT 技术就是超线程(Hyper-Threading, HT)[13]技术。超线程技术实际上只有一个实际的物理处理器但是从软件角度来看，存在多个逻辑处理器。超线程技术支持操作系统和应用程序将多个线程调度到多个逻辑处理器上，，就像多处理器一样。从微体系结构的角度来看，逻辑处理器的指令都是固定的，并且在共享的执行资源上同时执行。2.3.2 CMP 结构在同时多线程技术之后就出现了多核处理器。在 1996 年斯坦福大学的研究人员提出了单片多处理器（Chip Multi-Processor，CMP）结构，并进行了研究[14]。单片多核处理器的主要思想是通过简化超标量结构设计，将多个相对简单的超标量处理器核集成到一个芯片上，从而避免线延的影响，并充分开发 TLP，提高吞吐量。CMP 存在的主要问题是由于单片多处理器系统的资源是采用划分方式的,当没有足够的线程时,资源就浪费了[15]。按计算内核的对等与否，CMP 可分为同构多核和异构多核。计算内核相同，
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2009
【分类号】：TP332

【引证文献】