一种面向虚拟化云计算中截止期感知任务调度的新型推拉(Push-Pull)优化算法——基于链表( Linked List based Push and Pull, LPP)的虚拟机间任务迁移调度方法
《Franklin Open》:A Novel Push Pull Optimization Algorithm Fostered Deadline Aware Task Scheduling in Virtualized Cloud Computing
编辑推荐:
摘 要:云服务提供商面临的主要挑战是在满足服务质量(Quality of Service, QoS)指标(如可靠性、弹性、最小化响应时间、最大化吞吐量、遵守任务截止期及降低任务拒绝率)的同时进行任务调度。为此,需设计能从服务提供商角度出发,在最大化响应时间性能
摘 要:云服务提供商面临的主要挑战是在满足服务质量(Quality of Service, QoS)指标(如可靠性、弹性、最小化响应时间、最大化吞吐量、遵守任务截止期及降低任务拒绝率)的同时进行任务调度。为此,需设计能从服务提供商角度出发,在最大化响应时间性能、于用户定义截止期内完成任务、遵从服务等级协议(Service Level Agreement, SLA)、满足用户QoS要求并提升云计算资源利用率的调度方法。本文提出一种创新的"基于链表的云环境虚拟机间任务推拉(Linked List based Push and Pull, LPP)迁移调度技术——LPP任务调度算法"。该LPP方法利用链表(Linked List)概念将到达负载均衡分配至指定虚拟机(Virtual Machine, VM)。在该机制中,虚拟机采用推(Push)与拉(Pull)理念按时执行任务,在提升各任务响应时间的同时满足SLA要求并优化云资源使用。评估结果表明,与现有方法相比,所提策略降低了SLA违例率(SLA Violation Rate),改善了响应时间,并能保障用户在截止期内完成任务。所提算法基于CloudSim实现。
论文解读:基于链表推拉优化的截止期感知云计算任务调度(LPP)研究
一、研究背景与开展的研究及意义
云计算依托虚拟化技术动态分配资源以响应用户请求,而任务调度(Task Scheduling)是满足用户期望与达成系统目标的核心。传统调度算法多聚焦于缩短完工时间(Makespan)或最小化完成时间,且已被证明为NP完全(NP-complete)问题。现有算法常未能同时兼顾负载均衡、用户自定义截止期(Deadline)、降低服务等级协议违例率(SLA Violation Rate)及优化资源利用率。随云用户与计算需求增长,如何在异构或同构虚拟机(Virtual Machine, VM)集群中,依据任务独特属性(含截止期)将任务合理匹配至合适VM,成为亟待解决的问题。为此,Rajeshwari BS、Namratha M、Nikhil Srikanth、Nagaraj Vasudev Halatti及Pooja Srinivasan研究人员提出了一种基于链表(Linked List)的推拉(Push-Pull)任务迁移调度算法(LPP Task Scheduling),旨在减少响应与等待时间、提高截止期内完成率、降低SLA违例并均衡VM间负载。该研究发表于《Franklin Open》。实验验证表明LPP较传统Min-Min算法在多项指标上表现更优,对云数据中心任务调度实践具有一定参考价值。
二、主要关键技术方法
研究人员采用CloudSim 3.0.3仿真平台,使用Java编程实现所提LPP算法及对照Min-Min算法。仿真环境为Intel Core i7-3770、4GB DDR3、Windows 10 64位。数据中心配置:宿主机(Host)5台,处理单元20个,总处理能力48000 MIPS,存储60TB,内存200GB;创建虚拟机20台,平均镜像大小1000MB,平均内存682MB,平均带宽3700。任务规模测试集分别为100、500、1000、5000及10000个独立任务,各任务附长度(Length)与截止期(Deadline)。LPP方法将所有待调度任务封装为含截止信息的链表节点构成任务链表;各VM依当前队列预计完成时间与任务在本VM的处理时间(Processing Time = TaskLength/ ServiceRate(VMj))判断能否在截止前完成——若满足条件则"拉(Pull)"该节点纳入自身队列,否则将该链表"推(Push)"至下一VM继续判断;最终残留在链表中未被拉取的任务采用Min-Min算法兜底分配。算法目标函数定义为最小化用户任务i的响应时间RUserTaski与等待时间WUserTaski,约束条件为RUserTaski≤ taskDeadlinei。
三、研究结果
3. Proposed Linked List based Push and Pull Task Scheduling (LPP Task Scheduling)
研究人员构建了LPP调度架构:用户任务到达云端后,依据SLA数据库中信息识别优先级并计算截止期,随后为每个任务创建含截止信息的链表节点,串联成任务链表分发至VM群。各VM分析节点,若本机当前队列任务完成时间(finishtimeVMjqueuetasks)加任务i在VMj的处理时间(processingtimetaski)不大于taskDeadlinei,则Pull该节点;否则Push链表至下一VM。未被任何VM拉取之剩余任务交Min-Min算法分配。该设计使具备余力的VM主动获取可按时完成之任务,实现自适应负载分布与截止期保障。
4. Results and Discussion
研究人员在不同任务负载下对比LPP与Min-Min算法:
- •
图2(Completion time of tasks)显示LPP的任务完成时间短于Min-Min,因VM依资源能力主动拉取合适任务从而加快整体完工。
- •
图3(Waiting time of tasks)显示LPP显著降低任务平均等待时间,归因于截止期驱动的条件拉取减少了任务滞留。
- •
图4(Number of Tasks executed within Deadline)显示LPP使更多任务得以在各自截止期内执行,因任务被推送至能承诺按时完成的VM。
- •
图5(SLA Violation Rate)显示LPP相较Min-Min降低了SLA违例率,印证了截止期约束内调度有效性。
四、讨论与结论翻译
讨论与结论:在云计算背景下,本研究提出一种基于链表的推拉(Push-Pull)任务迁移方法,其中携带任务信息之节点由虚拟机依据其当前状态及任务截止期进行拉取(Pull)。任务截止期由存储于SLA数据库中的用户服务等级协议(Service Level Agreement, SLA)确定。研究结果表明,在完工时间(Completion Time)、等待时间(Waiting Time)、截止期内任务执行率及SLA违例率(SLA Violation Rate)方面,所提出的链表模型优于现有方法。
(Translated Conclusion: In a cloud computing context, the study provides a novel pull-and-push task migration method based on linked lists, where nodes carrying task information are pulled by virtual machines based on their current status and deadline. The user SLA agreement, which is saved in the SLA database, is used to determine the task's deadline. The findings demonstrate that, in terms of completion time, waiting time, task execution within the deadline and SLA violation rate, the suggested Linked list model performs better than the existing approach.)