三、互斥与同步

1.进程同步的基本概念

✔两种形式的制约关系：互斥与同步

✔临界资源：打印机、 磁带机、共享变量等，都属于临界资源，一次只能被一个进程使用的资源。诸进程互斥共享临界资源。

✔临界区：每个进程中访问临界资源的那段代码称为临界区

✔临界区管理的三个要求：

(1)  一次最多允许一个进程停留在相关的临界区内；

(2)  一个进程不能无限止地停留在临界区；

(3)  一个进程不能无限止地等待进入在临界区。

✔同步机制应遵循的规则：

空闲让进、忙则等待、有限等待、让权等待。

2、互斥的实现方法

2.1标志法

          

2.2硬件实现方法（TS、Swap、关中断）

（1）利用Test-and-Set指令实现互斥

Boolean TS（boolean *lock）{

         boolean old;

         old =*lock;

         *lock=true;

         return old;

}                                     

         …

         while TS(&lock);      //测试lock并设置lock的值

         临界区；

         lock = false;

         ….

分析：当TS(&lock)的值为假时，设置lock为真并结束循环。

当TS(&lock)的值为真时，继续循环。

（2）利用Swap指令实现进程互斥

swap(boolean a,boolean b)

{

         boolean temp;

         temp=a;

         a=b;

         b=temp

}

         …

         boolean key;   

         key=true;

         do

                   swap(&lock,key);

         while (key);

         临界区；

         lock=false;

         …

（3）关中断

在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。保证了对锁的测试和关锁操作的连续性和完整性，有效地保证了互斥。

但是，关中断的方法存在许多缺点：

①滥用关中断权力可能导致严重后果；②关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；③关中断方法也不适用于多CPU 系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。

2.3信号量及P、V原语

✔解决问题：

1）TS或SWAP指令管理临界区，采用忙式轮询，效率低；
2）关开中断管理临界区，不便交给用户程序使用。

1. 信号量的构思

       一种可动态定义的软件资源：信号量

◆核心数据结构：等待进程队列

◆信号量声明：资源报到，建立队列

◆申请资源的原语：若申请不到，调用进程入队等待。

◆归还资源的原语：若队列中有等待进程，需释放。

◆信号量撤销：资源注销，撤销队列。

2. 记录型信号量

■其数据结构如下：

    typedef struct semaphore{

        int value;              //信号量值

        struct pcb *list;    //信号量等待进程队列指针

      }

■ 每个信号量建立一个等待进程队列

■ 每个信号量相关一个整数值

✔正值表示资源可用的数量

✔0值表示无资源且无进程等待

✔负值表示等待队列中进程的个数

3.  P、V操作原语

　　Viod P(semaphore s){

      s.value=s.value-1;

      if (s.value<0) {

          将该进程插入到s.list的等待进程队列中；

          block(s.list);

      }

    }

    Viod V(semaphore s){

      s.value=s.value+1;

      if (s.value<=0) {

          从s.list的等待进程队列中释放一个进程P；

          wakeup(P);

      }

    }

2.4用P、V操作原语实现进程互斥

　　semaphore mutex；

    mutex=1；

    …

    process Pi{

      …

      P(mutex);

      进程Pi进入临界区

      V(mutex);

      …

    }

2.5用PV操作解决缓冲区问题

（1）单缓冲区问题

（2）M生产者N消费者K个缓冲区

3、进程通信

3.1进程通信的类型

1. 共享存储器系统(Shared-Memory System)

可分为以下两种类型：

①基于共享数据结构的通信方式。②基于共享存储区的通信方式。

2. 管道(pipe)通信系统

为了协调双方的通信，管道机制必须提供以下三方面的协调能力：

①互斥②同步③确定对方是否存在

3. 消息传递系统(Message passing system)

可进一步分成直接通信方式和间接通信方式

3.2消息传递通信的实现方式

1. 直接消息传递系统

1）直接传递原语

       send(P，信件)：把信件发送给进程P

       receive(Q ，信件)：从进程Q接收信件

2) 进程的同步方式

3) 通信链路

2.间接消息传递系统——信箱通信

■ 发送或者接收信件通过一个信箱来进行，该信箱有唯一标识符。

■多个进程共享一个信箱。

信箱通信原语

Send（A，信件）：把信件传送到A信箱；
Receive（A，信件）：从A信箱中接收信件。

4、死锁

4.1死锁的概念

1.定义：在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占有的资源。

2.可重用性资源和消耗性资源

3.可抢占性资源和不可抢占性资源

4. 计算机系统中的死锁

1）竞争不可抢占性资源引起死锁

2) 竞争可消耗资源引起死锁

3) 进程推进顺序不当引起死锁

4.2死锁的必要条件（互斥、部分分配、不可抢占、循环等待）

4.3死锁的防止：破坏产生死锁的四个必要条件中的一个或几个，以避免发生死锁。

■破坏互斥条件，把独占型资源改造成共享型资源

■采用剥夺式调度方法可以破坏不可抢占条件

■破坏部分分配条件，一次性为进程分配所有应使用的资源。

■破坏循环等待条件，使运行期间不存在进程循环等待现象。

*主要方法：

1. 静态分配法

■开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。破坏了部分分配条件。

■层次分配法

■ 在层次分配策略下，资源被分成多个层次；

■ 一个进程得到某一层的一个资源后，他只能在申请在较高层次的资源；

■当一个进程要释放一个资源时，必须先释放所占用的较高层次的资源；

■当一个进程获得了某一层的一个进程后，它想再申请改层中的另一个资源，那么，必须先释放改层中的已占有资源。

■不可能形成循环回路，故阻止了循环等待的出现。

4.4死锁的避免（银行家算法：借钱给有偿还能力的客户）

1.银行家算法（单一资源）

假设系统有三个进程P，Q，R，系统只有一类资源共10个，目前分配情况如下：

安全序列：{Q，P，R}

2.银行家算法（多个资源）

假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示，给出一个安全序列。

 (1)从题目中，可以提取出Max矩阵和Allocation，用二个矩阵相减得到Need矩阵：

(2)用Avaliable向量与Need矩阵各行比较，找出比Avaliable向量小的行：

（3  3  2）>(1  2  2)和（3  3  2）>(0  1  1)

对应的二个进程分别为P1和P3，我们选择P1加入安全序列。

(3)释放P1所占有的资源，即把P1进程对应的Allocation矩阵中的一行与Avaliable向量相加：

（3  3  2）+（2  0  0）=（5  3  2）=  Avaliable

(4)在Need矩阵中去掉P1对应的行

(5)重复第（2）步，最后得到一个安全序列：{P1，P3，P4，P2，P0} 

故系统是安全的。

4.5死锁的检测与恢复

如果在系统中，既不采取死锁预防措施，也未配有死锁避免算法，系统很可能会发生死锁。在这种情况下，系统应当提供两个算法：

① 死锁检测算法。该方法用于检测系统状态，以确定系统中是否发生了死锁。

② 死锁解除算法。当认定系统中已发生了死锁，利用该算法可将系统从死锁状态中解脱出来。

1. 死锁的检测
为了能对系统中是否已发生了死锁进行检测，在系统中必须：① 保存有关资源的请求和分配信息；② 提供一种算法，它利用这些信息来检测系统是否已进入死锁状态。
1) 资源分配图

2) 等待图：

2. 死锁的解除
1)终止进程的方法：终止所有死锁进程、逐个终止进程

2)校验点：执行过程中定时设置校验点。从校验点开始重新执行。