面向多核处理器的任务调度模型研究

摘要

随着多核处理器的技术快速发展，多核处理器不但性能远远超过传统单核处理器，而且兼具低功耗的优势，这些优势使得多核处理器越来越多地应用到各种不同的领域中。而对于多核处理器，影响其性能发挥的一个关键是任务调度。国内外学者提出了多种任务调度模型与算法，都有着各自的优缺点，但很少有人针对共享资源约束的情况下进行任务调度的研究。本文针对具有共享资源约束的多核任务调度模型进行研究。
　　多核处理器的任务调度已经被证明为是一个NP难问题，现有的解决办法大多是使用启发式算法。在这些启发式算法中，节约算法是调度成功率较高的一种算法。但是节约算法并未考虑任务间的并行性，仅仅是利用任务截止期进行判断，没有充分利用共享资源的约束。在任务之间的关联性较大、互斥资源较多的情况下，访问核间互斥资源的开销很大，容易使任务长时间的等待互斥资源，导致核的利用率降低，调度的成功率减小。针对这个问题，本文引入了任务相关度的概念，利用任务相关度来判断任务之间关联性的大小、共享互斥资源的多少，从而将任务相关度较大的多个任务尽量调度到同一个核当中，来减少相关任务间的互斥访问的开销。通过实验证明，改进的节约算法在共享资源较多的情况下比原算法有着更小互斥访问开销。
　　在现有的任务调度模型中，最常见的是集中式调度模型，节约算法就采用该种模型。而这种模型有一个集中的全局调度器，将任务调度到各个计算核进行处理。国内外学者对任务调度模型仅比较计算核的利用率，忽视了调度核的利用率，导致调度核与计算核之间处理能力的不均衡。本文新提出一种任务调度模型来解决这一问题。而多数任务调度模型使用存在于共享数据区的任务队列作为核间任务传递的主要方式，所以任务队列的性能十分关键。在现有的任务队列中，MS算法是经典的多生产者多消费者队列，但是MS算法中存在着伪共享缓存缺失的问题，本文解决这一问题并将改进的MS算法应用到新提出的任务调度模型中。最后通过实验证明，本文提出的任务调度模型比原本的集中式调度模型有着更均衡的处理能力。

目录

声明

摘要

第1章绪论

1．1论文研究背景及意义

1．2论文研究内容

1．3论文组织结构

第2章相关技术与研究现状

2．1引言

2．2多核处理器

2．2．1多核处理器的发展

2．2．1多核处理器的分类

2．2．2多核处理器的关键技术

2．2．3 Octeon多核处理器

2．3多核任务调度技术

2．3．1多核任务调度准则

2．3．2多核任务调度分类

2．3．3国内外研究现状总结

2．5本章小结

第3章一种限于共享资源约束的多核任务调度选择算法

3．1引言

3．2相关工作分析

3．2．1节约算法介绍

3．2．2分组适度算法介绍

3．3共享资源约束下的改进节约算法

3．3．1任务相关度

3．3．2相关定义

3．3．3改进算法描述

3．4实验结果与分析

3．4．1实验方案

3．4．2实验评价标准

3．4．3实验结果及分析

3．5本章小结

第4章一种基于共享内存的多核处理器任务调度分配模型

4．1引言

4．2相关工作分析

4．2．1任务调度分配模型

4．2．1高性能的无锁队列算法

4．3基于共享内存的任务调度分配模型

4．3．1改进的多生产者多消费者无锁队列算法

4．3．2改进的任务调度分配模型

4．4实验结果与分析

4．4．1实验方案

4．4．1实验结果及分析

4．5本章小结

结论

参考文献

攻读硕士学位期间发表的论文和取得的科研成果

致谢