在多道程序环境下，进程同步问题十分重要，也是相当有趣的问题，因而吸引了不少学者对它进行研究，由此而产生了一系列经典的进程同步问题，其中较有代表性的是“生产者—消费者”问题、“读者—写者问题”、“哲学家进餐问题”等等。

 

1.生产者-消费者问题

问题：一组生产者向一组消费者提供产品，他们共享一个有界缓冲区，生产者向其中投入产品，消费者从中取走产品。只有缓冲区没满时，生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，或一个消费者从中取出消息。

分析：假定在生产者和消费者之间的公用缓冲池中具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。

问题描述如下：

P(full)/P(empty)与 P(mutex)的顺序不可颠倒，必须先对资源信号量进行P 操作，再对互斥信号量进行P 操作，否则会导致死锁。例如，此时缓冲区已满，而生产者先P (mutex)，取得缓冲池访问权，再 P (empty),此时由于缓冲池已满，empty=0,导致P (empty)失败，生产者进程无法继续推进，始终掌握缓冲池访问权无法释放，因而消费者进程无法取出产品，导致死锁。

 

2.读者一写者问题

问题：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作前，应让已有的读者和写者全部退出。

• 读者优先

分析：两个进程，即读者和写者。写者是比较简单的，它和任何进程互斥，用互斥信号量的P操作、V操作即可解决。读者的问题比较复杂，它必须实现与写者互斥的同时还要实现与其他读者的同步，因此，仅仅简单的一对P操作、V操作是无法解决的。那么，在这里用到了一个计数器，用它来判断当前是否有读者读文件。当有读者的时候写者是无法写文件的，此时读者会一直占用文件，当没有读者的时候写者才可以写文件。同时这里不同读者对计数器的访问也应该是互斥的。

代码如下：

在上面的算法中，读进程是优先的，也就是说，当存在读进程时，写操作将被延迟，并且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式下，会导致写进程可能长时间等待，且存在写进程“饿死”的情况。

• 写者优先：

若要实现真正的写者优先（即当写者和读者同时等待时，后续写者到达时可以插队到等待的读者之前，只要等待队列中有写者，不管何时到达，都优先于读者被唤醒），则需要增设额外的信号量进行控制。

代码如下：

当一个写进程访问文件时，若先有一些读进程要求访问文件，后有另一个写进程要求访问文件，则当前访问文件的进程结束对文件的写操作时，会是一个读进程而不是一个写进程占用文件（在信号量w 的阻塞队列上，因为读进程先来，因此排在阻塞队列队首，而V操作唤醒 进程时唤醒的是队首进程），所以说这里的写优先是...

课后习题

 

1. 【2010统考真题】设与某资源关联的信号量初值为3，当前值为1.若M表示该资源的可用个数，N表示等待该资源的进程数，则M，N分别是（  ）。

A.0，1          B.1，0          C.1，2           D.2，0

【答案】B

【解析】信号量表示相关资源的当前可用数量。当信号量K >0时，表示还有K个相关资源可用，所以该资源的可用个数是1。而当信号量时 ，表示有|K|个进程在等待该资源。由于资源有剩余，可见没有其他进程等待使用该资源，因此进程数为0。

 

2. 有三个进程共享同一程序段，而每次只允许两个进程进入该程序段，若用PV操作同步机制，则信号量S 的取值范围是（ ）。

A. 2, 1 , 0 , -1                         B.3, 2, 1, 0

C.2, 1, 0, -1, -2                         D. 1, 0, -1, -2

【答案】A

【解析】因为每次允许两个进程进入该程序段，信号量最大值取2。至多有三个进程申请，则信号量最小为-1,所以信号量可以取2 ,l ,0 ,-1。

 

3. 以下关于管程的叙述中，错误的是（ ）。

A. 管程是进程同步工具，解决信号量机制大量同步操作分散的问题

B. 管程每次只允许一个进程进入管程

C. 管程中signal操作的作用和信号量机制中的V 操作相同

D. 管程是被进程调用的，管程是语法范围，无法创建和撤销

【答案】C

【解析】管程的signal操作与信号量机制中的V 操作不同，信号量机制中的V操作一定会改变信号量的值S = S+1。而管程中的signal操作是针对某个条件变量的，若不存在因该条件而阻塞的进程, 则signal不会产生任何影响。

 

4. 对信号量S 执行P 操作后，使该进程进入资源等待队列的条件是（ ）。

A. S.value < 0            B. S.value <= 0         C. S.value > 0           D. S.value >= 0

【答案】A

【解析】参见记录型信号量的解析。此处极易出S.value的物理概念题，现总结如下：

S.value>0, 表示某类可用资源的数量。每次P 操作，意味着请求分配一个单位的资源。

S.value< = 0 ,表示某类资源已经没有，或者说还有因请求该资源而被阻塞的进程。

S.value <= 0 时的绝对值，表示等待进程数目。

一定要看清题目中的陈述是执行P 操作前还是执行P操作后。

 

5.【2010统考真题】进程和进程的共享变量定义及其初值为:

boolean flag[2];

int turn=0;

flag[0]=false; flag[ 1 ] =false;

若进程和进程访问临界资源的类C代码实现如下：

void P0 () //进程 P0                      void Pl () //进程 Pl
{                                         {
    while(true)                               while(true)
    {                                         {
        flag[0]=true;turn=l;                       flag[1]=true;turn=0;                   
        while(flag[1]&&(turn==l));                 while(flag[0]&&(turn==0))

        临界区；                                    临界区；
        flag[0]=false;                             flag[1]=false;
    }                                          }
}                                          }

则并发执行进程和进程时产生的情况是（  ）。

A. 不能保证进程互斥进入临界区，会出现“饥饿”现象

B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象

C. 能保证进程互斥进入临界区，会出现“饥饿”现象

D. 能保证进程互斥进入临界区，不会出现“饥饿”现象

【答案】D

【解析】这是Peterson算法的实际实现，保证进入临界区的进程合理安全。 该算法为了防止两个进程为进入临界区而无限期等待，设置了变量turn，表示不允许进入临 界区的编号，每个进程在先设置自己的标志后再设置turn标志，不允许另一个进程进入。这时， 再同时检测另一个进程状态标志和不允许进入表示，就可保证当两个进程同时要求进入临界区时只允许一个进程进入临界区。保存的是较晚的一次赋值，因此较晚的进程等待，较早的进程进入。先到先入，后到等待，从而完成临界区访问的要求。

其实这里可想象为两个人进门，每个人进门前都会和对方客套一句“你走先”。若进门时没别人，就当和空气说句废话，然后大步登门入室；若两人同时进门，就互相先请，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大地进门。

 

6. 【2016统考真题】进程和进程均包含并发执行的线程，部分伪代码描述如下所示。

下列选项中，需要互斥执行的操作是（  ）。

A. a=1与a=2     B. a=x与b=x      C. x+=1与x+=2        D. x+=1与x+=3

【答案】C

【解析】中对a进行赋值，并不影响最终的结果，因此a = l与 a = 2 不需要互斥执行；a = x 与b = x 执行先后不影响a与b的结果，无须互斥执行；x + = l与x+=2执行先后会影响x的结果，需要互斥执行；中的x和中的x是不同范围中的x , 互不影响，不需要互斥执行。

 

7. 【2011统考真题】有两个并发执行的进程和进程，共享初值为1的变量x。对 x 加 1, 对x减1。加1和减1操作的指令序列分别如下:

//加1操作                               //加1操作
load R1，x //取x到寄存器R1               load R2，x //取x到寄存器R2
inc R1                                  inc R2
store x，R1 //将R1的内容存入x            store x，R1 //将R1的内容存入x

两个操作完成后，x 的值（ ）。

A.可能为-1或3                            B.只能为1

C.可能为0，1或2                          D.可能为-1，0，1或2

【答案】C

【解析】将中的3 条语句依次编号为1,2,3,将中的3 条语句依次编号为4, 5, 6 ,则依次执行1,2,3,4, 5, 6 得结果1 , 依次执行1,2, 4, 5, 6, 3 得结果2 , 依次执行4,5, 1,2, 3, 6得结果0。结果-1 不可能得出。

 

8.【2016统考真题】使用TSL （ Test and Set Lock） 指令实现进程互斥的伪代码如下所示。

do {
    …
    while(TSL(&lock)); 
    critical section; 
    lock=FALSE;
    …
} while(TRUE);

下列与该实现机制相关的叙述中，正确的是（ ）。

A. 退出临界区的进程负责唤醒阻塞态进程

B. 等待进入临界区的进程不会主动放弃CPU

C. 上述伪代码满足“让权等待”的同步准则

D. while（TSL（&lock））语句应在关中断状态下执行

【答案】B

【解析】当进程退出临界区时置lock为FALSE，会负责唤醒处于就绪态的进程，选项A 错误。等待进 入临界区的进程会一直停留在执行while(TSL(&lock))的循环中，不会主动放弃C PU ,选项B 正确。让权等待，即进程不能进入临界区时，应立即释放处理器，防止进程忙等待。通过B 选项的分析发现，上述伪代码并不满足“让权等待”的同步准则，选项C 错误。while(TSL(&lock))在关中断状态 下执行时，若 TSL(&lock)一直为true，不再开中断，则系统可能会因此终止，选项D 错误。

 

9. 【2018统考真题】属于同一进程的两个线程threadl和 血 ead2并发执行，共享初值为0 的全局变量x。thread 1和 thread2实现对全局变量x 加 1 的机器级代码描述如下。

在所有可能的指令执行序列中，使 X的值为2 的序列个数是（ ）。

A. 1           B. 2            C. 3             D. 4

【答案】B

【解析】仔细阅读两个线程代码可知, thread1和 thread2均是对x 进行加1操作，x 的初始值为0 , 若要使得最终x = 2 , 只能先执行完thread1再执行thread2, 或先执行完thread2再执行thread1， 因此仅有2 种可能，选 B。

 

10. 【2018统考真题】若 x 是管程内的条件变量，则当进程执行x.wait（）时所做的工作是（ ）。

A. 实现对变量x 的互斥访问

B. 唤醒一个在乂上阻塞的进程

C. 根据x 的值判断该进程是否进入阻塞态

D. 阻塞该进程，并将之插入x 的阻塞队列中

【答案】D

【解析】“条件变量”是管程内部说明和使用的一种特殊变量，其作用类似于信号量机制中的“信号量”,都用于实现进程同步。需要注意的是，在同一时刻，管程中只能有一个进程在执行。若进程A 执行了 x.wait()操作，则该进程会阻塞，并挂到条件变量x 对应的阻塞队列上。这样，管程的使用权被释放，就可以有另一个进程进入管程。若进程B 执行了 x.signal()操作，则会唤醒x 对应的阻塞队列 的队首进程。在 Pascal语言的管程中，规定只有一个进程要离开管程时才能调用signal()操作。

 

11. 【2018统考真题】在下列同步机制中；可以实现让权等待的是（ ）。

A. Peterson 方法   B. swap 指令   C .信号量方法   D. TestAndSet指令

【答案】C

【解析】硬件方法实现进程同步时不能实现让权等待，因此B、D 错 Peterson算法满足有限等待但不满足让权等待，因此A 错误；记录型信号量由于引入阻塞机制，消除了不让权等待的情况，因此C正确。

 

12. 【2009统考真题】三个进程、、互斥使用一个包含N ( N > 0 ) 个单元的缓冲区。每次用produce()生成一个正整数并用put()送入缓冲区某一空单元；每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义(要求用伪代码描述)。

【解析】

互斥资源：缓冲区只能互斥访问，因此设置互斥信号量mutex。

同步问题：P1、P2因为奇数的放置与取用而同步，设同步信号量odd；P1、P3因为偶数的放置与取用而同步，设置同步信号量even；P1、P2、P3因为共享缓冲区，设同步信号量empty,初值为N。 程序如下:

 

13. 【2013统考真题】某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一人通过。参观者的活动描述如下:

cobegin 
参观者进程i： 
{
    …
    进门。
    …
    参观；
    …
    出门；
    …
}
coend 

请添加必要的信号量和 P, V ［或 wait(),signal()］操作，以 实现上述过程中 的互斥与同步。 要求写出完整的过程，说明信号量的含义并赋初值。

【解析】

出入门一次仅允许一个人通过，设置互斥信号量mutex，初值为1。博物馆最多可同时容纳 500 人, 因此设置信号量empty，初值为500。

Semaphore empty=500; //博物馆可以容纳的最多人数 
Semaphore mutex=l; //用于出入口资源的控制 
cobegin
参观者进程i：
{
    …
    P(empty) ; //可容纳人数减1 
    P (mutex) ; //互斥使用门1
    进门；
    V (mutex);
    参观；
    P (mutex) ; //互斥使用门
    出门；
    V (mutex); 
    V (empty) ; //可容纳人数增1
    …
}
coend

 

14. 【2011统考真题】某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时,若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程

描述如下：

cobegin 
{
    process 顾客i
    {
        从取号机获取一个号码;
        等待叫号；
        获取服务；
    }
    process 营业员
    {
        while(TRUE)
        {
            叫号；
            为客户服务；
        }
    }
} coend

请添加必要的信号量和P，V [或wait(), signal()] 操作，实现上述过程中的互斥与同步。 要求写出完整的过程，说明信号量的含义并赋初值。

【解析】

互斥资源：取号机(一次只有一位顾客领号)，因此设置互斥信号量mutex。

同步问题：顾客需要获得空座位等待叫号。营业员空闲时，将选取一位顾客并为其服务。空座位的有、无影响等待顾客的数量，顾客的有无决定了营业员是否能开始服务，因此分别设置信号量empty和full来实现这一同步关系。另外，顾客获得空座位后，需要等待叫号和被服务。 这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量service来完成这一同步过程。

 

15. 【2014统考真题】系统中有多个生产者进程和多个消费者进程，共享一个能存放1000件产品的环形缓冲区（初始为空）。缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；缓冲区未空时，消费者进程可从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。请使用信号量P, V （ wait(),signal() ） 操作实现进程间的互斥与同步，要求写出完整的过程， 并说明所用信号量的含义和初值。

【解析】这是典型的生产者和消费者问题，只对典型问题加了一个条件，只需在标准模型上新加一个信号量，即可完成指定要求。

设置4 个变量mutex 1, mutex2, empty和full，mutex 1用于控制一个消费者进程在一个周期（10次）内对缓冲区的访问，初值为1；mutex2用于控制进程单次互斥地访问缓冲区，初值为1； empty 代表缓冲区的空位数，初值为1000； full代表缓冲区的产品数，初值为0 , 具体进程描述如下：

 

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

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

【解析】

 

17. 【2017统考真题】某进程中有3 个并发执行的线程thread1, thread2和 thread3, 其伪代码如下所示。

请添加必要的信号量和P, V ［或 wait(), signal()］ 操作，要求确保线程互斥访问临界资源, 并且最大限度地并发执行。

【解析】先找出线程对在各个变量上的互斥、并发关系。若为一读一写或两个都为写，则为互斥关系。每个互斥关系都需要一个信号量进行调节。

互斥代码如下:

 

18.【2019统考真题】有n(n > 3 ) 名哲学家围坐在一张圆桌边，每名哲学家交替地就餐和思考。在圆桌中心有m (m >=l ) 个碗，每两名哲学家之间有一根筷子。每名哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P, V操作［wait(), signal()操作］描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

【解析】本题可以用碗这个限制资源来避免死锁：当碗的数量m小于哲学家的数量n时，可以直接让碗的资源量等于m , 确保不会出现所有哲学家都拿一侧筷子而无限等待另一侧筷子进而造成死锁的情况；当碗的数量m大于等于哲学家的数量n时，为了让碗起到同样的限制效果，我们让碗的资源量等于n-1 , 这样就能保证最多只有n-1名哲学家同时进餐，所以得到碗的资源量为min{n-l, m}。在进行PV操作时，碗的资源量起限制哲学家取筷子的作用，所以需要先对碗的资源量进行P 操作。具体过程如下：