多核处理器中具有临界区的多线程调度方法研究

• 作 者: 李旭
• 机 构: 华北电力大学
• 出 处: 华北电力大学
• 发表日期: 2017年期
• 关键词: 临界区 多线程调度 多核 多线程模型 临界区迁移

随着多核技术以及多线程技术的发展,多线程在多核处理器上的调度问题成为研究热点。由于多核处理器结构的复杂性,使得资源管理更困难。当多线程在多核平台上运行时,怎样更好的利用多核资源,让多线程能够正确快速的执行,决定了系统性能的提高。一个优秀的针对多核处理器的线程调度算法可以有效利用资源,提高系统吞吐率,兼顾公平性,降低程序的响应时间和周转时间。对于多核多线程的调度方法的研究,一般都先提出一种多线程的模型,并在这种模型的基础上针对不同的多核平台提出不同的调度方法。在多线程模型上,很多人都选择DAG图,但是传统的DAG图有其自身的缺陷,例如不能对任务间的关系进行近一步的刻画。本文针对具有临界区的线程,提出一种基于Forest的多线程调度模型,通过该模型维护线程间的前后依赖、数据资源和共享资源关系。为有效的提高系统性能,减少计算资源空闲时间,提出了综合考虑线程共享资源情况以及前后依赖关系的调度方法CSTS算法。该算法以临界区作为线程间共享资源的依据,对具有相同临界区线程进行同核调度。并且由于临界区不可同时执行的特点,临界区成为限制系统整体性能的重要因素。为减少由临界区而造成的堵塞,算法提出了基于临界区的优先级计算方法,并且兼顾公平性。在多核处理器中,由于各核间计算能力的不同,异构多核处理器较同构多核处理器更具有实用性。因此,本文除针对一般多核处理器设计了多线程模型以及基于该森林模型的调度方法外,还针对异构多核处理器各核间处理能力的不同,优化了加速临界区算法。加速临界区算法可以有效缩短具有临界区的线程的执行时间,但是有可能会造成无关临界区串行化的问题。本文在加速临界区算法基础上提出改进加速临界区算法。该算法跟踪记录所有包含临界区的线程在核上的执行情况,对线程的优先级因子进行调整,通过该优先级因子指导线程在高速核与低速核间的动态迁移。该算法不仅加速了临界区的执行而且能有效解决加速临界区方法所造成的线程在高速核上的堵塞的问题。本文采用模拟实验的方法对基于森林线程模型的算法进行模拟验证。较同类算法对于临界区密集型任务具有较高的性能,核利用率也较高。针对于适应于异构平台改进临界区迁移算法,本文采用Simics仿真平台进行异构多核系统仿真,输入为12个临界区密集型负载,实验结果表明,该方法较原始加速临界区算法和朴素算法拥有更好的性能。