Linux系统超线程感知的调度算法研究 （2）

active_load_balance( )通过调用cpu_rq( )函数得到每一个逻辑CPU上的运行队列。如果运行队列上的当前运行线程为idle线程则说明当前逻辑CPU为空闲，如果发现一个物理CPU两个逻辑CPU都为空闲，而另一个物理CPU中的两个逻辑CPU的运行队列为繁忙的情况，则说明存在超线程引起的负载不均衡。这时当前CPU会唤醒迁移服务线程（migration_thread）来完成负载均衡的线程迁移。

（4）支持超线程感知的任务挑选

在超线程处理器中由于cache资源为两个逻辑处理器共享，因此调度器在选取一个新任务时，必须确保同组的任务尽量共享一个物理CPU，从而减少cache 失效的开销，提高系统的性能，而传统的调度器只是简单地为逻辑CPU选取一个任务，没有考虑物理CPU的影响。

Linux进行线程切换时会调用schedule( )函数进行具体的操作，如果没有找到合适的任务schedule（）函数则会调度idle线程在当前CPU上运行，在超线程环境中Linux调度idle线程运行之前会查询其同属CPU的忙闲状况，如果同属CPU上有等待运行的线程则会调用一次load_balance( )函数在两个同属CPU之间作一次负载均衡，将等待运行的线程迁移到当前CPU上，保证优先运行同属CPU上的任务。

（5）支持超线程感知的CPU唤醒

传统的调度器只知道当前CPU，而不知道同属的逻辑CPU，在超线程环境下，一个逻辑 CPU 正在执行任务，其上的一个线程被唤醒了 ，但它的同属逻辑CPU是空闲的，则应该在同属逻辑CPU上运行刚刚唤醒的任务。

Linux通过wake_up_cpu( )函数来实现CPU唤醒，在try_to_wakeup,pull_task,move_task_away加入了wake_up_cpu( )函数的相应调用点。wake_up_cpu（）首先查询当前CPU是不是空闲的，如果当前CPU为空闲，则调用resched_cpu( )函数启动调度器，将唤醒的线程调度上当前CPU执行 。如果当前CPU不是空闲，则查找其同属逻辑CPU，如果同属逻辑CPU是空闲的，则将唤醒的线程调度上同属逻辑CPU上执行。如果同属逻辑CPU也不为空闲，则再比较唤醒的线程和当前CPU上运行的线程的优先级，如果唤醒的线程的优先级高，或者优先级相等但是时间片多，则进行线程切换，在当前CPU上调度执行唤醒的线程。如果上述条件都不满足，最后比较唤醒的线程和当前CPU的同属逻辑CPU上运行的线程的优先级，如果唤醒的线程的优先级高，或者优先级相等但是时间片多，则在同属逻辑CPU上调度唤醒的线程

4 性能测试

Linux-2.6.0 HT-aware scheduler patch实现了上述的超线程调度优化，这里根据linux-2.6.0 HT-aware scheduler patch对这几种调度优化进行了性能测试。

测试硬件环境：Xeon 2.2G处理器（支持超线程）×4，2G SDRAM内存。

Benchmark：(1) volanomark是一个纯java的benchmark，专门用于测试系统调度器和线程环境的综合性能，它建立一个模拟Client/Server方式的Java聊天室，通过获取每秒平均发送的消息数来评测宿主机综合性能（数值越大性能越好）。Volanomark测试与Java虚拟机平台相关，本文使用Sun Java SDK 1.4.2作为测试用Java平台，Volanomark版本2.5.0.9。(2) LMBench： 是一个用于评价系统综合性能的多平台开源benchmark，,我们对其进行了修改实现了 lat_thread_ctx接口,用来测试线程的切换开销。

表4表明开启超线程后volanomark在Linux-2.6.0平台下平均吞吐量提高了25.5％。由于Linux的O(1)内核调度器实现比较好的SMP负载均衡算法，所以在超线程环境下整个系统的性能也有比较好的提升。

Linux在进行了超线程调度优化后，在支持超线程的平台上的获得的性能加速比。在Linux-2.6.0加入HT-aware scheduler patch后volanomark的平均吞吐提高了 8.5％，分别实现支持主动负载均衡，被动的负载均衡，CPU唤醒和任务挑选的相关代码后，吞吐量分别提高了1.8.%,.2.5%,2.3%和2.1％。

我们使用Lmbench创建了10~150个线程,测试在不同的负载条件下线程的切换开销。表一的数据显示HT-aware scheduler patch可以将线程的切换开销减少3%～7%。数据显示在轻负载情况下，系统可以获得更多的加速比。因为被动的负载均衡以及主动的负载均衡只有在系统有CPU空闲时才能发挥比较好的作用。

5 相关工作和展望

采用支持超线程技术的Linux可以获得较大的性能提升。但是其调度算法还要根据实际的应用进一步研究。在文献[7]中，提出“Symbiosis”概念用来衡量多个线程在SMT环境中同时执行的有效性。在文献[8]中提出了线程敏感的调度算法，用一组硬件性能计数器计算在两个逻辑CPU上运行不同作业子集的执行信息，利用这些信息来预测不同作业子集的执行性能，并选择具有最好预测性能的作业子集调度上同一个物理CPU执行。文献[9]中主要研究适合SMT 结构并考虑作业优先级的调度器。研究结果表明，这些调度算法能有效提高超线程系统的性能。

Intel的超线程技术是其企业产品线中的重要特征，并将会集成到越来越多的产品中，它标志着Intel微处理器一个新的时代：从指令级并行到线程级并行，这样使微处理器运行模式与多线程应用的运行模式更加接近，应用程序可以充分利用线程级和指令级并行进行优化。随着超线程处理器的发展可能会出现操作系统使用处理器系统中硬件性能监视器估算系统在某一个时间段的某些性能指标，然后利用这些性能指标来指导线程的调度策略。