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

论文摘要

随着计算机应用领域的迅速扩张与技术的进步,人们意识到:单个处理器的处理能力是有限的,由它所构成的单台计算机所能提供的计算能力也是有限的,它所能提供的计算能力的增长远远跟不上计算需求的增长。于是人们自然地想到利用多台计算机组成多计算机系统来获取更高的计算能力及更高的性价比。如何使多计算机系统中各计算机有效合作?这就涉及到将作业划分成可独立执行的任务、将任务分配到各计算机以进行执行的问题。集中队列法、基于长度猜测的任务分配算法(TAGS)、扩展的TAGS任务分配算法等就是针对这样的任务分配问题所提出来的。本文详细描述了集中队列法、TAGS 任务分配算法以及扩展的TAGS任务分配算法。后者是在集中队列法和TAGS 任务分配算法的基础上提出来的,它综合了二者的优点,具有良好的性能。本文的主要贡献是详细描述了扩展的TAGS 任务分配算法在Linux 2.4.18 内核版本操作系统Redhat Linux 上的实现,并设计产生了任务长度服从长尾分布的任务流,用其作为系统的测试输入,对系统进行了测试,验证了实现的正确性;同时,测得了在任务长度变化比较大的情况下系统的平均延迟比。对于TAGS 算法与扩展的TAGS 算法,已有性能的理论计算是基于各服务器的任务到达过程为泊松到达过程这一假设的。实际情况下的任务到过程并非泊松到达过程,但这一实际过程不便用已有的数学知识进行表达。本文所进行的工作的完成,为今后将TAGS 算法,集中队列法以及扩展的TAGS 算法应用于实际系统打下了基础,同时,也有利于实验基础上性能比较的进行,进而方便了对这些算法以及其它相关算法更进一步的研究。

论文目录

• 摘要
• ABSTRACT
• 目录
• 第一章 引言
• 1.1 课题背景
• 1.2 作者的主要工作
• 1.3 各章节安排
• 第二章 背景
• 2.1 术语
• 2.2 模型
• 2.2.1 适用范围
• 2.2.1.1 多部件
• 2.2.1.2 多计算机
• 2.2.1.3 多机器人
• 2.2.1.4 多人
• 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.3.2.1 Dispatcher 的功能需求
• 4.3.2.2 Server1 的功能需求
• 4.3.2.3 Serveri与ServeriLast 的功能需求
• 4.4 EXTAGS 系统设计的背景知识
• 4.4.1 Linux 的时钟
• 4.4.2 多线程与队列互斥访问的实现:pthread
• yield'>4.4.3 让任务占用更多的 CPU 时间:sched_yield
• 4.4.4 监视任务进程的运行:Linux 的信号
• 4.4.5 任务进程已运行时间的获取:/proc 文件系统
• 4.5 EXTAGS 系统的设计
• 4.5.1 系统的逻辑结构
• 4.5.2 Dispatcher 的设计
• 4.5.2.1 客户端与 Dispatcher 的通信协议
• 4.5.2.2 Dispatcher 与Server1 的通信协议
• 4.5.2.3 Dispatcher 的设计
• 4.5.3 Server1 的设计
• 4.5.4 Serveri 与ServeriLast 的设计
• 4.5.5 ExTags 系统中其它部分的设计
• 4.5.5.1 Dispatcher 中daemonOfJiffies 的设计
• 4.5.5.2 队列的设计
• 4.6 小结
• 第五章 系统测试与实验
• 5.1 系统的测试
• 5.1.1 测试环境
• 5.1.2 测试内容与结果
• 5.2 实验与结果分析
• 5.2.1 实验数据的生成
• 5.2.2 实验内容与结果
• 5.3 小结
• 第六章 结束语
• 6.1 本文的贡献
• 6.2 今后的工作
• 参考文献
• 致谢
• 个人简历及发表的学术论文