对具有共享资源竞争的任务调度算法的研究

论文摘要

近年来,计算机在交通控制、通讯网络等各个领域得到了广泛的应用。支持上述应用的基础理论问题为求解该领域内的NP完全问题的实用与快速算法,对上述领域内NP完全问题的快速算法的研究已经成为近年来计算机科学领域内的一个热点。本论文主要研究具有共享资源竞争的任务调度问题的快速算法。 在很多系统中,系统中的任务需要一定的资源完成,在任务执行完毕后就释放所占用的资源,任何两个需要相同资源而又互相冲突的任务不能同时进行。这属于具有共享资源竞争的任务调度问题的研究范畴,该类调度问题在现实世界具有广泛的应用,如计算机的实时控制、并行与分布式计算中的多处理机对共享资源的竞争解决问题、通讯过程中多个信源对线路的竞争求解、通信控制软件设计、移动通信控制等。采用何种调度方式和调度算法,将直接影响到系统的运行性能,因此对该类调度问题的研究具有广泛的意义。 本文首先以十字路口交通调度问题和哲学家就餐问题提出短时资源混杂占用型任务调度问题（简称DHDD）,该问题一般可描述为:在一定的时间区间内,让尽可能多的任务使用资源,并能避免死锁、饿死等现象的发生。在DHDD问题中,一个任务允许与任务集中若干任务共享资源,而同时又不允许与任务集中的某些任务共享资源。通常一个任务本身是由若干子任务组成,即表示一个任务类。以十字路口交通调度为例,一个方向的车辆集合为一个待调度的任务,而其中每辆汽车为子任务。为不产生混乱,我们称任务类中的任务为子任务,并称任务类中的子任务数为该任务的权。每一个任务内的子任务个数是随时间变化的,所以整个调度过程是一个联机调度过程。文章以互斥图G（V,E）表示问题的数学模型,给出了调度算法,首先把图G的顶点划分成k个独立集V1,V2,…Vk,设WT为系统要求任一任务可能等待的最长

论文目录

• 摘要
• ABSTRACT
• 第一章 研究背景与意义
• 1.1 问题的提出
• 1.2 论文组织结构
• 第二章 短时资源混杂占用型任务调度问题的描述
• 2.1 DHDD问题的描述
• 2.2 相关研究
• 2.2.1 哲学家问题
• 2.2.2 十字路口的交通调度问题
• 第三章 基础工作
• 3.1 NP难解问题的描述
• 3.2 任务调度问题
• 3.2.1 任务调度算法的分类
• 3.2.2 分布式实时系统中的任务调度问题
• 3.3 资源分配问题
• 3.3.1 对单个不可分资源的访问进行管理
• 3.3.2 多个通用资源分配算法
• 3.4 调度问题常用算法
• 3.4.1 经典生产调度问题的一般描述
• 3.4.2 经典生产调度问题的分类
• 3.4.3 求解调度问题的常见算法
• 3.5 DHDD问题与共享资源独占型的调度问题的比较
• 第四章 DHDD问题调度数学模型与调度算法
• 4.1 基本术语
• 4.2 调度模型
• 4.3 调度算法
• 第五章 划分算法及分析与调度算法分析
• 5.1 划分算法
• 5.2 划分算法与调度算法分析
• 第六章 结束语
• 6.1 结论
• 6.2 进一步的工作
• 附录
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 学位论文评阅及答辩情况表