目录
1 进程同步的基本概念
1.1 进程同步概念的引入
1.1.1 两种形式的制约关系
1.1.2 临界资源
1.2 临界区问题
2 信号量机制
2.1 信号量机制介绍
2.1.1 整型信号量
2.1.2 记录型信号量
2.1.3 AND 型信号量
2.1.4 信号量集
2.2 信号量的应用
3 管程机制
3.1 管程的定义
3.2 管程的特点
3.3 条件变量
4 经典的进程同步问题
5 相关例题
选择题
填空题
简答题
综合题
1 进程同步的基本概念
1.1 进程同步概念的引入
异步环境下的一组并发进程因直接制约而互相发送消息、互相合作、互相等待，使得各进程按一定的速度执行的过程，称为进程同步。
具有同步关系的一组并发进程称为协作进程。
1.1.1 两种形式的制约关系
（1）间接相互制约关系（互斥关系）。
多个程序在并发执行时，由于共享系统资源，如CPU、I/O设备等，这些并发执行的程序之
间会形成相互制约的关系。对于像打印机、磁带机这样的系统资源，必须保证多个进程对其只
能进行互斥访问，由此在这些进程间，形成了源于对该类资源共享的所谓间接相互制约关系，
也可称之为互斥关系。
（2）直接相互制约关系（同步关系）。
某些应用程序为了完成某项任务，会建立两个或多个进程。这些进程会为了完成同一任
务而相互合作。进程间的直接制约关系就是源于它们之间的相互合作，该关系也可称为同步关
系。
1.1.2 临界资源
许多硬件资源如打印机、磁带机等，进程在使用它们时都需要采用互斥方式，这样的资源被称为临界资源（critical resource）。
临界资源既可以是硬件资源，也可以是软件资源，如共享变量、文件等。
1.2 临界区问题
每个进程中访问临界资源的代码称为临界区（critical section）。
若能保证各进程互斥地进入自己的临界区，便可实现各进程对临界资源的互斥访问。
解决临界区问题的同步机制遵循：
（1）空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许1个请求进
入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
（2）忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入
临界区的进程必须等待，以保证对临界资源的互斥访问。
（3）有限等待。对于要求访问临界资源的进程，应保证其在有限时间内能进入自己的临界
区，以免陷入“死等”状态。
（4）让权等待（原则上应遵循，但非必须）。当进程不能进入自己的临界区时，应立即释
放处理机，以免进程陷入“忙等”状态。
2 信号量机制
2.1 信号量机制介绍
2.1.1 整型信号量
整型信号量：用于表示资源数目的整型量S，它仅能通过两个标准的原子操作(atomic operation)来访问，即wait(S)和signal(S)操作。分别称为P操作和V操作。
wait(S)和signal(S)是两个原子操作，因此，它们在执行时是不可中断的。亦即，当一个进程
在修改某信号量时，没有其他进程可同时对该信号量进行修改。此外，在wait(S)操作中，对S值
进行测试和做S:=S-1操作时都不可中断。
整型信号量的wait操作，只要是信号量S<=0，就会不断的测试，让进程处于一种“忙等”的状态，没有遵循让权等待的原则。
把信号量的初值置为1，表示只允许一个进程访问临界资源，此时的信号量就可以转换为互斥信号量，用于完成进程的互斥。
2.1.2 记录型信号量
S.value > 0时， S.value为系统中可用资源的数量；
S.value = 0时，可用资源量正好用完；
S.value < 0时，| S.value |为系统中等待使用该资源的队列长度，即 (在信号量上等待的进程数)。
2.1.3 AND 型信号量
AND型信号量机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部
分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能
为之分配的资源，也不分配给它。
2.1.4 信号量集
在前述记录型信号量机制中，wait(S)或signal(S)操作仅能对信号量施以加1或减1操作，这意
味着每次只能对某类临界资源进行一个单位的申请或释放。
对AND信号量机制加以扩充，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放。
优点：简单、易行且安全
缺点：1.资源被严重浪费，严重的恶化了资源的利用率；2.使进程经常会发生饥饿现象
2.2 信号量的应用
1．利用信号量实现进程互斥
为使多个进程能互斥地访问某临界资源，只须为该资源设置一个互斥型信号量mutex，并设
其初值为1，然后将各进程访问该资源的临界区置于wait(mutex)和signal(mutex)操作之间即可。
这样，每个欲访问该临界资源的进程，在进入临界区之前，都要先对mutex执行wait操作。若该
资源此刻未被访问，则本次wait操作必然成功，进程便可进入自己的临界区，这时若再有其他进
程也欲进入自己的临界区，则由于对mutex执行wait操作定会失败，因而该进程阻塞，从而保证
了该临界资源能被互斥地访问。当访问临界资源的进程退出临界区后，又应对mutex执行signal
操作，以便释放该临界资源。
2．利用信号量实现进程同步
协作进程间除了互斥地访问临界资源外，还需要相互制约和传递信息，以同步它们之间的
运行，利用信号量同样可以达到这一目的。
3 管程机制
3.1 管程的定义
一个管程定义了一个数据结构和能被并发进程 （在该数据结构上）所执行的一组操作，这组操作能同步进程和改变管程中的数据。
3.2 管程的特点
管程是由一个或多个过程、一个初始化序列和局部数据组成的软件模块.
- ·局部数据变量只能被管程的过程访问，任何外部过程都不能访问。
- ·一个进程通过调用管程的一个过程进入管程。
- ·在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程可用。
3.3 条件变量
x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列中，并释放管程，直至x条件发生变化。
x.signal：正在调用管程的进程因为x条件发生了变化（资源使用完，归还），则调用x.signal，重新启动一个因x条件而阻塞或挂起的进程，如果存在多个，则选择其中的一个，如果没有，继续执行原进程，不产生任何唤醒操作。
4 经典的进程同步问题
参考文章：经典的进程同步问题-----生产者-消费者问题详解_进程同步生产者消费者问题-CSDN博客
经典的进程同步问题-----读者-写者问题详解_读者-写者进程同步-CSDN博客
经典的进程同步问题-----哲学家进餐问题详解-CSDN博客
5 相关例题
选择题
填空题
简答题
答：进程进入临界区的调度原则是：①如果有若干进程要求进入空闲的临界区，一次仅允许一个进程进入。②任何时候，处于临界区内的进程不可多于一个。如已有进程进入自己的临界区，则其它所有试图进入临界区的进程必须等待。③进入临界区的进程要在有限时间内退出， 以便其它进程能及时进入自己的临界区。④如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。
答：S＞0时，S表示可使用的资源数；或表示可使用资源的进程数；S＝0时，表示无资源可供使用；或表示不允许进程再进入临界区；
S＜0时，－S表示等待使用资源的进程个数；或表示等待进入临界区的进程个数；
当S＞0时，调用P（S）的进程不会等待；调用V（S）后使可用资源数加1或使可用资 源的进程数加1；
当S＜0时，调用P（S）的进程必须等待；调用V（S）后将释放一个等待使用资源者或 释放一个等待进入临界区者。
答：状态 最大值 最小值运行态 1 1等待态 N-1 0就绪态 N-1 0
答：由于进程运行时会随时被中断（包括时间片到、申请资源等），不仅断点不固定，而且中断多长时间也不固定， 即进程是走走停停且它向前推进的相对速度无法由自身控制。有交往的并发进程可能会同时使用共享资源，如果对这种情况不加控制，由于进程占用处理器的时间、 执行的速度和外界的影响等， 就会引起与时间有关的错误。 只要使若干并发进程的相关临界区互斥执行，就可避免造成这类错误。
答： PV 操作能够实现对临界区的管理要求。它由P 操作原语和 V 操作原语组成，对信号量进行操作，具体定义如下：P （ S ）：①将信号量 S 的值减 1 ，即 S=S-1 ；②如果 S 0 ，则该进程继续执行；否则该进程置为等待状态，排入等待队列。V （ S ）：①将信号量 S 的值加 1 ，即 S=S+1 ；②如果 S>0 ，则该进程继续执行；否则释放队列中第一个等待信号量的进程。
综合题
1、五个哲学家围坐在一个圆桌周围，每个哲学家面前都有一只碗，各碗之间分别有一根筷子。哲学家的生活包括两种活动：即吃面条和思考。当哲学家觉得饿时，他就分两次去取他左边和右边的筷子，每次拿一根（不能强行从邻座手中抢过筷子），如果成功，他就开始吃面条，吃完后把筷子放回原处继续思考。为了保证不产生死锁，最多只允许4个哲学家同时进餐。请用P、V操作，以实现操作过程中的互斥与同步。算法描述如下：
semaphore chopstick [5] = ; //五根筷子互斥信号量
semaphoret count= ; //用于控制就餐人数
cobegin
哲学家进程i：
While (TRUE)
{
Think;
;
;
;
Eat；
;
;
;
}
coend
(1) {1,1,1,1,1};
(2）4;
(3)P(count);
(4)p(chopstick[i]);
(5)p(chopstick[（i+1）mod 5]);
(6)v(chopstick[i]);
(7)v(chopstick[（i+1）mod 5]);
(8)v(count);
2、有个山洞对面有洞口可以穿出，两面都可以入与出，但是每次仅允许一个人出入。描述这个活动，用P/V（或wait/signal）操作约束活动控制。
设互斥信号量mutex;
begin
mutex= ;//设置互斥信号量初始值;
cobegin
左面洞口的人过山洞进程；
begin
人员到左洞口
（1）
穿山洞；
（2）
其他活动
End
右面洞口的人过山洞进程；
begin
人员到右洞口
（3）
穿山洞；
（4）
其他活动
end
coend
end
这两个进程之间是 关系（同步还是互斥）
p(mutex)、v(mutex)、p(mutex)、v(mutex)、互斥
3、某家旅行社门票购买系统支持多个用户同时访问(系统数据库)。当有多个用户查询景区门票时，规定有用户在查询时，其他用户不能订门票；当用户正在进行购买门票时，不可以有其他用户使用数据库。试用P、V原语描述查询者和购票者的同步执行程序。设查询者互斥信号量为Xmutex, 购票者购票互斥信号量为Ymutex,查询者人数为count.
Semaphore Xmutex= , Ymutex= ;
Int count=0;
chaxunzhe()
{
While(true)
{
;
If(count==0) ;
count=count+1;
;
查票；
;
count=count-1;
if(count==0) ;
;
}
}
goupiaozhe()
{
While(true)
{
;
购票；
;
}
}
p(Xmutex)、p(Ymutex)、v(Xmutex)、p(Xmutex)、v(Ymutex)、v(Xmutex)、p(Ymutex)、v(Ymutex)
4、有一个生产者进程和消费者进程，它们共享一个单缓冲区，生产者进程不断地生产产品并将其放入单缓冲区中，消费者进程则负责从单缓冲区中取出每个产品进行消费，请用P、V操作实现生产者进程和消费者进程。
算法描述如下：
semaphore full = ; //满缓冲区个数
semaphore empty= ; //空缓冲区个数
producer() //生产者进程
{
While (TRUE)
{
Produce next product;
;
把生产好的产品放入缓冲区;
;
}
}
Consumer () //消费者进程
{
While (TRUE)
{ ;
从缓冲区中取走产品;
;
consume the product;
}
}
试说明生产者进程和消费者进程是 关系，解释该关系
(1)0;
(2)1;
(3)P(empty)
(4)v(full)
(5)p(full)
(6)v(empty)
(7)同步;
(8) 生产者进程和消费者进程是有时序上制约关系，先生产，后消费，共同完成任务。
