◆中心进程的作用是安排访问共享资源的顺序
第十章
多处理机操作系统
10.3 多处理机调度
10.3.1 调度性能评价
P1 P2 P3
T1 T2
T2 T1 时间
T3 T4 T5 0 1 2 3 4 5 6 7
图10-5 表示任务调度的Gantt图
第十章
多处理机操作系统
10.3.1 调度性能评价
◆任务流时间
◆调度流时间
◆平均流 ◆处理机的利用率
第十章
多处理机操作系统
10.3.1 调度性能评价
◆处理机平均利用率 ◆最小完成时间
◆加速比
第十章
多处理机操作系统
确定性调度
10.3.2
10 6 5 T1 T2 8 T3
图10-6 任务的优先图
T4 4 T5
3 T6
第十章
多处理机操作系统
确定性调度
◆最小完成时间的抢夺调度
T2 T5 T1 T3 T6 T7 T4 T9 T8 T10 T11
图10-9 w＝1的Gw
第十章
多处理机操作系统
确定性调度
◆第二种情况为根树 7.5
T1 7.5 T2 7.5 T3 1.0 T4 8.0 T5 1.5 T6 2.0 T7 2.0 T8 0.5 T9
10.3.2
(a) 根树
9
5 5 10 6 6
◆具有单机操作系统所具有的各种功能
◆应具有新的进程同步与互斥算法
◆地址变换机构比单机环境复杂 ◆应使操作系统具有重构能力
第十章
多处理机操作系统
10.2 多处理机操作系统的功能与类型
◆多处理机操作系统，目前有三种类型： (1)主从式 (2)独立监督式 (3)浮动监督式
◆中心进程又称协调进程，它是多处理机系统管理程 序的一部分
第十章
多处理机操作系统
10.1 多处理机系统结构
10.1.1 处理器与处理器之间的连接
P1 P2 P3 P4
M
M
M
注：P代表处理器，M代表存储器 图10-1 多端口存储器方式多处理器
P1
P2 集 中 式 开 关 M M
图10-2 集中控制开关方 式多处理器
Pn
M
P1 M1 M2
P2 Mn
Pn
集 中 式 开 关
T2
T4 T6 T9 T7 T8

时间
0 1 2 3 4 5 6 7 8 9 10 11 12 13
(c) 优化PS
第十章
多处理机操作系统
确定性调度
10.3.2
◆最小完成时间的非抢夺调度
1 T16 1 T17 1 T18 1 T19
标号 7
1 T12 1 T13 Hale Waihona Puke T14 1 T156 5
10.3.2
7 T1 14 T2
图10-7 G
10.5 T3
3.5 T21 3.5 T22
3.5 T11 3.5 T23
3.5 T12 3.5 T24 3.5 T31 3.5 T32 3.5 T33
图10-8 Gw
第十章
多处理机操作系统
确定性调度
10.3.2
◆首先考虑的是任何具有彼此可公度结点权的 任务图在2台处理机上的执行情况
1 T10 1 T11
1 T7 1 T8 1 T9
4
1 T4 1 T5 1 T6
3
1 T2 1 T3
2
1 T1
1
图10-11 按Hu算法标号的根树
第十章
多处理机操作系统
确定性调度
10.3.2
◆对于3个处理机P1, P2, P3的优化调度如下：
P1 T19 T16 T15 T11 T8 T5 T2 T1 P2 T18 T14 T13 T10 T7 T4 P3 T17 T12 T9 T6 T3 0
5 6
7
8
1
2
3
4
时间
由此可见，对图10-11的任务有向图(根树)的最少完 成时间Tmin = 8
第十章
多处理机操作系统
动态负载平衡 ◆接收者开始的负载平衡 ◆发送者开始的负载平衡
10.4
◆混合负载平衡
51 1213 63
P1 T1 P2 T2 P3 T3 0 1 2 3
T1 T2 T3 T5 4
=0.75 =0.75 =0.75 =0.75 5 6 7 8 9
T4 T6 T5 T7 T8
T9
时间
10 11 12 13 14
(b) M调度
P1 P2 P3 T3 T2
T1 T3 T5
M
M
图10-3 带局部存储器的 多处理器
M
P1 M1 开关 M2
P2 Mn 开关
Pn
开关
图10-4 分布式多处理器
◆图10-4被看作是松耦合型(loosely coupled)，图10-1 和图10-2(图10-3)被看作是紧耦合型(tightly coupled)
第十章
多处理机操作系统
10.2 多处理机操作系统的功能与类型