支持混合负载的存储系统调度技术研究

摘要

现代的存储系统需要为包括best-effort应用和不同类型流媒体应用的混合负载提供数据访问服务。支持混合负载的存储系统调度算法不仅要保证流媒体应用的服务质量需求，而且还要保证best-effort应用不会饥饿。由于两种应用类型相互干扰，现有的调度算法都无法为混合负载提供完善的调度服务。 本文建立了存储系统集成调度框架，对混合负载进行层次化的调度：首先将存储系统的服务资源在best-effort应用和流媒体应用两大类型之间进行保留与分配，然后再根据不同应用类型自身的特点分别进行针对性的调度。 STB-WFQ调度算法是集成调度框架的关键技术，它将存储系统的服务资源在best-effort应用类型和流媒体应用类型之间进行公平而稳定的分配。best-effort应用利用被分配服务资源避免了饥饿的产生，流媒体应用利用稳定分配的服务资源实现服务质量的保证。 QADPS调度算法实现了集成调度框架中针对流媒体应用的调度，它根据不同流媒体应用在服务质量需求上的差异实现了有差别的调度服务，服务质量需求越严格的应用将得到更多的服务机会。 支持混合类型流媒体负载的统计学访问控制算法为QADPS调度算法所调度的流媒体应用提供服务质量的保证，能够在保证流媒体应用服务质量的前提下，接受更多流媒体应用的并发访问。 我们利用DiskSim仿真系统建立了存储系统集成调度框架的原型，并对构成集成调度框架的调度算法和访问控制算法进行了功能和性能的测试。实验结果表明集成调度框架能够为混合负载提供完善的调度服务。

目录

文摘

英文文摘

论文说明：表格目录、图表目录

南开大学学位论文版权使用授权书和原创性声明

第1章绪论

1.1论文的研究动机

1.2论文的研究内容

1.3论文的主要贡献

1.4论文的组织结构

第2章相关技术背景

2.1 best-effort应用

2.2流媒体应用

2.2.1流媒体应用的定义

2.2.2流媒体应用的特点

2.2.3流媒体应用访问存储系统的过程

2.2.4流媒体应用的服务质量需求

2.2.5流媒体应用和best-effort应用的共存

2.3存储系统简介

2.3.1硬盘驱动器的结构

2.3.2硬盘的数据传输率与访问请求的服务时间

2.3.3存储系统的发展

2.4总结

第3章对存储系统调度算法的分析和研究

3.1简介

3.2存储系统调度算法的服务属性

3.2.1服务资源分配方式(Resource Allocation Model)

3.2.2服务质量保证的级别(QoS Guarantee Level)

3.2.3服务类型(Service Type)

3.2.4优先级(Priorities)

3.2.5用服务属性描述存储系统调度算法

3.3存储系统调度算法的分类

3.4对现有存储系统调度算法的分析

3.4.1面向性能的调度算法

3.4.2实时调度算法

3.4.3面向数据流的调度算法

3.4.4混合负载调度算法

3.5存储系统集成调度框架

3.5.1调度层次与调度类型

3.5.2存储系统集成调度框架的系统结构

3.5.3集成调度框架的特点

3.5.4集成调度框架的核心技术

3.6总结

第4章基于服务时间的加权公平队列调度算法STB-WFQ

4.1简介

4.2公平调度理论

4.3 STB-WFQ算法描述

4.4算法的复杂度分析

4.5算法的公平性分析

4.6算法的几点说明

4.6.1访问请求服务时间的确定

4.6.2对磁盘阵列的支持

4.7 STB-WFQ算法的特点

4.7.1可扩展性

4.7.2公平而稳定的服务时间分配

4.7.3存储系统结构的无关性

4.7.4实现work-conserving特性

4.8仿真试验

4.8.1仿真工具

4.8.2实验方法

4.8.3服务时间分配的公平性测试

4.8.4服务时间分配的稳定性测试

4.8.5 work-conserving特性测试

4.9总结

第5章基于服务质量的动态优先权调度算法QADPS

5.1简介

5.2研究动机

5.3流媒体应用服务质量需求的精确定义

5.4混合类型流媒体负载访问存储系统的过程模型

5.5 QADPS调度算法的描述

5.5.1定义流媒体应用接受服务的历史信息

5.5.2计算服务质量失败距离

5.5.3为流媒体应用设置优先权

5.6 QADPS调度算法的实现与优化

5.6.1同步流媒体应用进程与调度进程

5.6.2更新服务质量失败距离

5.6.3确定访问请求的调度顺序

5.6.4 QADPS调度算法的优化

5.7 QADPS调度算法的复杂度分析

5.8 QADPS调度算法的可扩展性

5.9仿真试验

5.9.1差别调度测试

5.9.2对比测试

5.10总结

第6章支持混合类型流媒体负载的统计学访问控制算法

6.1研究背景

6.2并发流媒体应用的汇聚负载模型

6.3混合类型流媒体负载的访问控制约束条件

6.4混合类型流媒体负载的访问控制算法

6.4.1访问控制函数

6.4.2混合负载访问控制算法的实现

6.5仿真试验

6.6总结

第7章总结与展望

致谢

参考文献

个人简历

攻读博士学位期间完成的主要工作

发表和完成的论文

参加的主要科研项目