异构系统中基于可用性的抢占式任务调度算法研究

摘要

在过去几十年中，异构系统已广泛用于科学和商业之中。近年来，很多学者致力于研究异构系统中以提高应用程序性能为目的的调度算法。调度理论中的基本假设是所有机器总是可用来处理任务的。这个假设可能在某些情况下是合理的，但当存在某种维护要求、中断或其他机器无法处理的限制等这些使机器不可用来处理任务的情况时，它并不是有效的，而这些约束因素实际存在于许多应用之中。 在本文中，可用性定义为一个计算节点在某一给定的时间间隔内运行的时间占总时间的比例。现在许多高效能的应用都需要具有高可用性的计算平台，如军事应用、医疗应用和国际商业应用等都需要非常高可用性的服务，因为只要有一个计算节点不可用都有可能导致严重故障或致命错误。因此，为了处理维护活动和意外失败等情况，异构系统的调度策略必须考虑到可用性因素。 为了解决这些问题，本文在对计算机系统可用性进行深入研究的基础上提出了一个基于可用性的异构系统的任务调度模型，分析了模型的可行性并提出了对抢占式任务的调度问题，通过对现有算法SSAC(Scheduling Strategy for multiple classes of tasks with Availability Constraints)的改进提出了一种基于可用性、支持多优先级的抢占式任务调度算法P-SSAC，并建立了负载平衡探测机制，对可用性的现实应用进行了扩展。该算法具有与现有算法近似的性能，但其可以工作在抢占模式下，且能保持可用性和响应能力之间一个良好的平衡，提高了任务的调度成功率。 在仿真实验部分，通过GridSim模拟器构造了一个含有十六个节点的异构系统，启用基于可用性的抢占式任务调度算法P-SSAC，通过新算法与几个经典的算法的实验结果的比较，表明P-SSAC算法显著提高了系统的可用性，原因在于它在分配任务给异构结点的过程中考虑了任务的可用性需求。

目录

文摘

英文文摘

论文说明：图表目录

声明

第1章绪论

1.1选题背景

1.2课题目的和意义

1.3国内外的研究现状

1.4本文研究内容

1.5论文组织结构

第2章背景知识

2.1集群系统

2.1.1集群系统的特点

2.1.2集群系统的类型

2.1.3集群系统的结构

2.1.4集群系统的发展趋势

2.2分布式系统

2.2.1分布式系统概述

2.2.2分布式并行系统的分类

2.3可用性问题

2.3.1高可用性计算及其机群的研究现状

2.3.2可用性问题的体系结构研究

2.3.3可用性问题的理论研究

第3章异构系统及其任务调度问题

3.1异构系统概述

3.2任务间的相关性

3.3任务调度的分类

3.4异构系统中任务的动态调度问题

3.4.1动态任务调度策略

3.4.2动态任务的调度算法

3.4.3已有任务调度算法分析

3.5异构系统中的负载平衡技术

3.5.1负载平衡产生的原因

3.5.2负载平衡算法的评价标准

3.5.3负载平衡问题的主要难点

第4章基于可用性的抢占式任务调度算法

4.1基于可用性的调度算法概述

4.2模型描述与问题公式化

4.2.1体系结构模型

4.2.2对具有可用性需求的多类任务建模

4.2.3问题公式化

4.2.4异构模型

4.2.5负载不平衡探测机制

4.2.6相关命题

4.3基于可用性的抢占式任务调度算法P-SSAC

4.3.1 P-SSAC算法描述

4.3.2调度算法P-SSAC算法的分析

第5章仿真实验结果分析

5.1仿真实验方法

5.2任务调度算法的GridSim实现及性能分析

结论

参考文献

附录A攻读学位期间所发表的学术论文目录

附录B攻读学位期间所参与的科研活动

致谢