量减少并行程序的执行时间。
2. 多处理机调度方式
确定性调度：在调度之前必须知道所有有关信息，例如每个任务的执行时间 和任务间的依赖关系，以便合理地把任务分派到处理机。 不确定性调度：根据任务运行的动态行为，将任务分配到特定的处理机上。
3. 调度性能评价
评价多处理机调度性能的参数有： 任务流时间 ：完成任务所需要的时间
2.独立监督式
独立监督式中，每一个处理机均有各自的管理程序(核心)。
3.浮动监督式
每次只有一台处理机作为执行全面管理功能的“主处理机”，但根 据需要，“主处理机”是可浮动的，即从一台切换到另一台处理机。
多处理机系统控制
多处理机调度
1.什么是多处理机调度
将作业或任务分配给指定的处理机，并要求在指定的时间内完成。调度算 法的一般目标是：使用最少的处理机、在最短的时间内完成并行程序的执 行任务。在处理机器数目固定时，要改进处理机分配和进程调度算法，尽

I／O操作
Cache中的内容可能与由I／O子系统输入输出形成的存储 器对应部分的内容不同。

共享数据
不同处理器的Cache都保存有对应存储器单元的内容。
存储器的一致性
如果对某个数据项的任何读操作均可得到其最新写入的值，
则认为这个存储系统是一致的 需满足以下条件 ① 处理器P对X进行一次写之后又对X进行读，读和写之间没有
存储器
I/O 系统
多个处理器共享一个存储器 当处理器规模较小时，这种机器十分经济 支持对共享数据和私有数据的cache缓存 私有数据供一个单独的处理器使用，而共享数据供多个处 理器使用
共享数据进入cache ，产生一个新的问题
Cache一致性问题！
多处理机cache的一致性
产生cache不一致的原因
其它处理器对X进行写，则读的返回值总是写进的值。
②一个处理器对X进行写之后，另一处理器对X进行读，读和写 之间无其它写，则读X的返回值应为写进的值。 ③ 对同一单元的写是顺序化的，即任意两个处理器对同一单 元的两次写，从所有处理器看来顺序都应是相同的。
实现一致性的基本方案
(1) Cache一致性协议：对多个处理器维护一致性的协议 (2) 关键：跟踪记录共享数据块的状态 (3) 共享数据状态跟踪记录技术
多处理机系统结构
多处理机硬件结构——紧耦合和松耦合
1.紧耦合多处理机
紧耦合多处理机是通过共享主存来实现处理机间通信的， 其通信速率受限于主存的频宽。但是，由于各处理机与主存
经互连网络连接，系统中处理机数就受限于互连网络带宽及
多台处理机同时访问主存发生冲突的概率。
图 7.1 紧耦合多处理机的结构
带非对称I/O子系统的多处理机
第二种方法是在私有的地址空间进行通信。多个私有地址空 间在逻辑上是分散的，并且不能被远程处理器寻址，数据通 信通过显式地在处理器间传松消息来完成。如集群，就是使 用消息传递的一类系统。
多处理机系统死锁
死锁问题是由于各处理机为争夺全局范围内的资源而引发的。
传统的狭义多处理机系统是利用系统内的多台处理器并行执行用
处理器 ＋cache
处理器 ＋cache
处理器 ＋cache
处理器 ＋cache
节点通过网络互连。访问可以是
互 连 网 络
本地的，也可是远程的；
可以不支持cache一致性协议，
I/o 存储器 I/o
存储器
I/o
存储器
I/o
存储器
规定共享数据不进入cache，仅私
有数据才保存在cache中。
处理器 ＋cache 处理器 ＋cache 处理器 ＋cache 处理器 ＋cache
解决Cache一致性问题的关键：
寻找替代监听协议的一致性协议
目录协议
在每个结点增加目录存储器，用于存放目录 基于目录的Cache一致性及其实现 目录协议必须实现两种基本操作
处理读失效；处理对共享、干净块的写
目录必须跟踪记录每个存储块的状态
必须记录哪些块有该处理器的拷贝
多处理机操作系统
1.主从式
主从式操作系统由一台主处理机记录、控制其它从处理机的状态， 并分配任务给从处理机。
调度流时间 ：调度中所有任务流的时间
平均流 ： 平均流等于调度流之和除以最大有效时间单位 加速比 ：用于度量系统的速度，等于各处理机忙时间之和除以并行工作 时间
吞吐率：单位时间内系统完成的任务数
多处理机间进程通讯
第一种方法是在共享的地址空间进行通信。物理上分开的存 储器能够作为逻辑上共享的地址空间进行寻址，利用地址空 间通过load和store操作隐式地传递数据；
采用冗余连接的非对称I/O子系统
2.松耦合多处理机
松耦合多处理机是通过消息传送系统连接的多处理机结 构。
机间互联形式
1. 总线形式 多个处理机、存贮器模块和外围设备通过接口与公用总线
相连，采用分时或多路转接技术传送。其中，单总线方式结构
简单、成本低， 系统上增减模块方便，但对总线的失效敏感。 而且，处理机数增加会增大访问总线冲突的概率而导致系统效 率急剧下降。虽然可以在处理机中设置局部存贮器和专用外围 设备来减少访问总线的冲突，但这种单总线形式也只适用于处 理机数较少的场合。IBM Stretch和UNIVAC Larg多处理机采用 的就是单总线方式。

目录
物理存储器中共享数据块的状态及相关信息均被保存 在一个称为目录的地方。

监听（snooping）
每个Cache除了包含物理存储器中块的数据拷贝之外， 也保存着各个块的共享状态信息。
2.分布式共享存储器 特点：
存储器分布于各节点中，所有
存储器 I/o 存储器 I/o 存储器 I/o 存储器 I/o
2. 环形互连形式
机间采用环形互连的多处理机
3. 交叉开关形式
图 7.7 交叉开关形式
交叉开关中结点开关的结构
存储器组织
1.集中式共享存储器 三个特点：
CPU0 CPU1 CPU2 CPU3
一级或 多级 cache
一级或 多级 cache
一级或 多级 cache
一级或 多级 cache
处理器数量不大——从而所有 处理器可共享一个集中式存储器， 处理器和存储器通过总线互连。 ������ 采用大容量Cache——可使采 用单一总线和单一存储器满足数 目不多处理器对存储器的要求。 ������ 每一处理器访问存储器的时 间是相等的