基于动态自适应策略的多核调度算法分析

《基于动态自适应策略的多核调度算法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据东北大学硕士学位论文目录6．2研究展望⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．57参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯．59致谢⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯63VII万方数据东北大学硕士学位论文第1章绪论1．1研究背景随着半导体工艺的不断发展，人们通过提高处理器主频的方法来提高处理器性能。但随着芯片制造工艺的不断进步，从体系结构看，传统的处理器体系结构技术已面临瓶颈，集成的晶体管数量有数亿个，半导体工艺达到了物理极限，很难通过提高主

2、频来提升性能，并且主频提高的同时引起功耗的不断提高，单核处理器性能提升遭遇瓶颈【l】；从应用需求看，日益复杂的科学计算、多媒体等众多应用领域都需要有更强大计算能力的计算机。在这种背景下，多核处理器应运而生并得到了迅速的发展【2】，多核处理器已成为处理器的主流产品。高速发展的处理器芯片技术发生了革命性的变化，已经由单核处理器发展成为多核处理器。多核处理器系统提供了高性能计算的硬件基础，然而系统性能的提高不仅在于硬件的支持，更需要软件系统的支撑。操作系统作为计算机系统重要组成部分的系统软件，管理计算机硬件并为应用程序提供执行环

3、境。操作系统能否为应用软件提供基础平台，是否支持多处理器结构是多核处理器系统应用的基础问题，操作系统中与处理器系统联系最紧密、最为核心的部分是任务调度系统，任务调度算法的好坏直接影响着系统性能的发挥，高效的任务调度算法是提高系统性能的关键所在，并且能够合理地利用系统中的各种资源，调度不当则会降低多核处理器的性能【3】。因此任务调度算法的研究成为计算机科学技术研究最基本的课题。1．2研究现状任务调度作为多核系统的一个新的研究热点，大量学者对多核处理器系统任务调度算法进行了深入的研究，并取得了许多有效成果。1．2．1国外研究现

4、状Freund和Gherrityt4]提出了MCT(MinimumCompletionTime)算法，该算法将任务分配到最早完成时间的处理器上执行调度，由于任务在处理器上执行时间的差异，该算法适合同构处理器任务调度。Andersson和Jonsson[5】提出了基于多核动态到达周期任务的一个高效的、非抢占式调度算法。TanPL[61提出一种混合调度算法，为了达到更好的并行性，首先尽可能地将应用程序分割成若干个并行任务；其次将这些任务分配到不同的核上。Chetto等【7】讨论了在分布式实时系统中采用流水化处理周期任务的方法。

5、万方数据东北大学硕士学位论文第1章绪论通过对异构环境下的任务调度进行大量分析，HalukTopcuoglu和SalimHaririt8】在此基础上提出了两种调度效率较高的算法：CPOP(Critical．Path—on．a-Processor)和HEFT(HeterogeneousEarliest．Finish．Time)算法。CPOP算法和HEFT算法都属于启发式表调度算法，其基本思想是：首先确定任务的优先级，然后根据任务优先级对任务进行调度，将任务分配到具有最早完成时间的处理器。Baruah和Goossensl9,10

6、]改进了基于单核处理器的EDF算法，使EDF算法扩展到一组异构多核上，其研究的是周期任务系统的一个子集，只适合独立任务之间的调度。Shin和AbdelzahertllJ根据任务的周期性将任务进行分簇，提出了适应异构多核、扩展性强的调度算法。S．Ali等【l2J分析了Max．min算法、Min．min算法等任务调度算法，论述了各算法之间的不同。SanjeevBaskiyar等IJ3J提出了关键任务优先调度算法，该算法保证关键路径任务优先调度，有利于缩短整个任务的总调度长度。该算法不适用于独立任务的调度，为了解决这一问题，Sa

7、njeevBaskiyar等提出了最大任务优先算法，通过将最大任务调度到最早完成时间的处理器执行，减少了任务的执行时间，降低了算法的复杂度。1．2。2国内研究现状国内在多核处理器任务调度方面的研究起步比较晚，但也取得了不少成果。王俊祥f14】详细讨论了先来先服务调度算法、最高优先权优先调度算法、时间片轮转调度算法、短任务优先调度算法等常用任务调度算法的基本思想，并对算法进行了分析和评价。金海等Ll5J在典型任务调度算法的基础上，研究了Min-Min算法，该算法每次选择小任务分配到执行它最快的处理器，反复执行相同的策略直到完

8、成，缺点是如果系统中不断有任务进入，大任务将无法得到及时处理。何小珊等【16】提出了Max．Min调度算法，该算法每次选择大任务分配到执行它最快的处理器，反复执行相同的调度策略直到完成，该算法对小任务不利，等待时间过长。袁云和邵时【17J提出了两轮操作完成任务分配与调度，首先用启发式任务分组，将任务分配