进程同步：
进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好的互相合作，从而使程序的执行具有可再现性。

临界资源：
是在一段时间内只允许一个进程访问的资源。系统中的大多数的物理设备，以及栈、变量、表格，都属于临界资源，这些进程间应采用互斥方式，实现对这些资源的共享。

临界区：
每个进程中访问临界资源的代码称为临界区。
若能保证进程互斥的进入自己的临界区，便可实现进程对临界资源的互斥访问。如果某一时间临界资源未被访问，进程便可进入临界区对该资源进行检查，看是否被访问；如果某一时间该临界资源被访问，该进程不能进入临界区。

while(TRUE)
{
    进入区
    临界区
    退出区
    剩余区
}

同步机制应遵循的规则：
1.空闲让进：
无进程处于临界区时，表名临界资源处于空闲状态，允许一个请求进入临界资源区的进程立即进入自己的临界区。
2.忙则等待：
当有进程进入临界区时，表明资源正在被访问，其他想进入该临界区的资源必须等待，以保证对临界资源的互斥访问。
3.有限等待：
对要求访问资源的进程，应保证在有限的时间内能进入自己的临界区，以避免陷入“死等”状态。
4.让权等待：
当进程不能进入自己的临界区时，应立即释放处理机，以避免进程进入“忙等”状态。

实际上，在对临界区资源进行管理的时候，可以将标志看做一个“锁”，“锁开”进入，“锁关”等待， 起初锁是打开的。每个要进入临界资源的进程必须先对锁进程测试，当锁未开时，则必须等待，直至锁被打开。反之，当锁是打开的，则应立即把锁锁上，以阻止其他进程进入临界区。显然，测试和关锁必须是连续的，不允许分开执行。

解决临界区的问题：
1.关中断是最简单实现互斥的方法。在进入锁测试之前关闭中断，直到完成锁测试并上锁后才能打开中断。
因此，进程在临界区执行期间，计算机系统不断相应中断，从而不会引发调度，也就不会发生进程或线程切换。保证了对锁测试的和关锁测试的完整性和连续性。

缺点：
滥用关中断权利可能导致严重后果；
关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力；
不适用于多处理器系统，因为在一个处理器上关中断并不能防止进程在其他处理器上执行相同的代码。

经典进程同步问题

1.生产者-消费者问题

问题描述：有一群生产者进程在生产产品，并将这些产品提供给消费者进程进行消费，为生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将其所生产的产品放入一个缓冲区中；消费者进程可以从一个缓冲区中取走产品去消费。

尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，既不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

我们可以利用一个数组buffer来表示上述具有n个缓冲区的缓冲池。每投入一个产品时，缓冲池buffer中暂存产品的数组指针in加1.由于这里由buffer组成的缓冲池是被组织成循环缓冲的，故in=(in+1)%n表示+1操作。输出指针out,out=(out+1)%n，当(in+1)%n==out时，表示缓冲池已满；当in==out时，表示缓冲池为空。此外，还引入一个整型变量count，初始值为0，每当生产者进程向缓冲池中投放（或取走）一个产品后，count加1（或减1）。注意生产者进程和消费者进程共享这些变量。

虽然生产者程序和消费者程序单独看都是正确的，但若并发执行就会出现差错，问题就在于count加1（或减1）操作在机器语言中被分为三部分：
register=count;
register=register+1;
count=register;
我们知道，count就是一个不能共同访问的临界资源。

2.哲学家就餐问题

问题描述：有5位哲学家，围绕一张圆桌吃饭，桌子上放着5根筷子，每两个哲学家之间放一支。哲学家的动作包括思考和进餐，进餐时需要同时拿到左右两边的叉子，思考时将两支叉子放回原处。
问题：如何保证哲学家的动作有序进行？

方案一：
利用信号量解决

#define N 5   //哲学家个数
semaphore chop[5];//信号量初值为1
void phil(int i)//哲学家编号：0-4
{
   while(TRUE){
     think();//哲学家思考
     P(chop[i]);//拿左边的筷子
     P(chop[i+1]%N);//拿右边的筷子
     eat();//进食
     V(chop[i]);//放下左边的筷子
     V(chop[i+1]%N);//放下右边的筷子
     }
}

缺点：当每个哲学家都先拿左边的筷子，都陷入等待状态，进入死锁的状态。

方案二：

#define N 5   //哲学家个数
semaphore chop[5];//信号量初值为1
semaphore mutex;//互斥信号量，初值1
void phil(int i)//哲学家编号：0-4
{
   while(TRUE){
     think();//哲学家思考
     P(mutex);//进入临界区
     P(chop[i]);//拿左边的筷子
     P(chop[i+1]%N);//拿右边的筷子
     eat();//进食
     V(chop[i]);//放下左边的筷子
     V(chop[i+1]%N);//放下右边的筷子
     V(mutex);//退出临界区
     }
}

保证大家顺序吃饭，互斥访问正确，但只允许一人进餐，效率低。

方案三：

#define N 5   //哲学家个数
semaphore chop[5];//信号量初值为1
void phil(int i)//哲学家编号：0-4
{
   while(TRUE){
     think();//哲学家思考
     if(i%2 == 0){
         P(chop[i]);//拿左边的筷子
         P(chop[i+1]%N);//拿右边的筷子
     }else{
         P(chop[i+1]%N);//拿右边的筷子
         P(chop[i]);//拿左边的筷子
     }
     eat();//进食
      V(chop[i]);//放下左边的筷子
      V(chop[i+1]%N);//放下右边的筷子
     }
}

偶数编号的哲学家先拿左边，再拿右边；奇数编号的哲学家先拿右边的，再拿左边的。可以同时有两位哲学家进行就餐，提高了进餐效率。

方案四：
除了方案三的解决方法外，我们可以在方案二的基础上增加以下约束条件：
至多只允许四个哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够就餐，并在用完时释放出他使用过的两只筷子，从而使更多的哲学家能够就餐。

方案五：
利用AND信号量机制解决，即仅当哲学家左右两边的筷子均可使用时，才允许进餐。

semaphore chop[5];
do{
   think();
   P(chop[(i+1)%N],chop[i]);//左右筷子同时拿起
   eat();
   V(chop[(i+1)%N],chop[i]);//左右筷子同时释放
}whiel(TRUE);

3.读者-写者问题

问题描述：对共享数据的访问有两类使用者，读者和写者，读者只能读数据，不修改；写者可以读取和修改数据。“读-读”允许，“读-写”互斥，“写-写”互斥，即允许有多个读者读，没有写者时读者才可读，没有读者时写者才可写，没有其他写者时写者才可写。

semaphore rmutex = 1; wmutex = 1;//互斥锁
int readcount = 0;
void reader(){
     do{
          P(rmutex);//关锁
          if (readcount == 0)wait(wmutex);//把写操作锁住，只需要在第一次读时
          readcount++;//读者数目+1
          V(rmutex);//开锁
          read();

          P(rmutex);//关锁
          readcount--;//读者数目-1
          if (readcount == 0)V(wmutex);//没有读者，执行写操作
          V(rmutex);//开锁
     } while (TRUE);
}
void writer(){
     do{
          P(rmutex);
          write();
          V(rmutex);
     } while (TRUE);
}
void main(){
     cobegin
          reader(); writer();
     coend
}

readcount记录读者的个数，当readcount=0，表示尚无读者在读，将写操作上锁（只需在第一次读时），若写操作执行成功，读操作便可进行读，readcount+1，执行读操作后，readcount-1。若没有读者读，便可进行写操作。

1. 基本结构

typedef struct {
	int value;  //信号量值
	struct process_cntrol_block *list;  //阻塞队列
}semaphore;

在应用信号量的时候，信号量的值往往是临界资源的数量。当临界资源数量不足时，新的进程就阻塞，并插入到信号量阻塞队列中。

2. P,V操作

wait(S)和signal(S)操作是信号量机制的基本操作(通常称作P，V操作)，定义如下：

wait(semaphore *S) {
	S->value--;  //信号量的值减一
	if(S->value < 0) block(S->list);  //如果信号量的值小于零,进程阻塞

signal(semaphore *S) {
	S->value++;  //信号量的值加一
	if(S->value <= 0) wakeup(S->list);  //唤醒
}

在实现进程同步时，一般先将S->value的初值设定为临界资源的初始数量，一旦进程要请求一个临界资源，先对代表此进程的信号量执行P操作，也就意味着资源数减一，当该进程运行完毕时，执行V操作，意味着资源数加一。值得注意的是，如果当前资源数量为0，再有进程想请求临界资源，就会在执行P操作时进入阻塞队列，信号量值变为-1，此后执行P操作的进程也都会被阻塞，信号量的绝对值为阻塞的进程数目。

3. 信号量的应用

3.1 信号量实现进程互斥

有了P,V操作，我们就能很简单的实现进程互斥。方法是：设mutex为互斥信号量，初值为1。在需要互斥的临界区前后分别使用P,V操作即可，示意代码如下：

semaphore mutex = 1;  //一般初值为1的信号量用来实现互斥
P_A() {  //进程A
	while(1) {
		P(mutex);
		临界区；
		V(mutex);
		剩余区；
	}
}
P_B() {  //进程B
	while(1) {
		P(mutex);
		临界区；
		V(mutex);
		剩余区；
	}
}

在互斥问题中，我们可以把P操作理解成“上锁”，把V操作理解成“解锁”，当P_A和P_B两个进程并发执行时，无论哪一个进程先执行到了P操作，都会接下来执行P操作的进程阻塞，直到前一个进程执行到了V操作为止，这样就实现了临界区的互斥。

3.2 信号量实现前驱关系

思路如下：为每一组想要实现前后关系的进程，都分别定义一个信号量，初值设为0，把你想要先执行的进程后面加一个V操作，想要后执行的进程前面加一个P操作。这样一来，你想要后执行的进程如果先执行了，就会因为执行了其前面的P操作而阻塞，直到你想要先执行的进程执行完了，执行V操作后，才能解除阻塞继续执行。以上就是用信号量实现前驱关系的过程。
假如我们要实现四个语句S1,S2,S3,S4需要按照一定的顺序同步执行，比如S1执行完S2，S3才能执行，S2,S3执行完了S4才能执行，代码如下：

p1() {S1; V(a); V(b);}
p2() {P(a); S2; V(c);}
p3() {P(b); S3; V(d);}
p4() {P(c); P(d); S4;}

main() {
	semaphore a,b,c,d = 0;
	cobegin
		p1();p2();p3();p4();
	coend
}

4. 用信号量解经典同步问题

4.1 生产者消费者问题

假定生产者和消费者之间的公用缓冲池有n个缓冲区，生产者可以向缓冲区生产一个产品，消费者可以从缓冲区消耗一个产品，注意：生产者不能同时生产，消费者也不能同时消费，也不能同时生产和消费，当缓冲区空时无法消费，当缓冲区满时无法生产。请用信号量机制解决这一问题。
解法如下：

semaphore mutex = 1;  //实现生产与消费、生产与生产、消费与消费
semaphore full = 0, empty = n;  //full表示已用缓冲区数，empty表示空缓冲区数
void producer() {
	while(1) {
		P(empty);  //每次生产会减少一个空缓冲区，如果没有空缓存区了就阻塞
	    P(mutex);  //保证互斥
	    生产一个产品;
	    V(mutex);  //保证互斥
	    V(full);  //每次生产增加一个已用缓冲区
	}
}
void consumer() {
	while(1) {
		P(full);  //每次消费会减少一个已用缓冲区，如果没有已用缓存区了就阻塞
	    P(mutex);
	    消耗一个产品;
	    V(mutex);
	    V(empty);  //每次生产增加一个空缓冲区
	}
}

4.2 读者写者问题

假设一个文件可被多个进程共享，我们允许多个进程同时读这个共享对象，但是不允许一个进程写这个共享对象的同时，别的进程进行读或写。换句话说：读和读不互斥，读和写互斥，写和写互斥。请用信号量机制解决这一问题。
解法如下：

semaphore rmutex, wmutex = 1; //wmutex用以实现写进程与其它进程的互斥
int readcount = 0;  //记录读进程的数量
void reader() {
	while(1) {
		P(rmutex);  //见下文解释
		if(readcount == 0) P(wmutex);  //第一个读进程去把写进程上锁
		readcount++;  
		V(rmutex);  //见下文解释
		读者读;
		P(rmutex);  //见下文解释
		readcount--;
		if(readcount == 0) V(wmutex);  //解锁
		V(rmutex);  //见下文解释
	}
}
void writer() {
	while(1) {
		P(wmutex);  //实现写进程与其他进程都互斥
		写者写;
		V(wmutex);
	}
}

这个问题的程序中有个关键点，就是明明读进程是不互斥的，为什么还需要rmutex来实现if判断的互斥呢。原因如下：当我们在进程互斥中使用条件语句和数值变化的时候，如果不把那一段也实现互斥的话，很有可能出问题，比如在这段代码中，要是不加第5行和第8行的话：如果一个读进程执行完了第6行，还没有执行第7行的readcount++操作之前，这个读进程被剥夺了处理机，换另一个读进程上处理机运行了，那么另一个读进程就会阻塞在第6行的P操作上，就无法实现多个读者一起读了；10行和13行同理，如果一个读进程执行完了第11行就被剥夺处理机，换上另一个读进程也执行了11行，这样readcount被连减两次，那么这两个进程都能通过12行的if判断，会执行两次V操作，产生错误。

4.3 狒狒过桥问题

一个主修人类学、辅修计算机科学的学生参加了一个课题，调查非洲狒狒是否能被教会理解死锁。他找到一处很深的峡谷，在上边固定了一根横跨峡谷的绳索，这样狒狒就可以攀住绳索越过峡谷。同一时刻可以有几只狒狒通过，只要它们朝着相同的方向。但如果向东和向西的狒狒同时攀在绳索上则将发生死锁（狒狒将被卡在中间），因为它们无法在吊在峡谷上时从另一只的背上翻过去。如果一只狒狒想越过峡谷，它必须看当前是否有别的狒狒正在逆向通过。使用信号量写一个避免死锁的程序来解决该问题。
解法如下：

semaphore wmutex, emutex, mutex = 1; 
int wcount, ecount = 0;  //分别记录东西狒狒上绳索的个数
void west_monkey {
	while(1) {
		P(wmutex);  //使if语句互斥
		if(wcount == 0) P(mutex);  //第一个西狒狒给东狒狒上锁
		wcount++;
		V(wmutex);  //使if语句互斥
		西狒狒过桥；
		P(wmutex);
		wcount--;
		if(wcount == 0) V(mutex);
		V(wmutex);
	}
}
void east_monkey {  //和上面的一样
	while(1) {
		P(emutex);
		if(ecount == 0) P(mutex);
		ecount++;
		V(emutex);
		西狒狒过桥；
		P(emutex);
		ecount--;
		if(ecount == 0) V(mutex);
		V(emutex);
	}
}

该问题属于读者写者问题的改进，如果完全理解了读者写者问题的解法，那么这个问题也能很快解决。东狒狒之间不互斥，西狒狒之间不互斥，东西狒狒之间互斥，思路是第一个东狒狒给西狒狒上锁，第一个西狒狒给东狒狒上锁，注意if判断也要实现互斥。

4.4 理发师理发问题

理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉。当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，他们就坐下来等。如果没有空椅子，他就离开。这里的问题是为理发师和顾客各编写一段程序来描述他们的行为，要求不能带有竞争条件。
解法如下：

semaphore customer, barber = 0;  //一开始没有顾客，理发师也是睡着的
semaphore mutex = 1;  //互斥信号量
int empty = N;  //空椅子数量为N
void Barber() {
	while(1) {
		P(customer);  //只有顾客进程的V执行后才能执行，没有顾客就阻塞（睡觉）
		P(mutex);  //把数量的变化实现互斥，以免影响到顾客进程的if判断语句
		empty++;  //椅子上的顾客起身
		V(barber);  //有了一个理发师可以理发
		V(mutex);
		理发;
	}
}
void Customer() {
	P(mutex);
	if(empty > 0) {
		empty--;  //不管是不是第一个顾客，来了先得坐凳子上，因为理发师在理发椅上睡觉呢
		V(customer);  //增加一个顾客，唤醒沉睡的理发师
		V(mutex); 
		P(barber);  //消耗一个理发师，没有理发师就阻塞
		理发;
	} else {
		V(mutex);
		离开;
	}
}

这道题本身不难，但其中很多细节的实现需要实现，比如座位是有上限的，这样就不得不设置判断条件和计数，来使超过N个的顾客离开，而加入计数和判断条件后就又要实现其互斥，增加了问题的复杂性。

4.5 哲学家进餐问题

五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在桌子上有五只碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐毕，放下筷子继续思考。请用信号量机制解决。
这是一个讲解死锁的时候的经典例子，解决这道题的直接思路如下：

semaphore chopstick[5] = {1,1,1,1,1};
void philosopher() {
	while(1) {
	/*当哲学家饥饿时，总是先拿左边的筷子，再拿右边的筷子*/
	P(chopstick[i]);
	P(chopstick[(i+1)%5]);
	吃饭;
	V(chopstick[i]);
	V(chopstick[(i+1)%5]);
	}
}

但是这样可能会出现死锁问题：如果所有哲学家都拿起了左手边筷子，五个进程就会死锁。对于避免哲学家进餐问题发生死锁的方法有很多，这里只讲一种：只有当同时一个哲学家能同时拿起左右两只筷子时，才允许拿筷子，解法如下：

semaphore chopstick[5] = {1,1,1,1,1};
semaphore mutex = 1;
void philosopher() {
	while(1) {
		P(mutex);
        P(chopstick[i]);
		P(chopstick[(i+1)%5]);
		V(mutex);
		吃饭;
		V(chopstick[i]);
		V(chopstick[(i+1)%5]);
	}
}

但仅仅这样做还是有问题，如果一个哲学家获得了两只筷子，开始进餐，此时他左边或者右边的哲学家进入了临界区后，被阻塞在第6行或者第7行，那么其他的哲学家就无法进入临界区了，也就是说这个时间只能有一个哲学家进餐，但显然同一时间是可以有不相邻的两个哲学家同时进餐的。
对这个问题的更好解决方法可以去看Dijkstra在1965年给出的算法。

经典同步问题及及解决方案

哲学家问题

1、 问题描述：

一张圆桌上坐着 5 名哲学家，桌子上每两个哲学家之间摆了一根叉子，桌子的中间是一碗米饭，如图所示：

哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿的时候，才试图拿起左、右两根叉子（一根一根拿起）。如果叉子已在他人手上，则需等待。饥饿的哲学家只有同时拿到了两根叉子才可以开始进餐，当进餐完毕后，放下叉子继续思考。

2、问题分析

（1）5名哲学家与左右邻居对其中间叉子的访问是互斥关系。同时当哲学家要使用叉子时需要等待两个邻居都放下叉子才行，他们又是同步关系
（2）解决办法：这里要开5个线程，每个哲学家对应一个线程。最开始想到的办法是：每个哲学家先拿起左叉子，再拿起右叉子。

//Philosopher i:
do {
    wait(chopstick[i])        //等左侧的筷子
    wait(chopstick[(i+1) % 5])//等右侧的筷子
         …
        eat
         …
    signal(chopstick[i]);    //放下左侧
    signal(chopstick[(i+1) % 5]);//放下右侧
         …
        think
         …
    } while (1);
}

但是这样会存在问题：如果每个哲学家同时拿起左叉子，都在等待右叉子时造成死锁。
为了防止死锁的发生，可以对哲学家线程施加一些限制条件，比如：
（1）同时只允许一位哲学家就餐
（2）对哲学家顺序编号，要求奇数号哲学家先抓左边的叉子，然后再抓他右边的叉子，而偶数号哲学家刚好相反。
（3）仅当一个哲学家左右两边的叉子都可用时才允许他抓起叉子；

3、解决方案

方法1

//Philosopher i:
semaphore mutex = 1;
do {
    wait(mutex);             //当某一人请求用餐时，其他人不能用
    wait(chopstick[i])        //等左侧的筷子
    wait(chopstick[(i+1) % 5])//等右侧的筷子
         …
        eat
         …
    signal(chopstick[i]);    //放下左侧
    signal(chopstick[(i+1) % 5]);//放下右侧
    signal(mutex);
         …
        think
         …
    } while (1);
}

这里把就餐（而不是叉子）看做是互斥访问的临界资源，因此会造成（叉子）资源的浪费。从理论上说，如果有五把叉子，应允许两个不相邻的哲学家同时进餐。

方法2

//Philosopher i:

do {
    if(i%2==1){
    wait(chopstick[i]);        //等左侧的筷子
    wait(chopstick[(i+1) % 5]);//等右侧的筷子
    }
    else{
    wait(chopstick[(i+1)%5]); //等待右侧的筷子
    wait(chopstick[i]);        //等左侧的筷子     
    }
         …
        eat
         …
    signal(chopstick[i]);    //放下左侧
    signal(chopstick[(i+1) % 5]);//放下右侧
         …
        think
         …
    } while (1);
}

规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。这样请求资源时，不会出现相互等待，死等的情况。

生产者消费者问题

最简单的情形–（一个生产者 + 一个消费者 + 一个大小为1的有限缓冲）

其中的同步关系：

• 必须在生产者放入一个产品之后，消费者才能够从缓冲中取出产品来消费。
• 只有在消费者从缓冲区中取出产品（消费）之后，生产者才能再放新的产品进缓冲区。

缓冲区的状态决定了生产者和消费者的行为：
- 空——只能放，不能取
- 满——只能取，不能放

设置两个信号量empty = 1，full = 0；

semaphore empty=1; 
semaphore full=0; 
Producer：
while(true){
    //生产一个产品;
    wait(empty);
    //送产品到缓冲区;
    signal(full);
};

Consumer:
while(true){
    wait(full);
    //从缓冲区取产品
    signal(empty);
    //消费产品
};

一个消费者+一个生产者+n个buffer

我们使用了两个信号量：full 和 empty 。
信号量mutex作为互斥信号量，它用于控制互斥访问缓冲池，互斥信号量初值为 1；
信号量 full 用于记录当前缓冲池中“满”缓冲区数，初值为0。
信号量 empty 用于记录当前缓冲池中“空”缓冲区数，初值为n。
新的数据添加到缓存中后，full 在增加，而 empty 则减少。
如果生产者试图在 empty 为0时减少其值，生产者就会被“催眠”。下一轮中有数据被消费掉时，empty就会增加，生产者就会被“唤醒”。

semaphore mutex=1; //临界区互斥信号量
semaphore empty=n;  //空闲缓冲区
semaphore full=0;  //缓冲区初始化为空
producer ()//生产者进程 
{
    while(1)
    {
        //生产数据
        wait(empty);  //获取空缓冲区单元
        wait(mutex);  //进入临界区.
        //将数据放入缓冲区
        i = (i+1)%n;
        signal(mutex);  //离开临界区,释放互斥信号量
        signal(full);  //满缓冲区数加1
    }
}

consumer ()//消费者进程
{
    while(1)
    {
        wait(full);  //获取满缓冲区单元
        wait(mutex);  // 进入临界区
        //从缓冲区中取出数据
        j = (j+1)%n;
        signal (mutex);  //离开临界区，释放互斥信号量
        signal (empty) ;  //空缓冲区数加1
        //消费数据
    }
}

m个生产者+k个消费者+n个缓冲区

1）用两个信号量empty,full;
2)m个生产者之间要互斥，n个消费者之间也要互斥,同时要求生产者和消费者互斥存取物品,
因此设两个计数器i,j和一个互斥信号量mutex.

semaphore mutex1=1; //生产者临界区互斥信号量
semaphore mutex2=1； //消费者临界区互斥信号量
semaphore empty=n;  //空闲缓冲区
semaphore full=0;  //缓冲区初始化为空
producer ()//生产者进程 
{
    while(1)
    {
        //生产数据
        wait(empty);  //获取空缓冲区单元
        wait(mutex1);  //进入临界区.
        //将数据放入缓冲区
        i = (i+1)%n;
        signal(mutex1);  //离开临界区,释放互斥信号量
        signal(full);  //满缓冲区数加1
    }
}

consumer ()//消费者进程
{
    while(1)
    {
        wait(full);  //获取满缓冲区单元
        wait(mutex2);  // 进入临界区
        //从缓冲区中取出数据
        j = (j+1)%n;
        signal (mutex2);  //离开临界区，释放互斥信号量
        signal (empty) ;  //空缓冲区数加1
        //消费数据
    }
}

司机&售票员

要求：
先关门，后开车；
先形势，后售票；
先停车，后开门；

司机：
等待关门，启动，行驶，停车

售票员：
关门，等待行驶，售票，等待停车，开门

semaphore door=1;     //door=1开门， =0关门 
semaphore stop=1；      //1=汽车停止
semaphore start=0;    //1=启动汽车

Driver（）{           //司机
    while(True){
    wait(door);
    //启动汽车；
    signal(start);
    //行驶
    //到站停车
    signal(stop)；
    }
} 

Busserver(){      //售票员
    while(True){
    //关门
    signal(door);
    wait(start);
    //售票
    wait(stop)；
    //开门
    }
}

设有两个优先级相同的进程p1和p2如下。信号量S1和S2的初值均为0，试问P1和P2并发执行结束后，x、y、z的值各位多少？

进程P1               进程P2
1)y = 1；             7)x = 1;
2)y = y+2;          8)x = x +1;
3)V(S1);              9)P(S1);
4)z = y+1;          10)x = x+y;
5)P(S2);              11)V(S2);
6)y = z + y;          12)z=x+z;

首先不论P1、P2谁先执行，到语句10）都没问题，
10）此时x=5,y=3,z=4
但是如果P1先执行，那么先执行语句6）y=7，后执行12）z=9
若P2先执行，那么先执行语句12）z=9，后执行6）y=12

因此，结果为：
1）P1先执行 x=5,y=7,z=9;
2) P2先执行 x=5,y=12,z=9;

假定系统有3个并发进程get 、copy 和put共享缓冲器B1和B2。进程get负责从输入设备上读信息，每读出一条记录后放到B1中。进程copy从缓冲器B1中取出一条记录拷贝后存入B2。进程put取出B2中的记录打印输出。B1和B2每次只能存放一条记录。要求3个进程协调完成任务，使打印出来的与读入的记录个数、次序完全一样。请用记录型信号量写出并发程序。（北大1990年试题）

解题思路：由于是两个资源B1，B2，分别对应着各自的空状态和满状态。因此，需要4个信号量。

semaphore fullB1=0;
semaphore emptyB1=1;
semaphore fullB2=0;
semaphore emptyB2=1;


get(){
    while(true){
    //输入设备读入数据
    wait(emptyB1);   //等待B1空闲
    //将数据传入B1
    signal(fullB1);
    }
}

copy(){
    while(ture){
    wait(fullB1);    //B1有数据
    //从B1取出数据
    signal(emptyB1);
    wait(emptyB2);      //B2空闲
    //将数据拷贝到B2
    signal(fullB2);
    }
}

put(){
    while(true){
    wait(fullB2);       //B2有数据
    //从B2取数据打印
    signal(emptyB2);
    }
}

读者-写者问题

读者优先

读者（reader）：只能读
写者（writer）：能读也能写

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

semaphore mutex = 1;    //更新count时保证互斥
semaphore wrt = 1;      //读者和写者的互斥访问临界区
int readcount = 0;  //记录读者的数量

Writer Process{    //写者进程
wait(wrt);
     …
//writing;
     …
signal(wrt);

}


Reader Process{     //读者进程
wait(mutex);     //更新count时互斥
readcount++;

if (readcount == 1)
    wait(wrt);     //拥塞写者
signal(mutex);
     …
//reading;
     …
wait(mutex);
readcount--;        //更新count时互斥
if (readcount == 0)
    signal(wrt);    //释放写者
signal(mutex);
}

在上面的算法中，读进程是优先的，也就是说，当存在读进程时，写操作将被延迟，并且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式下，会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

写者优先

如果希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等待到已在共享文件的读进程执行完毕则立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。
所以，需要加一个信号量给写者，用于写者优先。

/*初始化读者、写者队列为0，初始化临界区资源、读写计数器资源的初始值为1*/  
int readCount = 0;  
int writeCount = 0;  
semaphore read = 1;  
semaphore readCountSignal = 1;  
semaphore writeCountSignal = 1;
semaphore fileSrc=1;        //临界区资源的互斥访问  

reader()  
{  
      while(true)  
     {  
        wait(read);            //申请令牌  
        wait(readCountSignal); //申请读者队列计数器  

        if(!readCount)         //如果读者队列为空，申请文件资源  
           wait(fileSrc);   
        readCount++;  

        signal(readCountSignal); //释放读者计数器资源  
        signal(read);            //释放令牌  

        ...  
        perform read operation //执行读操作       
        ...  

        wait(readCountSignal);     
        readCount--;  
        if(!readCount)          //如果读者队列为空，释放文件资源  
          signal(fileSrc);  
        signal(readCountSignal);   
      }  
}  

writer()  
{  
     while(true)  
     {  
       wait(writeCountSignal);  //申请写者计数器资源  
       if(!writeCount)          //如果写者队列为空则申请令牌  
         wait(read);  
       writeCount++;  
       signal(writeCountSignal); //释放写者计数器资源  
       wait(file);               //申请文件资源  

       ...  
       perform write operation   //执行写操作
       ...  

       signal(fileSrc);          //释放文件资源  
       wait(writeCountSignal);   
       writeCount--;  
       if(!writeCount)           //如果写者队列为空则释放令牌  
          signal(read);  
       signal(writeCountSignal); 
      }  
}  

公平竞争

公平竞争要求：
1.优先级相同。
2.写者、读者互斥访问。
3.只能有一个写者访问临界区。
4.可以有多个读者同时访问临界资源。

具体实现：
1.设置fileSrc信号量实现对临界资源的互斥访问。
2.设置计数器readCount实现多个读者访问临界资源，通过设置信号readCountsignal实现对readCount计数器的互斥访问。
3.设置信号量keySignal实现读者和写者的公平竞争。
4.设置信号量OneSignal实现只有读者队列或写者阻塞在keySignal。

/* 读者队列初始值为0，其他资源初始值为1*/  
int readCount = 0;  
semaphore keySignal = 1;  
semaphore OneSignal = 1;  
semaphore readCountSignal = 1;  
semaphore fileSrc=1;

reader()  
{  
    while(true)  
    {  
      wait(keySignal);        //申请令牌  
      wait(readCountSignal);   
      if(!readCount)          //为零则申请文件资源  
         wait(fileSrc);  
      readCount++;  
      signal(readCountSignal); 
      signal(keySignal);      //释放令牌  

      ...  
      perform read operation  //执行读操作
      ...  

      wait(readCountSignal);  
      readCount--;  
      if(!readCount)                //为零则释放文件资源  
         signal(fileSrc);  
    signal(readCountSignal); 
    }  
}  

writer()  
{  
     while(true)  
     {  
        wait(OneSignal);     //申请令牌资源  
        wait(keySignal);     //申请令牌  
        wait(fileSrc);       //申请文件资源  

        ...  
        perform write operation //执行写操作 
        ...  

        signal(fileSrc);    
        signal(keysignal); 
        signal(OneSignal);  
     }  
} 

猴子过桥

一个主修动物行为学、辅修计算机科学的学生参加了一个课题，调查花果山的猴子是否能被教会理解死锁。他找到一处峡谷，横跨峡谷拉了一根绳索（假设为南北方向），这样猴子就可以攀着绳索越过峡谷。只要它们朝着相同的方向，同一时刻可以有多只猴子通过。但是如果在相反的方向上同时有猴子通过则会发生死锁（这些猴子将被卡在绳索中间，假设这些猴子无法在绳索上从另一只猴子身上翻过去）。如果一只猴子相越过峡谷，它必须看当前是否有别的猴子在逆向通过。请使用P/V 操作来解决该问题。
(南航研究生试题)
要求
- 关键在于明确南北的猴子之间互斥，但同一个方向可以允许多只猴子通过，所以临界区可允许多个实例访问。
- 当一方有猴子在绳索上时，同方向的猴子可继续通过，但此时要防止另一方的猴子跨越绳索。

int southnum=0;
int northnum=0;
semaphore mutex=1;//绳索互斥访问
semaphore south=1;//南方猴子互斥信号量
semaphore north=1;//北方猴子互斥信号量

southi(){
    wait(south);
    if(southnum==0)
        wait(mutex);

    southnum++;

    signal(south);
    signal(mutex);
    //cross越过绳索

    wait(south);
    southnum--;
    if(southnum==0)
        signal(mutex);
    signal(mutex);
    signal(south);
}


northi(){
    wait(north);
    if(northnum==0)
        wait(mutex);

    northnum++;

    signal(north);
    signal(mutex);
    //cross越过绳索

    wait(north);
    northnum--;
    if(northnum==0)
        signal(mutex);
    signal(north);
}

给出一个并发程序的描述：semaphore X1=X2=Y=1; int c1=c2=0; f1，f2流程如下。问computeA和computeB各自能有多少并发执行，会不会出现饿死？（清华大学）

procedure f1:
p(X1)
if (++c1 == 1) 
p(Y)
v(X1)
compute A
p(X1)
if (--c1 == 0) 
v(Y)
v(X1)

procedure f2:
p(X2)
if (++c2 == 1) 
p(Y)
v(X2)
compute B
p(X2)
if (--c2 == 0) 
v(Y)
v(X2)

A、B各自能有多个并发执行
考虑到一种极端情况，f1一直有进程存在，那么f2会饥饿。

有桥如图所示。车流如箭头所示。桥上不允许两车交会，但允许同方向多辆车依次通过（即桥上可以有多个同方向的车）。用P、V操作实现交通管理以防止桥上堵塞。(北京大学）

semaphore mutex=1;//道路互斥访问
semaphore south=n;//南方互斥信号量记录型
semaphore north=n;//北方互斥信号量记录型

southi(){
    wait(south);
    wait(mutex);
    //过桥    
    signal(south);
    signal(mutex);
}

northi(){
    wait(north);
    wait(mutex);
    //过桥    
    signal(north);
    signal(mutex);
}