YiNotes

题21

Jun 19, 20255 min read

题21

题目

【2015 统考真题】有 两人通过信箱进行辩论,每个人都从自己的信箱中取得对方的问题，将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设 的信箱最多放 个邮件, 的信箱最多放 个邮件。初始时 的信箱中有 个邮件 , 的信箱中有 个邮件 。辩论者每取出一个邮件,邮件数减 1 。A 和 B 两人的操作过程描述如下:

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

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

分析

题15
具体的流程看这里，非常详细：题目 5：既是生产者又是消费者、双缓冲区、单次取出
先分析一下我是怎么想的

  • 首先我没注意到，邮箱这个东西，每次要么是A自己取，要么是B来取，不能两个人同时来拿这个邮箱，这个也就是一个互斥量，需要给一把锁
  • 然后其中的资源A和B信箱中的信，因为有两波人在拿，所以应该是维护一个A_empty和A_full，B_empty和B_full，每次看信箱，先看箱子上有没有锁，然后再操作，和银行那个题目不一样的是，这里没有两个A共用的某一个资源，同时存在先后顺序，形成了同步，所以，不会在A处用P上锁，然后在B处执行，用V来释放这种结构

解

CoBegin
A {
	while(1) {
		P(A信箱里有没有信？如果有-1，如果没有，等待)
		//通过检查，现在打开信箱
		P(A的锁)
		//取出信
		V(A的锁)
		V(A箱的空位+1)
		回答问题，然后放入B箱
		P(B箱有没有满？如果满，等待)
		//通过检查，现在打开信箱
		P(B的锁)
		//放入信
		V(B的锁)
		V(B箱的信+1)
	}
}
 
B {
while(1) {
    P(B信箱里有没有信？如果有-1，如果没有，等待)
    //通过检查，现在打开信箱
    P(B的锁)
    //取出信
    V(B的锁)
    V(B箱的空位+1)
    回答问题，然后放入A箱
    P(A箱有没有满？如果满，等待)
    //通过检查，现在打开信箱
    P(A的锁)
    //放入信
    V(A的锁)
    V(A箱的信+1)
  }
}

我们现在来定义变量，把这个中文描述去掉

semaphore A_lock = 1, B_lock = 1, A_empty = M-x, A_full = x, B_empty = N-y, B_full = y;
 
CoBegin {
    A {
		 while(1) {
				 P(A_full); //A中有信，我要申请
				 P(A_lock);//申请到了，上锁查看
				 从A中取出信件
				 V(A_lock);//取出信件后，解锁
				 V(A_empty);//取出信件后，空位+1
				 回答问题，然后放入B箱
				//申请B的空位
				 P(B_empty);
				 P(B_lock);
				 放入信
				 V(B_lock);
				 V(B_full);
		 }
    }
 
B {
  while(1) {
    P(B_full);
    P(B_lock);
    从B中取出信
    V(B_lock);
    V(B_empty);
    回答问题，然后放入A箱
    P(A_empty);
    P(A_lock);
    放入信
    V(A_lock);
    V(A_full);
  }
}
 
CoEnd

Graph View

Backlinks