2019/10/24
17
T1 1
T2 2
T3 1
非抢先调度
T4 4
T5 4
给定一个任务图，结点表示
子任务，有向线表示各子任
务之间关系，结点右侧数字
T7 7
T8 4
T6 3
表示子任务的运行时间。
T9 1
P1 T1 T3
T6
T5
T7
P2 φ T2
T4
φ
T8
0
2019/10/24
3
7
9
13
两台处理机的尽早分配任务调度
c为正整数
所需最少处理机数目可由下式求出：
p
1

1 r*
c
r* j 1
(amax 1 j) p
其中ρ (i)表示途中标号 ai的结点数，
r*是给定表达式值为最大的常数r值
2019/10/24
26
标号
7
T16
T17
T18
T19
C=0，T=amax=7 r=1: ρ (7)/1= 4/1=4
单位权结点的抢先调度 两台处理机：
P1
T1
T3
P2
T2
T4
任务数为偶数
P1
T1
T2
P2 T2
T3
2019/10/24
任务数为奇数
1.5
31
对于三台处理机
P1
T1
P2
T2
P3
T3
T2 T3 T4
任务数为4
2019/10/24
P1
T1
P2
T2
T4
P3
T3
任务数为5
T2 T3
T5
32
最小完成时间的抢先调度算法：
设任务图为一颗根树，结点权可公度
1. 将单位权结点划分为若干个不相交的子集，子集内的结点相互独立， 可以同时运行
2. 任务图按层分割，结束结点为第一层，向上单位时间完成的结点为 第二层，依此类推。
3. 在不违背原图前趋的条件下，下层结点可以移至上层结点。 4. 首先调度最高层，逐步向下，可获得最小完成时间
19
从上图可以看出，处理机空闲时立即分配 任务不一定获得最小完成时间。
最早调度策略——从开始结点计算结点的 最早分配时间
最晚调度策略——从结束结点推算计算最 晚调度时间
一个任务图的任务分配是一个网络规划问 题
2019/10/24
20
一个任务图，可由图G=(T,Q）表示：
T={t1,t2,t3,……….tn} T为任务集 ti为结点权，表示子任务的运行时间。
11
k:=d*f
12
l:=j*k
13
m:=4*l
14
n:=3*m
15
o:=n*i
16
p:=o*h
17
q=p*g
2019/10/24
End
39
指令1，2，3，4，5，6是存储器访问（取数据） 操作，每个结点用一个周期进行寻址，用六个周 期从存储器取数。
指令7-17是CPU操作，每个需要两个周期完成。
为：
Tmin》＝ amax
amax为图的图的最大路径
2019/10/24
24
调度过程：
对于P台处理机 首先调度P个最大标号结点，可能包括两层
结点
把处理过的P个结点从图中删除，剩下没有 前趋的结点为开始结点
重复以上过程
2019/10/24
25
设一个任务图的执行时间为：
T= amax+c
T9
φ 17
18
T1 1
T2 2
T3 1
最小完成时间，由关键路径决定
所需最多处理机个数——图宽度 T4 4
T5 4
结点的最早调度时间 结点的最晚调度时间
T7 7
T8 4
T6 3
T9 1
P1 T1 T3 φ
T4
T7
P2 φ
T2
T5
T8
T6
0
2019/10/24
3
7
11
两台处理机的最佳分配任务调度
T9 φ 14 15
T6 11 2
T72 11 2
T82
1 1
2
公度结点权
T9 1
2
2019/10/24
35
31/6
64/6
73/6
P1
T1
7+1/2
P2
T2 14/3+1/2
T3
P3 T3 7/3+1/2
T5 7
012 3 456 7
T2 7/3
14/3
89
T4
T6 T9
1
3/2 1/2
T5 T7 Φ
1
3/2
T T T8 Φ
Q={q1,q2,q3,……. qm} Q为通信集 qj＝（ ti,tk)为 ti与 tk两个结点之间边的权，
表示两个子任务之间的通信量。
确定性调度，结点权是个常数，不确定性调 度结点权是不确定的数。
2019/10/24
21
一个多机系统可由系统图H＝（P,E) 表示 P={p1,p2,……….Ps} P为处理机集
37
细粒度程序的调度举例
Var a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q

Begin
1
a:=1
2
b:=2
3
c:=3
4
d:=4
5
e:=5
6
f:=6
2019/10/24
38
7
g:=a*b
8
h:=c*d
9
i:=d*e
10
j:=e*f
T22
T23 T12
T24
T31
2019/10/24
T3 4
公度（单位）结点权为4
29
最小完成时间的抢先调度
假设对n个相互独立任务和p台处理机进行调度， n个任务的权分别是w1,w2,…..wn，
最小完成时间是：
w

max{max(
wi ),
1 p
n i 1
wi }
2019/10/24
30
6 T12
T13
T14
T15
5
T10
T11
r=2: (ρ(7)+ ρ(6))/1
4
T7
T8
T9
= (4+4)/1=4 r=4
3
T4
T5
T6
(ρ(7)+ ρ(6)+ ρ(5)+ ρ(4))/4 2 =13/4=3.25
T3
T2
2019/10/24
1
T1
27
标号
7
T16
T17
T18
T19
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
6 T12
T13
T14
T15
5
T10
T11
4
T7
T8
T9
3
T4
T5
T6
2
T3
T2
1
T1
2019/10/24 r=2和r=5时，产生r*值，表达式值最大
28
抢先调度
公度结点权 定义：设如果存在一个正数w，
使得每个结点的权是w的正倍 数，称这组结点的权是相互 成比例的或是可公度的。
T1 8
T2 16
T21 T11
基本特点：

每个处理机有各自的私有表格，而有些表
格是系统公用的，增加了表格存取控制的 复杂性
每个处理机可以根据自身的需要及所分配
的任务进行管理
2019/10/24
6
管理程序的代码必须是可重入的，或者 是为每个处理机装入专用的管理程序副 本
某个处理机出了故障不一定会引起整个 系统瘫痪，但恢复困难。
2019/10/24
33
例：
T1 7 1 2
T2 7 1 2
T3 7 1 2
T4 1 T5 8
2019/10/24
T6 11 2
T7 2
T8 2
T9 1 2
34
T11 1 2
T21 1 2
T31 1 2
T12 7 T22 7 T32 7 T571 7
T4 1 T52 1
1 T71 2
1 T81 2
控制分布——处理机结点由自己的操作系统或 管理程序管理和控制本结点的资源和进程
资源分布——系统所有资源分布在各结点上， 便于各进程对资源的共享
2019/10/24
2
通信与同步——存在结点内并发进程之间 的同步和通信，各不同结点进程之间需要 同步和通信
系统容错——当系统中某一个部件或结点 发生故障，系统应能动态重新组合，降级 使用
2019/10/24
11
与调度相关的一些性能指标（参数） 1. 最小完成时间 2. 所需最少处理机数目 3. 最小平均流 4. 处理机最大利用率 5. 处理机最小空闲时间
2019/10/24
12
一般情况下，寻找最优的调度算法不一定 是最好的调度算法或不存在最优调度算法。 所以最优调度算法往往指为合理的调度算 法
决定把程序和数据分配到物理存储器的什 么位置
决定每个进程在哪个处理机上运行