实时调度算法与MapReduce云平台性能研究

170 浏览量更新于2024-07-15 收藏 980KB PDF 举报

本文档探讨了一篇发表在《JSupercomput》(2014年卷69，第739-765页)的研究论文，标题为"一种基于MapReduce的云计算中的实时调度算法及其性能分析"。MapReduce作为一种广泛应用于数据密集型任务处理的流行编程模型，已经在诸如搜索引擎索引、社交网络挖掘、协同推荐和垃圾邮件检测等领域取得了显著成功。然而，其默认调度器存在两个主要局限性：首先，它不支持云数据中心内的并发服务共享，这限制了系统的灵活性；其次，MapReduce并不能确保满足响应时间约束的服务。为解决这些问题，作者FeiTeng等人提出了Paused Rate Monotonic (PRM)算法，专为在MapReduce架构上调度硬实时任务而设计。该算法的核心在于考虑任务的暂停速率与执行顺序，以实现更有效的资源分配和响应时间保障。论文对PRM算法进行了理论上的深入分析，包括证明了一个关于集群利用率的界限，这个界限可以作为判断给定任务集是否能被成功调度的充分条件。理论分析部分不仅涉及算法的构造，还涵盖了其复杂性分析以及如何确保在实时性约束下任务的正确执行。通过严谨的数学推导，作者揭示了PRM算法如何优化资源分配，从而提高系统整体效率，尤其是在处理那些对延迟敏感的应用时。此外，论文还包括了实验评估部分，通过实际的性能测试和对比，验证了PRM算法相对于传统调度策略在实时性和系统性能方面的优势。这些实验结果为其他研究人员提供了实证依据，有助于他们理解和改进云计算环境下的实时任务调度策略。这篇论文不仅为MapReduce平台的实时任务调度提供了一种创新方法，而且为优化资源利用和提升服务质量提供了有价值的理论基础和实践经验，对于云计算领域的研究者和实践者来说具有重要的参考价值。

744 F. Teng et al.

Fig. 2 Key moments in the kth instance of MapReduce task τ

the two operations. α is mainly determined by the functionality of a MapReduce

task, that is, the computation complexities for the map and reduce operations. Here,

we apply the same α for all tasks which makes sense if all tasks have the same

functionality.

There are several important time instants for τ

i,k

, including the following:

– a

i,k

: activation time when τ

i,k

is released to the scheduler.

– m

i,k

: map starting time when the ﬁrst map operation of τ

i,k

starts.

– r

i,k

: reduce starting time when the ﬁrst reduce operation of τ

i,k

starts.

– f

i,k

: ﬁnishing time when the last reduce operation of τ

i,k

ﬁnishes.

– d

i,k

: overdue time by which time τ

i,k

is required to be ﬁnished.

The relationship between these times is shown in Fig. 2.

Some properties must be outlined here. All instances are activated after the request

is submitted, so a

i,k

= O

+(k−1)T

. The map starting time m

i,k

cannot be earlier than

the activation time a

i,k

. The total execution time for mapping is M

, and m

i,k

+ M

≤

i,k

. Since the last reduce ends at f

i,k

,wehavem

i,k

+ M

+ R

≤ f

i,k

. The deadline

i,k

is the absolute latest time for completion of τ

i,k

,sod

i,k

= a

i,k

+ T

3.2 MapReduce cluster

In this paper, the MapReduce-based cloud is a s et of machines, P, running the MapRe-

duce programming model, and thus, it is collectively referred to as a MapReduce cluster

with a certain computing capability.

3.2.1 Exclusive MapReduce cluster

The MapReduce programming model has several implementations, among which the

open source Hadoop is the most popular both in industry and academic institutions.

A typical Hadoop cluster consists of one master and multiple worker nodes, where

the single master is responsible for scheduling tasks to workers and monitoring their

execution. An interesting phenomenon caught our attention. The master using the

Hadoop default FIFO scheduling policy, assigns tasks in the order of their submission,

and processes them one by one. Therefore, the MapReduce cluster here does not allow

multiple tasks running concurrently, even though it consists of a number of machines.

Parallel execution only exists between the map or reduce operations, rather than the

123

剩余26页未读，继续阅读

weixin_38691319

粉丝: 3
资源: 908

实时调度算法与MapReduce云平台性能研究

real time linux

coflow scheduling frameworks

the sstf scheduling algorithm

mapreduce近三年参考文献

找十条中英文关于企业会议室预约与管理系统的参考文献以及段落

Which Linux functions are included in the schedule() scheduling algorithm

scheduling slot

最新资源