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

前言

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

一、思路

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

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

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

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

二、题目

45. 有 A、B 两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设 A 的信箱最多放 M 个邮件，B 的信箱最多放 N 个邮件。初始时 A 的信箱中有 x 个邮件（0 < x < M），B 的信箱中有 y 个（0 < y < N）。辩论者每取出一个邮件，邮件数减 1。A 和 B 两人的操作过程描述如下：

CoBeginA{while(TRUE){从 A 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入 B 的信箱；}
}B{while(TRUE){从 B 的信箱中取出一个邮件； 回答问题并提出一个新问题； 将新邮件放入 A 的信箱；}
}
CoEnd

当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P、V（或 wait、signal）操作，以实现上述过程的同步。要求写出完整过程，并说明信号量的含义和初值。

解：

（1）互斥资源：进程 A、B 对两个信箱的访问都是互斥的。有两个信箱，所以设置两个互斥信号量。mutex_A 和 mutex_B 分别用于对 A、B 信箱的互斥访问。

（2）同步问题：

A 信箱中有信时 A 才能取信，B 信箱中有信时 B 才能取信，设同步信号量 Full_A 、Full_B；

B 信箱中有空位时 A 才能放信，A 信箱中有空位时 B 才能放信，设同步信号量 empty_A、empty_B；

由于初始时 A 的信箱中有 x 个邮件（0 < x < M），B 的信箱中有 y 个（0 < y < N）

所以 Full_A = x、Full_B = y、empty_A = M - x、empty_B = N - y;

（3）A、B之间的同步互斥关系图如下：

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

（4）伪代码如下：

semaphore mutex_A = 1;  // mutex_A 用于 A 的信箱互斥
semaphore mutex_B = 1;  // mutex_B 用于 B 的信箱互斥semaphore Empty_A = M - x;  // empty_A 表示 A 信箱中还可存放的邮件数量
semaphore Full_A = x;  // Full_A 表示 A 信箱中的邮件数semaphore Empty_B = N - y;  // empty_B 表示 B 信箱中还可存放的邮件数量
semaphore Full_B = x;  // Full_B 表示 B 信箱中的邮件数

分解步骤：一是先整互斥关系：

A(){  // 先使 A 和 B 互斥访问信箱while(TRUE){p(mutex_A)；从A的信箱中取出一个邮件；v(mutex_A)；回答问题竟提出新问题；p(mutex_B)；将邮件放入B的信箱中；v(mutex_B)；}
}B() {while(TRUE){     p(mutex_B)；从B的信箱中取出一个邮件；v(mutex_B)；回答问题竟提出新问题；  p(mutex_A)；将邮件放入A的信箱中；v(mutex_A)；}
}

二是整同步关系：（分为两步）

第一步：从 A 取和往 A 放，从 B 取和往 B 放。

A(){  // 先使 A 和 B 互斥访问信箱while(TRUE){P(Full_A);  // 起初信箱 A 有 x 封邮件，对 A 取邮件，则改变 x 值p(mutex_A)从A的信箱中取出一个邮件；v(mutex_A)回答问题竟提出新问题；p(mutex_B)将邮件放入B的信箱中；v(mutex_B)V(Full_B);  // 往 B 信箱放邮件，则改变 y 值}
}B() {while(TRUE){  P(Full_B);  // 起初信箱 B 有 y 封邮件，对 B 取邮件，则改变 y 值p(mutex_B)从B的信箱中取出一个邮件；v(mutex_B) 回答问题竟提出新问题；  p(mutex_A)将邮件放入A的信箱中；v(mutex_A)V(Full_A);  // 往 A 信箱放邮件，则改变 x 值}
}

第二步：判断此时 A、B 信箱内是否还可存放邮件

A(){  // 先使 A 和 B 互斥访问信箱while(TRUE){P(Full_A);  // 起初信箱 A 有 x 封邮件，对 A 取邮件，则改变 x 值p(mutex_A);从A的信箱中取出一个邮件；v(mutex_A);V(Empty_A);   // 从 A 中取出一个邮件后，A 的容量加一回答问题竟提出新问题；P(Empty_B);   // 判断此时 B 信箱内是否还可存放邮件p(mutex_B);将邮件放入B的信箱中；v(mutex_B);V(Full_B);  // 往 B 信箱放邮件，则改变 y 值}
}B() {while(TRUE){  P(Full_B);  // 起初信箱 B 有 y 封邮件，对 B 取邮件，则改变 y 值p(mutex_B);从B的信箱中取出一个邮件；v(mutex_B);V(Empty_B);   // 从 B 中取出一个邮件后，B 的容量加一回答问题竟提出新问题；  P(Empty_A);  // 判断此时 A 信箱内是否还可存放邮件p(mutex_A);将邮件放入A的信箱中；v(mutex_A);V(Full_A);  // 往 A 信箱放邮件，则改变 x 值}
}

完整代码如下：

semaphore mutex_A = 1;  // mutex_A 用于 A 的信箱互斥
semaphore mutex_B = 1;  // mutex_B 用于 B 的信箱互斥semaphore Empty_A = M - x;  // empty_A 表示 A 信箱中还可存放的邮件数量
semaphore Full_A = x;  // Full_A 表示 A 信箱中的邮件数semaphore Empty_B = N - y;  // empty_B 表示 B 信箱中还可存放的邮件数量
semaphore Full_B = x;  // Full_B 表示 B 信箱中的邮件数A(){while(TRUE){p(Full_A);p(mutex_A);从A的信箱中取出一个邮件;v(mutex_A);v(Empty_A);回答问题竟提出新问题;p(Empty_B);p(mutex_B);将邮件放入B的信箱中;v(mutex_B);v(Full_B);}
}B() {while(TRUE){p(Full_B);p(mutex_B);从B的信箱中取出一个邮件;v(mutex_B);v(Empty_B);回答问题竟提出新问题;p(Empty_A);p(mutex_A);将邮件放入A的信箱中;v(mutex_A);v(Full_A);}
}

另外一种解法（由评论区粉丝提供的思路编写而成）

semaphore numA = x;    //初始A信箱中信的数量 
semaphore numB = y;   //初始B信箱中信的数量
semaphore mutexA = 1;    //实现对A的互斥访问
semaphore mutexB = 1;   //实现对B的互斥访问A(){while(true){p(mutexA);if(numA > 0){ numA--;从A中取件；}V(mutexA);回答并提问；P(mutexB);if(numB < N){numB++;放入B中;}V(mutexB);}
}B(){while(true){p(mutexB);if(numB>0){numB--;从B中取件；}V(mutexB);回答并提问；P(mutexA);if(numA < M){numA++;放入A中;}V(mutexA);}
}