【操作系统习题】三个并发进程 R、M、P 共享一个可循环使用的缓冲区 B

习题题目

今有三个并发进程 R、M、P，它们共享了一个可循环使用的缓冲区 B，缓冲区 B 共有 N 个单元。进程 R 负责从输入设备读信息，每读一个字符后，把它存放在缓冲区 B 的一个单元中；进程 M 负责处理读入的字符，若发现读入的字符中有空格符，则把它改成“，”；进程 P 负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程 P 取出后，则又可用来存放下一次读入的字符。请用 P、V 操作为同步机制写出它们能正确并发执行的程序。

一、解题思路

本题和一个经典进程同步问题—— “生产者——消费者” 问题相似，“生产者——消费者” 描述了一组生产者向一组消费者提供产品，它们共享一个有界缓冲区，生产者向其中投放产品，消费者从中取得产品。以此基本问题为启发思路，对上面的并发进程 “R、M、P” 问题我想到了可以设置如下几个同步信号量。

• 空缓冲区的数目，用 empty 表示，其初值为 N
• 满缓冲单元的数目（即字符数目），用 full 表示，其初值为 0
• 存在缓存区但未处理的字符数目，用 undeal 表示，其初值为 0（这里的 undeal 这个单词可能不符合英语语言，为了便于理解，用了这个单词，若有更好的意见，请在评论区回复）
• 存在缓存区且已处理的字符数目，用 dealed 表示，其初值为 0

在本题目中，有三个进程 R、M、P 在执行时都要对有界缓冲区进行操作，也就是说它们需要共享有界缓冲区，因此对有界缓冲区的使用必须互斥，为此还需要设置一个互斥信号量 mutex，其初值为 1。

二、代码

该并发进程 “R、M、P” 问题的同步描述如下：

semaphore full=0;               /* 满缓冲单元的数目 */
semaphore empty=N;              /* 空缓冲单元的数目 */
semaphore undeal=0;             /* 未处理的字符数目 */
semaphore dealed=0;             /* 已处理的字符数目 */
semaphore mutex=1;              /* 对有界缓冲区进行操作的互斥信号量 */

main()
{
	cobegin
		R();
		M();
		P();
	coend
}
R()
{
	while (true)
	{
		读一个字符;
		P(empty);
		P(mutex);
		将一个字符送入缓冲区;
		V(mutex);
		V(undeal)
		V(full);
	}
}
M()
{
	while (true)
	{
		P(undeal);
		P(mutex);
		处理字符;
		V(mutex);
		V(dealed);
	}
}
P()
{
	while (true)
	{
		P(full)
		P(dealed);
		P(mutex);
		从缓冲区中取一个字符;
		V(mutex);
		V(empty);
		打印一个字符;
	}
}

结语

欢迎大家评论留言讨论，若有不当和错误的地方也欢迎大家指出，共同进步！

引用

• [1] 郑鹏，曾平，金晶. 计算机操作系统（第二版）[M]. 武汉：武汉大学出版社，2014：56-58.