OS管理进程同步时主要做两个工作：

1.保证多个进程互斥的访问临界资源。

2.协调多进程间执行顺序，以实现程序可再现性。

2.4.1　进程同步的基本概念

1．并发进程两种关系

 (1)共享资源（间接关系、互斥）。

 (2)相互合作（直接关系、同步）。

2. 临界资源：互斥共享

   以生产者-消费者问题为例分析为何要互斥共享临界资源。

生产者-消费者(producer-consumer)问题：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。

   假设由若干个缓冲区首尾相连形成一个环形缓冲区，由生产者进程生产产品放入缓冲区中，由消费者从缓冲区中取走产品。

   过程中遵守的原则：

①若缓冲区中产品满则不能再生产产品放入缓冲区；

②若缓冲区空则不能从缓冲区中取走产品消费

简化问题，形成模型：

假设：3个缓冲区2个指针1个变量

in:指向存放产品的缓冲区。

out:指向取产品的缓冲区。

counter:每生产一个产品值+1；

        每取走一个产品，值-1

in/out初值设为1，可能取值0、1、2

每生产一个产品，in的下个取值为in:=(in+1)mod 3

in,out重逢时可能有两种情况：

1）in=out,缓冲池空

2）(in+1)mod3=out，缓冲区满

P-C问题描述：

1)两进程公用变量：

 Var n：integer；

 type item=…；

 var buffer: array[0，1，…，n-1]ofitem；

 in，out: 0，1，…，n-1；

 counter: 0，1，…，n；

2)两进程局部变量

 nextp:P进程，存放每次刚生产出来的产品；  

 nextc：C进程，存放每次要消费的产品。

生产者程序和消费者程序分别执行、顺序执行时结果都是正确的，但若并发执行就会出现差错。问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：

生产者进程对counter

加1操作过程

A:register1:=counter；

B:register1:=register1+1；

C:counter:=register1；

消费者进程对counter

减1操作过程

D:register2:=counter；

E:register2:=register2-1；

F:counter:=register2；

假设counter的当前值是5：

1)若先P进程再C进程则共享变量counter的值仍为5；

2)若先C进程再P进程则counter值也还是5;

3)若按下述顺序执行：A,B,D,E,C,F，则counter的值是4；

4)若按下述顺序执行：A,B,D,E,F,C,则counter的值是6；

程序失去了再现性。解决此问题的关键是应把变量counter作为临界资源处理，亦即，令生产者进程和消费者进程互斥地访问变量counter。

3．临界区

访问临界资源的进程可分为四个部分：

4．同步机制应遵循的规则（临界区管理原则）

   (1)空闲让进。

   (2)忙则等待。

   (3)有限等待。

      避免“死等”状态。

   (4)让权等待。

     避免“忙等”状态。

补:(5)有限时间使用。

补充：5.互斥与同步的关系

1)区别：

  互斥：联系松散,取用资源随机,有则用；

  同步：联系紧密，按序执行，有资源也不一定能用；

2)联系：

  都是进程间的相互制约关系，互斥是特殊的同步，二者统称为进程同步。

2.4.2 硬件同步

1.关中断

2.利用test-and-set(ts指令）

3.利用swap指令

2.4.3　信号量机制

  最初由Dijkstra提出。

 1．整型信号量

　　定义整型信号量S，表示资源数目初值为1。与一般整型量不同，S仅能通过原子操作wait(S)和signal(S)来访问。

  早期这两个操作一直被分别称为P、V操作，执行时不可中断。

P操作：申请资源

    1)若S ≤0，不做任何操作；

    2)若S>0,可进入临界区，同时S自减1变为0，为临资加锁；

P(S) 描述：

while  S<=0 do no-op；

S:=S-1；

V操作：释放资源

    1)退出临界区；　

    2)S自加1，解锁；

V(S)描述：

S:=S+1；

临资互斥访问:s在0和1之间变化

  P(S)

  临界区

  V(S)

整型信号量的缺点：

  1）让进程处于忙等状态

  2）对于等待的进程没有相应操作

改进思想：增加阻塞、唤醒原语。

2．记录型信号量

   记录型信号量是由于它采用了记录型的数据结构而得名的。它包含两个数据项：

S.value:代表资源数量。

S.L：指向阻塞队列的指针。

3．AND型信号量集

　　当系统中多个进程共同访问多个临资时会发生资源抢夺现象导致“死锁”。

解决方法：对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。

在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait。

缺点：

1)一次能申请多类资源，但每类只能申请一。

2)有些资源当数量低于某个限制数则不能再进行分配，AND信号量不能实现。

4．一般信号量集

对AND信号量机制加以扩充，形成一般化的“信号量集”机制。Swait操作可描述如下，Swait(…Si ，ti，di，…，)其中S为信号量，t为下限值，而d为需求值。

一般“信号量集”的几种特殊情况：

(1)Swait(S，d，d)。

   每次申请d个资源，当现有资源数少于d时不予分配。

 (2)Swait(S，1，1)。

   当S>1时，记录型信号量；  

   当S=1时，互斥信号量。

 (3)Swait(S，1，0)可控开关。

   当S≥1时，允许多个进程进入某特定区；

   当S=0时，阻止任何进程进入特定区。

2.4.4　信号量的应用

1．利用信号量实现进程互斥

为临界资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。利用信号量实现进程互斥的进程可描述如下：

2．利用信号量实现前趋关系(同步）

2. 4.5　管程机制

管程的引入原因

1．管程的定义：

   把资源以数据结构的形式抽象化，把对资源的操作以过程、函数的形式加以定义。

   定义：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块，称之为管程。

管程主要有以下特性：

  (1)模块化。管程是一个基本程序单位，可以单独编译。

(2)数据类型抽象化。管程中不仅有数据，而且有对数据的操作。

(3)信息掩蔽。管程内的变量和过程对于调用管程的进程而言是透明的。

管程和进程不同：

(1)二者数据结构不同:进程的PCB是私有数据结构，管程的是公共数据结构；

(2)二者操作不同:进程是程序执行有关的操作，管程主要是同步操作和初始化操作；

(3)二者设置的目的不同:进程是为了实现系统的并发性，管程则是为了解决共享资源的互斥使用；

  (4)二者工作方式不同:进程可调用管程，但反之不可。进程主动，管程被动；

  (5)二者并发性不同:进程之间能并发执行，而管程则不能与其调用者并发执行；

  (6)二者状态不同:进程具有动态性，管程则是操作系统中的一个资源管理模块静态。

2．条件变量

重新启动进程产生的问题：　　

    若进程Q因x条件处于阻塞状态，进程P接着调用管程执行,当P执行了x.v操作后进程Q被重新启动，此时两个进程P和Q如何确定哪个执行哪个等待?

  可采用下述两种方式之一进行处理：

(1)P等待,直至Q离开管程或等待另一条件。

(2)Q等待,直至P离开管程或等待另一条件。