# 背景

对共享数据的并发访问可能导致数据的不一致性
要保持数据的一致性，就需要一种保证并发进程的正确执行顺序的机制
解决有界缓冲区问题的共享内存方法在类数据 count 上存在竞争条件
竞争条件
若干个并发的进程 (线程) 都可以访问和操纵同一个共享数据，从而执行结果就取决于并发进程对这个数据的访问次序.
为了保证数据的一致性，需要有同步机制来保证多个进程对共享数据的互斥访问.
进程类型
协作进程
独立进程
进程间资源访问冲突
共享变量的修改冲突
操作顺序冲突
进程间的制约关系
间接制约：有些资源需要互斥使用，因此各进程进行竞争－－独占分配到的部分或全部共享资源，进程的这种关系为进程的互斥
直接制约：进行协作－－具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪态。进程的这种关系为进程的同步（等待来自其他进程的信息，“同步”)

# 进程间的交互关系

互斥，指多个进程不能同时使用同一个资源；
同步，进程之间的协作；
死锁，指多个进程互不相让，都得不到足够的资源；
饥饿，指一个进程一直得不到资源（其他进程可能轮流占用资源）

# 临界区问题

# 临界区的访问过程

因此，对于临界资源，多个进程必须互斥的对它进行访问。
临界区 (critical section)：进程中访问临界资源的一段代码。
实现进程对临界资源的互斥访问 — 各进程互斥的进入自己的临界区
假定一个系统有 n 个进程 {P0,P1,……,Pn-1}, 每个进程有一个代码段称为临界区，在该区中进程可能修改共享变量 \ 更新一个表 \ 写一个文件等。当一个进程在临界区中执行时，其他进程都不能进入临界区
临界区的执行在时间上是互斥的，进程必须请求允许进入临界区
进入区 (entry section)：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，通常设置相应 “正在访问临界区” 标志。
退出区 (exit section)：用于将 "正在访问临界区" 标志清除。
剩余区 (remainder section)：代码中的其余部分。

# 临界区的解决办法

互斥 Mutual Exclusion。假定进程 Pi 在其临界区内执行，其他任何进程将被排斥在自己的临界区之外
有空让进 Progress。临界区虽没有进程执行，但有些进程需要进入临界区，不能无限期地延长下一个要进入临界区进程的等待时间
有限等待 Bounded Waiting。在一个进程提出进入临界区的请求和该请求得到答复的时间内，其他进程进入临界区的次数必须是有限的

# 同步机制应遵循的准则

空闲则入：其他进程均不处于临界区；
忙则等待：已有进程处于其临界区；
有限等待：等待进入临界区的进程不能 "死等"；
让权等待：不能进入临界区的进程，应释放 CPU（如转换到阻塞状态）

# 同步硬件

Uniprocessors–could disable interrupts 单处理器能够禁止中断
Currently running code would execute without preemption 当前执行的指令不被抢占
Generally too inefficient on multiprocessor systems 但对多处理器不适用
Many systems provide hardware support for critical section code 许多系统对临界区代码提供硬件支持
特殊硬件指令－－原子地执行，因而保证读写操作不被中断:
Test-and-Set (TS) 指令
SWAP 指令

# 硬件方法的优点

适用于任意数目的进程，在单处理器或多处理器上
简单，容易验证其正确性
可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量

# 硬件方法的缺点

等待要耗费 CPU 时间，不能实现 "让权等待"
可能" 饥饿 "：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上

# 信号量 Semaphore

前面的互斥算法存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS 可从进程管理者的角度来处理互斥的问题，信号量就是 OS 提供的管理公有资源的有效手段.
1965 年，由荷兰学者 Dijkstra 提出（所以 P、V 分别是荷兰语的 test (proberen) 和 increment (verhogen)），是一种卓有成效的进程同步机制。
用于保证多个进程在执行次序上的协调关系的相应机制称为进程同步机制。
信号量代表可用资源实体的数量。
信号量 S – 整型变量，代表可用资源实体的数量
除了初始化之外，仅能通过两个不可分割的 [原子] 操作访问
存在忙等 —— 自旋锁：进程在等待锁时自旋

pandv

P (S):  
while S<= 0 do no-op;		
    S--;	  
V(S): 
    S++;

一种不需要忙等待的同步工具

不需要盲等

P (S): 
    S--; 
    if  S< 0 do block; 		
V(S): 
    S++;
    if S<=0 then wakeup;

S 是与临界区内所使用的公用资源有关的信号量
在信号量经典定义下，信号量 S 的值不可能为负
S≥0 可供并发进程使用的资源数
S<0 其绝对值就是正在等待进入临界区的进程数
信号量只能通过初始化和两个标准的原语来访问－－作为 OS 核心代码执行，不受进程调度的打断
初始化指定一个非负整数值，表示空闲资源总数

# 利用信号量实现互斥

为临界资源设置一个互斥信号量，其初值为 1；
Semaphore S; // initialized to 1

在每个进程中将临界区代码置于 P (S) 和 V (S) 原语之间
P (S);
CriticalSection()
V(S);

# 利用信号量来描述互斥关系

前趋关系：并发执行的进程 P1 和 P2 中，分别有代码 C1 和 C2，要求 C1 在 C2 开始前完成；
为每个前趋关系设置一个同步信号量 S12，其初值为 0
方法：前趋图
若图中存在结点 S1 指向结点 S2 的有向边，表示进程 P1 中的程序段 S1 应该先执行，而进程 P2 中的程序段 S2 后执行。设置一个信号量 s, 初值为 0，将 V (s) 放在 S1 后面，而在 S2 前面先执行 P (s)。
进程 P1 的语句序列为：S1;V (s)
进程 P2 的语句序列为：P (s);S2

# Semaphore 机制

同步、互斥的约束条件
临界资源的抽象
初始条件
正确的 P-V 操作

# 经典同步问题

# 哲学家进餐问题

# 问题描述

（由 Dijkstra 首先提出并解决）5 个哲学家围绕一张圆桌而坐，桌子上放着 5 支筷子，每两个哲学家之间放一支；哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子

# 解决方法

思考；
取 chopStick [i];
取 chopStick [(i+1) mod 5]；
进食；
放 chopStick [i];
放 chopStick [(i+1) mod 5]；

哲学家进餐

while (true) {
	// get left chopstick
	chopStick[i].P();
	// get right chopstick
	chopStick[(i + 1) % 5].P();

	// eat for awhile
	
	//return left chopstick
	 chopStick[i].V();
	// return right chopstick
	 chopStick[(i + 1) % 5].V();

	// think for awhile
}

可能会出现死锁，五个哲学家每人拿起了他左边的筷子

最多允许四个哲学家同时就坐
同时拿起两根筷子
非对称解决

# 生产者－消费者问题 (the producer-consumer problem)

# 问题描述

若干进程通过有限的共享缓冲区交换数据。其中，"生产者" 进程不断写入，而 "消费者" 进程不断读出；共享缓冲区共有 N 个；任何时刻只能有一个进程可对共享缓冲区进行操作

# 解决方法

采用信号量机制：
full 是 "满" 数目，初值为 0，empty 是 "空" 数目，初值为 N。实际上，full + empty == N
mutex 用于访问缓冲区时的互斥，初值是 1
每个进程中各个 P 操作的次序是重要的：先检查资源数目，再检查是否互斥――否则可能死锁

# 读者－写者问题 (the readers-writers problem)

# 问题描述

对共享资源的读写操作，任一时刻 “写者” 最多只允许一个，而 “读者” 则允许多个
“读－写” 互斥，
“写－写” 互斥，
"读－读" 允许

# 解决方法

采用信号量机制：
信号量 Wmutex 表示 "允许写"，初值是 1。
公共变量 Rcount 表示 “正在读” 的进程数，初值是 0；
信号量 Rmutex 表示对 Rcount 的互斥操作，初值是 1。

读写问题

reader(){
	while(true){
		P(Rmutex);
		if(Rcount==0)
			P(mutex);//第一个读者，阻止写入
		Rcount++;
		V(Rmutex);//允许其他读者读
		read;
		P(Rmutex);//保护Rcount
		Rcount--;
		if(Rcount==0)
			V(mutex);//允许写入
		V(Rmutex);//允许其他读者读
	}		
}
writer(){
	P(mutex);//对写进行控制
	write;
	V(mutex);
}

# pv 操作讨论

信号量的物理含义：
S>0 表示有 S 个资源可用
S=0 表示无资源可用
S<0 则 | S | 表示 S 等待队列中的进程个数
P (S): 表示申请一个资源
V (S): 表示释放一个资源。
信号量的初值应该大于等于 0
PV 操作必须成对出现，有一个 P 操作就一定有一个 V 操作
当为互斥操作时，它们处于同一进程
当为同步操作时，则不在同一进程中出现
对于前后相连的两个 P (S1) 和 P (S2) ，顺序是至关重要的：同步 P 操作应该放在互斥 P 操作前，而两个 V 操作顺序则无关紧要

# 背景

# 进程间的交互关系

# 临界区问题

# 临界区的访问过程

# 临界区的解决办法

# 同步机制应遵循的准则

# 同步硬件

# 硬件方法的优点

# 硬件方法的缺点

# 信号量 Semaphore

# 利用信号量实现互斥

# 利用信号量来描述互斥关系

# Semaphore 机制

# 经典同步问题

# 哲学家进餐问题

# 问题描述

# 解决方法

# 生产者－消费者问题 (the producer-consumer problem)

# 问题描述

# 解决方法

# 读者－写者问题 (the readers-writers problem)

# 问题描述

# 解决方法

# pv 操作讨论

linux基础使用

死锁