同步与互斥——相互合作，相互制约

选择题：互斥机制，信号量解决互斥同步

大题：PV操作处理进程的同步与互斥

目的：解决临界区资源使用问题

一、临界资源

一次仅允许一个进程使用的资源

二、同步与互斥

同步：AB相互合作，A放B取，B取A放

互斥：AB相互制约，A用B等，B用A等

三、互斥方法

1、单标志法

（违背空闲让进）

P1                  P2
while(turn!=0);     while(turn!=1);
//临界区。           //临界区
turn = 1;          turn = 1;
//剩余区            //剩余区

2、双标志法

同时进入进程时会同时进入临界区，违背忙则等待

Pi                    Pj
while(flag[j]);       while(flag[i]);
flag[i] = TRUE;        flag[j] = TRUE;
//临界区                //临界区
flag[i] = FALSE;        flag[j] = FALSE;
//剩余区                //剩余区

3、双标志法后检查

Pi：                    Pj:
flag[i] = TRUE;        flag[j] = TRUE;
while(flag[j]);       while(flag[i]);
//临界区                //临界区
flag[i] = FALSE;        flag[j] = FALSE;
//剩余区                //剩余区

同时进入时，都为TRUE，都无法进入，产生饥饿现象。

违背"有限等待"，"空闲让进"

4、Peterson's Algorithm

Pj若在临界区内，则此时flag[i] = TRUE，turn = j 满足Pi的while循环条件会一直等到Pj推出。

若同时进入，也会违背"空闲让进"

Pi                        Pj
flag[i] = TRUE; turn = j;       flag[j] = TRUE; turn = i;
while(flag[j]&&turn == j);      while(flag[i] && turn == i);
//临界区                         //临界区
flag[i] = FALSE;                flag[j] = FALSE;
//剩余区                         //剩余区

四、经典同步问题

1、生产者-消费者问题

（1）只有一个放，只有一个取；放时不能取，取时不能放。

（2）不满才能放，空了不能取

总结：一放一取，满了不放，空了不取

 信号量：full = 0，empty = n，mutex = 1（控制互斥访问缓冲池）

2、读者-写者问题

（1）可以一起读

（2）只能一个写

（3）写时不读不写

（4）写操作前，所有进程必须退出

总结：一起读，写时不读写，操作全退出

信号量：count = 0（读者数量） ， mutex =  1（更新count的互斥）， rw = 1（读写互斥），w  = 1（写优先）；

3、 哲学家进餐问题

（1）筷子一根根拿，只有两根筷子才能进餐

（2）中间筷子互斥

（3）左右都能取，我才取

总结：筷子逐根取，两根才能动，中间你取我不取，都拿我才拿

信号量： chopstick[n] = {1,1,1,……,1}，mutex = 1；

//拿右边的筷子P(chopsticks[(i + 1) % 5])，左边的筷子P(chopsticks[i])