操作系统期末复习大题---经典进程的同步问题

一、经典进程的同步问题

1. 利用记录型信号量解决生产者—消费者问题

执行流程：

”生产者-消费者”问题模型代码框架如下：

注意：

小结：

复习典型例题：

解答：

2. 利用AND信号量解决生产者——消费者问题

代码框架：

生产者消费者模型举例

例一、

例二、

例3：父亲-母亲-儿子-女儿两个苹果或桔子

例4

练一练（2009年考研真题）

题目：

分析：考虑题目中的互斥和同步问题

答案：

例题：

分析：

解答

练一练（2014年真题）

2.5.2哲学家进餐问题

学以致用（2019真题）

2.5.3 读者-写者问题

补充：吸烟者问题

一、经典进程的同步问题

重点内容：

•掌握“生产者-消费者”问题模型

•掌握“哲学家进餐”问题模型

•掌握“读者-写者”问题模型

1. 利用记录型信号量解决生产者—消费者问题

执行流程：

”生产者-消费者”问题模型代码框架如下：

semaphone mutex=1,empty=n,full=0;
item buffer[n];
int in=0, out = 0;
main(){
   cobegin
   { producer{  
        produce an item nextp;
        wait(empty);
        wait(mutex);
        buffer(in)=nextp;
        in=(in+1) % n;
        signal(mutex);   //释放使用权
        signal(full);    //唤醒消费者
      }
    consumer
      {
        wait(full);
        wait(mutex);
        nextc=buffer(out);
        out= (out+1) % n;
        signal(mutex);    //释放使用权
        signal(empty);    //唤醒生产者
        consume the item in nextc;
      }
   }coend
}

注意：

在有多个信号量同时存在的情况下，WAIT操作往往是不能颠倒顺序的，必须先对资源信号量进行WAIT操作，再对互斥信号量进行WAIT操作，这样可以在占用共享资源的访问权时保证有资源可用，不然会导致产生占用使用权而无资源可用的“死等”现象。

小结：

复习典型例题：

解答：

2. 利用AND信号量解决生产者——消费者问题

代码框架：

semaphone mutex=1,empty=n,full=0;
item buffer[n];
int in=0, out = 0;
main(){
   cobegin
   { 
     producer
      {  
        produce an item nextp;
        wait(empty,mutex);
        buffer(in)=nextp;
        in=(in+1) % n;
        signal(mutex,full);
      }
    consumer
      {
        wait(full,mutex);
        nextc=buffer(out);
        out= (out+1) % n;
        signal(mutex,empty); 
        consume the item in nextc;
      }
   }coend
}

问题推广：

一组生产者，一组消费者，公用 n个环形缓冲区

思考：如何高效的存取，生产者之间公用一个in指针，消费者之间公用一个out指针，如何设置信号量？

empty：表示缓冲区是否为空，初值为n; full:表示缓冲区是否为满，初值为0。

mutex1：生产者之间的互斥信号量，初值为1;mutex2：消费者之间的互斥信号量，初值为1。

设缓冲区的编号为1～n-1，定义两个指针in和out，分别是生产者进程和消费者进程使用的指针，指向下一个可用的缓冲区。

第三种情况，可以理解成有多间牛奶生产厂家，如蒙牛，达能，光明等，消费者也不只小明一人，有许许多多消费者。不同的牛奶生产厂家生产的商品可以放在不同的零售分店中销售，而不同的消费者可以去不同的分店中购买。当某一分店已放满某个厂家的商品时，下一个厂家只能把商品放在下一间分店。所以在这种情况中，生产者与消费者存在同步关系，而且各个生产者之间、各个消费者之间存在互斥关系,他们必须互斥地访问缓冲区。

生产者消费者模型举例

例一、

分析：爸爸和儿子两个进程相互制约，爸爸进程执行完即往盘中放入苹果后，儿子进程才能执行即吃苹果。因此该问题为进程间的同步问题。

例二、

例2. 桌上有一空盘，允许存放一只水果，爸爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用。

请用Wait/Signal原语实现爸爸、儿子、女儿三个并发进程的同步。

设置三个信号量：

Semaphore S=1; //S 表示盘子是否为空；
Semaphore S1=0; //S1表示盘中是否有苹果；
Semaphore S2=0; //S2表示盘中是否有桔子；

此问题还可继续推广：父亲-母亲-儿子-女儿一个苹果或桔子问题；父亲-母亲-儿子-女儿两个苹果或桔子问题；

例3：父亲-母亲-儿子-女儿两个苹果或桔子

分析：盘子为互斥资源，因可以放2个水果，empty初值为2；且需设置互斥信号量mutex=1

还可进一步推广：两个儿子，两个女儿的情况！

semaphore：s=2(可用位置); s1=0(苹果数); s2=0(桔子数);mutex=1;

爸爸：wait(s); wait(mutex);放苹果; signal(mutex); signal(s1);

妈妈：wait(s); wait(mutex); 放桔子; signal(mutex); signal(s2);

儿子：wait(s2); wait(mutex); 取桔子; signal(mutex); signal(s);

女儿：wait(s1); wait(mutex); 取苹果; signal(mutex); signal(s);

例4

例4：某幼儿园举行趣味活动，每两个小朋友一组。重复做如下活动：一个小朋友负责用一个小桶在A沙堆取沙子，然后倒入一大盆中，另一小朋友负责用一个小桶从大盆中取沙子倒入B沙堆。大盆最多能装10桶沙子，且在大盆中取沙子和倒沙子不能同时进行。试用信号量操作描述这两个小朋友的同步过程。

empty：表示大盆是否为空，初值为10。

full ：表示大盆是否为满，初值为0。

mutex: 表示可否对大盆进行操作，初值为1.

解答：

练一练（2009年考研真题）

题目：

三个进程P1、P2、P3互斥使用一个包含N个单元的缓冲区。P1每次用produe()产生一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步和互斥活动，并说明所定义信号量的含义（要求用伪代码描述）。

分析：考虑题目中的互斥和同步问题

• 互斥问题：缓冲区只能互斥，设置互斥信号量 mutex ;

• 同步问题 : P1 、 P2 因为奇数的放置和取用同步，设置信号量 odd ； P1 、 P3 因为偶数的放置与取用取得同步，设置同步信号量 even ； P1 、 P2 、 P3 因为共享缓冲区，设置同步信号量 empty.

信号量定义：

semaphore mutex=1;//缓冲区操作互斥信号量
semaphore odd=0,even=0;//奇数偶数同步信号量
semaphore empty=N;//空缓冲区个数

答案：

例题：

某寺庙有小和尚、老和尚若干。

• 有一个水缸，由小和尚打水入缸供老和尚饮用。 水缸可容纳 10 桶水。

• 水取自同一井中。 每次只能容纳一个桶取水 。 水桶总数为 3 个 。每次入、取水仅为一桶， 且不可同时进行 。

• 给出有关取水、入水的算法描述。

分析：

semaphore empty=10;// 表示缸中目前还能装多少桶水，初始时能装10桶水

semaphore full=0;// 表示缸中有多少桶水，初始时缸中没有水

semaphore buckets=3;// 表示有多少只空桶可用，初值为3

semaphore mutex_well=1;// 用于实现对井的互斥操作

semaphore mutex_bigjar=1; // 用于实现对缸的互斥操作

解答

练一练（2014年真题）

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

分析：

semaphore empty=1000;//空缓冲区的个数
semaphore full=0;//缓冲区的产品数
semaphore mutex1=1;//控制消费者进程一个周期内互斥访问
semaphore muter2=1;//进程单次互斥访问临界区

解答：

2.5.2哲学家进餐问题

前面描述了多个进程竞争一个临界资源的情况及通用模板，那么，对于多个进程竞争多个临界资源的情况，又该如何描述呢？哲学家就餐问题就是对这类问题的一个抽象！

思考：如果同时拿起左筷子？

死锁解决方法：

解决方法1：

解决方法2：

解决方法3：

学以致用（2019真题）

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

信号量bowl用于协调哲学家对碗的使用， bowl<n，确保不死锁，

即至少保证有一个人拿不到碗，那么就能保证至少有一个人能拿到左右的筷子。

semaphone bowl=min(n-1,m);

信号量chopsticks用于协调哲学家对筷子的使用，两个哲学家之间的筷子数量为1

semaphone chopsticks[n]={1,1,...,1};

2.5.3 读者-写者问题

对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个。

“读－写”互斥，
“写－写”互斥，
"读－读"允许

补充：吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉完成了，供应者就会放另外两种材料在桌上，这种过程一直重复（三个抽烟者轮流地抽烟）