学年论文题目Linux调度器对多核处理器的支持学生指导教师副教授年级2008级专业计算机科学与技术系别计算机系学院计算机科学与信息工程学院2011年11月论文提要随着科学技术发展，各种各样嵌入式设备快速发展，同时Linux操作系统也得到了更加广泛的应用。

嵌入式设备的应用包括了手机、便携式电脑、GPS、游戏机等。

虽然不同的嵌入式设备对于运行在其中的Linux操作系统有着不同的要求，但是Linux操作系统的任务调度器还是在其中起着至关重要的作用。

随着Linux版本的更新，Linux任务调度器也在不断的发展，功能从简单到复杂。

计算机是一个系统，包含了软件和硬件。

仅仅对其中的硬件进行修改并不能使整个系统的性能得到本质的提高，必须有软件的辅助。

系统的任务调度器给与处理器足够的支持，才能使多核处理器在操作系统中发挥出其真正优势。

本文主要研究Linux系统调度器对多核处理器的支持。

Linux调度器对多核处理器的支持李明摘要：本文对CFS调度器源码进行了分析，并使用Linux内核调度模拟器Linsched 对最新的CFS调度器的工作进行了功能性模拟。

深入理解分析了调度器中各个模块的工作流程及其对于多核处理器的支持。

通过功能性模拟得到多核处理器体系结构下调度器调度特性，结合实验讨论处理器核数和调度粒度对于调度器性能的影响。

定义了用吞吐量和响应时间与调度器性能的关系式，利用这个关系式讨论针对不同实际任务优化调度器的方法。

关键词：CFS调度器多核处理器体系结构Linux任务调度器一、多核处理体系结构（一）多核处理器的相关技术在处理器的初期研究过程中，处理器性能的提高主要利用超标量技术((Superscalar),其实现是每个时钟周期发射多条指令到功能部件上执行，其目的是利用程序的指令级并行(Instruction-Level Parallelism, ILP)来提高处理器的处理能力。

可是，超标量处理器在单个程序下，由于ILP不高所以资源利用率不高，一味增加指令发射宽度只能使情况变差。

并行性不能只限于ILP，从而线程级并行性(Thread-Level Parallelism, TLP)被引入进来。

实现包括:多线程处理器(Multithreaded Processor)、同时多线程(Simultaneous Multithreading, SMT)、单片多处理器(Chip Multi Processor, CMP)。

在2005年时，SLTN公司又提出了将CMP与SMT结合起来的构想，并研制出了CMT(Chip Multithreading)处理器。

（二）SMT结构SMT结构的实现原理是:在一个时钟周期内发射多个线程的指令到功能部件上执行，以提高线程对于功能部件的利用率。

此设计由加利福尼亚大学的Tullsen于1995年在华盛顿大学攻读博士提出，他提出的SMT结构仅仅对传统超标量处理器结构做了少量的改动，但得亘了明显的性能提升(11]。

因此，一些主流的商业微处理器也采用了这种设计，如DEC Alpha21464t12], Intel Xeontl3]。

超标量处理器的SMT设计是基于乱序执行(Out of order3xecution) (1l]的，这样就解决了大寄存器读写和指令调度在内的具体实现问题。

Intel 的研究人员也基于SMT技术设计了超线程(Hyper-Threading,HT)技术[14]。

从硬件上看只有一个物理处理器，但是从程序运行角度上看，却有多个逻辑处理核心。

（三）CMP结构片上多处理器(Chip Multiprocessor CMP)结构是由斯坦福大学的研究小组提出的。

其设计思想是通过简化超标量结构设计，将多个相对简单的超标量处理器核集成到一个芯片上，这样就避免了如多处理器SMP芯片上类似的线延的缺点，从而提高了线程级并行性，改善了处理器吞吐量。

但CMP处理器还是存在着明显的缺点，它的资源是采用划分方式的，当没有足够的线程时，资源就浪费了，而高效的调度算法就可以来解决这个问题按计算内核的地位对等与否，CMP可分为同构多核和异构多核。

典型的同构多核处理器是Intel最新的多核处理器架构一Core微架构。

典型的异构多核处理器是由索尼、东芝和IBM共同研发的多核心微处理器—Cell处理器。

（四）CMT结构为了解决CMP结构中存在的TLP利用率较低的情况，S LJN公司的研究人员将CMP 与SMT两种技术结合了起来，发展出了CMT技术。

CMT技术继承了两者的优点，既有SMJ 的高资源利用率的特点，又有CMP结构]实现的简单性。

SUN公司宣称在Niagara处理器中使用这种新的多核多线程技术。

（五）现有操作系统对多核处理器的支持通用的操作系统都支持多任务的执行，利用单核处理器进行分时处理，给系统中的任务分给不同长度的时间片，使用时间片轮转算法，从而达到多任务处理。

对于多核处理器这种新的架构，操作系统也不需要做很大的更改。

由于许多操作系统本身就对于多路处理器有支持，基本不用做改变就可以实现对多核处理器的支持。

二、对多核计算机硬件系统的研究（一）多核处理器的体系结构多核处理器是指将多个中央处理单元的内核集成在同一个处理器芯片中的处理器。

其通过将任务分解到多个中央处理单元来提高计算机系统的计算能力。

本文主要研究的是Intel 公司的多核处理器。

这种多核处理器的特点是:在一个芯片上包括多个处理器核心，每个处理器核心地位都相同并且都是采用X86体系结构设计的，而且每个处理器核心具有独立的一级缓存，所有处理器核共享一个大的二级缓存。

各个处理器核心通过片内的高速互联总线来进行通信，这样使得各个处理器核心上执行的程序之间进行数据共享与同步成为可能。

Intel多核处理器通过允许多个现程同时的并行执行，从而改善了芯片资源的利用率。

为了提高多核处理器的性能，我们的办法是先识别出可能成为系统性能瓶颈的资源(包括一级缓存，二级缓存，处理器线路等)，而后审查操作系统的相应模块，并针对此瓶颈进行优化设计。

通过研究发现影响多核处理器性能的主要瓶颈是二级缓存缺失率的大小和处理器线路利用率。

在后续部分将详细描述降低二级缓存缺失率和提高处理器线路利用率的方法。

（二）用多核技术来提高计算机系统性能的可行性分析要使多核的超强计算能力体现在应用程序的性能提高上，我们必须优化目前主要面向单核处理器的操作系统和编译器。

我们先从理论上对多核处理器对应用程序(通常作组线程在操作系统中运行)的性能提高(用并行加速比来衡量)进行分析。

并行加速比就是指对于一个给定的应用程序，采用并行算法的执行速度和采用串行算法的执行速度相比加快了多少倍。

为了下面讨论的方便，定义如下参数:nrCore为多核处理器中处理器核的数目;W是应用程序的问题规模，Ws是应用程序中的串行部分的问题规模，Wp是应用程序中的可并行化部分的问题规模(cW=Ws+Wp); W。

为应用程序在多核系统中运行的额外开销，在将一个应用程序分解到多个可并行执行的多个线程时，额外花费w。

为:线程的创建，终止，切换的花费，线程间通信的花费，线程间的同步的花费，线程空闲时间的总和等;f是串行分量占问题总量的比例(f = Ws/w)，1-f为并行分量占问题总量的比例;S为加速比。

我们先从理论上分析多核处理器对应用程序(通常作为一个进程在操作系统中运行)性能的提高情况(用并行加速比来衡量):简单地讲，并行加速比就是指对于一个给定的应用程序，采用并行算法的执行速度对于串行算法的执行速度加快了多少倍。

1．用固定应用程序问题规模的Amdahl加速定律如果我们将应用程序的问题规模固定，并且将并行部分平均分解到p个线程中，每个线程在一个CPU中运行。

则S=(ws+wp>/(ws+饰/p+wo)分式上下同除以w得:S二(f+(1-f))/(f+(1-f) /p+wo*p/w)=P/(1+f (p-1)+p*wo/w)当p趋于无穷大时，上式变为:s=1/(f+wo/w)由上式我们会得到一个比较悲观的结论:即使CPU的数目无限增大，并行系统所能达到的加速上限为1/ (f+Wo/W)。

如果f=0.8，则即使我们将处理器核的数目增加到超过16个其性能提高也不会超过2596。

也就是说，增加CPU数量对现有应用程序(问题规模固定的性能提高理论上限。

2．问题规模随CPU数目线性增长的情况我们设Wsl为在cpu个数为1时的Ws, Wpl为在cpu个数为1时的wp, w1为在cpu数目为1时的W;因为假设问题规模随nrCore线性增长可设W (nrCore)二u*nrCore*W1，u为常数，在实际分析中我们发现串行部分的问题规模通常相对比较固定并不会因为线程数的增加或计算精度的提高而线性增长，因此我们可以将上式改写为:W(p)=u*Wsl+u*nrCore*Wpl。

根据Gustafson定律，得放大问题规模的加速公式：S=(Ws+wp)/(Ws+Wp/nrCore+Wo)=(u*Wsl+u*nrCore*Wpl)/(u*Ws1+u*nrCore*Wpl/nrCore+Wo)=(f+nrCore(1-f))/(1+Wo/ (u*W1))从上式可以看出，当nrCore充分大时，假设w。

花费不会增加太多则s与p几乎成线性关系，其斜率为1-f.串行比例f不再是程序的瓶颈。

而且在现实应用中，应用程序的基于上面的论证，各主流处理器厂商纷纷将产品战略从提高芯片的时钟频率转向实现片上多内核与超线程技术。

三、CFS完全公平调度器分析（一）CFS调度器简介在Linux2.6.23内核中发布CFS(Completely Fair Scheduler)调度器，它采用了与以往调度器完全不同的设计理念。

CFS完全公平调度器相对于以前的任务调度器的主要改进在于以下几个方面:1．使用红黑查找树这种数据结构取代了复杂的数学公式，经实验证明这种改变不但没有导致性能降低，而且在公平性上有了一定的提高。

2．取掉了静态时间片的概念，取而代之的是动态时间片的概念，即virtual runtime。

这样以来，减轻了某些高优先级进程对于处理器的独占情况，保证了调度的公平性。

3．增加了组调度这种调度方式，方便用户控制系统资源的分配。

也方便管理员根据任务的轻重缓急，对有限的资源进行分配。

4．调度器的负载平衡模块加强了对多核处理器负载平衡的支持。

把负载平衡与处理器功耗控制联系起来，使多核处理器的功耗控制更加聪明。

（二）CFS调度器代码分析1．调度器中的重要数据结构Linux完全公平调度器源代码中有几个比较重要的数据结构，它们对于调度器的工作起了至关重要的作用，下面我们就逐一分析一下这些数据结构。

1)调度类结构和完全公平调度类结构:调度类结构中声明了调度器的相关操作函数，引将其分为三类，常用操作、与组调度相关的操作和与SMP或多核负载平衡相关的操作。