《计算机操作系统》（第4版）第10章 多处理机操作系统 复习笔记

第10章 多处理机操作系统

一、多处理机系统的基本概念

1. 多处理机系统的引入

(1)CPU   时钟频率接近极限。

(2)增加系统吞吐量。

(3)节省投资。

(4)提高系统可靠性。

2.多处理机系统的类型

(1)紧密耦合MPS 和松散耦合MPS

①紧密耦合MPS

紧密耦合通常是通过高速总线或高速交叉开关来实现多个处理器之间的互连的。系统中的所有资源和进程都 由操作系统实施统一的控制和管理。

②松散耦合MPS

在松散耦合MPS 中，通常是通过通道或通信线路来实现多台计算机之间的互连。每台计算机都有自己的存 储器和I/O 设备，并配置了OS 来管理本地资源和在本地运行的进程。

(2)对称多处理器系统和非对称多处理器系统

①对称多处理器系统SMPS(Symmetric Multiprocessor System)

在系统中所包含的各处理器单元，在功能和结构上都是相同的，当前的绝大多数NIPS 都属于SMP 系统。

② 非对称多处理器系统ASMPS(Asymmetric Multiprocessor System)

在系统中有多种类型的处理单元，它们的功能和结构各不相同。系统中只有一个主处理器，有多个从处理器。

二、多处理机系统的结构

1.UMA  多处理机系统的结构

(1)基于单总线的SMP 结构

基于单总线的 SMP 结构如图10-1 (a)   和 (b)   所示，其中有高速缓存的比没有高速缓存的可伸缩性强，同 时也可接入更多的CPU。

图10-1 基于单总线的SMP 结构

(2)使用多层总线的SMP 结构

使用多层总线的SMP 结构如图10-1 (c)   所示，其私有存储器与CPU 通过了本地总线相连，系统总线再与 本地总线相连。

(3)使用单级交叉开关的系统结构

这种系统结构将CPU 与存储器结点通过交叉开关阵列相互连接，从而避免了在多个CPU 之间因为要访问存 储器模块所形成的对链路的争夺，如图10-2所示。

图10-2 使用交叉开关的LIMA 多处理机系统

(4)使用多级交换网络的系统结构

多级交换网络通过将分级小交换开关分级连接起来，形成多级交叉开关网络，如图10-3所示。

图10-3 使用多级交换网络的SMP 结构示意图

2.NUMA   多处理机系统结构

NUMA即非统一内存访问。在这种结构的多处理机系统中，其访问时间随存储字的位置不同而变化，系统  中的公共存储器和分布在所有处理机的本地存储器共同构成了系统的全局地址空间，可被所有的处理机访问。如 图10-4所示。

图10-4 NUMA结构的多处理机系统

三、多处理机操作系统的特征与分类

1. 多处理机操作系统的特征

(1)并行性。

(2)分布性

① 任务的分布。

②资源的分布。

③控制的分布。

(3)机间的通信和同步性。

(4)可重构性。

2.多处理机操作系统的功能

(1)进程管理

①进程同步。

②进程通信。

③ 进程调度。

(2)存储器管理

除了需要具有单机多道程序系统中的地址变换机构和虚拟存储器功能外，还应增强和增加下面的功能和机制：

①地址变换机构。

②访问冲突仲裁机构。

③数据一致性机制。

(3)文件管理

①集中式。

②分散式。

③分布式。

(4)系统重构。

3.多处理机操作系统的类型

(1)主从式 (master-slave) 

①概述

在这种类型的操作系统中，有一台特定的处理机被称为主处理机，其他处理机则称为从处理机。从处理机只 能处理主处理机分配给它的任务。

②优缺点

a.   易于实现。

b. 资源利用率低。

c.   安全性较差。

(2)独立监督式 (separate supervisor System)

①概述

独立监督式，也称为独立管理程序系统，它与主从式不同。在这种系统中，每个处理机上都有自己的管理程 序(操作系统内核),并拥有各自的专用资源。

②优缺点

a. 自主性强。 

b. 可靠性高。 

c.   实现复杂。

d.  存储空间开销大。

e.  处理机负载不平衡。

(3)浮动监督式 (floating supervisor Control Mode) ①概 述

浮动监督式，也称为浮动管理程序控制方式，这是最复杂的，但也是最有效、最灵活的一种多处理机操作系 统方式，常用于紧密耦合式的对称多处理机系统中。在这种方式实现的系统中，所有的处理机组成一个处理机池， 每台处理机都可对整个系统中的任何一台I/O 设备进行控制，以及对任何一个存储器模块进行访问，这些处理机 由操作系统统一进行管理。

②优缺点

a.  高灵活性。 

b.  高可靠性。 

c.   负载均衡。 

d. 实现复杂。

四 、进程同步

1. 集中式与分布式同步方式

(1)中心同步实体

为实现进程之间的同步，系统中必须有相应的同步实体(Synchronizing     Entity),如硬件锁、信号量以及进程等。如果该同步实体满足下述两个条件，则称之为中心同步实体：

①具有唯一的名字，并且为彼此必须同步的所有进程所知道；

② 在任何时刻，这些进程中的任何一个都可以访问该同步实体。

(2)集中式同步机构

基于中心同步实体所构成的所有同步机构被称为集中式同步机构。相应的，其他同步机构则称为非集中式同 步机构。在多处理机系统中，除了采用单处理机的同步机制，如硬件锁。信号量等，又增加了一些如自旋锁、

RCU锁、时间邮戳、事件计数以及中心进程等多种同步机制。

(3)集中式与分布式同步算法

①集中式同步算法 a.  特征

第一，对于多个进程需要同时访问共享资源或进行通信时，仅由中心控制结点做出判定，选择一个进程执行； 第二，判定所需要的全部信息都集中在中心控制结点。

b.   缺点

第一，可靠性差。

第二，易形成瓶颈。

②分布式同步算法

一个完全分布式同步算法具有以下特征：

a.  所有结点具有相同的信息；

b. 所有结点仅基于本地信息做出判断；

c. 为了做出最后的判定，所有的结点担负相同的职责；

d.  为了做出最后的判定，所有的结点要付出同样的工作量；

e.  通常一个结点发生故障，不会导致整个系统的崩溃。

2. 自旋锁 (spin lock)

(1)自旋锁的引入

为了防止处理机对总线资源的竞争，在多处理机中引入对总线实现互斥的机制，即自旋锁。

(2)实现对总线互斥访问的方法

在总线上设置一个自旋锁，该锁最多只能被一个内核进程持有。当一个内核进程需要使用总线时，先请求自 旋锁，如果该锁被占用，那么这个进程就会一直进行“旋转”,循环测试锁的状态，直到自旋锁重新可用。

(3)自旋锁与信号量的主要差别

自旋锁应用于对总线资源的竞争，其效率远高于信号量机制，且在多处理器环境中非常方便。

(4)自旋锁的类型

①普通自旋锁。

②读写自旋锁。

③大读者自旋锁。

3.读-拷贝-修改锁

(1)RCU(Read-Copy-Update)锁

当某写进程要往某文件中写入数据时，它先读该文件，将文件的内容拷贝到一个副本上，以后只对副本上的 内容进行修改。修改完成后，在适当时候再将修改完后的文件全部写回去。

(2)写回时机

在 RCU 锁机构中，将修改后的内容写回的时机最好是在所有读者都已完成自己的读任务后再将修改后的文 件写回。

(3)RCU   锁的优点

①读者不会被阻塞。

②无需为共享文件(数据)设置同步机构。

4.二进制指数补偿算法和待锁CPU等待队列机构

(1)二进制指数补偿算法

①基本思想

为每一个CPU 对锁进行测试的TSL(Test and Set Lock)指令设置一个指令延迟执行时间，使该指令的下次  执行是在该延迟执行时间设定的时间后进行，其延迟时间是按照一个TSL 指令执行周期的二进制指数方式增加。

②优点

a.可以将短时间内各CPU 对锁的需求，在时间上进行不同程度的延迟，增加测试的成功率，减少各CPU 对锁的测试次数；

b.在锁不空闲时，也很大程度地减少各CPU 对其进行测试的频率。

③缺点

锁被释放时，可能由于各CPU 的测试指令的延迟时间未到，没有一个CPU 会及时地对锁进行测试，即不能 及时地发现锁的空闲，造成浪费。

(2)待锁CPU 等待队列机构

①在整个过程中，每一个待锁CPU 都仅是在自己的高速缓存中，对其私有的锁变量进行不断的测试，不会 对总线进行访问，减少了总线的流量。

②一旦锁空闲，便由释放该锁的CPU 通过修改其待锁清单中的下一个待锁CPU 的锁变量的方法，及时通知 下一个待锁CPU 进入临界区，从而避免了资源空闲而造成的浪费。

5.定序机构

(1)时间邮戳定序机构 (Timestamp Ordering Mechanism)

对时间邮戳定序机构最基本的要求是，在系统中应具有唯一的、由单一物理时钟驱动的物理时钟体系，确保各处理机时钟间的严格同步。该定序机构的基本功能是：

①对所有的特殊事件，如资源请求、通信等，加印上时间邮戳；

②对每一种特殊事件，只能使用唯一的时间邮戳；

③根据事件上的时间邮戳，定义所有事件的全序。

(2)事件计数 (Event  Counts) 同步机构

①await(E,V)

每当进程要进入临界区之前，先执行await  操作，如果 E<V,  将执行进程插入到EQ 队列，并重新调度；否 则进程继续执行。

②advance(E)

每当进程退出临界区时，应执行 advance(E)    操作，使E 值增1。如果EQ 队列不空，则进一步检查队首进 程的V 值；若E=V, 则唤醒该进程。

6. 面包房算法

该算法是最早的分布式进程同步算法，是利用事件排序的方法对要求访问临界资源的全部事件进行排序，按 照FCFS(first  come  first  service) 次序对事件进行处理。

7.令牌环算法

该算法属于分布式同步算法，是将所有进程组成一个逻辑环(logical Ring),系统中设置一个象征存取权力 的令牌(Token),  它是一种特定格式的报文，在进程所组成的逻辑环中，不断地循环传递，获得令牌的进程，才 有权力进入临界区，访问共享资源。

五 、多处理机系统的进程调度

1. 评价调度性能的若干因素

(1)任务流时间

把完成任务所需要的时间定义为任务流时间，例如，如图10-5所示，T1  的任务流时间为7个时间单位，T2 为6.5个时间单位，而T3 、T4 、T5 都为2个时间单位。

图10-5 任务流和调度流示意图

(2)调度流时间

在多处理机系统中，任务可以被分配到多个处理机上去运行。一个调度流时间是系统中所有处理机上的任务 流时间的总和。在如图10-5所示的例子中，在三台处理机上，调度流时间：T1 流+T2 流+T3 流+T4 流+T5 流=7+6.5+2+2+2=19.5(个时间单位)。

(3)平均流

平均流等于调度流时间除以任务数，最少平均流时间就是系统吞吐率的一个间接度量参数。

(4)处理机利用率

处理机的利用率等于该处理机上任务流之和除以最大有效时间单位。

(5)加速比

加速比等于各处理机忙时间之和除以并行工作时间。加速比用于度量多处理机系统的加速程度。

(6)吞吐率

吞吐率是单位时间(例如每小时)内系统完成的任务数。可以用任务流的最小完成时间来度量系统的吞吐率。 吞吐率的高低与调度算法有着十分密切的关系。

2.进程分配方式

(1)对称多处理机系统中的进程分配方式

①静态分配 (Static Assignment)方式

指一个进程从开始执行直至其完成，都被固定地分配到一个处理器上去执行，其优点是进程调度的开销小， 但会使各处理器的忙闲不均。

②动态分配 (Dynamic Assignment)方式

为了防止系统中的多个处理器忙闲不均，可以在系统中仅设置一个公共的就绪队列，系统中的所有就绪进程 都被放在该队列中。分配进程时，可将进程分配到任何一个处理器上。其优点是消除了各处理器忙闲不均的现象， 但会造成调度开销的明显增加。

(2)非对称MPS 中的进程分配方式

对于非对称MPS, 其 OS 大多采用主一从(Master  Slave)式 OS,即 OS的核心部分驻留在一台主机上(Master), 而从机 (Slave)  上只是用户程序，进程调度只由主机执行。

3.进程(线程)调度方式

(1)自调度 (Self-Scheduling)  方式

①自调度机制

自调度机制是在系统中设置有一个公共的进程或线程就绪队列，所有的处理器在空闲时，都可自己到该队列 中取得一进程(或线程)来运行。

②自调度方式的优点

a.  较容易将单机处理机的调度机制移植到多处理机上。

b. 有利于提高处理机的利用率。

③自调度方式的缺点

a.  瓶颈问题。

b. 低效性。

c.   线程切换频繁。

(2)成组调度 (Gang  Scheduling) 方式

为了解决在自调度方式中线程被频繁切换的问题，提出了成组调度方式。该方式将一个进程中的一组线程分 配到一组处理器上去执行。在成组调度时，如何为应用程序分配处理器时间，可考虑采用以下两种方式：

①面向所有应用程序平均分配处理器时间。

②面向所有线程平均分配处理机时间。

(3)专用处理机分配 (Dedicated Processor Assignment) 方式

专用处理机分配方式是指在一个应用程序的执行期间，专门为该应用程序分配一组处理机，每一个线程一个 处理机。这组处理机仅供该应用程序专用，直至该应用程序完成。很明显，这会造成处理机的严重浪费。但可以 把这种调度方式用于并发程度相当高的多处理机环境。

(4)动态调度

动态调度的原则为：

①空闲则分配。

②新作业绝对优先。

③保持等待。

④释放即分配。

4 . 死锁

(1)死锁的类型

①资源死锁。

②通信死锁。

(2)死锁的检测和解除

①集中式检测。

②分布式检测。

六、网络操作系统

1. 网络操作系统及其分类

(1)网络操作系统及其特征

①概述

网络操作系统建立在网络中计算机各自不同的单机操作系统之上，为用户提供使用网络系统资源的桥梁。

②特征

a.   硬件独立性。

b.  接口一致性。

c.   资源透明性。

d.    系统可靠性。

e. 执行并行性。

(2)网络操作系统的分类

① 对等模式 (peer-to-peer model)

a.  概述

在该模式的操作系统管理下，网络上的每台计算机处于平等的地位，系统中不设专用服务器，任何一台计算 机和其他计算机之间没有从属关系。

b.  特点

第一，适用于较小范围和规模的网络；

第二，结构简单，容易安装和维护，网络中任意两个节点均可直接通信；

第三，降低了信息处理能力。

②工作站/服务器模式(Workstation/Server model)

该模式将网络中的节点计算机分为两类：网络服务器 (Server)   和网络工作站  (Workstation) 。 服务器以集 中方式管理网络中的共享资源，为工作站提供服务，服务器不再作其他用途。工作站为本地用户访问本地资源和 访问网络资源服务。

③客户服务器模式 (Client/Server model)

④浏览器服务器模式(Browser/Server model)

2. 网络操作系统的功能

(1)数据通信

①连接的建立与拆除。

②报文的分解与组装。

③传输控制。

④流量控制。

⑤差错的检测与纠正。

(2)应用互操作

①信息的互通性。

②信息的“互用性”。

(3)网络管理

①网络管理的目标

a.   增强网络的可用性。

b.  提高网络的运行质量。

c.   提高网络的资源利用率。

d. 保障网络数据的安全性。

e.   提高网络的社会和经济效益。

②网络管理的功能

a.   配置管理。

b.   故障管理。

c.   性能管理。

d. 安全管理。

e.  计费管理。

七、分布式文件系统

1. 分布式系统

(1)分布式系统的特征

分布式系统(distributed   system),是基于软件实现的一种多处理机系统，是多个处理机通过通信线路互连而 构成的松散耦合系统，系统的处理和控制功能分布在各个处理机上。分布式系统应具有以下几个主要特征：

①分布性。

②透明性。

③同一性。

④全局性。

(2)分布式系统的优点

①计算能力强。

②易于实现共享。

③方便通信。

④可靠性高。

⑤可扩充性好。

(3)分布式系统的缺点

①主要表现为可用软件不足。

②在通信网络方面的信息丢失、网络安全方面的数据安全保密等存在一些潜在的不足。

(4)分布式操作系统

分布式操作系统除了涵盖单机操作系统的主要功能外，还应该包括：

a.  通信管理功能。

b.  资源管理功能。

c.   进程管理功能。

2.分布式文件系统的实现方式和基本要求

(1)DFS的实现方式

①共享文件系统方式(shared file system approach)。

②共享磁盘方式 (shared disk approach)。

(2)基本要求

①透明性

a.  位置的透明性。

b.  移动透明性。

c. 性能透明性。

d.  扩展透明性。

②高性能和高可靠性。

③容错性

一般采用多种冗余技术实现对故障的掩盖，包括：

a. 信息冗余；

b.  时间冗余；

c.   物理冗余。

④安全性。

⑤一致性。

3. 命名及共享语义

(1)命名

命名就是在数据的逻辑对象和物理对象之间建立的映射。在DFS 中，主要有三种命名方案：

①结合主机名和本地名对文件命名；

②将若干台服务器中的远程目录，加载到客户机的本地目录中；

③全局统一命名。

(2)共享语义

通常，实现多个客户机共享文件的方法主要有四种：