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

发布时间:2024年01月06日

目录

一、经典进程的同步问题

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

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

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


生产者消费者模型举例

例一、

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

?


例二、?

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

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

设置三个信号量:

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

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

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

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

还可进一步推广:两个儿子,两个女儿的情况!

semaphores=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年考研真题)

题目:

????????三个进程P1P2P3互斥使用一个包含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件产品后,其他消费者进程才可以取产品。请使用信号量PVwait,singnal)操作实现进程间的互斥和同步,要求写出完整的过程,并说明所用信号量的含义和初值。

分析:

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

解答:


2.5.2哲学家进餐问题

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

思考:如果同时拿起左筷子?

死锁解决方法:

?解决方法1:

?

解决方法2:

解决方法3:

?学以致用(2019真题)

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

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

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

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

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

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


2.5.3? 读者-写者问题

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

  • “读-写”互斥,
  • “写-写”互斥,
  • "读-读"允许


?补充:吸烟者问题

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

文章来源:https://blog.csdn.net/m0_63064861/article/details/135417851
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。