【考研】操作系统：2014年真题47（同步互斥问题）_综合

前言

解决同步互斥问题的思路，源于对王道讲解的总结笔记

一、思路

解决同步互斥问题，思路步骤：

1. 分析各进程之间的同步互斥关系；

2. 设置互斥信号量 mutex = 1、同步信号量（一般设可使用的资源数为empty = N）。

3. 最好画出同步互斥关系图，并判断属于哪一种类型，如生产者-消费者问题、读者-写者问题、哲学家进餐问题、吸烟者问题。

二、题目

45. 系统中有多个生产者进程和消费者进程，共享用一个可以存 1000 个产品的环形缓冲区（初始为空），当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出 10件产品后，其他消费者进程才可以取产品，请用信号量 P, V（ wait ， signed ）操作实现进程间的互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值。

解：（1）互斥资源：

一个消费者进程从缓冲区连续取出 10件产品后，其他消费者进程才可取产品，设置互斥信号量 mutex1 = 1;

生产者和消费者对缓冲区的访问进行设置互斥信号量：mutex2 = 1;

（2）同步关系：生产者和消费者进程共享用一个可以存 1000 个产品的缓冲区（初始为空），则设同步信号量 empty = 1000，代表有几个空闲缓冲单元; 设同步信号量 full = 0，代表此时缓冲区的产品数;

（3）同步互斥关系图如下：（生产者-消费者的变型）

（4）伪代码如下：

第一步：设置信号量

semaphore mutex1 = 1;
semaphore mutex2 = 1; 
semaphore empty = 1000;  // 有几个空闲缓冲单元
semaphore full = 0;

第二步：首先确定是生产者-消费者的问题，列出如下伪代码

producer(){while(1){生产一个产品；把产品放入缓冲区；}
}consumer(){while(1){从缓冲区取出一件产品；消费这件产品；}
}

第三步：再设置进程单次互斥访问缓冲区

producer(){while(1){生产一个产品；P(mutex2);把产品放入缓冲区；V(mutex2);}
}consumer(){while(1){P(mutex2);从缓冲区取出一件产品；V(mutex2);消费这件产品；}
}

第四步：生产者：放产品前判断缓冲区是否有空位；消费者：取出产品后再腾出空位。

producer(){while(1){生产一个产品；P(empty);  // 判断缓冲区是否有空位P(mutex2);把产品放入缓冲区；V(mutex2);}
}consumer(){while(1){P(mutex2);从缓冲区取出一件产品；V(mutex2);V(empty);  // 取出产品后再腾出空位消费这件产品；}
}

第五步：在生产者生产一个产品后，此时缓冲区的产品数加一；在消费者使用一个产品后，此时缓冲区的产品数减一；

producer(){while(1){生产一个产品；P(empty);  // 判断缓冲区是否有空位P(mutex2);把产品放入缓冲区；V(mutex2);V(full);   // 缓冲区产品数加一}
}consumer(){while(1){P(full);   // 缓冲区产品数减一P(mutex2);从缓冲区取出一件产品；V(mutex2);V(empty);  // 取出产品后再腾出空位消费这件产品；}
}

第六步：与经典的生产者-消费者问题的不同在于，要求一个消费者进程从缓冲区连续取出 10件产品后，其他消费者进程才可取产品。

所以，用互斥信号mutex1来实现消费者之间的制约, 用 for 循环来实现一个消费者连续取10次后，下一个消费者才可从缓冲区取产品。

producer(){while(1){生产一个产品；P(empty);  // 判断缓冲区是否有空位P(mutex2);把产品放入缓冲区；V(mutex2);V(full);   // 缓冲区产品数加一}
}consumer(){while(1){P(mutex1);   // 设置互斥信号量，实现一个消费者进程一个周期（10次）内次对缓冲区的控制for(int i = 0; i < 10; i++){   // 用 for 循环实现连续取 10 次P(full);   // 缓冲区产品数减一P(mutex2);从缓冲区取出一件产品；V(mutex2);V(empty);  // 取出产品后再腾出空位消费这件产品；}V(mutex1);  }
}

完整代码如下：

semaphore mutex1 = 1;
semaphore mutex2 = 1; 
semaphore empty = 1000;  // 有几个空闲缓冲单元
semaphore full = 0;producer(){while(1){生产一个产品；P(empty);  // 判断缓冲区是否有空位P(mutex2);把产品放入缓冲区；V(mutex2);V(full);   // 缓冲区产品数加一}
}consumer(){while(1){P(mutex1);   // 设置互斥信号量，实现一个消费者进程一个周期（10次）内次对缓冲区的控制for(int i = 0; i < 10; i++){   // 用 for 循环实现连续取 10 次P(full);   // 缓冲区产品数减一P(mutex2);从缓冲区取出一件产品；V(mutex2);V(empty);  // 取出产品后再腾出空位消费这件产品；}V(mutex1);  }
}

三、进一步理解

系统中有多个生产者进程和消费者进程，共享用一个可以存 1000 个产品的环形缓冲区（初始为空）。

环形缓冲区，相当于一个循环队列。可以设置一个大小为1000的循环缓冲区。

【考研】操作系统：2014年真题47（同步互斥问题）

在本题里，不用再额外判断循环队列是否“满 / 空”，因为设置了 P(mutex) 和 P(full) 来分别判断缓冲区是否有空位，缓冲区是否有产品。

备注：判断栈、队列为 “ 满 / 空 ” 和其长度。

满

空

长度

栈

s->top == maxsize - 1;

s->top == -1;

顺序栈：s->top == s->base;
链栈：s->next == NULL

s->top + 1;

队列

(Q.rear + 1) % maxsize == Q.front

Q.front == Q.rear == 0

链队：
if(Q.rear == NULL) return 1;

(rear - front + maxsize) % maxsize