面向云计算实时服务的调度模型与算法研究

With cloud computing services spreading in industries, the picky cloud clients expect to be served in real-time. The recent researches related to real-time cloud computing focus on the quick response, not on the hard deadline. Considering that cloud infrastructure applies distributed data storage, parallel computing model and dynamic cluster configuration, traditional real-time scheduling algorithms are not able to solve real-time scheduling problems in cloud environment. It will limit the extension of cloud service. This proposal aims at finding reliable real-time scheduling algorithms for cloud computing. Firstly, a specified scheduling model will be established to describe the real-time cloud services. This model is obtained by analysis of popular parallel processing frameworks and abstraction of their common execution flow. Secondly, three methods that can improve scheduling reliability will be studied deliberately: (1) Schedulability analysis and on-line admission control test for hard real-time jobs; (2) Server capacity and response speed for soft real-time jobs;(3) Version control and redundancy reducing for real-time fault tolerance. Thirdly, an adaptive real-time scheduler will be developed for hands-on purpose, which should have the ability of fault avoidance and fault tolerance in real cloud infrastructures. This proposal contributes to improving cloud computing with practical real-time services, initialing model research on parallel processing frameworks and laying the theoretical foundation for real-time scheduling in cloud computing.

随着云计算与各行业广泛而深入的结合，多样化的服务对于时效性要求越来越高。当前云计算实时研究多关注于响应速度而忽视截止期保障。由于云平台数据分布化、计算并行化、集群动态化等特点，传统实时调度理论无法应用于云计算场景，妨碍了云服务的拓展。本课题围绕云计算实时调度的核心问题，首先分析多种基于并行数据计算框架云平台的结构和存储特点，提炼其计算流程的共性，建立形式化、可分析的云计算实时调度理论模型。其次，研究解决实时调度可靠性中的三个关键问题：①硬实时作业的可调度性分析和在线接入控制测试方法；②软实时作业服务器的接纳能力和响应速度；③实时容错版本控制和冗余缩减等。最后，研究大规模异构系统中作业完成时间的估计方法，设计面向现实云计算系统具有避错容错功能的自适应多模实时调度器。本课题旨在增强现有云计算系统对实时服务的处理能力，创新并行数据计算框架的模型研究，从而为建立云计算实时调度理论体系奠定基础。

随着云计算在各个行业的深入和普通用户的激增，服务种类多样化，服务作业的实时性需求也越来越高，然而云计算平台对实时调度的支持和研究相对较少。本课题以开源Hadoop平台为例分析了云平台的结构特点和并行数据计算框架的执行流程，分别提出了适用于物理集群和虚拟集群的云计算实时调度的理论模型，重点开展了周期性实时作业的可调度性能理论分析，主要结论包括（1）建立了系统利用率和作业集可调度性之间的关系，推导了系统的最小使用率公式并以此作为系统接入控制的理论上限。（2）探讨了IaaS平台下虚拟资源分配与系统空闲时间的关系，提高了对实时作业的接纳能力。（3）研究了在节点速度可变的异构云平台下实时作业的可调度性判定问题，证明了系统状态转换时的维持任务级可调度的充分条件，推导了能耗最小化时单一节点的最优计算速度（4）容错方面，设计了基于并行数据计算框架的副版本容错模型，推导了采用主动副版本策略所需要的副版本数的理论下限。根据不同节点的可靠性及计算性能建立了节点宕机误判损失算法，缩短容错处理时间。在以上理论研究的基础上，针对不同作业服务类型提出了适用于Hadoop平台的作业时间估计算法和实时调度算法，开发了云平台调度管理系统软件，通过Xen虚拟化技术实现了对云平台资源的快速部署、调度和伸缩。鉴于并行数据计算框架种类不断丰富，开发了多种并行数据计算框架的代码自动翻译软件，扩展研究了云计算调度在粗糙集、聚类集成、知识获取上的应用。