扩展的TAGS任务分配算法在微机集群上的实现

摘要

本文详细描述了集中队列法、TAGS任务分配算法以及扩展的TAGS任务分配算法.后者是在集中队列法和TAGS任务分配算法的基础上提出来的,它综合了二者的优点,具有良好的性能.本文的主要贡献是详细描述了扩展的TAGS任务分配算法在Linux 2.4.18内核版本操作系统Redhat Linux上的实现,并设计产生了任务长度服从长尾分布的任务流,用其作为系统的测试输入,对系统进行了测试,验证了实现的正确性;同时,测得了在任务长度变化比较大的情况下系统的平均延迟比.对于TAGS算法与扩展的TAGS算法,已有性能的理论计算是基于各服务器的任务到达过程为泊松到达过程这一假设的.实际情况下的任务到过程并非泊松到达过程,但这一实际过程不便用已有的数学知识进行表达.本文所进行的工作的完成,为今后将TAGS算法,集中队列法以及扩展的TAGS算法应用于实际系统打下了基础,同时,也有利于实验基础上性能比较的进行,进而方便了对这些算法以及其它相关算法更进一步的研究.

目录

文摘

英文文摘

独创性声明及关于论文使用授权的说明

第一章引言

1.1课题背景

1.2作者的主要工作

1.3各章节安排

第二章背景

2.1术语

2.2模型

2.2.1适用范围

2.2.2同构与异构

2.2.3集中与分布

2.2.4静态与动态

2.2.5约束条件

2.3目标

2.4性能评价标准

2.4.1周转时间

2.4.2吞吐量

2.4.3延迟比

2.4.4提高任务执行性能的途径

2.5小结

第三章扩展的基于长度猜测的任务分配算法

3.1系统模型

3.1.1基本模型

3.1.2集中与分布

3.1.3同构与异构

3.1.4长尾分布

3.1.5任务不可剥夺

3.1.6公平性

3.1.7性能评价标准

3.1.8其他特性

3.2相关算法

3.2.1轮循法与随机法

3.2.2集中队列法

3.2.3 TAGS算法

3.2.4性能比较

3.2.5 TAGS算法的扩展性限制

3.3一类TAGS算法的扩展

3.3.1算法简要分析

3.3.2性能计算

3.4 小结

第四章扩展TAGS任务分配算法的实现：EXTAGS系统分析与设计

4.1微机集群

4.2实现平台与实现方案的选择

4.3 EXTAGS系统的组成部分与各部分的功能需求

4.3.1 ExTags系统的组成部分

4.3.2系统组成部分的功能需求

4.4 EXTAGS系统设计的背景知识

4.4.1 Linux的时钟

4.4.2多线程与队列互斥访问的实现：pthread

4.4.3让任务占用更多的CPU时间：schedyield

4.4.4监视任务进程的运行：Linux的信号

4.4.5任务进程已运行时间的获取：/proc文件系统

4.5 ExTAGs系统的设计

4.5.1系统的逻辑结构

4.5.2 Dispatcher的设计

4.5.3 Serverl的设计

4.5.4 Serveri与ServeriLast的设计

4.5.5 ExTags系统中其它部分的设计

4.6小结

第五章系统测试与实验

5.1系统的测试

5.1.1测试环境

5.1.2测试内容与结果

5.2实验与结果分析

5.2.1实验数据的生成

5.2.2实验内容与结果

5.3小结

第六章结束语

6.1本文的贡献

6.2今后的工作

参考文献

致谢

个人简历及发表的学术论文