【多机树型任务的调度算法及调度方案的自动生成】刘桂霞.pdf

【多机树型任务的调度算法及调度方案的自动生成】刘桂霞.pdf

多机树型任务的调度算法及调度方案的自动生成 The scheduling algorithm and the scheduling schemes auto—achieving for tree—type tasks in multiprocessor 刘桂霞 导师:张学惠教授 专业:计算机应用 吉林大学计算机科学系 一九九六年四月目录 第一章前.第二章多处理机系统任务调度策略基础 2多处理机系统任务调度主要研究的几类问题 2任务系统的表述与任务的描述 2多处理机系统调度算法的种类 2衡量多处理机系统调度算法性能的标准 第三章Hu氏调度算法 3问题的提出.Hu氏调度算法概述 3Hu氏调度算法的正确性 3Hu氏调度算法的三种调度方案及其性能分析 第四章分枝限界调度算法 4分枝限界调度算法概述 4分枝限界调度算法的实现分枝限界调度算法的性能分析 第五章多机系统任务调度结果的处理 5多机系统任务调度结果的存贮.处理机的调度模型基本上有两种形式:确定性调度模型和非确定性调度模型。在确 定性模式中,表达问题特性的所有信息在打算求解问题即调度之前是已知的,这类特性 指出每个任务的执行时间和系统中任务与任务之间的相互关系,产生调度的目的是要优 化一个或多个评价准则。例如,在确定性模式中,每个任务的执行时间可解释为最大的 处理时间或期望的处理时间。在前一情况中,完成调度的时间认为是完成系统若干任务 的最大时间.在后一情况中,调度长度代表了计算平均长度的粗略估计。确定性模式调 度的优点是方法有效、设计简单易行,用途比较广泛。