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

小鱼儿 2024-02-05 22:16 97阅读 0赞

**目录**

一、经典进程的同步问题

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

执行流程：

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

注意：

小结：

复习典型例题：

解答：

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

代码框架：

生产者消费者模型举例

例一、

例二、

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

例4

练一练（2009年考研真题）

题目：

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

答案：

例题：

分析：

解答

练一练（2014年真题）

2.5.2哲学家进餐问题

学以致用（2019真题）

2.5.3 读者-写者问题

补充：吸烟者问题

--------------------

### **一、经典进程的同步问题**  ###

重点内容：

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

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

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

![dbc026b31e074656b8bb79ef174d54c7.png][]

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

##### **执行流程：** #####

![65a23e14e9384f678d3b69480e82a731.png][]![fe1827ae7c6f43eebb0392708986b875.png][]

![b778ce2dbcf446bf8b3b31647cc5b6ac.png][]

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

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操作****，这样可以在占用共享资源的访问权时保证有资源可用，不然会****导致产生占用使用权而无资源可用的“死等”现象。**

##### 小结： #####

![b0d84f31038f443b831237cc6089b2a4.png][]

##### 复习典型例题： #####

![d2cb191e7b644fea9574aec18b5f76fb.png][]

##### 解答： #####

![bcfc483cc3d447dfb7f4a8d155299cbd.png][]

#### **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****个环形缓冲区**

![fbde217505f4447691938f1ce4c33f38.png][]

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

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

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

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

![2561ada1512b427882ca2645eaeb15dc.png][]

![a2786accbece4d939e4b0795b99bfad6.png][]

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

--------------------

#### **生产者消费者模型举例** ####

##### **例一、** #####

![8296ed082b404287a0b5684d90998cbc.png][]

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

![383a0304a19447e69d5a1f4f76288ebe.png][]![93ba578612fb4c2d9def7a775528aa4e.png][]

![9ff49feb9ba343a98e1ff00c23b897de.png][]

--------------------

##### 例二、 #####

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

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

**设置三个信号量：**

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

![8f3fc142fd494a54a086b36ea8880224.png][]

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

##### **例****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****.**

解答：

![b621f87f37094861a490fae47601e116.png][]

#### **练一练（****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;//****空缓冲区个数**

##### 答案： #####

![a0b4514bf8aa477e9f77917fac482457.png][]

--------------------

#####  **例题：** #####

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

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

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

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

###### **分析：** ######

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

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

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

**semaphore** **mutex\_well****=1;//** **用于实现对井的互斥操作**

**semaphore** **mutex\_bigjar****=1; //** **用于实现对缸的互斥操作**

###### **解答** ######

![0bad7b3adf754befa54a9431d2606eb7.png][]

--------------------

#### **练一练（****2014****年真题）** ####

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

**分析：**

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

**解答：**

![032a1fbce7a44b45acca120e2c35e806.png][]

--------------------

#### **2.5.2****哲学家进餐问题** ####

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

![0d320b9a58d947d5aeceb0d60ed9fb8e.png][]

![0a6dfaadec224c79820344172f794a23.png][]

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

**死锁解决方法：**

![8d6cd416342a499ca1a79fd4bec101e4.png][]

**解决方法****1：**

![1d21f405fbff4b6cbadf41ad94815ac2.png][]

**解决方法****2：**

![b059212d66584eb5beea4ab0d983e52f.png][]

**解决方法****3：**

![075736fba568420b8dd1877e49bb68fd.png][]

##### **学以致用（****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\};**

![83bb83a1ef864e158c3ab6cbd9638900.png][]

--------------------

#### **2.5.3** **读者****-****写者问题** ####

![62381f5be1e547619b11be5ecdad1560.png][]

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

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

![76ff9389d1db41bfb8cc4e06f284acf5.png][]

![874bd84e25ab47c5a3f2108fa00ecc21.png][]

![24d84cd7c61e424b91aec43dbaa27a7c.png][]

![b20f8accd61d4fefa65de2adff1f5487.png][]

![5270ed5430c14a44b42d7c4cd7f67d0f.png][]

![5643f372a7044e3fbbc16571e76dbed5.png][]

![68fc90df96fd4ff9b946d29ef2e13968.png][]

![86ecb5aeec794741947767b81543f0a9.png][]

![d317a13fc952456ba9b1e61e0e94f0cd.png][]

![fa32050de1ee45cf9105fd68d9edfe86.png][]

![f20538619d714abcbd0b49d26d38c281.png][]

--------------------

##### **补充：吸烟者问题** #####

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

![0af10709db0949e68e60fcc0ec1f389d.png][]

![f9e94fb490cb40fb9fcf75c64a91e3d1.png][]

![520c8b92bcca4fbebfd74155181f72d5.png][]

[dbc026b31e074656b8bb79ef174d54c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/43da7c4dad1b4bd5a478a5f293fb7d36.png
[65a23e14e9384f678d3b69480e82a731.png]: https://img-blog.csdnimg.cn/direct/65a23e14e9384f678d3b69480e82a731.png
[fe1827ae7c6f43eebb0392708986b875.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/9c6469bc725b4325a743496c7272a419.png
[b778ce2dbcf446bf8b3b31647cc5b6ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/c89c9ef6a67e41e3948af2a556feadae.png
[b0d84f31038f443b831237cc6089b2a4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/954c23eb69d6412c8271ce136e31615e.png
[d2cb191e7b644fea9574aec18b5f76fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/c9f2e5820def449e932ed08a42cf9ba3.png
[bcfc483cc3d447dfb7f4a8d155299cbd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/22a44bc9575544149878a07b0f5f7993.png
[fbde217505f4447691938f1ce4c33f38.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/3100a7e5d6134a97a51cb34fd4a6a136.png
[2561ada1512b427882ca2645eaeb15dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/0096af1270b14dc6bbf70fdb2e754f04.png
[a2786accbece4d939e4b0795b99bfad6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/5c64d221a88048b4a3c4f88de787b942.png
[8296ed082b404287a0b5684d90998cbc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/316155ba0dd449c0ae58849a2d6c2824.png
[383a0304a19447e69d5a1f4f76288ebe.png]: https://img-blog.csdnimg.cn/direct/383a0304a19447e69d5a1f4f76288ebe.png
[93ba578612fb4c2d9def7a775528aa4e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ecad8a4f5fb54985a7c6441ca5683ba5.png
[9ff49feb9ba343a98e1ff00c23b897de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/cf0e7f0558b94e939ef29aa6d9bb5c90.png
[8f3fc142fd494a54a086b36ea8880224.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/6f13572fbf6e49cc8e6a75025bb0170c.png
[b621f87f37094861a490fae47601e116.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/580f7bad93b14e68bc75eff7bb60dfef.png
[a0b4514bf8aa477e9f77917fac482457.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/51cf12768be44808bf2e94789c91e6bc.png
[0bad7b3adf754befa54a9431d2606eb7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/c473fcd5c8ff4e49b33c1fcc62c8a659.png
[032a1fbce7a44b45acca120e2c35e806.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/fa5891a27fb945baa6854e39ab822c52.png
[0d320b9a58d947d5aeceb0d60ed9fb8e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ce3831318368415aa257978e01399a58.png
[0a6dfaadec224c79820344172f794a23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/864569216f9645d0bcab306537824607.png
[8d6cd416342a499ca1a79fd4bec101e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/c44ba790d01e468d95a9762ca5da1dda.png
[1d21f405fbff4b6cbadf41ad94815ac2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/16495c64fe3949a788bcd3fbcf0760c3.png
[b059212d66584eb5beea4ab0d983e52f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/a30b508f1d1e4723843188c0aa162742.png
[075736fba568420b8dd1877e49bb68fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/5a6342a620634e03bbc31f63717e3a4b.png
[83bb83a1ef864e158c3ab6cbd9638900.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/602a11a5d54942989bd0187220818c07.png
[62381f5be1e547619b11be5ecdad1560.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/a9cf93267bad47e9a01bc6c5c40e1fed.png
[76ff9389d1db41bfb8cc4e06f284acf5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/7896a954db9c4dfabbb202b7e6663b32.png
[874bd84e25ab47c5a3f2108fa00ecc21.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/bfb12872af7f4c199dfb5f60c46640a2.png
[24d84cd7c61e424b91aec43dbaa27a7c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/69c50fe5517b46b0b908256f7ad83465.png
[b20f8accd61d4fefa65de2adff1f5487.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/c8e554bf62af43a0a682e0927d944952.png
[5270ed5430c14a44b42d7c4cd7f67d0f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/31b951880021437eb772f9993c90d8bc.png
[5643f372a7044e3fbbc16571e76dbed5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/45d566893141439cb190bfa44a6ccd11.png
[68fc90df96fd4ff9b946d29ef2e13968.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/8965b89f31aa450989498eb5f5d559b7.png
[86ecb5aeec794741947767b81543f0a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/07f32ace16f74e578a19ea18eaa8683b.png
[d317a13fc952456ba9b1e61e0e94f0cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/e01d23d389be47f29af60b4c29f0df92.png
[fa32050de1ee45cf9105fd68d9edfe86.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/23505f39cd2d4dfaa699a9a76b692b26.png
[f20538619d714abcbd0b49d26d38c281.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/41ac7b6faf5e452e96a9add12045bd1e.png
[0af10709db0949e68e60fcc0ec1f389d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/621a4c303d0748a7a13e4767887e7297.png
[f9e94fb490cb40fb9fcf75c64a91e3d1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/7b2aecd9502147ee9ff7994752c081a9.png
[520c8b92bcca4fbebfd74155181f72d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/5eba745d75c44d8880aac9081805d5da.png