二、进程管理（三）同步与互斥

目录

3.1 临界资源与临界区

3.2 同步与互斥概念

3.3 实现临界区互斥的基本方法

3.3.1 软件实现方法

3.3.1.1 单标志法

3.3.1.2 双标志先检查法

3.3.1.3 双标志后检查法

3.3.1.4 Peterson算法

3.3.2 硬件实现方法

3.3.2.1 中断屏蔽方法

3.3.2.2 硬件指令方法之TestAndSet指令

3.3.2.3 硬件指令方法之Swap指令

3.4信号量

3.4.1整型信号量

3.4.2记录型信号量

3.4.3信号量实现同步

3.4.4信号量实现互斥

3.4.5信号量实现前驱关系 

3.5互斥锁

3.6管程

3.6.1管程的概念

3.6.2条件变量 

---

3.1 临界资源与临界区

临界资源是一段时间仅允许一个进程使用的资源。

包括，许多物理设备（如打印机）、变量、数据（公用队列）、共享缓存区。

注：可以共享的资源分为临界资源（非并发）和同时访问资源（并发）。

此外还有私有数据（非共享）这种资源只能供一个进程使用。

还有共享程序段（并行）可能同时被多个进程使用，必须是可重入代码，也称纯代码，允许多个进程同时访问。

 将临界资源的访问过程分以下4个部分：

1. 进入区。检查能否进入临界区，如果能够进入则设置标志阻止其他进程进入临界区。
2. 临界区（临界段）。进程中访问临界资源的那段代码。
3. 退出区。将正在访问的临界区标志清除。
4. 剩余区。代码中的其余部分。

3.2 同步与互斥概念

同步的概念是与异步对立的，异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进，即 “具有多个相异” 的 “步骤”  。

同步也称直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系源于它们之间的相互合作。

互斥也称间接制约关系，当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

进程同步的解决的就是进程由于异步性而出现的错误，错误也包括两个进程同时进入了临界区，所以同步机制应该遵循以下准则。

• 空闲让进。临界区空闲时让请求访问临界区的进程进入。
• 忙则等待。当已有进程进入临界区后，其他试图进入临界区的进程必须等待而不能进入。
• 有限等待。对请求访问的进程，必须在有限的时间内进入临界区。
• 让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

 注：这里忙则等待和忙等待着重点不同，前者是一瞬间，后者是长时间。

3.3 实现临界区互斥的基本方法

3.3.1 软件实现方法

 在进入区设置并检查一些标志，若不满足进入条件则循环检查等待，在退出区修改标志。

注：单标志法在进入区不设置标志 。

3.3.1.1 单标志法

turn：公用整型变量，比如为0时表示进程0可以进入。为1时表示进程1可以进入。

在进入区只会检查能否进入，如果不能则循环等待。

可以看到只有另一个进程进入临界区后才会在退出区改变turn让其他进程有进入的资格，

所以当一个有资格的进程长时间不进入临界区会导致另一个进程想进也无法进入临界区，违反空闲让进。

3.3.1.2 双标志先检查法

 flag[ i ]：表明第 i 个程序是否进入临界区，当检查到其他程序进入临界区时不能进入。

进入区要干两件事情，一个是检查，一个是检查成功后修改 flag[ i ] 。这两次操作不能一步完成，所以可能会出现两个进程依次都先检查后允许进入，出现错误。违反忙则等待。

3.3.1.3 双标志后检查法

两个进程先修改标志再进入检查， 结果发现对方都正在使用临界区（其实没有），违反空闲让进、有限等待准则。

3.3.1.4 Peterson算法

Peterson算法同时使用turn和flag[]，turn表示该进程有进入的意愿（自己给的资格），flag表示别的进程是否占用临界区

仅当某一个进程有意愿进入临界区和其他进程没有进入临界区时该进程可以进入临界区。

 

Perterson是单标志法和双标志后检查法的优点结合。利用flag实现临界资源的互斥访问，利用turn实现空闲让进，避免饥饿现象发生。

上述四种软件实现的临界区互斥都违背让权等待。

3.3.2 硬件实现方法

计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或对两个字的内容进行交换等。通过硬件支持实现临界段问题的方法称为低级方法，或元方法。  

3.3.2.1 中断屏蔽方法

 利用“开/关中断指令”实现，

缺点：不适合多处理机（另外一个处理机上的进程还可访问临界区）；只能在内核态完成，故只适用于内核进程。

3.3.2.2 硬件指令方法之TestAndSet指令

又称TS、TSL指令，是用硬件实现的，执行的过程是一气呵成的，双标志先检查由于上锁和检查不是一气呵成的而出错。以下是C语言描述的逻辑：

3.3.2.3 硬件指令方法之Swap指令

又称Exchge指令、XCHG指令。以下是C语言描述的逻辑。

共享布尔变量lock，初值为false表示未上锁。当old为ture时会不断循环交换函数，只有当lock为false时只需交换一次然后上锁，在退出区再解锁。

上面两种硬件指令方法适用于任意数目的进程，不管是单处理机还是多处理机。多处理机更适宜，因为单处理机会忙等。

上述三种低级（元）方法都没法实现让权等待。

3.4信号量

信号量机制是一种用来解决同步和互斥问题的机制，它只能被两个标准的原语wait（S）和signal（S）访问，可记为“P操作”和“V操作” 

3.4.1整型信号量

定义为一个用于表示资源数目的整型量S 。

3.4.2记录型信号量

记录型信号量是在整型信号量的基础上实现让权等待即解决忙等待而提出的。下面是定义：

 

• block原语实现自我阻塞，将进程从运行态→阻塞态。
• wakeup原语实现唤醒，将另一个进程从阻塞态→运行态。它们是成对出现的。

 注：若无特别说明，P/V操作都是记录型信号量。

3.4.3信号量实现同步

在前操作后执行V操作，在后操作前执行P操作。初值为0

• 假如先进行P1操作，则V（S）使S++，后面进行P2的P(S)操作没有阻塞。
• 假如先进行P2操作，则P（S）使P2进程阻塞，直到V（S）后P2才转到就绪态。

注：这个只是一个简单的同步问题，即P1操作的代码1,2一定要在P2操作的代码4,5,6前面。

当同步问题为一个进程中所进行的事情是某资源加一，而另一个进程中某事件的前提条件是某资源不为零，则同步信号量的初值不是恒为0。这些问题在后面的经典同步问题中会遇见。

3.4.4信号量实现互斥

用P/V操作夹住临界区。初值为1.

3.4.5信号量实现前驱关系 

为每一对前驱关系都设置一个信号量，初值为0。 

3.5互斥锁

解决临界区的最简单的工具就是互斥锁（mutex lock）函数acquire()获得锁，而函数release（）释放锁。

互斥锁的主要缺点是忙等待，可称为自旋锁（spin lock），如前面的TSL指令、swap指令、单标志法、Peterson。

互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。 

3.6管程

3.6.1管程的概念

信号量机制存在的问题：编写程序困难，易出错。引入管程进行封装，简化内部实现细节。

它有这些部分组成：

1. 局部于管程的共享数据结构说明。
2. 对该数据结构进行操作的一组函数。
3. 对局部于管程的共享数据初始化的函数。
4. 管程有一个名字。

一个进程只有通过调用管程内的函数才能进入管程访问共享资源。

每次仅允许一个进程进入管程，从而实现进程互斥。

 实现同步也可以执行调用这些函数：

3.6.2条件变量 

当一个进程进入管程后被阻塞，此时其他进程无法进入管程。

将阻塞原因定义为条件变量（condition），只能对其进行wait和signal操作。

x.wait：当x对应的条件不满足时，正在调用管程的进程调用x.wait将自己插入x条件的等待队列，并释放管程。

x.signal：x对应的条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞的进程。 

条件变量和信号量的比较：条件变量的wait和signal和信号量的P/V操作是不同的，条件变量的wait和signal操作类似于P/V操作中的block和wakeup原语，能够实现进程的阻塞/唤醒。而信号量中的P/V操作是“有值”的，信号量的值反映了剩余资源数（或排队等待的阻塞进程数），而在管程中，剩余资源数用共享数据结构记录，被封装了起来，程序员无需关心。