进程同步
进程同步的基本概念
两种形式的制约关系：
（1）间接相互制约关系。同处于一个系统中的进程，通常都共享着某种系统资源，如共享 CPU、共享 I/O 设备等。所谓间接相互制约即源于这种资源共享 。
（2）直接相互制约关系。这种制约主要源于进程间的合作 。
临界资源：
生产者-消费者(producer-consumer)问题是一个著名的进程同步问题
程序的执行失去了再现性。为了预防产生这种错误，解决此问题的关键是应把变量counter作为临界资源处理，亦即，令生产者进程和消费者进程互斥地访问变量counter。
临界区：
把在每个进程中访问临界资源的那段代码称为临界区(critical section)。显然 ，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问
进入区和退出区：
必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区(entry section)。相应地，在临界区后面也要加上一段称为退出区(exit section)的代码，用于将临界区正被访问的标志恢复为未被访问的标志。
同步机制都应遵循下述四条准则：
- 空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
- 忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
- 有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。
- 让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。
硬件同步机制
在对临界区进行管理时，可以将标志看作一个锁，“锁开”进入，“锁关”等待，初始时锁打开，每个要进入临界区的进程必须先对锁进行测试，当锁未开是，则必须等待，直至锁被打开。反之，当锁是打开时，则应立即把其锁上，阻止其他进程进入临界区。（测试和关锁的操作必须是连续的，不允许分开进行。）
1.关中断
进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。
关中断的缺点：（1）滥用关中断权力可能会导致严重后果。（2）关中断时间过长会影响系统效率。（3）关中断不适用多CPU系统。
2.利用Test-and-Set指令实现互斥
3.利用Swap指令实现进程互斥
信号量机制
1965年，荷兰学者Dijkstra提出的信号量(Semaphores)机制是一种卓有成效的进程同步工具。
1.整形信号量：
最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S)来访问。很长时间以来，这两个操作一直被分别称为P、V操作。
wait(S): while S<=0 do no-op;S:=S-1;
signal(S):S:=S+1;
wait(S)和signal(S)是两个原子操作，因此，它们在执行时是不可中断的。
存在的问题 ：整型信号量机制中的wait操作，只要是信号量S≤0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。
在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。
为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针L，用于链接上述的所有等待进程。
2.记录型信号量：
记录型信号量是由于它采用了记录型的数据结构而得名；当 S.value<0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L 中。该机制遵循了“让权等待”准则。此时 S.value 的绝对值表示在该信号量链表中已阻塞进程的数目
若加1后仍是S.value≤0，则表示在该信号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒
注意边界条件，小于等于0，意思就是只要之前有等待的进程，加一后可以满足一个等待进程的资源请求，所以就唤醒一个等待进程。
如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。
新的问题：在有些应用场合，是一个进程需要先获得两个或更多的共享资源后方能执行其任务。
3.AND型信号量：
基本思想：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在 wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作(只是wait，没有signal)
在记录型信号量机制中，wait(S)或signal(S)操作仅能对信号量施以加1或减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要 N 个某类临界资源时，便要进行N次wait(S)操作，显然这是低效的。此外，在有些情况下，当资源数量低于某一下限值时，便不予以分配。因而，在每次分配之前，都必须测试该资源的数量，看其是否大于其下限值。基于上述两点，可以对AND信号量机制加以扩充，形成一般化的“信号量集”机制。
一次分配多个资源，且考虑资源下限
4.信号量集：
(1) Swait(S，d，d)。此时在信号量集中只有一个信号量 S，但允许它每次申请 d 个资源，当现有资源数少于d时，不予分配。
(2) Swait(S，1，1)。此时的信号量集已蜕化为一般的记录型信号量(S>1时)或互斥信号量(S=1时)。
(3) Swait(S，1，0)。这是一种很特殊且很有用的信号量操作。当 S≥1 时，允许多个进程进入某特定区；当 S 变为 0 后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。
信号量的应用
- 利用信号量实现进程互斥。
- 利用信号量实现前趋关系。
管程机制
管程是代表共享资源的数据结构以及由对该共享数据结构实时操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块。
管程由四部分组成：
- 管程名称。
- 局部于管程的共享数据结构说明。
- 对该数据结构进行操作的一组过程。
- 对局部于管程的共享数据设置初始值的语句。
管程与进程的异同点：
- 二者都定义了数据结构，但进程定义的是私有PCB，管程是公共数据结构：如消息队列等。
- 二者都有对各自数据结构上的操作，进程是由顺序程序执行有关操作，管程主要进行同步和初始化操作。
- 进程目的在于实现OS并发性，管程是为了解决共享资源互斥使用问题。
- 管程为被动工作方式，进程为主动工作方式，进程通过调用管程中的过程对共享数据结构实行操作。
- 进程能够并发执行，管程不能与其调用者并发。
- 进程具有动态性（由“创建”而生，“撤销”而亡），管程是OS中的一个资源管理模块，供进程调用。
经典进程同步问题
1.生产者-消费者问题
利用记录型信号量解决生产者—消费者问题
首先，在每个程序中用于实现互斥的 wait(mutex)和signal(mutex)必须成对地出现；
其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中 。
最后，在每个程序中的多个 wait 操作顺序不能颠倒，应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。
对于生产者—消费者问题，也可利用 AND 信号量来解决，即用 Swait(empty，mutex)来代替wait(empty)和wait(mutex)；
2.哲学家进餐问题
当哲学家饥饿时，总是先去拿他左边的筷子，即执行wait(chopstick[i])； 成功后，再去拿他右边的筷子，即执行wait(chopstick[(i+1)mod 5])；又成功后便可进餐。进餐完毕，又先放下他左边的筷子，然后再放右边的筷子。
存在的问题
虽然上述解法可保证不会有两个相邻的哲学家同时进餐，但有可能引起死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0； 当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待
各种解决方案
(1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。
(2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
(3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。
故用AND信号量机制可获得最简洁的解法。
3.读者-写者问题
问题描述
所谓“读者—写者问题(Reader-Writer Problem)”是指保证一个 Writer 进程必须与其他进程互斥地访问共享对象的同步问题。读者—写者问题常被用来测试新同步原语。
解决
为实现 Reader 与 Writer 进程间在读或写时的互斥而设置了一个互斥信号量 Wmutex。另外，再设置一个整型变量 Readcount 表示正在读的进程数目。由于只要有一个 Reader 进程在读，便不允许 Writer 进程去写。因此，仅当 Readcount=0，表示尚无 Reader 进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若 Wait(Wmutex)操作成功，Reader进程便可去读，相应地，做 Readcount+1 操作。同理，仅当 Reader 进程在执行了 Readcount 减 1操作后其值为0时，才须执行signal(Wmutex)操作，以 便 让 Writer进程写。又因为Readcount是一个可被多个 Reader 进程访问的临界资源，因此，也应该为它设置一个互斥信号量rmutex。
wait(rmutex);
if readcount=0 then wait(wmutex);Readcount:=Readcount+1;
signal(rmutex);
perform read;
wait(rmutex);
readcount:=readcount-1;
if readcount=0 then signal(wmutex);
signal(rmutex);
这里的读者—写者问题与前面的略有不同，它增加了一个限制，即最多只允许RN个读者同时读。为此，又引入了一个信号量 L，并赋予其初值为 RN，通过执行 wait(L，1，1)操作，来控制读者的数目。每当有一个读者进入时，就要先执行 wait(L，1，1)操作，使 L的值减1。当有RN个读者进入读后，L便减为0，第RN+1个读者要进入读时，必然会因wait(L，1，1)操作失败而阻塞