5.经典进程同步问题

生产者消费者问题

一组生产者进程和一组消费者进程共享一个初始为空，大小为n的缓冲区。当缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待，只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

semaphore mutex=1; //临界区互斥信号量
semaphore empty=n; //空闲缓冲区
semaphore full=0; //满缓冲区
int in=0,out=0;
item buffer[n];

//生产者
producer()
{
	while(1){
         produce an item nextp; //生产产品
		wait(empty); //获取空缓冲区
		wait(mutex); //进入临界区
		buffer[in]=nextp; //数据放入临界区
		in=(int+1)%n; 
		signal(mutex);  //离开临界区，释放互斥信号量
		signal(full);  //满缓冲区数+1
	}
}

//消费者
consumer()
{
	while(1){
		wait(full); //获取满缓冲区
		wait(mutex); //进入临界区
		nextc=buffer[out]; //从缓冲区取数据
		out=(out+1)%n;
		signal(mutex); //离开临界区，释放互斥信号量
		signal(empty); //空缓冲区数+1
         consume the item in nextc; //消费产品
	}
}

读者写者问题

有读写两组进程，共享一个文件，

①多个读者可同时访问文件

②但多个写者不能同时访问文件

③写者和读者不能同时访问文件

semaphore rmutex=1; //保护counter变量的互斥信号量
semaphore wmutex=1; //保证读者和写者互斥访问文件
int counter=0;  //记录当前读者数量

//读者
reader(){
    while(1){
        wait(rmutex);  //互斥访问counter变量
        if(counter==0)wait(wmutex);  //当第一个读者时，阻止写进程写
        couter++;  //计数器+1
        signal(rmutex);  //释放互斥变量counter
        
        reading  //读操作 
            
        wait(rmutex);  //互斥访问counter变量
        counter--;  //计数器-1
        if(counter==0)signal(wmutex); //当最后一个读者时，允许写进程写
        signal(rmutex);  //释放互斥变量counter
    }	
}



//写者
writer(){
	while(1){
        wait(wmutex);  //互斥访问共享文件
        writing  //写操作
        signal(wmutex);	//释放共享文件
	}
}

哲学家就餐

有五个哲学家围在一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐完毕后，放下筷子继续思考。

• 由问题描述我们可以知道，一共有五个哲学家，也就是五个进程；五只筷子，也就是五个临界资源；因为哲学家想要进餐，必须要同时获得左边和右边的筷子，这就是要同时进入两个临界区（使用临界资源），才可以进餐。

semaphore chopstick[5] = {1,1,1,1,1}; 		//初始化信号量

void P(){
  while(1)
  {
    think;			//思考
    wait(chopstick[i]);//判断哲学家左边的筷子是否可用
    wait(chopstick[(i+1)%5]);//判断哲学家右边的筷子是否可用
    
    eat;		//进餐
    
    signal(chopstick[i]); //退出临界区，允许别的进程操作缓冲池
    signal(chopstick[(i+1)%5]); //缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程
  }
}

问题：如果考虑到并发问题，五个哲学家同时拿起了左边的筷子，此时，五只筷子立刻都被占用了，没有可用的筷子了，当所有的哲学家再想拿起右边筷子的时候，因为临界资源不足，只能将自身阻塞，而所有的哲学家全部都会阻塞，并且不会释放自己手中拿着的左边的筷子，因此就会一直处于阻塞状态，无法进行进餐并思考。

解决方法：

1. 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用餐完毕后能释放他占用的筷子，从而使别的哲学家能够进餐
2. 仅当哲学家的左、右两支筷子可用时，才允许他拿起筷子
3. 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反

方法1（增加一个信号量实现）：

semaphore chopstick[5] = {1,1,1,1,1}; 		//初始化信号量
semaphore sm=4;

void P(){
  while(1)
  {
    think;			//思考
    wait(sm);
    wait(chopstick[i]);//判断哲学家左边的筷子是否可用
    wait(chopstick[(i+1)%5]);//判断哲学家右边的筷子是否可用
    signal(sm);
    
    eat;		//进餐
    
    signal(chopstick[i]); //退出临界区，允许别的进程操作缓冲池
    signal(chopstick[(i+1)%5]); //缓冲池中非空的缓冲区数量加1，可以唤醒等待的消费者进程
  }
}

方法2（使用AND型信号量）：

semaphore chopstick[5] = {1,1,1,1,1}; 		//初始化信号量
semaphore sm=4;

void P(){
  while(1)
  {
    think;			//思考
    wait(chopstick[i],chopstick[(i+1)%5]); //判断哲学家左右筷子是否同时可用
    
    eat;
    signal(chopstick[i]，chopstick[(i+1)%5]); //进餐完毕，释放哲学家占有的筷子
  }
}

方法3（添加判断来决定获取左、右筷子的顺序，规定偶数号哲学家先拿左手筷子，再拿右手筷子）：

semaphore chopstick[5] = {1,1,1,1,1}; 		//初始化信号量
semaphore sm=4;

void P(){
  while(1)
  {
    think;			//思考
    if(i%2==0){
    	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]); //释放右边筷子
  }
}