任务分配与调PPT学习教案

1、会计学1 任务分配与调任务分配与调 2021-7-162 第1页/共90页 2021-7-163 第2页/共90页 2021-7-164 n 不要求各管理程序模块编写为 可重入结构 主从式主从式操作系统仅在指定的主处理机 上运行。主处理机管理整个系统并为从处 理机分配任务，从处理机通过软中断或访 管访问主机。 第3页/共90页 2021-7-165 第4页/共90页 2021-7-166 基本特点： 每个处理机有各自的私有表格，而有些表 格是系统公用的，增加了表格存取控制的 复杂性 每个处理机可以根据自身的需要及所分配 的任务进行管理 单独管理单独管理每个处理机具有自己的操 作系统或管理程序，

2、按照自身需要，独 立运行和管理。 第5页/共90页 2021-7-167 第6页/共90页 2021-7-168 基本特点：基本特点： 管理程序的代码必须写成可重入的 可以获得较好的系统负载平衡 第7页/共90页 2021-7-169 第8页/共90页 2021-7-1610 第9页/共90页 2021-7-1611 第10页/共90页 2021-7-1612 第11页/共90页 2021-7-1613 第12页/共90页 2021-7-1614 第13页/共90页 2021-7-1615 第14页/共90页 2021-7-1616 第15页/共90页 2021-7-1617 02467 P1

3、 P2 P3 T1 T2 T3T4T5 T2 T1 可以表示处理机的调度过程，反映各种运行参数 第16页/共90页 2021-7-1618 T1T3T6 T5 T7T9 T2 T4 T8 03791317 P1 P2 两台处理机的尽早分配任务调度 第17页/共90页 2021-7-1619 0371115 P1 P2 两台处理机的最佳分配任务调度两台处理机的最佳分配任务调度 T1T3T4T7T9 T2T5T8T6 14 最小完成时间，由关键路径决定最小完成时间，由关键路径决定 所需最多处理机个数所需最多处理机个数图宽度图宽度 结点的最早调度时间结点的最早调度时间 结点的最晚调度时间结点的最晚调

4、度时间 第18页/共90页 2021-7-1620 第19页/共90页 2021-7-1621 第20页/共90页 2021-7-1622 调度过程可以归纳为任务图到系统图的映射调度过程可以归纳为任务图到系统图的映射 第21页/共90页 2021-7-1623 第22页/共90页 2021-7-1624 第23页/共90页 2021-7-1625 第24页/共90页 2021-7-1626 pja cr p r j )1( 1 1 max 1 * * 其中(i)表示途中标号 ai的结点数， r*是给定表达式值为最大的常数r值 第25页/共90页 2021-7-1627 C=0，T=amax=7

5、 r=1: (7)/1= 4/1=4 r=2: (7)+ (6)/1 = (4+4)/1=4 r=4 (7)+ (6)+ (5)+ (4)/4 =13/4=3.25 第26页/共90页 2021-7-1628 C=1，T=amax+1=8 r=1: 4/2=2 r=2: 8/3=2.66 r=3: 10/4=2.5 r=4: 13/5=2.6 r=5: 16/6=2.66 r=6: 18/7=2.57 r=7: 19/8=2.357 r=2和和r=5时，产生时，产生r*值，表达式值最值，表达式值最 大大 第27页/共90页 2021-7-1629 公度（单位）结点权为4 第28页/共90页 2

6、021-7-1630 1 ),maxmax( 1 n i ii w p ww 第29页/共90页 2021-7-1631 T1T3 T2T4 单位权结点的抢先调度单位权结点的抢先调度 两台处理机：两台处理机： T1T2 T2T3 P 1 P2 P 1 P2 任务数为偶数 任务数为奇数 1.5 第30页/共90页 2021-7-1632 T1T2 T2T3 T3T4 P1 P2 P3 T1T2 T2T4T3 T3T5 P1 P2 P3 任务数为4 任务数为5 第31页/共90页 2021-7-1633 第32页/共90页 2021-7-1634 例：例： 第33页/共90页 2021-7-163

7、5 公度结点权 第34页/共90页 2021-7-1636 T1 7+1/2T2 7/3 T4 1 T6 3/2 T9 1/2 T2 14/3+1/2T3 14/3 T5 1 T7 3/2 T3 7/3+1/2T5 7 T 7 T 8 T8 3/2 12345678910 11 1213 0 P1 P2 P3 31/664/6 73/6 76/6 第35页/共90页 2021-7-1637 粒度组合与调度粒度组合与调度 做并行程序设计时要回答两个基本问题：做并行程序设计时要回答两个基本问题： （1）如何将程序划分成并行模块、子任务以获得）如何将程序划分成并行模块、子任务以获得 最短执行时间。最

8、短执行时间。 （2）计算中的并发粒度为多大会比较理想。）计算中的并发粒度为多大会比较理想。 与问题以及机器有关，需要在并行性与调度开销之 间做折衷。 第36页/共90页 2021-7-1638 细粒度程序的调度举例细粒度程序的调度举例 Var a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q nBegin n1a:=1 n2b:=2 n3c:=3 n4d:=4 n5e:=5 n6f:=6 第37页/共90页 2021-7-1639 n7 g:=a*b n8 h:=c*d n9i:=d*e n10j:=e*f n11k:=d*f n12l:=j*

9、k n13 m:=4*l n14 n:=3*m n15o:=n*i n16 p:=o*h n17q=p*g nEnd 第38页/共90页 2021-7-1640 n指令1，2，3，4，5，6是存储器访问（取数据） 操作，每个结点用一个周期进行寻址，用六个 周期从存储器取数。 n指令7-17是CPU操作，每个需要两个周期完成。 程序图： n每个结点相当于程序中的计算单元 n粒度用执行结点中全部操作所需要的基本时间 来度量（处理机和存储器） n程序图中的结点表示如下图： 第39页/共90页 2021-7-1641 n，s x， i y， j u，kv，h n（n，s）=（结点名，粒度） n（x，i

10、）=（输入变量，延迟） n（u，k）=（输出变量，延迟） n粒度是指程序段所含的计算量； n延迟主要指通信延迟，包括通道延迟和消息延迟。 第40页/共90页 2021-7-1642 n程序初始尽可能细分，任务图如下： 1,12,13,14,15,16,1 7,28,29,210,211,2 12,2 13,2 14,2 15,2 16,2 17,2 a,6b,6c,6 d,6 d,6 e,6 e,6 d,6 f,6f,6 g,4h,4 i,4 j,4 k,4 l,3 4,0 3,0 m, 3 n,4 o,3 p,3 q,3 第41页/共90页 2021-7-1643 2台处理机的细粒度调度：台

11、处理机的细粒度调度： P1 P2 6 11 1 2 3 9 8 7 0 17 9 10111218 20 22 2428 5 10 12 13 14 4 0 1 281014 16 19 2124 26 15 16 17 30 32 35 37 40 42 阴影部分为通信延迟阴影部分为通信延迟 第42页/共90页 2021-7-1644 粒度的组合粒度的组合 n如果加大粒度有可能消除消除一些不必要的通信 时延或降低总的调度开销，则将多个细粒度结点 组合成粗粒度结点。 n前面细粒度的程序图经过粒度组合可以得到粗粒 度的程序图如下所示： 第43页/共90页 2021-7-1645 1,12,13,

12、14,15,16,1 7,28,29,210,211,2 12,2 13,2 14,2 15,2 16,2 17,2 a,6b,6c,6 d,6 d,6 e,6 e,6 d,6 f,6 g,4h,4 i,4 j,4 k,4 l,3 4,0 3,0 m, 3 n,4 o,3 p,3 q,3 A B C D E 第44页/共90页 2021-7-1646 n例中的粗粒度程序图如下： A,8 B,4C,4 D,6 E,6 a,6 b,6 c,6 d,6 d,6 e,6 f,6 g,4 h,4 i,4 j,4 k,4 n,4 q,0 第45页/共90页 2021-7-1647 2台处理机的粗粒度调度台

13、处理机的粗粒度调度 P1 P2 阴影部分为通信延迟 I表示处理机空闲 A C D 08142228323818 E I B 0142218 I 第46页/共90页 2021-7-1648 静态多处理机调度静态多处理机调度 结点复制：结点复制：为了消除空闲时间和进一步降低处理机 间的通信延迟。以下面的程序图为例： d,4 A,4 B,1 E,2 C,1 D,2 a, 1 b, 1 c, 8 a, 8 c, 1 e,4 第47页/共90页 2021-7-1649 2台处理机的不用结点复制技术的调度方案台处理机的不用结点复制技术的调度方案: d,4 A,4 B,1 E,2 C,1 D,2 a,1 b

14、, 1 c,8 a,8 c,1 e,4 P1P2 A B I P1 0 4 5 7 13 21 23 6 D 27 得到d P2 I C 0 4 16 12 得到e E 13 14 20 阴影部分为通信延迟阴影部分为通信延迟 I表示处理机空闲表示处理机空闲 第48页/共90页 2021-7-1650 n2台处理机的采用结点复制技术的调度方台处理机的采用结点复制技术的调度方 案案: d,4 A,4 B,1 E,2 C,1 D,2 a,1 b, 1 c,1 a,1 c,1 e,4 P1P2 A,4 C,1 a,1 A B C P1 0 4 5 7 10 6 D 14 得到d 8 P2 A C 0

15、4 9 5 得到e E 6 7 13 阴影部分为通信延迟阴影部分为通信延迟 I 表示处理机空闲表示处理机空闲 第49页/共90页 2021-7-1651 n比较两种方案： n采用结点复制的技术后，调度方案 所用的时间几乎短了50%，其原因是 由于消除了两台处理机之间的延迟 （a，8）和（c，8）。 第50页/共90页 2021-7-1652 粒度确定和调度优化过程： n第一步：第一步：构造细粒度的程序图 n第二步：第二步：调度细粒度运算 n第三步：第三步：进行粒度组合得到粗粒度 n第四步：第四步：在组合图基础上产生并行调度 方案 第51页/共90页 2021-7-1653 静态多处理机调度的程

16、序分解 22211211 2222122122 2122112121 2212121112 2112111111 2221 1211 2221 1211 2221 1211 CCCCSum BABAC BABAC BABAC BABAC CC CC BB BB AA AA n需要8次乘法（每次需要101个CPU周期），7次加 法（每次需要8个CPU周期），以二叉树结构完成， 如下。 第52页/共90页 2021-7-1654 Aik Bkj k=1,2粒度=101 Aik Bkj Ai1 B1jAi2 B2j 粒度=8 Gij= Ai1 B1j+ Ai2 B2j 第53页/共90页 2021-

17、7-1655 n在20MHz下，M68000汇编代码如下（后面的数字 是指令所用的周期数）： nMoveWAxx,D115 nMoveWBxx,D215 nMPTYD1,D271 nMoveLD2,PAR20 nMoveLPAR1,D120 nMoveLPAR2,D220 nADDLD1,D28 nMoveLD2,PSUM 20 第54页/共90页 2021-7-1656 n通信延迟d的计算： P1 存储器 DMADMA P2 存储器 T1 T2 T3 T4 T5 串行链路 n其中，T3是32位在20Mbps下的传输时间，折合成 M68000的周期，T6是由于软件协议的延迟（假定 用5条Mov

18、e指令，共100个周期）。 周期2121002020322020654321TTTTTTd 第55页/共90页 2021-7-1657 n细粒度的程序图如下： ABCDEFGH dddddddd JKLM dd dd N O P dd SUM 第56页/共90页 2021-7-1658 n细粒度的顺序调度方案如下： P1 A B 0 202 101 C D 404 303 E F 606 505 G H 808 707 J K L M N O P 816 824 832 840 848 856 864 808 n共需864个周期。 第57页/共90页 2021-7-1659 n细粒度的并行调度

19、方案如下（8处理器）： P1 AB 0 313 101 CD 321 =101EF 531 523 GH 751 743 JKLM NO P P2P3P4P5P6P7P8 I II I II 图中的阴影部分为通信延迟 I表示处理机空闲 =8 d=212 =8 d=212 =8 d=212 第58页/共90页 2021-7-1660 n使用8个处理机进行并行调度，共需751个周期。 n和顺序调度相比，获得的加速比为: 15.1 751 864 S 第59页/共90页 2021-7-1661 n采用粒度组合减少通信开销： ABCDEFGH dddddddd JKLM dd dd N O P dd

20、SUM V W X Y Z 第60页/共90页 2021-7-1662 n通信延迟为： 周期212d n各结点粒度为： 24888 2108101101 Z YXWV n程序图中最大并行度已降为4，所以只需要用4台 处理机执行此粗粒度程序即可。 n上述调度方案只用了 94.1 446 864 44624212210 S 个周期， 第61页/共90页 2021-7-1663 第62页/共90页 2021-7-1664 T2 T3T1 T4T5 P1 P2 P3 12 345 0 最小平均流时间调度就是 在矩阵中找出一个调度流 时间最小的n元素组，该 元素组中两个或两个以上 元素不能在矩阵同一列上

21、 第63页/共90页 2021-7-1665 第64页/共90页 2021-7-1666 第65页/共90页 2021-7-1667 分布 2.排队规则排队规则 即时制立即服务，无柜台空即走不等待 等待制排队 等待服务次序先来先服务，先来后服务，随机服务， 优先权服务等 第66页/共90页 2021-7-1668 三个影响最大的因素：三个影响最大的因素：顾客到达时间间隔分布顾客到达时间间隔分布 服务时间分布服务时间分布 服务台的个数服务台的个数 可以求出顾客等待平均时间或所需服务台个数可以求出顾客等待平均时间或所需服务台个数 第67页/共90页 2021-7-1669 动态调度的依据，系统状态

22、信息。需要通过交换信息了动态调度的依据，系统状态信息。需要通过交换信息了 解系统状态解系统状态 两种交换方式：两种交换方式： 同步方式：按固定时间互通信息同步方式：按固定时间互通信息 （ 多长时间互通一次信息？）多长时间互通一次信息？） 异步方式：因某一事件触发互通信息异步方式：因某一事件触发互通信息 动态负载平衡动态负载平衡 第68页/共90页 2021-7-1670 行执行过程中，重载处理机按 “招标协议”向外广播寻求帮 助。空载处理机收到请求，给 予响应。 “征兵协议征兵协议”适用于负载比较平衡的系统适用于负载比较平衡的系统 “招标协议招标协议”适用于负载不平衡的系统适用于负载不平衡的系

23、统 第69页/共90页 2021-7-1671 TcTp/22Tc。 第70页/共90页 2021-7-1672 第71页/共90页 2021-7-1673 所生成的树所生成的树 例例 ： 并行求解迷宫问题并行求解迷宫问题 第72页/共90页 2021-7-1674 1 2 3 4 5 6 7 8 方位图方位图 第73页/共90页 2021-7-1675 第74页/共90页 2021-7-1676 n依此类推 第75页/共90页 2021-7-1677 第76页/共90页 2021-7-1678 第77页/共90页 2021-7-1679 222222222222222222 20110000

24、1111111002 210001111111110102 210101100001101102 210101101111011102 210101100000111112 211101101110111112 200000000010101112 211101101010010002 200001100010111112 211101111110111112 211101111101011112 211011000011100012 210111111011101112 201111111011101112 211111111101100012 211111111101111102 222222222222222222 迷宫问题描述迷宫问题描述 第78页/共90页 2021-7-1680 3.负载阈值