操作系统进程同步问题解析（哲学家问题、生产消费问题、小和尚打水问题等大量例子）

操作系统是大学里非常重要的课程，对于科班出身的同学来说，把这门课程学号是非常必要的，下面我将我的课堂笔记整理好跟大家分享，虽然这些例子都是很简单的，代码也都能在网上找到，但是我想经过自己整理的代码，才能把知识固定在脑子里，希望我的笔记对大家操作系统的学习有利，特别是非科班出身而且对计算机感兴趣的同学；

正文：

信号量的本质是一种数据操作锁，它本身不具有数据交换的功能，而是通过控制其他的通信资源（文件，外部设备）来实现进程间通信，它本身只是一种外部资源的标识。信号量在此过程中负责数据操作的互斥、同步等功能。

   当请求一个使用信号量来表示的资源时，进程需要先读取信号量的值来判断资源是否可用。大于0，资源可以请求，等于0，无资源可用，进程会进入睡眠状态直至资源可用。

信号量结构体：

struct{ unsigned short semval;

          pid_t          sempid;

          unsigned short semncent;

        .....

        };

信号量的两个操作：

<!--[if !supportLists]-->1、<!--[endif]-->阻塞操作——Wait

<!--[if !supportLists]-->2、<!--[endif]-->唤醒操作——Signal

 

信号量分类

<!--[if !supportLists]-->1、<!--[endif]-->技数信号量：

使用范围：资源数量有多个（共享资源有多个备份，他们的使用是互斥的）；

 

取值范围：大于1的整数值，

<!--[if !supportLists]-->2、<!--[endif]-->二元信号量：

取值范围：0、1

使用范围：实现互斥；

Semaphore S;

Wait(S):

Critical Section;

Signal(S);

二元信号量其实就是一个锁；

Wait——获取锁的钥匙

Signal——钥匙扔掉

 

二元信号量比较简单，比较复杂的计数信号量可以用二元信号量来实现：

 

Data Structures:

Int c;//计数信号量的取值

Binary-Semaphore  S1,S2;//对C的操作要求互斥，S1作为C的互斥锁；

//S2做为技术信号量的wait的等待;

Initialization:

S1 = 1

S2 = 0

C = intial value of semaphore S;

 

Wait(C) operation

Wait(S1)l;

C--;

If(C<0){

Signal(S1);//唤醒S1

Wait(S2);

}

Signal(S1);

 

Signal(C) operation

Wait(S1);

C++;

If(C<=0)

Signal(S2);

Else

Signal(S1);

 

同步问题的例子

解决同步问题思路步骤：

参与者与规则；

资源：具体问题所涉及的资源，而这些资源一般都是共享的，资源的数量也是有限的；

继续处理前必须获得资源——技术信号量或者变量计数；

共享变量

必须保护访问——二元信号量；

<!--[if !supportLists]-->1、<!--[endif]-->有限缓存问题（生产者消费者问题）：

问题描述：两个共享固定大小缓冲区的线程——即所谓的“生产者”和“消费者”——在实际运行时会发生的问题。生产者的主要作用是生成一定量的数据放到缓冲区中，然后重复此过程。与此同时，消费者也在缓冲区消耗这些数据。该问题的关键就是要保证生产者不会在缓冲区满时加入数据，消费者也不会在缓冲区中空时消耗数据。

游戏参与者：生产者、消费者

活动限制：共享一个固定大小的缓冲区；

对共享数据的访问要求：互斥（生产消费操作必须互斥），缓存区满后停止生产，有产品后才消费；

怎样保证互斥：设置一个信号量，用信号量保证互斥；

缓存区满后停止生产：获得空的缓存去单元，用一个计数信号量表示空的单元数，empty；

有生产后才消费：有一个“满”的资源才能进行消费；

一个生产者，一个消费者，公用一个缓冲区

定义两个同步信号量：

empty——表示缓冲区是否为空，初值为1。

full——表示缓冲区中是否为满，初值为0。

生产者进程

while(TRUE){

生产一个产品;

     P(empty);

     产品送往Buffer;

     V(full);

}

消费者进程

while(TRUE){

P(full);

   从Buffer取出一个产品;

   V(empty);

   消费该产品;

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

——N个缓冲区形成一个环形缓冲区要利用指针。缓冲区的指向则通过模运算得到。

empty——表示缓冲区是否为空，初值为n。

full——表示缓冲区中是否为满，初值为0。

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

 

生产者进程

while(TRUE){

     生产一个产品;

     P(empty);

     产品送往buffer（in）；

     in=(in+1)mod n；

     V(full);

     }

消费者进程

while(TRUE){

 P(full);

   从buffer（out）中取出产品；

   out=(out+1)mod n；

   V(empty);

   消费该产品;

   }

 

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

——在这种情况中，生产者与消费者存在同步关系，而且各个生产者之间、各个消费者之间存在互斥关系,他们必须互斥地访问缓冲区。

定义四个信号量：

empty——表示缓冲区是否为空，初值为n。

full——表示缓冲区中是否为满，初值为0。

mutex1——生产者之间的互斥信号量，初值为1。

mutex2——消费者之间的互斥信号量，初值为1。

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

 

生产者进程

while(TRUE){

     生产一个产品;

     P(empty);

     P(mutex1)；

     产品送往buffer（in）；

     in=(in+1)mod n；

     V(mutex1);

     V(full);

     }

消费者进程

while(TRUE){

 P(full);

   P(mutex2)；

   从buffer（out）中取出产品；

   out=(out+1)mod n；

   V（mutex2）；

   V(empty);

 

<!--[if !supportLists]-->2、<!--[endif]-->读者\写者问题：

问题描述：读者—写者问题（Readers-Writers problem）也是一个经典的并发程序设计问题，是经常出现的一种同步问题。计算机系统中的数据（文件、记录）常被多个进程共享，但其中某些进程可能只要求读数据（称为读者Reader）；另一些进程则要求修改数据（称为写者Writer）。就共享数据而言，Reader和Writer是两组并发进程共享一组数据区，要求：

游戏参与者：读者、写者

活动限制：读写操作是在同一个临界区；

对共享数据的访问要求：（互斥）读和写不能同时进行，允许多个读者同时执行读操作，不允许读者、写者同时操作，不允许多个写者同时操作；

许多个读者同时执行读操作，第一个读者解锁；最后一个读者加锁，使用一个计数器readcount来计算读者的数量；

Shared data

Semaphore mutex 保证读者对readcount访问的互斥

  Wrt： 保证读写互斥

Readcount：记录读者数量

 

<!--[if !supportLists]-->3、<!--[endif]-->哲学家问题

问题描述：在餐桌旁的哲学家有两种操作，思考，就餐，餐桌上每个哲学家的右边有一只筷子，两只筷子才能就餐；

 

 

游戏参与者：哲学家

共享资源：筷子（二元信号量）；

对共享数据的访问要求：每个筷子的使用是互斥的，每个哲学家只能使用身边的筷子；

哲学家就餐防止死锁：

当一个哲学家身边的两个筷子都可以用才可以允许它拿筷子；

给所有哲学家编号，奇数号的哲学家首先拿左边的筷子；偶数号的哲学家先拿右边的筷子；

如果哲学家总数已知，可以让控制最多让总数-1的哲学家就餐；

 

<!--[if !supportLists]-->4、<!--[endif]-->理发师问题：

问题描述：

<!--[if !supportLists]-->1、<!--[endif]-->休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发；

<!--[if !supportLists]-->2、<!--[endif]-->处理休息状态的理发师可为在沙发上等待时间最长的顾客理发；

<!--[if !supportLists]-->3、<!--[endif]-->理发时间长短由理发师决定；

<!--[if !supportLists]-->4、<!--[endif]-->在站席区等待时间最长的顾客可坐到空闲的理发上；

<!--[if !supportLists]-->5、<!--[endif]-->任何时刻最多只能有一个理发师在收银。

游戏参与者：理发师，顾客

伪代码：

semaphore stand_capacity=5;
　　semaphore sofa=4;
　　semaphore barber_chair=3;
　　semaphore customer_ready=0;
　　semaphore mutex=3;
　　semaphore mutex1=1;
　　semaphore finished[3]={0,0,0};
　　semaphore leave_barberchair=0;
　　semaphore payment=0;
　　semaphore receipt=0;
　　void customer()
　　{

顾客：
　　int barber_number;
　　wait(stand_capacity); //等待进入理发店
　　enter_room(); //进入理发店
　　wait(sofa); //等待沙发
　　leave_stand_section(); //离开站席区
　　signal(stand_capacity);
　　sit_on_sofa(); //坐在沙发上
　　wait(barber_chair); //等待理发椅
　　get_up_sofa(); //离开沙发
　　signal(sofa);
　　wait(mutex1);
　　sit_on_barberchair(); //坐到理发椅上
　　signal(customer_ready);
　　barber_number=dequeue(); //得到理发师编号
　　signal(mutex1);
　　wait(finished[barber_number]); //等待理发结束
　　pay(); //付款
　　signal(payment); //付款
　　wait(receipt); //等待收据
　　get_up_barberchair(); //离开理发椅
　　signal(leave_barberchair); //发出离开理发椅信号
　　exit_shop(); //了离开理发店
　　}

对于理发师：
　　void barber(int i)
　　{
　　while(true)
　　{
　　wait(mutex1);
　　enqueue(i); //将该理发师的编号加入队列
　　signal(mutex1);
　　wait(customer_ready); //等待顾客准备好
　　wait(mutex);
　　cut_hair(); //理发
　　signal(mutex);
　　signal(finished[i]); //理发结束
　　wait(leave_barberchair); //等待顾客离开理发椅信号
　　signal(barber_chair); //释放barber_chair 信号
　　}
　　}
　　void cash() //收银
　　{
　　while(true)
　　{
　　wait(payment); //等待顾客付款
　　wait(mutex); //原子操作
　　get_pay(); //接受付款
　　give_receipt(); //给顾客收据
　　signal(mutex);
　　signal(receipt); //收银完毕，释放信号
　　}
　　} 

6、过桥问题

问题：一座小桥（最多能承重两个人）横跨南北两岸，任意时刻同一方向只允许一个人过桥；南侧的桥段和北侧的桥段较窄只能一个人通过，桥中央一处宽敞，允许两个人通过或者休息。

游戏参与者：南北过桥者；

资源：桥的承重（对多两人，相当于资源的两个份额）

信号量使用：

Load：（技术信号量）

North：（二元信号量）

South：（二元信号量）

伪代码：

int countSN=0;

int countNS=0;

semaphore mutexSN=1;

semaphore mutexNS=1;

semaphore bridge=1;

 

 

 

6、和尚打水问题（生产消费变种）：

问题描述：某寺庙，有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳10桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为3个。每次入水、取水仅为一桶，且不可同时进行

信号量设置：

<!--[if !supportLists]-->1、<!--[endif]-->对于水缸——以一个水桶水为单位，empty=30、full = 0两个计数信号量

<!--[if !supportLists]-->2、<!--[endif]-->小和尚对缸操作：mutex-jar = 1二元信号量；

<!--[if !supportLists]-->3、<!--[endif]-->水桶个数（资源数）：bucket = 5计数信号量

<!--[if !supportLists]-->4、<!--[endif]-->取水操作（每次入水、取水仅为一桶）：互斥mutex-well = 1二元信号量；

伪代码：

 

 

7、一家人吃水果问题：

问题描述：桌子上有一只盘子，每次只能放一个水果，爸爸专向里面放苹果，妈妈放橘子，儿子专吃橘子，女儿专吃苹果，仅当盘子空闲时，爸爸妈妈才可以向里面放水果，仅当盘子里有自己需要的水果时，儿子女儿才可以从里面取出一只水果。

生产者消费者变种问题：

1、空间变为一个，不同的消费者需求不同；

2、信号量变化：Full——用两个信号量表示So=0、SA=0（表示橘子和苹果两种），empty=1不变；

伪代码：

int e=1,a=o=0;
main()
{father();
 //son();
 //daughter();/*三个为并发进程*/
}
father()
{while(1)
  { 洗水果
    wait(e)
    把水果放入盘子
    if（水果是苹果）signal(a)
    else signal(o)
   }
} 
son()
{while(1)
    {wait(o)
     从盘子里取桔子
     signal(e)
     吃桔子}
}

daughter()
{while(1)
   {wait(a)
    从盘子里取苹果
    signal(e)
    吃苹果}
}