经典进程同步与互斥问题（5）

た入场券 2024-03-30 17:34 85阅读 0赞

经典进程同步与互斥问题

### 1 生产者-消费者问题 ###

##### 1.1 问题描述 #####

*  生产者-消费者问题是指有两组进程共享一个环形的缓冲池。一组进程被称为生产者，另一组进程被称为消费者。
 *  缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲区可以容纳一个产品。
 *  生产者进程不断地将生产的产品放入缓冲池，消费者进程不断地将产品从缓冲池中取出。  
    ![在这里插入图片描述][a2b1dc2d725646a5b14717cab18680d0.png]

在生产者-消费者问题中

*  存在着进程同步问题：当缓冲区满时，表示供大于求，生产者必须停止生产，进入等待状态，同时唤醒消费者；当所有的缓冲区都空时，表示供不应求，消费者必须停止消费，唤醒生产者。
 *  存在着临界区的互斥问题：缓冲池是一个临界资源，必须要等缓冲池里满了，消费者才能取，缓冲池空了，生产者才能生产。所以对于缓冲池的操作是互斥的。

##### 1.2 利用信号量与P,V操作解决生产者-消费者问题。 #####

必须保证先装满再取，取空再装的原则
    semaphore mutex =1;
    semaphore empty = n;    //缓冲池还剩的空闲位,初始值为n
    semaphore full = 0;      //缓冲池的资源数目,因此empty+full=n
    int i,j;
    ITEM  buffer[n];
    ITEM  data_p, data_c;
    
    voidproducer()      //生产者进程
    {
        while(true)
    	{
        produce an item in data_p;
    	P(empty);                  //p,v操作实现进程的互斥，必须是成对出现的
    	P(mutex);
    	buffer[i] = data_p;
    	i = (i + 1) % n;
    	V(mutex);
    	V(full);}
    }
    
    voidconsumer()  //消费者进程
    {
        while(true)
    	{
        P(full);
    	P(mutex);
    	data_c=buffer[j];
    	j=(j+1)%n;
    	V(mutex);
    	V(empty);
    	consumetheitemindata_c;}
    }

### 2 读者-写者问题 ###

##### 2.1 问题描述 #####

一个数据对象若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求写操作，对此，我们把只想读的进程称为“读者”，而把要求写的进程称为“写者”。  
问题描述：

*  读者可同时读；
 *  读者读时，写者不可写；
 *  写者写时，其他的读者、写者均不可进入。

为了解决该问题，只需要解决“写者与写者”和“写者与第一个读者”的互斥问题。

##### 2.2 用信号量解决读者-写者问题 #####

semaphore Wmutex=1;
    读者进程：
    while(true)
    {
        
    	‘有人要读’P(Wmutex);
    	读;
    	‘无人读了’V(Wmutex);
    }
    
    写者进程：
    while(true)
    {
        
    	P(Wmutex);
    	写;
    	V(Wmutex);
    }

Semaphore Wmutex,Rmutex=1,1; 
    int Rcount;
    void reader()/*读者进程*/
    {
        while(true)
    	{
        P(Rmutex);
    	if(Rcount==0)P(Wmutex);
    	Rcount=Rcount+1;
    	V(Rmutex);
    	read;/*执行读操作*/
    	P(Rmutex);
    	Rcount=Rcount-1;
    	if(Rcount==0)V(Wmutex);
    	V(Rmutex);}
    }
    
    voidwriter()  /*写者进程*/
    {
        
    while(true){
         
    	P(Wmutex);
    	write;      
    /* 执行写操作*/
    	V(Wmutex);
    	}
    }

### 3 哲学家进餐问题 ###

##### 3.1 问题描述 #####

五个哲学家，他们的生活方式是交替地思考和进餐。

*  哲学家们共用一张圆桌，围绕着圆桌而坐，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时拿起其左、右的两支筷子，试图进餐，进餐完毕又进行思考。
 *  这里的问题是哲学家只有拿到靠近他的两支筷子才能进餐，而拿到两支筷子的条件是他的左、右邻居此时都没有进餐。  
    \-![在这里插入图片描述][75e0df5106b048469e9dc58100dec1a6.png]

##### 3.2 用信号量解决哲学家进餐问题 #####

由分析可知，筷子是临界资源，一次只允许一个哲学家使用，因此可以用互斥信号量来实现。

semaphore chopstick[5]={
        1,1,1,1,1};
    void philosopher(inti)/*哲学家进程*/
    {
        while(true){
        
    	P(chopstick[i]);
    	P(chopstick[(i+1)%5]);
    	eating;     /*进餐*/
    	V(chopstick[i]);
    	V(chopstick[(i+1)%5]);
    	thinking;  /*思考*/}
    	}

以上算法虽然解决了相邻两个哲学家不会同时进餐的问题，但如果所有的哲学家总是先拿起左边的筷子，再拿起右边的筷子，那么就会导致死锁。

### 4 打磕睡的理发师问题 ###

##### 4.1 问题描述 #####

理发店有一名理发师，一把理发椅，还有N把供等候理发的顾客坐的普通椅子。如果没有顾客到来，理发师就坐在理发椅上打磕睡。当顾客到来时，就唤醒理发师。如果顾客到来时理发师正在理发，顾客就坐下来等待。如果N把椅子都坐满了，顾客就离开该理发店去别处理发。  
![在这里插入图片描述][80681bc0bc5e432fafab84af4c66036e.png]

##### 4.2 用信号量解决打磕睡的理发师问题 #####

#define CHAIRS 5//为等候的顾客准备的座椅数
    semaphore customers = 0;
    semaphore barners = 0;
    semaphore mutex = 1;
    int waiting;
    void barber()//理发师进程
    {
        
    	while(true){
        
    	P(customers);//如果没有顾客，理发师就打磕睡
    	P(mutex);//互斥进入临界区
    	waiting--;
    	V(barners);//理发师准备理发了
    	V(mutex);
    	cut_hair();//理发
    	}
    }
    
    void customer ()//顾客进程
    {
        P(mutex);
    if(waiting < CHAIRS)//如果有空位，顾客等待
    	{
        waiting++; 
    	V(customers);//如果有必要，唤醒理发师
    	V(mutex);
    	P(barners);  //如果理发师正在理发，则顾客等待
    	get_haircut();}
    else//如果没有空位，则顾客离开
    V(mutex);
    }

[a2b1dc2d725646a5b14717cab18680d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c020e09c0fff46faa1fab11db26c8a7c.png
[75e0df5106b048469e9dc58100dec1a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4f1115677c4f44e9920bcf7da9202d8f.png
[80681bc0bc5e432fafab84af4c66036e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/eb35c97132f34808bd4882c3e102ec80.png