第二章 进程管理
（三） 进程同步 5、经典同步问题 1、生产者—消费者问题
生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消 费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。
问题1：设某计算进程CP和打印进程IOP共用一个单缓冲区，CP进程负责不断地计算数据并送入缓冲区T中，IOP进程负责不断地从缓冲区T中取出数据去打印。
通过分析可知，ＣＰ、ＩＯＰ必须遵守以下同步规则：
(1)当ＣＰ进程把计算结果送入缓冲区时，IOP进程才 能从缓冲区中取出结果去打印; (2)当IOP进程把缓冲区中的数据取出打印后，ＣＰ进程才能把下一个计算结果送入缓冲区.
(3)为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。
两个进程的同步可以描述如下：
问题2：一组生产者通过具有N个缓冲区的共享缓冲池向一组消费者提供数据。
生产者进程 缓冲池 消费者进程 1 ┇ ┇ i ┇ ┇
问题分析”：
为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用empty表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用full表示，初值为０。
由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为１。
问题的解：
注意：在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对的出现
对资源信号量empty和full的P和V操作，同样需要成对地出现，但它们分别处于不同的程序中。在每个程序中的多个P操作顺序不能颠倒。先同步后互斥。
2、哲学家就餐问题
有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。每个哲学家的行为是思考，感到饥饿，然后吃通心粉。为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。 1、为防止死锁发生可采取的措施：
最多允许4个哲学家同时坐在桌子周围；仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（AND信号量）；给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之。
设chopstick [5]为5 个信号量，初值为均1。设信号量S ，初值为4 S用于封锁第5个哲学家
给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之； 设chopstick [5]为5 个信号量，初值均为1； Philosopher i： if [i mod 2 =0] then repeat { 思考； P(chopstick[(i+1) mod 5])； if [i mod 2 =1] then P(chopstick[i]); {P(chopstick[i]); P(chopstick[(i+1) mod 进食； 5])； V(chopstick[(i+1) mod 5])； 进食； V(chopstick[i]); V(chopstick[i]); V(chopstick[(i+1) } mod 5])； Until false; } 3、读者——写者问题
（1）有两组并发进程:
读者和写者,共享一组数据区 （2）要求：
允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作
读者写者问题的解法：
设有两个信号量wmutex=1，rmutex=1 另设一个全局变量readcount =0
wmutex用于读者和写者、写者和写者之间的互斥
readcount表示正在读的读者数目
rmutex用于对readcount 这个临界资源的互斥访问 读者： 写者： repeat repeat P(rmutex); P(wmutex); if (readcount=0) then 写; P (wmutex); V(wmutex); readcount := readcount+1; until false; V(rmutex); 读; P(rmutex); readcount:= readcount-1; if (readcount=0) then V(wmutex); V(rmutex); until false;
同步与互斥的解题思路
①分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。
②对互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，通常只设置一个互斥信号量，且初值为1，代表一次只允许一个进程对临界资源访问。
③对同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。
④在每个进程中用于实现互斥的PV操作必须成对出现；用于实现同步的PV操作也必须成对出现，但可以分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的P操作，则其顺序不能颠倒，必须先执行对同步信号量的P操作，再执行对互斥信号量的P操作，但V操作的顺序没有严格要求。
同步与互斥的解题步骤
（1）确定进程。包括进程的数量、进程的工作内容，可以用流程图描述。
（2）确定同步互斥关系。根据是否使用的是临界资源，还是处理的前后关系，确定同步与互斥，然后确定信号量的个数、含义，以及对信号量的P、V操作。 （3）用类C语言描述同步或互斥算法。
第二章 进程同步举例
例题1：下面是两个并发执行的进程，他们能正确运行吗？若不能，请举例说明，并改正。
int x; Process_P1{ int y,z; x=1; y=0; if(x>=1) y=y+1; z=y; } Process_P2{ int t,u; x=0; t=0; if(x<=1) t=t+2; u=t; } 例题1答案：不能正确执行。X是一个临界资源，没有保护 。
int x; Process_P2{ Semaphore mutex=1;//访问X的互斥信号 int t,u; 量 wait(mutex) Process_P1{ int y,z; x=0; wait(mutex); t=0; x=1;y=0; if(x<=1) if(x>=1) y=y+1; t=t+2; signal(mutex); signal(mutex) z=y； u=t; } } 例题2：生产者 — 消费者问题演变。
一个 buffer ，一个生产者，一个消费者，生产者只生产一个东西，消费者只进行一次消费，即：生产者只进行一次 putdata 操作，消费者只进行一次 getdata 操作。 例题2答案： var full:semaphore:=0; consumer: buffer: array [ 1 ] of item; begin producer: P (full); begin getdata; putdata ； end V (full); end 例题3：一个 buffer ，多个生产者，多个消费者，多个生产者和消费者都在不断地存取 buffer ，即生产者不断地进行 putdata 操作，消费者不断地进行 getdata 操作。
例题4：三个进程P1 P2 P3互斥使用一个包含N（N>0)个单元的缓冲区。P1每次用
produce()生成一个正整数并用put()送入缓冲区某一空单元中； P2每次用getodd()从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三