进程同步

进程同步的基本概念
实现临界区互斥的基本方法
进程互斥：锁
信号量机制
经典同步问题
管程

进程同步的基本概念

进程的异步性：各并发执行的进程以各自独立的、不可预知的速度向前推进。

例子：进程通信——管道通信

读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中，又必须按照“写数据→读数据”的顺序来执行的。

如何解决这种异步问题，就是“进程同步”所讨论的内容。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待;
有限等待。对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）；
让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

do{
	entry section;//进入区
	critical section; //临界区
	exit section;//退出区
	remainder section; //剩余区

}while(true)

实现临界区互斥的基本方法

进程互斥：锁

解决临界区最简单的工具就是互斥锁（mutex lock）。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁。

每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用acqiure()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

acquire()
	while(!available)
	;
	//忙等待
	available = false;
	//获得锁
}
release(){
	available = true;
	//释放锁
}

acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。

需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock），如TSL指令、swap指令、单标志法。

信号量机制

复习回顾+思考：之前学习的这些进程互斥的解决方案分别存在哪些问题？

进程互斥的四种软件实现方式（单标志法、双标志先检查、双标志后检查、Peterson算法）

进程互斥的三种硬件实现方式（中断屏蔽方法、TS/TSL指令、Swap/XCHG指令）

1.在双标志先检查法中，进入区的“检查”、“上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题；

2.所有的解决方案都无法实现“让权等待”

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法一一信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。

一对原语：wait(S)原语和 signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为 wait 和 signal，括号里的信号量S其实就是函数调用时传入的一个参数。

wait、signal原语常简称为P、V操作（来自荷兰语 proberen 和verhogen）。因此，做题的时候常把 wait(S)、signal(S)两个操作分别写为 P(S)、V(S)

信号量机制实现进程同步

进程同步：要让各并发进程按要求有序地推进。

比如，P1、P2 并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。

若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。

这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。

P1(){
	代码1;
	代码2；
	代码3；
}

P2(){
	代码4；
	代码5；
	代码6;
}

经典同步问题

生产者消费者问题

semaphore mutex = 1;
//互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;
//同步信号量，表示空闲缓冲区的数量
semaphore full = 0;
//同步信号量，表示产品的数量，也即非空缓冲区的数量

多生产者多消费者问题

原因在于：本题中的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此在任何时刻最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区.

如果盘子的容量为2的话，结果会是什么样？？？

父亲 P(plate)，可以访问盘子→母亲 P(plate)，可以访问盘子→父亲在往盘子里放苹果，同时母亲也可以往盘子里放橘子。于是就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。

因此，如果缓冲区大小大于1，就必须专门设置一个互斥信号量mutex来保证互斥访问缓冲区。

总结：在生产者-消费者问题中，如果缓冲区大小为1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。

建议：在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。

但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起“死锁”。

PV操作题目的解题思路：

关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

吸烟者问题

吸烟者问题可以为我们解决“可以生产多个产品的单生产者”问题提供一个思路。

值得吸取的精华是：“轮流让各个吸烟者吸烟”必然需要“轮流的在桌上放上组合一、二、三”，注意体会我们是如何用一个整型变量i实现这个“轮流”过程的。

如果题目改为“每次随机地让一个吸烟者吸烟”，我们有应该如何用代码写出这个逻辑呢？

若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个V操作应该放在各自对应的 “事件”发生之后的位置。

读者写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。

1.关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。 2.整理思路。根据各进程的操作流程确定P、V操作的大致顺序 3.设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

两类进程：写进程、读进程

互斥关系：写进程一写进程、写进程一读进程。读进程与读进程不存在互斥问题。