【操作系统】第四章 进程同步

目录

进程同步的概念

软件同步机制

硬件同步机制

信号量机制

管程机制

经典进程的同步问题

生产者-消费者问题

哲学家进餐问题

读者-写者问题

Linux进程同步机制

---

进程同步的概念

主要任务：使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。

进程间的制约关系：
间接相互制约关系(互斥关系)： 进程互斥使用临界资源
直接相互制约关系（同步关系）： 进程间相互合作

临界资源
系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。
诸进程间应采取互斥方式，实现对这种资源的共享。

数据不一致例子：生产者－消费者问题

共享变量
缓冲池buffer： 用数组来表示具有n个缓冲区的缓冲池
输入指针in： 指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1，初值为0
输出指针out： 指示下一个可获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1，初值为0
整型变量count： 初值为0，表示缓冲区中的产品个数

临界区：

同步机制应遵循的准则：
1）空闲让进：当无进程处于临界区，应允许一个请求进入临界区的进程立即进入自己的临界区；
2）忙则等待：已有进程处于其临界区，其它试图进入临界区的进程必须等待；
3）有限等待：等待进入临界区的进程不能"死等"；
4）让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）

进程同步机制
1）软件同步进制：使用编程方法解决临界区问题 有难度、具有局限性，现在很少采用
2）硬件同步机制：使用特殊的硬件指令，可有效实现进程互斥
3）信号量机制：一种有效的进程同步机制，已被广泛应用
4）管程机制：新的进程同步机制

软件同步机制——Perterson解决方案

硬件同步机制

1）关中断：
进入锁测试之前关闭中断，完成锁测试并上锁之后才打开中断
可有效保证互斥，但存在许多缺点
2）Test-and-Set指令（实现互斥）

3）Swap指令

4）缺点：不符合“让权等待”原则，浪费CPU时间；很难解决复杂的同步问题

信号量机制

信号量机制：
1965年，由荷兰学者迪科斯彻Dijkstra提出（P、V分别代表荷兰语的Proberen (test)和Verhogen (increment)），是一种卓有成效的进程同步机制。
类型：整型信号量；记录型信号量；AND型信号量；信号量集

整型信号量：
信号量S-整型变量
提供两个不可分割的[原子操作]访问信号量

Wait(s)又称为P(S) ；Signal(s)又称为V(S)
缺点：进程忙等

记录型信号量
每个信号量S除一个整数值S.value外，还有一个进程等待队列S.list，存放阻塞在该信号量的各个进程PCB
> 信号量只能通过初始化和两个标准的原语PV来访问－－作为OS核心代码执行，不受进程调度的打断
>?初始化指定一个非负整数值，表示空闲资源总数（又称为"资源信号量"）－－若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数

AND型信号量
AND型信号量同步的基本思想：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。
对若干个临界资源的分配，采用原子操作。
在wait(S)操作中增加了一个“AND”条件，故称之为AND同步，或同时wait(S)操作，即Swait(Simultaneous wait)。

信号量集
在记录型信号量中，wait或signal仅能对某类临界资源进行一个单位的申请和释放，当需要对N个单位进行操作时，需要N次wait/signal操作，效率低下
扩充AND信号量：对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放
>?进程对信号量Si的测试值是该资源的分配下限值ti，即要求Si≥ti，否则不予分配。一旦允许分配，进程对该资源的需求值为di，即表示资源占用量，进行Si= Si-di操作
> Swait(S1，t1，d1，…，Sn，tn，dn)
>?Ssignal(S1，d1，…，Sn，dn)
应用：
1）利用信号量实现进程互斥：设置互斥信号量

2）利用信号量实现前趋关系

3）利用信号量实现进程同步：设置同步信号量

管程机制

信号量：分散式? ? 管程：集中式
信号量机制的问题：需要程序员实现，编程困难； 维护困难； 容易出错? （wait/signal位置错 ? wait/signal不配对）
解决方法：由编程语言解决同步互斥问题；管程（1970s, Hoare和Hansen）

管程
定义：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据

功能：
互斥：
>?管程中的变量只能被管程中的操作访问
>?任何时候只有一个进程在管程中操作
>?类似临界区
>?由编译器完成
同步：
条件变量；唤醒和阻塞操作

条件变量：
condition x, y;
条件变量的操作：阻塞操作：wait 唤醒操作：signal
x.wait(): 进程阻塞直到另外一个进程调用x.signal()
x.signal()：唤醒另外一个进程
条件变量问题：
> 管程内可能存在不止1个进程。 例如：进程P调用signal操作唤醒进程Q后。
> 存在的可能处理方式：
????????P等待，直到Q离开管程或等待另一条件（Hoare）。
????????Q等待，直到P离开管程或等待另一条件（Hansen）。

经典进程的同步问题

生产者-消费者问题

生产者-消费者问题是相互合作进程关系的一种抽象
利用记录型信号量实现：
> 假定，在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，可利用互斥信号量mutex使诸进程实现对缓冲池的互斥使用；
?> 利用资源信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。
?> 又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息
其它解决方案：AND信号集、管程
描述：生产者（M个）：生产产品，并放入缓冲区
??????????消费者（N个）：从缓冲区取产品消费

互斥分析：

同步分析：

问题：如何实现生产者和消费者之间的同步和互斥？

同步信号量定义：
共享数据
semaphore *full, *empty, *m; ?//full:满缓冲区数量 ? empty：空缓冲区数量
初始化:
full->value = 0;?? ? empty->vaule = N;?? ?m->vaule = 1；

解决方法：

利用AND信号量解决

利用管程解决：

哲学家进餐问题

?问题描述：五个哲学家的生活方式：交替思考和进餐 共用一张圆桌，分别坐在五张椅子上 在圆桌上有五个碗和五支筷子 平时哲学家思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在拿到两支筷子时才能进餐 进餐毕，放下筷子又继续思考 ?
解决方案：记录型信号量； AND信号量集、管程。

利用记录型信号量解决

存在问题：可能引起死锁，如五个哲学家同时饥饿而各自拿起左筷子时，会使信号量chopstick均为0；因此他们试图去拿右筷子时，无法拿到而无限期等待。
解决方法：1）最多允许4个哲学家同时坐在桌子周围；2）仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子。3） 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之

利用AND信号量机制解决

利用管程解决

读者-写者问题

?有两组并发进程：读者和写者，共享一组数据区。
要求：允许多个读者同时执行读操作；
???????????不允许读者、写者同时操作；
? ? ? ? ? ?不允许多个写者同时操作。
分类：读者优先(第一类读者写者问题) 写者优先(第二类读者写者问题)
解决方案：记录型信号量； 信号量集
读者优先
读者来：有读者或无读写者则读，有写者无读者则新读者等
写者来：有读者或写者则等待，否则可写

写者优先
问题描述：
多个读者可以同时进行读
写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）
如何用PV操作实现？
> P.V操作必须成对出现，有一个P操作就一定有一个V操作
>?当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现
>?如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前
>?而两个V操作无关紧要

信号量的使用：
信号量必须置一次且只能置一次初值，初值不能为负数
?除了初始化，只能通过执行P、V操作来访问信号量
使用中存在的问题：死锁 ；饥饿
死锁 ：两个或多个进程无限期地等待一个事件的发生，而该事件正是由其中的一个等待进程引起的
饥饿 ：无限期地阻塞，进程可能永远无法从它等待的信号量队列中移去（只涉及一个进程）。

信号量的物理含义：
S>0表示有S个资源可用；
S=0表示无资源可用；
S<0则| S |表示S等待队列中的进程个数。
P(S):表示申请一个资源;
V(S)表示释放一个资源。信号量的初值应该大于等于0

信号量同步的缺点：
同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）
不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；
易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；
正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；

Linux进程同步机制

Linux并发的主要来源： 中断处理、内核态抢占、多处理器的并发。

同步方法：
原子操作
自旋锁（spin lock）：?不会引起调用者阻塞（在多处理机系统中提供对共享数据的保护）
信号量（Semaphore）
互斥锁（Mutex）
禁止中断（单处理器不可抢占系统）

本篇介绍了进程同步的基本概念、临界区问题、常用的进程同步机制和经典的进程同步问题。进程同步机制中分别介绍了软件同步、硬件同步、信号量和管程等4种机制。