进程的同步和互斥
由于进程的异步性，在争用资源时，常会出现以下的问题：
系统混乱、数据处理的不可再现性。
为了使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性，必须提供进程同步机制。
进程的相互关系主要分为如下三种形式：
① 互斥：竞争关系
② 同步：协作关系
③ 通信：信息交流
竞争条件
分析两个进程共用同一表格的情况：假定进程Pa负责为用户作业分配打印机，进程Pb负责释放打印机。系统中设立一个打印机分配表，由各个进程共用。
分配表中相关信息项的值是与两个进程运行的时间顺序直接相关。
两个或多个进程同时访问和操纵相同的数据时，最后的执行结果取决于进程运行的精确时序，这种情况称做竞争条件（Race Condition）
随着内核数目的增加，并行性增加了，于是竞争条件也变得更常见。
为保障执行结果的唯一性，必须采取另外的措施。
临界资源和临界区
1．临界资源和临界区
一次仅允许一个进程使用的资源称为临界资源（Critical Resource）。
如：进程Ａ、Ｂ共享一台打印机，若让它们交替使用, 则得到的结果肯定不是我们希望的。
临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。
并发进程对临界资源的访问必须作某种限制，否则就可能出与时间有关的错误，如：联网售票。
临界区
在每个进程中访问临界资源的那段程序叫做临界区（Critical Section），简称CS区。
各进程要互斥地进入自己的临界区。
【注意】：临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不存在互斥。
例如：有程序段A、B是关于变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。
2．进程进入临界区的一般结构
进程互斥进入临界区都要遵循一种通用模式：
进入前要申请， 获准后方可进入； 执行后要退出 (释放) ， 然后才可以执行其他代码
3．临界区进入准则（安全使用临界资源）
① 单个进入。如果若干进程要求进入空闲的临界区，一次仅允许一个进程进入。（空闲让进）
② 独自占用。任何时候，处于临界区内的进程不可多于一个。 （忙则等待）
③ 尽快退出。进入临界区的进程要在有限时间内退出。 （有限等待）
④ 避免忙等。如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。（让权等待）
进程互斥与同步的概念
1．同步（接力赛、工业生产流水线）
定义 ：逻辑上相关的一组并发进程为完成一项任务，通过协调活动来使用共有资源而产生的执行时序的约束关系。
- 相互合作关系
- 直接相互制约
2．互斥
定义：逻辑上无关的多个进程由于竞争临界资源而发生的相互制约的关系。
它们的运行不具有时间次序的特征：谁先向系统提出申请，谁就先执行
- 相互竞争关系，其资源具有独占型
- 间接相互制约
同步和互斥的实质都是对进程在执行时序上的某种限制 ，广义上，互斥是一种特殊的同步。
进程同步：指多个相关进程在执行次序上协调。用于保证这种关系的相应机制称为进程同步机制。
小练
说明下列活动是属于哪些制约关系？(同步/互斥)
1）若干同学去图书馆借书
这项活动通常可以同步进行，因为多个同学可以同时在图书馆选择和借阅不同的书籍，除非特定书籍的数量有限，此时可能出现互斥关系，即一位同学正在借阅的书籍不能被其他同学同时借阅。但在大多数情况下，这属于同步关系。
2）两队进行篮球比赛
篮球比赛中的两队是在同一时间进行比赛的，他们之间的活动是同步的。但场上的队员之间存在互斥关系，比如同一时刻一个篮球只有一个队员可以控制。
3）流水线生产中的各道工序
流水线上的各道工序通常是设计为连续和同步进行的，每一道工序完成后，产品会移动到下一个工序。这里的制约关系是同步的，因为每个工序都需要前一个工序完成后才能开始。
4）商品生产和社会消费
商品生产和社会消费是相互依赖的活动，它们可以同步进行。生产出的商品需要消费者购买和使用，而消费者的消费需求又促进商品的生产。然而，在某些情况下，如果商品供不应求或者过剩，可能会出现制约（比如生产速度跟不上消费速度，或消费能力不足以吸纳生产出的商品），但这些更多是由市场供需关系决定的，而不是活动本身的制约关系。因此，这通常也属于同步关系。
综上所述，活动的制约关系如下：
1）若干同学去图书馆借书 —— 无特定制约关系。
2）两队进行篮球比赛 —— 同步。
3）流水线生产中的各道工序 —— 互斥。
4）商品生产和社会消费 —— 同步。
实现互斥的方式
从实现机制方面来说，分为：
- 硬件方法
- 软件方法
1．利用硬件方法解决进程互斥问题
（1）禁止中断：进程进入临界区后立即关闭中断，即将离开之前开放中断。
（2）专用机器指令：利用TSL指令解决进程互斥进入临界区问题
2．利用软件方法解决进程互斥问题
为每类临界区设置一把锁（W），该锁有打开和关闭两种状态。
- 关锁原语lock (W):
while (W==1);
W=1;
- 开锁原语unlock (W):
W =0;
A、B两个进程互斥使用一台打印机，W初值为0
3．原语
是机器指令的延伸，往往是为完成某些特定的功能而编制的一段系统程序。原语操作也称做“原子操作”（atomic action），即一个操作中的所有动作要么全做，要么全不做。
执行原语操作时，要屏蔽中断，以保证其操作的不可分割性。
如P、V操作等。
信号量
1965年，荷兰学者E.W.Dijkstra提出。
- 整型信号量 （多用于进程互斥, 忙式等待）
- 结构型信号量（多用于进程同步,让权等待）
- 二值信号量（只有0、1两个值)
现在，信号量机制已广泛应用于单处理机、多处理机及计算机网络中。
1．整型信号量
除初始化外，仅能通过两个标准的原子操作来访问。 两个原子操作为：P操作、 V操作
P操作最初源于荷兰语proberen，表示测试；
V操作源于荷兰语verhogen，表示增加。
有些书上将P操作称做wait或者DOWN操作，将V操作称做signal或者UP操作。
典型的P和V操作的伪代码如下
以上操作均为不可中断的原语操作
利用信号量实现互斥
设置一互斥信号量mutex，初值为1，然后将各进程的CS置于P(mutex)和V(mutex)之间即可。
2．结构型信号量（记录型信号量）
因其采用了结构型的数据结构而得名。
整型信号机制使进程处于“忙式等待”状态，消耗CPU时间。结构型信号量采取“让权等待”策略
没有特殊说明，凡称信号量就指结构型信号量。
结构型信号量一般是由两个成员组成的数据结构。其中一个成员是整型变量，表示该信号量的值；另一个是指向PCB的指针。
P操作的定义如下：
V操作的定义如下：
在具体实现时应注意，P, V操作都应作为一个整体实施，不允许分割或相互穿插执行
设结构型信号量S
物理意义: S.Value的初值为系统中某类资源的总数（资源信号量），为1时即临界资源 （此时的信号量为互斥信号量）
S.Value>0: 某类可用资源的数量。
S.Value<=0: 无资源可用，|S.Value|表示等待队列中的进程数。
P(S)：请求分配一个单位的资源。
V(S)：释放一个单位资源、唤醒等待队列中的进程。
信号量的值与相应资源的使用情况有关
对信号量的操作有如下严格限制：
1. 信号量可以赋初值，且初值为非负数。
2. 信号量的值可以修改，但只能由P和V操作来访问
3．二值信号量
- 结构型信号量的取值可以是正数、0或者负数
- 二值信号量的值只能是0或1
信号量的一般应用
1．用信号量实现进程互斥
利用信号量实现互斥的一般模型是：
使用P, V操作实现互斥时应注意两点：
① 在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现，即先做P，进入临界区；后做V，退出临界区。
② 互斥信号量mutex的初值一般为1。
2．用信号量实现进程简单同步
供者和用者间要交换两个消息：缓冲区空和缓冲区满的状态。
设置两个信号量：
- S1表示缓冲区是否空（0表示不空，1表示空）。
- S2表示缓冲区是否满（0表示不满，1表示满）。
规定S1和S2的初值分别为1和0
用P和V操作实现同步时应注意
① 分析进程间的制约关系，确定信号量种类。
② 信号量的初值与相应资源的数量有关，也与P, V操作在程序代码中出现的位置有关。
③ 同一信号量的P, V操作要“成对”出现，但是，它们分别出现在不同的进程代码中。
希望对你有帮助！加油！
若您认为本文内容有益，请不吝赐予赞同并订阅，以便持续接收有价值的信息。衷心感谢您的关注和支持！
