多核平台全局EDF算法的可调度性判定研究.docx

多核平台全局EDF算法的可调度性判定研究
多核平台全局EDF算法的可调度性判定研究
随着多核处理器在大型计算机和嵌入式系统中的应用越来越广泛，对多核平台的调度问题越来越受到关注。MPCP（多处理器耦合协议）[1]是最早提出的多核处理器任务调度协议之一。它采用静态分配的方式将处理器分配给任务，并以保证可调度为目标。但是其分配静态化不能独立适应任何平台。全局EDF（EarliestDeadlineFirst）算法则更符合将任意数量任务载入平台并使其能够保证调度（即可调度性），从而实现更具灵活性的任务调度需求。
本文就多核平台全局EDF算法的可调度性判定进行探讨，并对其进行分析和验证。
1.多核平台全局EDF算法原理
EDF算法是一种贪心算法，能够保证在一个单处理器上多个任务严格按照截止时间的顺序执行。其基本思想是选用截止时间最早的任务进行执行。
但是多核处理器上的任务调度则需要考虑不同核的负载情况，以及各个核之间的协调。因此需要基于EDF算法进行改进。全局EDF算法采用了任务优先级继承（PriorityInheritance）技术，因此可以适用于多核环境下的任务调度。
多核平台全局EDF调度算法通过在每个处理器上使用本地EDF算法，以达到全局EDF调度目的。即首先在本地找到最早的截止时间任务，之后全局扫描所有的进程、任务，如发现一个任务比本地最早截止时间还要早，则在本地抢占任务。通过这样的方式，全局EDF算法可以确保所有核上的任务都按照“最早截止时间优先”原则被分配并调度。
2.可调度性判定
多核平台全局EDF调度算法在执行过程中需要考虑可调度性。在任务分配后，每个处理器需要能够按照EDF算法的原则将任务分配到可用的处理器上。
对于多核平台全局EDF算法的可调度性判定，有多种方法可以进行实现。其中一种常用的方法是利用伸缩性风险（ScaleabilityRisk）指标来评估可调度性。该方法是通过将问题分解成一组小问题、比较每个问题大小、按比例扩放问题，并在每个问题上执行算法来实现的。
伸缩性风险指标（SR）是根据处理器数量（P）来计算的，其表达式如下：
SR=∑i=1n(Ci/Ti)-P
其中，Ci是任务i的计算时间，Ti是任务i的截止时间，n是任务数量。显然，当SR>0时，任务可以满足调度要求。
3.实验验证
为了验证多核平台全局EDF算法的可调度性，我们进行了一系列实验。实验平台为多核处理器，其中包括8个处理器和10个任务。
通过对每个任务的处理时间、优先级以及截止时间进行设定，以模拟出一个多核平台下的任务调度过程。
通过实验，我们发现，对于全局EDF算法，当任务数量较少时，调度效果非常好，但是当任务数量增加到一定程度时，调度效果反而会下降。这是由于当任务数量过多时，需要对任务进行更多的协调和分配，因此会受到处理器数量的限制，从而导致调度效果下降。
4.结论
多核平台全局EDF算法是一种优秀的调度算法，能够适用于多核平台下的任务调度。通过本文的探讨，我们对该算法的可调度性判定方法和实验验证进行了详细讨论，得出了一些结论。
总体而言，多核平台全局EDF算法可以通过伸缩性风险指标来进行可调度性的判定，但是该方法无法完全解决可调度性判定问题。在实际应用中，需要根据具体的应用场景，综合考虑处理器数量、任务数量、处理尺寸、任务优先级等多种因素，以做出最优的任务调度方案。
参考文献：
[1]Liu,C.L.,&Layland,J.W.(1973).Schedulingalgorithmsformultiprogramminginahardreal-timeenvironment.JournaloftheACM(JACM),20(1),46-61.