注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Crayon

只想做自己

 
 
 

日志

 
 

Linux超线程感知的调度算法研究  

2012-03-04 20:56:49|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  随着计算机应用的日益普及,用户对计算机的处理能力的需求成指数级增长。为了满足用户的需求,处理器生产厂商采用了诸如超流水、分支预测、超标量、乱序执行及缓存等技术以提高处理器的性能。但是这些技术的采用增加了微处理器的复杂性,带来了诸如材料、功耗、光刻、电磁兼容性等一系列问题。因此处理器设计人员开始寻找新的途径来提高处理器的性能。Intel公司于2002年底推出了超线程技术,通过共享处理器的执行资源,提高CPU的利用率,让处理单元获得更高的吞吐量。

  1 超线程技术背景

  传统的处理器内部存在着多种并行操作方式。①指令级并行ILP(Instruction Level Paramllelism):同时执行几条指令,单CPU就能完成。但是,传统的单CPU处理器只能同时执行一个线程,很难保证CPU资源得到100%的利用,性能提高只能通过提升时钟频率和改进架构来实现。②线程级并行TLP(Thread Level Paramllesim):可以同时执行多个线程,但是需要多处理器系统的支持,通过增加CPU的数量来提高性能。

  超线程微处理器将同时多线程技术SMT(Simultaneous Multi-Threading)引入Intel体系结构,支持超线程技术的操作系统将一个物理处理器视为两个逻辑处理器,并且为每个逻辑处理器分配一个线程运行。物理处理器在两个逻辑处理器之间分配高速缓存、执行单元、总线等执行资源,让暂时闲置的运算单元去执行其他线程代码,从而最大限度地提升CPU资源的利用率。

  Intel 超线程技术通过复制、划分、共享Intel的Netburst微架构的资源让一个物理CPU中具有两个逻辑CPU。(1)复制的资源:每个逻辑CPU都维持一套完整的体系结构状态,包括通用寄存器、控制寄存器、高级可编程寄存器(APIC)以及一些机器状态寄存器,体系结构状态对程序或线程流进行跟踪。从软件的角度,一旦体系结构状态被复制,就可以将一个物理CPU视为两个逻辑CPU。(2)划分的资源:包括重定序(re-order)缓冲、Load/Store缓冲、队列等。划分的资源在多任务模式时分给两个逻辑CPU使用,在单任务模式时合并起来给一个逻辑CPU使用。(3)共享的资源:包括cache及执行单元等,逻辑CPU共享物理CPU的执行单元进行加、减、取数等操作。

  在线程调度时,体系结构状态对程序或线程流进行跟踪,各项工作(包括加、乘、加载等)由执行资源(处理器上的单元)负责完成。每个逻辑处理器可以单独对中断作出响应。第一个逻辑处理器跟踪一个线程时,第二个逻辑处理器可以同时跟踪另一个线程。例如,当一个逻辑处理器在执行浮点运算时,另一个逻辑处理器可以执行加法运算和加载操作。拥有超线程技术的CPU可以同时执行处理两个线程,它可以将来自两个线程的指令同时发送到处理器内核执行。处理器内核采用乱序指令调度并发执行两个线程,以确保其执行单元在各时钟周期均处于运行状态。

  图1和图2分别为传统的双处理器系统和支持超线程的双处理器系统。传统的双处理器系统中,每个处理器有一套独立的体系结构状态和处理器执行资源,每个处理器上只能同时执行一个线程。支持超线程的双处理器系统中,每个处理器有两套独立体系结构状态,可以独立地响应中断。

传统的双处理器系统和支持超线程的双处理器系统

  2 Linux超线程感知调度优化

  Linux从2.4.17版开始支持超线程技术,传统的Linux O(1)调度器不能区分物理CPU和逻辑CPU,因此不能充分利用超线程处理器的特性。Ingo Monlar编写了“HT-aware scheduler patch”,针对超线程技术对O(1)调度器进行了调度算法优化:优先安排线程在空闲的物理CPU的逻辑CPU上运行,避免资源竞争带来的性能下降;在线程调度时考虑了在两个逻辑CPU之间进行线程迁移的开销远远小于物理CPU之间的迁移开销以及逻辑CPU共享cache等资源的特性。这些优化的相关算法被Linux的后期版本所吸收,具体如下:

  (1)共享运行队列

  在对称多处理SMP(Symmetrical Multi-Processing)环境中,O(1)调度器为每个CPU分配了一个运行队列,避免了多CPU共用一个运行队列带来的资源竞争。Linux会将超线程CPU中的两个逻辑CPU视为SMP的两个独立CPU,各维持一个运行队列。但是这两个逻辑CPU共享cache等资源,没有体现超线程CPU的特性。因此引入了共享运行队列的概念。HT-aware scheduler patch在运行队列struct runqueue结构中增加了nr_cpu和cpu两个属性,nr_cpu记录物理CPU中的逻辑CPU数目,CPU则指向同属CPU(同一个物理CPU上的另一个逻辑CPU)的运行队列,如图3所示。

共享运行队列

  在Linux中通过调用sched_map_runqueue( )函数实现两个逻辑CPU的运行队列的合并。sched_map_runqueue( )首先会查询系统的CPU队列,通过phys_proc_id(记录逻辑CPU所属的物理CPU的ID)判断当前CPU的同属逻辑CPU。如果找到同属逻辑CPU,则将当前CPU运行队列的cpu属性指向同属逻辑CPU的运行队列。

  评论这张
 
阅读(272)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017