经典同步问题

经典进程同步问题 经典进程同步问题是从进程并发执行中归纳的典型例子。主要的经典同步问题有生产者-消费者问题、读者-写者问题、哲学家进餐问题等。 生产者-消费者问题（producer-consumer Problem ） 生产者-消费者问题是最著名的同步问题，它描述一组生产者（P1 ……Pm）向一组消费者（C1……Cq）提供消息。它们共享一个有界缓冲池（bounded buffer pool）,生产者向其中投放消息，消费者从中取得消息，如下图所示。生产者-消费者问题是许多相互合作进程的一种抽象。

生产者-消费者问题 P1 Pm C1 Cq B0 B1 …. …... ……… Bn-1 假定缓冲池中有n个缓冲区，每个缓冲区存放一个消息。由于缓冲池是临界资源，它只允许一个生产者投入消息，或者一个消费者从中取出消息。即生产者之间、生产者与消费者之间、消费者之间都必须互斥使用缓冲池。所以必须设置互斥信号量mutex，它代表缓冲池资源，它的数值为1。

生产者-消费者问题 生产者和消费者二类进程之间应满足下列二个同步条件： 只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。 只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。 为了满足第一个同步条件，设置一个同步信号量full，它代表的资源是缓冲区满，它的初始值为0，它的值为n时整个缓冲池满。 为了满足第二个同步条件，设置另一个同步信号量empty，它代表的资源是缓冲区空，它的初始值为n，表示缓冲池中所有缓冲区空。

生产者-消费者问题 Shared data semaphore full=0, empty=n, mutex=1; main() cobegin{ }coend Pi //生产者进程 do { … produce an item in nextp P(empty); P(mutex); add nextp to buffer V(mutex); V(full); } while (1); Ci //消费者进程 do { P(full); P(mutex); … remove an item from buffer to nextc V(mutex); V(empty); consume the item in nextc } while (1);

读者-写者问题The Readers-Writers Problem 一个数据集（如文件）如果被几个并行进程所共享： 有些进程只要求读数据集内容，它称读者 一些进程则要求修改数据集内容，它称写者 几个读者可以同时读些数据集，而不需要互斥 一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥。 信号量及变量设置： 写者与写者及读者需要互斥，用互斥信号量wrt表示，初值为1 readcount变量来记录读者数，初值为0 由于readcount是读者间共享变量，属于临界资源，它也需互斥，设置互斥信号量mutex，初值为1。

读者写者问题： Shared data semaphore mutex=1, wrt=1; int readcount = 0；// readcount变量来记录读者数 main（） cobegin{ Writer process： while（1）{ wait(wrt); … writing is performed signal(wrt); }

读者写者问题： Reader Process： while（1）{ readcount++; if (readcount == 1) wait(mutex); readcount++; if (readcount == 1) wait(wrt); signal(mutex); … reading is performed readcount--; if (readcount == 0) signal(wrt); signal(mutex)； } }coend

哲学家进餐问题Dining-Philosophers Problem 问题描述（由Dijkstra首先提出并解决） ： 5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支； 哲学家的动作包括思考和进餐，进餐时需要同时拿起他左边和右边的两支筷子，思考时则同时将两支筷子放回原处。 如何保证哲学家们的动作有序进行？如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子；

Dining-Philosophers Problem Shared data semaphore chopstick[5]; Initially all values are 1

The structure of Philosophers i Philosopher i: do { wait(chopstick[i]) wait(chopstick[(i+1) % 5]) … eat signal(chopstick[i]); signal(chopstick[(i+1) % 5]); think } while (1);

哲学家就餐问题讨论 为防止死锁发生可采取的措施： 最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿 每个哲学家拿起第1根筷子一定时间后，若拿不到第2根筷子，再放下第1根筷子。

例题分析： 2、对信号量S执行P（或wait）操作后，使进程进入等待队列的条件是 。 1、6个进程共享某一临界资源，则互斥信号量的取值范围为 。 0~1 B. 0~-6 C. 0~ -5 D. 1~ -5 2、对信号量S执行P（或wait）操作后，使进程进入等待队列的条件是 。 Ａ. S.value < 0 B. S.value <= 0 Ｃ. S.value > 0 D. S.value >= 0 3、操作系统在使用信号量解决同步与互斥问题中，若P（或wait）、V（或signal）操作的信号量S初值为2， 当前值为-3， 则表示有 等待进程。 A. 0个 B. 1个 C. 2个 D. 3个 4、设有4个进程共享一程序段，而每次最多允许２个进程进入该程序段，则信号量的初值是____ Ａ、4 Ｂ、2 Ｃ、1 Ｄ、0

例题分析： 5、下列哪一个问题只包含进程互斥问题？ A． 田径场上的接力比赛 B． 两个进程都要使用打印机 C． 一个生产者和一个消费者通过一个缓冲区传递产品 D． 公共汽车上司机和售票员的协作 6、在9个生产者、6个消费者共享容量为8的缓冲器的生产者-消费者问题中，互斥使用缓冲器的信号量mutex的初始值为 。 A. 1 B. 6 C. 8 D. 9 7、有一个计数信号量S，若干个进程对S进行了28次P操作和18次V操作后，信号量S的值为0，然后又对信号量S进行了3次V操作。请问此时有多少个进程等待在信号量S的队列中？ A. 2 B. 0 C. 3 D. 7 8、假设一个正在运行的进程对信号量S进行了P（WAIT）操作后，信号量S的值变为-1，此时该进程将 。 A. 转为等待状态 B. 转为就绪状态 C. 继续运行 D. 终止

End