分类： 第5章 互斥与同步

前述各种互斥手段的缺点

临界段操作的代码以及进入和退出临界段时的“上锁”和“开锁”操作代码，均要由用户来编写，加重了用户的负担；
所有同步原语操作都分散在用户编写的各程序代码中，由进程来执行，这样系统无法有效地控制和管理这些同步原语操作；
用户编程时难免会发生不正确地使用同步原语操作的错误，这种错误会给系统带来不堪设想的后果（如死锁），更麻烦的是，无论是编译程序或操作系统都无法发现和纠正此类错误。

管程的引入

使用PV操作实现同步时，对共享资源的管理分散在各个进程之中，进程能直接对共享变量进行处理，因此，难以防止有意或无意的违法同步操作，而且容易造成程序设计错误。如果能把有关共享变量的操作集中在一起，就可使并发进程之间的相互作用更为清晰,更容易编写出正确的并发程序。

进程间通信

并发进程之间的交往本质上是互相交换信息。有些情况下进程之间交换的信息量很少，例如仅仅交换某个状态信息。有些情况下进程之间交换大批数据，例如传送一批信息或整个文件。
进程之间互相交换信息的工作称之为进程通信IPC(InterProcess Communication)。

在进程间交换一定数量的信息，称为进程间通信；
进程间通信不但存在于一个作业的诸进程间，而且也存在于共享有关资源的进程之间，以及客户和服务器进程之间。

进程间通信的方式

通过软中断提供的信号（signal）通信机制；
使用信号量及其原语操作（PV、读写锁、管程或其他操作）控制的共享存储区(shared memory)通信机制；
通过管道(pipeline)提供的共享文件(shared file)通信机制；
使用信箱和发信/收信原语的消息传递(message passing)通信机制。
其中前两种通信方式属于低级通信机制，仅适用于集中式操作系统。
消息传递机制属于高级通信机制，共享文件通信机制是消息传递机制的变种，这两种通信机制，既适用于集中式操作系统，又适用于分布式操作系统。

间接通信方式

发送者进程不是把消息直接发送给接收者进程，而是把消息发送到一个共享的数据结构—信箱中去。接收者进程也到信箱中去取消息。
直接通信常用于进程间相互关系比较紧密的情况下；
间接通信用于联系不十分紧密的进程间；
间接通信方式的灵活性：
 发送者进程和接收者进程之间的关系可以有一对一、一对多、多对一、多对多等多种关系；
 信箱可以是静态的、固定不变的，也可以是动态的、可变的。

一对一：主要用于两个进程间建立私用的通信连接，可以不受其他进程的干扰和影响；
一对多：指一个发送者和多个接收者的通信关系，用于一个发送者进程向一组中的多个进程以广播的方式发送一个或多个消息的应用场合；
多对一：客户/服务器模式下客户进程和服务器进程之间的关系。

消息传递的方式

直接通信方式—消息缓冲区
 在直接通信方式下，企图发送或接收消息的每个进程必须指出信件发给谁或从谁那里接收消息。
间接通信方式—信箱
 采用间接通信方式时，进程间发送或接收消息通过一个信箱来进行，消息可以被理解成信件，每个信箱有一个唯一的标识符。当两个以上的进程有一个共享的信箱时，它们就能进行通信。一个进程也可以分别与多个进程共享多个不同的信箱，这样，一个进程可以同时和多个进程进行通信。

生产者—消费者问题

在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。
生产者--消费者问题表述如下：有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上，故又叫有界缓冲问题。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；类似地，只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。
缓冲区可以解决处理器处理速度和输出设备输出不匹配的问题

引入信号量

出现不正确结果不是因为并发进程共享了缓冲区，而是因为它们访问缓冲区的速率不匹配，或者说pi，cj的相对速度不协调，需要调整并发进程的进行速度。
并发进程间的这种制约关系称进程同步，交往的并发进程之间通过交换信号或消息来达到调整相互速率，保证进程协调运行的目的。
操作系统实现进程同步的机制称同步机制，它通常由同步原语组成。不同的同步机制采用不同的同步方法，迄今己设计出许多种同步机制，其中最常用的同步机制：信号量，管程和消息传递。

信号量（semaphore）

在多个相互合作的进程之间使用简单的信号来同步，一个进程被强制停止在某一特定状态，直到收到专门的信号为止。
一个信号量被定义为一个整型变量，在其上定义了以下三个操作：
 可以被“初始化”为一个非负数；
（P操作） Wait操作将信号量值减1后，若该值为负，则执行wait操作的进程等待；
（V操作） Signal操作将信号量值增1后，若该值非正，则执行signal操作的进程唤醒等待进程。
（信号量表示可使用资源个数）

用信号量实现进程间互斥

对于两个并发进程，互斥信号量的值仅取1、0和-1三个值：
 若mutex = 1，表示没有进程进入临界区；
 若mutex = 0，表示有一个进程进入临界区；
 若mutex = -1，表示一个进程进入临界区，另一个进程等待进入。

生产者—消费者问题举例

桌上有一只盘子，每次只能放入一只水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔于(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。

这个问题实际上是两个生产者和两个消费者被连结到仅能放一个产品的缓冲器上。生产者各自生产不同的产品，但就其本质而言，他们是同一类生产者。而消费者则各自取需要的产品消费，他们的消费方式不同。

读者—写者问题

有两组并发进程：读者和写者，共享一个文件F，要求：
 允许多个读者同时执行读操作；
 任一写者在完成写操作之前不允许其它读者或写者工作；
 写者执行写操作前，应让已有的写者和读者全部退出。
单纯使用信号量不能完成读者与写者问题，必须引入计数器rc对读进程计数，s是用于对计数器rc互斥的信号量，W表示允许写的信号量。
（s控制对rc的访问）

互斥的软件方法

问题：有两个并行进程P0和P1 ，互斥地共享单个资源（磁带机或某共享数据）。P0和P1是一个循环进程（即进程执行一个无限循环程序），每次只使用资源为一个有限的时间间隔。

解法1：用标志位flag[i]来标示进程i是否在临界段中执行，当flag[i]为真，则表示它正在执行临界段，反之不在临界段中执行；

存在的问题：当两个进程的标志位最初都为false，这时刚好两个进程同时都想进入临界段，并且同时发现对方标志位为false，于是两个进程同时进入了各自的临界段，违背了临界段设计原则，每次至多只允许一个进程进入临界段。（并发问题）

解法2：用一个指针turn来指示应该哪个进程进入临界段，若turn = i，则该进程Pi进入临界段；

存在的问题：强制两个进程以交替次序进入临界段，如果Pi进程的处理器速度要快得多，或者进程Pi的其他代码部分很长，那么进程Pi在进程Pj尚未进入临界段前要求再次进入临界段时，尽管此时临界段为空（无进程处于其中），进程Pi也无法进入临界段，从而使临界资源的使用率不高。

解法3：用flag[i]来表示进程i想要进入临界段，这是基于对解法1存在的问题：未表明自己想进入临界段的意向，而只检测对方是否已在临界段中，从而导致同时进入的情况的改进；

存在的问题：两个进程同时想进入临界段，于是把各自的标志位都置为true，并且同时检测对方的状态，发现对方也想进入（或已在临界段中），于是互相“谦让”而阻塞了自己，谁也进不了临界段，从而违反了临界段设计原则（2）。

解法4：为每个进程设置一个标志位flag[i]，同样，当该位为真时，则表示该进程Pi要求进入临界段（或已在临界段中执行），反之为假，另外还设置了一个指针turn以指出应该由哪一个进程进入临界段，若turn=i则应该由进程Pi进入临界段。

引入硬件方法

分析临界区管理的尝试中的几种算法，问题出在管理临界区的标志时要用到两条指令，而这两条指令在执行过程中有可能被中断，从而导致了执行的不正确。
能否把标志看作为一个锁，开始时锁是打开的，在一个进程进入临界区时便把锁锁上以封锁其它进程进入临界区，直至它离开其临界区，再把锁打开以允许其它进程进入临界区。如果希望进入其临界区的一个进程发现锁未开，它将等待，直到锁被打开。
要进入临界区的每个进程必须首先测试锁是否打开，如果是打开的则应立即把它锁上，以排斥其它进程进入临界区。
测试和上锁这两个动作不能分开，以防两个或多个进程同时测试到允许进入临界区的状态。

互斥的硬件方法

中断屏蔽方法
 在单处理器系统中，引起进程开关，使得当前运行进程交出处理器的唯一原因是中断；
 屏蔽中断就能保证当前运行进程把临界段代码顺利地执行完，保证互斥实现，然后再开中断；
 缺点：首先系统要付出较高代价；其次这种方法在多处理器系统中是不能保证进程间互斥的。
当进入锁测试之前关闭中断，直到完成锁测试并上锁之后再开中断。在这一短暂的期间，计算机系统不响应中断，因此不会转向调度，也就不会引起进程或线程切换，从而保证了锁测试和上锁操作的连续性和完整性，有效的实现了临界区管理。
但关中断时间过长会影响系统效率，关中断方法也不适用于多CPU系统。

硬件指令方法
TS（test-and-set）指令，又称检测和设置指令；
Swap指令，又称交换指令；
实现互斥的方法：为每个临界段或其他互斥的资源设置一个布尔变量，当其值为false则临界段未被使用，反之则说明正有进程在临界段中执行；
缺点：当进程正在临界段中执行时，其他想进入临界段的进程必须不断地检测布尔变量的值，即所谓“忙等待”，从而造成了处理器机时的浪费。

硬件指令实现互斥的优缺点

硬件指令方法实现互斥不但适用于单处理器情况，而且适用于共享主存的对称多处理器情况；
方法简单、行而有效；
可以被使用于多重临界段情况，每个临界段可以定义它自己的共享变量。
但，硬件指令方法一般采取“忙等待”的简单方法，进程不断地检测临界段状态，会造成处理器时间的浪费。

临界区（critical sections）
 进程中访问共享变量的代码段
 不同进程关于同一变量的临界段代码可能是完全不同的
 临界资源—共享变量（一次只允许一个使用）

临界区的互斥要求

进程对共享变量的读写操作必须互斥的进行；
对进程互斥地使用临界区有以下原则：
 在共享同一个临界资源的所有进程中，每次只允许有一个进程处于它的临界区；
 若有多个进程同时要求进入它们的临界区时，应在有限的时间内让其中之一进入临  界区，而不应相互阻塞；
 进程只应在临界区内逗留有限时间；
 不应使要进入临界区的进程无限期地等待在临界区之外；
 在临界区之外运行的进程不可以阻止其他的进程进入临界区；
 不要预期和假定进程进展的相对速度以及可用的处理器数目，因为这是不可预期的。

在多道程序设计系统中，同一时刻可能有许多进程，这些进程之间存在两种基本关系：竞争关系和协作关系。
竞争关系：（系统中的多个进程之间彼此无关，它们并不知道其他进程的存在，但由于共享系统资源，就会出现竞争。当多个进程竞争共享硬设备、变量、表格、链表、文件等资源时，可能导致处理出错。）
 死锁、饥饿（资源的竞争出现了这两个控制问题）
 进程的互斥（临界区管理）(特殊的同步)
协作关系：（某些进程为完成同一任务需要分工协作。例如：input, compute, output ，协作进程之间各自知道对方的存在）
 进程的同步（解决进程间协作关系的手段 ）
进程互斥关系是一种特殊的进程同步关系，即逐次使用共享资源。