第十一讲任务调度

《第十一讲任务调度》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上节回顾负载平衡•控制方式：：：集中与分布式：集中与分布式任务分配调度•信息机制：：：信息的收集方式：信息的收集方式，，，刷新周期，刷新周期；；；•传输策略(when)(when)：(when)：：：–负载指标–发送者，，，服务者方法，服务者方法（（（征兵法（征兵法）））•定位策略(where)(where)：(where)：：：–定位方式（（（自定位等（自定位等），–选择处理机算法：：：招标算法：招标算法，，，剃度算法，剃度算法，，，渗透算法，渗透算法，，，集中，集中///分/分分分布式方法•选择策略(which)(which)：(which)：：：–加权算法，，，–预测方法，

2、，，进程生命周期，进程生命周期，，，选择任务算法，选择任务算法。。。计算机学院计算机学院2聚焦点•任务分配与调度•任务分配调度分类•常用方法和策略基本概念•任务调度模式•DAGDAG模式DAG模式•表调度算法•启发式调度算法•任务分配模式计算机学院3计算机学院4SchedulingSchedulingvsSchedulingvsvsvsAllocationAllocation调度与分配方法调度和分配问题研究如何把任务集或一组程序在时间目标：：：减少系统中各处理机间的通信开销和执行模块开销：减少系统中各处理机间的通信开销和执行模块开销和空间上最优化地分配到一组处理单元以取得某种最I

3、PCIPC＝IPC＝＝＝f(IMC,MAPf(IMC,MAPf(IMC,MAP）f(IMC,MAP）））其中其中佳并行效果。。。IMCIMC：IMC：：：模块间通信模块间通信•任务调度：：：任务调度指调度一组：任务调度指调度一组有顺序关系的任务，，，MAPMAP：MAP：：：任务分配任务分配并行应用运行时系统不仅要决定任务在哪个处理机上运行，，，还要决定任务，还要决定任务任务划分静态调度静态vsvsvs动态方法vs动态方法资源监视的执行顺序任务提交初始调度•任务分配：：：任务分配是指分配一组：任务分配是指分配一组无顺序关系的任务•基于图论的算法运行空闲机能力到多个处理机上执行。。

4、。•数学规划方法•负载共享策略迁移负载平衡•启发式算法•专家系统方法图3.16并行应用和运行系统计算机学院5计算机学院61单处理机模型分布式处理模型用用用户用户户户P1用用用户用户户户……M5M4M3M2M1S…m5m4m3m2m1SP2用用用户用户户户…单处理机模型Pn令用户产生请求λλλ///秒/秒秒秒，，，，处理机能处理请求处理机能处理请求µµµ///秒/秒秒秒，，，，则则则则：：：：（（（m1,m2（m1,m2m1,m2…m1,m2………))))为模块集为模块集平均周转时间TTT≈≈≈1/(µµµ---λλλ)))（（（p1,p2（p1,p2p1,p2…p1,p2………)

5、)))为处理机集为处理机集，，，SSS为模块分配机制S为模块分配机制，，，如果服务器处理能力加大，，，有，有有有nnnn个个个个CPUCPUCPU，CPU，，，处理能力将为处理能力将为nnnµµµ，，，而请求，而请求率同步扩大为nnnλλλ，，，则，则则则：：：：通常m>n,m>n,所有机器兼容m>n,所有机器兼容，，，全连通，全连通平均周转时间将为1/(1/(n1/(nnnµµµ---n-nnnλλλ)=T/n计算机学院7计算机学院8分配调度系统调度性能性能和效率是评价一个调度系统P1T1T6E好坏的两个重要标准，，，即在设计，即在设计P2T2E算法取得某种优化调度结果时时时，

6、时，，，必须考虑算法本身的时间复杂度P3T3T4T5E。。。任务调度的性能指标常用：：：•最小完成时间GanttGantt图Gantt图图图不仅能表示任务被分客户资源模式:::配到何处理机上，，，还能表示某一，还能表示某一•处理机利用率一组任务是客户，，，处理机是资源，处理机是资源，，，调度系统按某些策略决定，调度系统按某些策略决定处理机上任务执行的先后顺序、、、哪个客户占有哪个资源（（（如（如如如FCFSFCFSFCFS）FCFS）））•系统吞吐量每个任务的完成时间和整个程序
一般形式下的任务调度问题是著名的NPNPNP完全问题NP完全问题，，，•系统响应时间的完成时间
一种调

7、度算法常加有许多限制和先设条件，，，只能适应于某些，只能适应于某些•并行加速比等来衡量情况和环境中计算机学院9计算机学院10调度目标设计方法假定任务由mmm个模块组成m个模块组成，，，分配在，分配在nnn个处理机上执行n个处理机上执行，，，eik，eik•常以数学的方法和程序模块相关图的方法寻求任务的最佳表示模块iii在处理机i在处理机kkk上执行时间k上执行时间，，，Cij，CijCij表示模块之间的数Cij表示模块之间的数匹配据通信量单位数，，，wkb，wkbwkb表示处理机