操作系统期末复习大题

目录

一、经典进程的同步问题

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

执行流程：

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

 注意：

小结：

复习典型例题：

解答：

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

代码框架：

生产者消费者模型举例

例一、

例二、 

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

例4

练一练（2009年考研真题）

题目：

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

答案：

 例题：

分析：

解答

练一练（2014年真题）

2.5.2哲学家进餐问题

 学以致用（2019真题）

2.5.3  读者-写者问题

 补充：吸烟者问题

重点内容：

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

问题推广：

                  一组生产者，一组消费者，公用 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表示盘中是否有桔子；

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

分析：盘子为互斥资源，因可以放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：某幼儿园举行趣味活动，每两个小朋友一组。重复做如下活动：一个小朋友负责用一个小桶在A沙堆取沙子，然后倒入一大盆中，另一小朋友负责用一个小桶从大盆中取沙子倒入B沙堆。大盆最多能装10桶沙子，且在大盆中取沙子和倒沙子不能同时进行。试用信号量操作描述这两个小朋友的同步过程。

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

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

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

解答：

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

信号量定义：

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

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

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

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

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

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

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

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

分析：

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

解答：

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

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

死锁解决方法：

 解决方法1：

解决方法2：

解决方法3：

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

   信号量bowl用于协调哲学家对碗的使用， bowl