背景
多个进程需要合作完成一个任务，在进程合作过程中，除了并行执行之外，还经常存在两个进程需要共享信息相互等待的协作过程。为了满足上述要求，因此进程之间需要同步。如生产者消费者问题就是一个典型的需要同步的问题。
互斥与临界区问题
-
竞争条件：多个进程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关。
如何尝试避免竞争条件？资源加锁。
临界资源：把一次仅允许一个进程使用的资源称为临界资源。如只能独享的物理设备(打印机)、共享变量等等。
-
临界区：在每个进程中，访问临界资源的那段程序称为临界区。
如何进入临界区：互斥进入（这是临界区进入的基本原则和正确性保证），还需要考虑有空闲时进入，以及从请求进入到被允许进不能无限等待
临界区问题的解决
即如何进入和退出临界区以达到进程互斥和同步的目的
-
一般软件法
-
轮换法
满足互斥但是不满足空闲进入，即A进程离开临界区后即使B没有到达临界区也不能再次进入临界区。必须轮流进入
-
标记法
进入临界区就做一个标记，后者根据标记决定是否进入临界区。但是由于时间片的切换，有可能导致两者同时标记了进入临界区但是没能成功进入，这就会导致无限等待。
-
Peterson算法
结合了标记和轮转两种方法，每个进程包含一个flag标记，此外还含有轮转标记。
- 满足互斥进入
以2个进程为例：如果不互斥，需要满足flag[0] == true && flag[1] == true && turn == 0 && turn == 1矛盾。
- 满足有空进入
如果P1不在临界区，那么turn==0 或者flag[1] = false因此P0可以进入
- 满足有限等待。
优先级反转
当进程P1(L)处于临界区运行，若此时P1(L)尚未离开它的临界区而被切换到P0(H)运行。若运行到它的“进入区”处于“忙等待”状态时恰巧被切换，则其处于“就绪态”。但由于P0(H)优先级高，则会优先被调度，因此它将永远会“忙等待”。
-
面包店算法
仍然是标记和轮转的结合。该算法的基本思想源于顾客在面包店中购买面包时的排队原理. 顾客在进入面包店前, 首先抓一个号, 然后按照号码由小到大的次序依次进入面包店购买面包. 这里, 面包店发放的号码是由小到大的, 但是两个或两个以上的顾客却有可能得到相同的号码(使所抓号码不同需要互斥), 如果多个顾客抓到相同的号码, 则规定按照顾客名字的字典次序进行排序, 这里假定顾客是没有重名的. 在计算机系统中, 顾客就相当于进程, 每个进程有一个唯一的标识, 我们用P的下面加一个下标来表示. 例如: 对于 Pi和Pj, 如果有i
-
进程同步
多个进程按照指定的协作顺序执行
-
使用信号量实现进程同步
-
生产者消费者问题
需要3个信号量协作完成任务：互斥信号量、空闲资源信号量、满的资源信号量
-
哲学家进餐问题
问题描述：有五位哲学家围坐在一圆桌旁，桌*有一盘面条，每人面前有一只空盘子，每两人之间放一根筷子，每位哲学家相互不进行任何交流，只独自思考，若感到饥饿就拿起二根筷子吃面条，为吃到面条，每位哲学家必须获得二根筷子，且每人只能从自己左边或右边拿筷子。
直观解法
semaphore chopstick[5];
for(i=0;i<5;i++)chopstick[i]=1;
Philosopher-i( ) { /* i=0,1,2,3,4 共5个函数 */
while (True) {
chopstick[i].p(); /* 取左手边筷子 */
chopstick[(i+1)%5].p(); /* 取右手边筷子 */
eating(); /* 用餐 */
chopstick[i].v(); /* 放下左手边筷子 */
chopstick[(i+1)%5].v(); /* 放下右手边筷子 */
thinking(); /* 思考 */
}
}
但是上述情况容易出现死锁例如所有哲学家同时拿其左边的筷子或者同时拿到其右边的筷子，那么谁都不能继续吃而且停留在这里继续等待。那么如何避免死锁：可以至多允许四个哲学家吃，或者奇数哲学家取左手，偶数取右手，或者一个哲学家必须两只筷子都拿到手才取否则一个也不取。采用第一种方法，可以在开始和结束添加一个数值为4的允许吃的信号量。
-