A novel real-time scheduling algorithm and performance analysis ...

MapReduce编程模型是一种为处理数据密集型任务而设计的流行编程模型，已在搜索索引、社交网络挖掘、协同推荐和垃圾邮件检测等多种应用中取得巨大成功。然而，MapReduce的默认调度器存在两个方面的局限性：它不支持共享云计算中心的并发服务；它不能保证截止期限约束的服务的响应时间。本文提出了一种名为Paused Rate Monotonic（PRM）的新实时调度算法，用于在基于MapReduce的云上调度硬实时任务。通过理论分析对调度性能进行了分析，并证明了集群利用率的上限，可以作为测试给定任务集是否可以被调度的充分条件。理论分析和实验评估都表明，PRM算法在提升在基于MapReduce的云上调度实时任务集的概率方面优于传统的实时调度算法。 MapReduce模型能够支持大数据中心以云计算服务的形式提供计算资源，近年来各大公司对此进行了大量投资。MapReduce因其强大的并行计算能力而成为云计算数据中心的基础编程模型。然而，为了更好地调度实时任务，尤其是硬实时任务，传统的调度器往往有所欠缺。这是因为传统的调度算法，如速率单调算法（Rate Monotonic，RM）和最早截止时间优先算法（Earliest Deadline First，EDF），虽然在单处理器系统中被证明是有效的，但在多处理器系统中却可能不适用，特别是在处理任务有截止时间限制时。 在这篇论文中，作者们提出了一种新的实时调度算法，即Paused Rate Monotonic（PRM）算法，并对其性能进行了深入的分析。该算法特别针对基于MapReduce的云环境进行了设计，旨在解决传统调度器难以克服的问题。PRM算法的一个关键创新点是引入了“暂停”的概念，在一定条件下，任务可以被暂停以等待系统利用率下降，从而增加任务能够被调度的概率。 理论分析证明了利用率为调度任务集提供了一个重要的判定条件。在该理论基础上，PRM算法利用集群利用率的上限来判断给定任务集是否可以被调度。这种理论上的分析为云环境中的实时任务调度提供了新的视角，并为实际应用提供了可操作的理论依据。 研究中还指出，PRM算法能够提高在基于MapReduce的云计算环境中实时任务集的调度概率。作者通过对比分析PRM算法与传统实时调度算法（如RM和EDF），使用仿真实验验证了PRM算法在集群利用率和任务调度概率方面的优势。实验结果表明，在不同负载和不同任务集的情况下，PRM算法都能有效地提高任务的调度成功率，从而在保证服务质量的同时，提高云计算资源的利用率。 本研究得到了中国国家自然科学基金（编号：***）、中央高校基本科研业务费（编号：SWJTU12CX098）以及IRT SystemX（Systematic竞争力联合体）的支持。研究团队由西南交通大学信息科学与技术学院的FeiTeng、巴黎中央理工学院的Frédéric Magoulès、北京航空航天大学中法工程师学院的Lei Yu和Tianrui Li组成。 这些研究工作不仅在理论上对实时调度算法进行了创新，也为实践提供了可操作的解决方案，对于云计算和大数据中心的实时任务调度具有重要的指导意义。通过对PRM算法的深入分析和实验验证，可以预见该算法将在实际云服务中得到广泛应用，为云计算提供更加高效和可靠的实时任务处理能力。