2010-05-22 15:20:00 do2jiang 阅读数 9077

     2.理发师问题:一个理发店有一个入口和一个出口。理发店内有一个可站5 位顾客的站席区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等待;没有空沙发时,可在站席区等待;站席区满时,只能在入口外等待。理发师可从事理发、收银和休息三种活动。理发店的活动满足下列条件:
  1)休息的理发师是坐地自己专用的理发椅上,不会占用顾客的沙发;
  2)处理休息状态的理发师可为在沙发上等待时间最长的顾客理发;
  3)理发时间长短由理发师决定;
  4)在站席区等待时间最长的顾客可坐到空闲的理发上;
  5)任何时刻最多只能有一个理发师在收银。
  试用信号量机制或管程机制实现理发师进程和顾客进程。
  原理:
  (1)customer 进程:
  首先检查站席区是否已满(stand_capacity),若满选择离开,否则进入站席区,即进入理发店。在站席区等待沙发的空位(信号量sofa),如果沙发已满,则进入阻塞等待队列,直到出现空位,在站席区中等待时间最长的顾客离开站席区(stand_capacity)。坐到沙发上,等待理发椅(barber_chair),如果理发椅已满,则进入阻塞等待队列,直到出现空位,在沙发上等待时间最长的顾客离开沙发(释放信号量sofa)。坐到理发椅上,释放准备好的信号(customer_ready),获得该理发师的编号(0~1 的数字)。等待理发师理发结束(finished[barber_number])。在离开理发椅之前付款(payment),等待收据(receipt),离开理发椅(leave_barberchair)。最后离开理发店。
  这里需要注意几点:
  a) 首先是几个需要进行互斥处理的地方,主要包括:进入站席区、进入沙发、进入理发椅和付款几个地方。
  b) 通过barber_chair 保证一个理发椅上最多只有一名顾客。但这也不够,因为单凭baber_chair 无法保证一名顾客离开理发椅之前,另一位顾客不会坐到该理发椅上,因此增加信号量leave_barberchair,让顾客离开理发椅后,释放该信号,而理发师接收到该信号后才释放barber_chair 等待下一位顾客。
  c) 在理发的过程中,需要保证是自己理发完毕,才能够进行下面的付款、离开理发椅的活动。这个机制是通过customer 进程获得给他理发的理发师编号来实现的,这样,当该编号的理发师释放对应的finished[i]信号的时候,该顾客才理发完毕。
  d) 理发师是通过mutex 信号量保证他们每个人同时只进行一项操作(理发或者收款)。
  e) 为了保证该顾客理发完毕后马上可以付款离开,就应该保证给该顾客理发的理发师在理
  发完毕后马上到收银台进入收款操作而不是给下一位顾客服务。在伪码中由以下机制实现:即顾客在释放离开理发椅的信号前,发出付款的信号。这样该理发师得不到顾客的离开理发椅的信号,不能进入下一个循环为下一名顾客服务,而只能进入收款台的收款操作。直到顾客接到收据后,才释放离开理发椅的信号,离开理发椅,让理发师释放该理发椅的信号,让下一位等待的顾客坐到理发椅上。
  (2)barber 进程
  首先将该理发师的编号压入队列,供顾客提取。等待顾客坐到理发椅坐好(信号量customer_ready),开始理发,理发结束后释放结束信号(finished[i])。等待顾客离开理发椅(leave_barberchair)(期间去收银台进行收款活动),释放理发椅空闲信号(barber_chair),等待下一位顾客坐上来。
  (3)cash(收银台)进程
  等待顾客付款(payment),执行收款操作,收款操作结束,给付收据(receipt)。
  信号量总表:
  信号量 wait signal
  stand_capacity 顾客等待进入理发店 顾客离开站席区
  sofa 顾客等待坐到沙发 顾客离开沙发
  barber_chair 顾客等待空理发椅 理发师释放空理发椅
  customer_ready 理发师等待,直到一个顾客坐到理发椅顾客坐到理发椅上,给理发师发出信号mutex 等待理发师空闲,执行理发或收款操作理发师执行理发或收款结束,进入空闲状态mutex1 执行入队或出队等待 入队或出队结束,释放信号finished[i] 顾客等待对应编号理发师理发结束;理发师理发结束,释放信号leave_barberchair 理发师等待顾客离开理发椅 顾客付款完毕得到收据,离开理发椅释放信号payment 收银员等待顾客付款 顾客付款,发出信号receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据,释放信号


  伪码:
  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); //收银完毕,释放信号
  }
  }


  分析:
  在分析该问题过程中,出现若干问题,是参阅相关资料后才认识到这些问题的隐蔽性和严重性的,主要包括:
  (1)在顾客进程,如果是在释放leave_barberchair 信号之后进行付款动作的话,很容易造成没有收银员为其收款的情形, 原因是: 为该顾客理发的理发师收到leave_barberchair 信号后,释放barber_chair 信号,另外一名顾客坐到理发椅上,该理发师有可能为这另外一名顾客理发,而没有为刚理完发的顾客收款。为解决这个问题,就是采取在释放leave_barberchair 信号之前,完成付款操作。这样该理发师无法进入下一轮循环为另外顾客服务,只能到收银台收款。
  (2)本算法是通过给理发师编号的方式,当顾客坐到某理发椅上也同时获得理发师的编号,如此,当该理发师理发结束,释放信号,顾客只有接收到为其理发的理发师的理发结束信号才会进行付款等操作。这样实现,是为避免这样的错误,即:如果仅用一个finished 信号量的话,很容易出现别的理发师理发完毕释放了finished 信号,把正在理发的这位顾客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编号,让理发师获取他理发的顾客的编号,但这样就会限制顾客的数量,因为finished[]数组不能是无限的。而为理发师编号,则只需要三个元素即可。

2018-11-30 13:50:16 Albert_1000 阅读数 1880

前言

睡眠的理发师问题是操作系统中P、V操作部分的经典问题


睡眠的理发师问题

1. 问题描述

理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子,要求:

  1. 如果没有顾客,理发师便在理发椅上睡觉
  2. 一个顾客到来时,它必须叫醒理发师
  3. 如果理发师正在理发时又有顾客来到,则如果有空椅子可坐,就坐下来等待,否则就离开

2. 问题分析

​ 理发师和顾客是同步关系,理发师等待顾客来,然后为顾客服务,顾客来了之后叫醒理发师,执行上是有先后顺序的,所以应该有两个同步信号量,且散在两个进程里;另一方面,顾客对椅子的操作又是互斥的,属于竞争关系,所以需要互斥信号量来保证椅子的数量准确。

3. P、V操作

int waiting = 0; // 等候理发师 顾客坐的椅子数
int CHAIRS = N;  // 为顾客准备的椅子数
semaphore customers = 0; // 等候的顾客数
semaphore barbers = 0;   // 空闲的理发师数
semaphore mutex = 1;     // 互斥信号量,保证waiting++操作完整进行

cobegin
process barber() {  // 理发师
    while(true) {
        P(customers); // 有顾客吗?若无顾客,理发师睡眠
        P(mutex);     // 保证waiting--完整进行
        // 若有顾客时,进入临界区
        waiting--;    // 等候区顾客数减一
        V(barbers);   // 理发师准备为顾客理发
        V(mutex);
        cut_hair();   // 理发师正在理发(非临界区)
    }
}

process customer_i() {  // 顾客
    P(mutex);     // 进入临界区
    if(waiting < CHAIRS) {  // 有空椅子
    	waiting++;    // 等候顾客加一
        V(customers); // 唤醒理发师
    	V(mutex);     // 退出临界区
   	 	P(barbers);   // 理发师忙,顾客坐下等待
   	 	get_haircut();// 否则顾客坐下理发
    } else
    	V(mutex);     // 没椅子,顾客走人
}
coend

d=====( ̄▽ ̄*)b

2013-11-19 15:31:00 lishuhuakai 阅读数 14516
     理发师问题:
     一个理发店由一个有几张椅子的等待室和一个放有一张理发椅的理发室组成。
     1. 若没有要理发的顾客,则理发师去睡觉;
     2. 若一顾客进入理发店,理发师正在为别人理发,且等待室有空椅子,则该顾客就找张椅子按顺序坐下;
     3. 若一顾客进入理发店,理发师在睡觉,则叫醒理发师为该顾客理发;
     4. 若一顾客进入理发店且所有椅子都被占用了,则该顾客就离开。
    伪码实现:

    引入3个信号量和一个控制变量:

    1)控制变量waiting用来记录等候理发的顾客数,初值均为0; 

    2)信号量customers用来记录等候理发的顾客数,并用作阻塞理发师进程,初值为0; 

    3)信号量barbers用来记录正在等候顾客的理发师数,并用作阻塞顾客进程,初值为0(刚开始时理发师在睡觉,所以理发师这个资源数目为0); 

    4)信号量mutex用于互斥,初值为1. 

    关于p,v操作:

     P操作可以看做是申请一个资源,不管这个资源有没有都将这个资源的数目减1,如果现在资源数目小于0,就阻塞。

     v操作就是释放资源,先将这个资源的数目加1,如果发现这个资源数目小于等于0,就会唤醒在阻塞队列上的一个进程。

     先做一些初始化工作:

var waiting : integer; /*等候理发的顾客数*/
CHAIRS:integer; /*为顾客准备的椅子数*/ 
customers, barbers,mutex : semaphore; 
customers := 0; barbers := 0; waiting := 0; mutex := 1;

     理发师进程:

Procedure barber; 
begin while(TRUE); /*理完一人,还有顾客吗?*/ 
P(cutomers); /*若无顾客,理发师睡眠*/ 
P(mutex); /*进程互斥*/ 
waiting := waiting – 1; /*等候顾客数少一个*/ 
V(barbers); /*理发师去为一个顾客理发,如果babaers等于0,则顾客都会阻塞*/ 
/*刚开始时babers = 0,表示理发师这个资源为0,所以顾客进程执行至
P(barbers)时也无法让理发师为其理发,现在理发师醒了,表示理发店里拥有
理发师这个资源了,所以执行V(barbers)这个操作,将资源数加1,此时会唤醒
一个在队列上阻塞的顾客*/
V(mutex); /*开放临界区*/ 
cut-hair( ); /*正在理发*/ 
end; 


    顾客进程:

procedure customer begin 
P(mutex); /*进程互斥*/ 
if (waiting < n) waiting := waiting+1; /* n表示椅子的数目,等候顾客数加1*/ 
V(customers); /*必要的话唤醒理发师*/ 
V(mutex); /*开放临界区*/ 
P(barbers); /*无理发师, 顾客坐着养神*/ 
get-haircut( ); /*一个顾客坐下等理发*/ 
end V(mutex); /*人满了,走吧!*/ 
end; 



2017-09-26 16:45:11 qq_37383691 阅读数 3500

The Sleeping-Barber Problem.

A barbershop consists of a waiting room with n chairs and barber room containing the barber chair.If these are no customers to be served ,the barber goes to sleep.If a customer enters the barbershop and all chairs are occupied,then the customer leaves the shop. If the barber is busy but chairs are available,then customer sits in one of the free chairs.If the barber is asleep,the customer wakes up the barber.Write a program to coordinate the barber and the customers.

一个理发店由一个含有n把椅子等候房间和一个只有一把理发椅子的剪发房间组成。如果没有顾客的时候,发型师就去睡觉了。如果一位顾客到来时,理发店的所有椅子都没有空闲,那么这位顾客会离开。如果理发师正在给顾客剪头发,理发店还有空闲的椅子,那么在此时到达的顾客会坐下等待。如果理发师睡着了,顾客会唤醒理发师。写一个程序去处理理发师和顾客的关系。


对于问题,首先需要思考进程个数、信号量个数、共享资源和互斥信号的问题。

在此问题中:
进程个数:2,理发师与顾客
信号量个数:5,空闲椅子情况empty,full;理发师状态cut;椅子总数N;互斥信号量mutex
共享资源:count
同时,剪发师可以看作生产者与消费者的问题,顾客可以看作读者写者问题。

我个人的一些思考,不一定正确,需慎重!
对于顾客:三种情况

  1. 第一个顾客到达,那么直接剪发,count=1,空闲椅子依然为N,此时是full还是empty修改呢?!
  2. 当第二个或第N+1个顾客到达,count=[2,N+1],空闲椅子数为[N-1,0]。
  3. 当第N+2个顾客到达,那么直接离开。

对于剪发师:两种情况

  1. 有顾客到来的时候,也就是count不等于0,那么剪发。
  2. 当count=0时,那么剪发师就可以睡觉了。

最后,应该怎么考虑顾客剪完头发的椅子释放问题呢?!

Semaphore mutex=1,chair=N,empty=1,full=0,cut=0;
          int  count=0;
Barber: 
    while(1)
    {
        wait(full);
        cut hair;
        signal(cut);
    }
Guest:
    while(1)
    {
        wait(mutex);             //互斥信号减一,以下的执行都必须满足这一条,否则阻塞在此
        if (count>N)             //顾客人数大于椅子个数
        {
            signal(mutex);       //释放互斥信号
            exit  shop;          //离开店铺
        }
       else 
       {
           count++;              //椅子还有空闲的时候
           if (count>1) 
           {
               wait(chair);     //顾客加一,椅子就要释放一
               sit on chair;
               wait(empty);     //此为等待剪发师空闲
               get up from chair;
               signal(chair);   //椅子唤醒
           }  
          else 
               wait(empty); 
         signal(mutex);

         sit on the baber_chair;
         signal(full);         //这是无条件的加一,此时理发师可以开始工作了
         wait(cut);            //有条件的减一,当这两条都满足的时候,就可以剪发了
         cutting;
         get up from the baber_chair;      
         signal(empty);      //释放理发的座位
         wait(mutex);        //加互斥信号,不允许同时对count进行修改
         count- -;
         signal(mutex);
         exit shop;
      }
    }
2018-03-27 17:40:04 kuishao1314aa 阅读数 7687
 
 

PV操作:对信号量进行相应操作

S:信号量

P:请求操作,相当于S=S-1;S>=0,进程继续进行

V:释放操作,相当于S=S+1,S>0,进程被唤醒

理发师问题 

一个理发师,一把理发椅,n把等候理发的顾客椅子,如果没有顾客则理发师便在理发椅上睡觉 ,当有一个顾客到达时,首先看理发师在干什么,如果理发师在睡觉,则唤醒理发师理发,如果理发师正在理发,则查看是否有空的顾客椅子可坐,  如果有,坐下等待,如果没有,则离开。 

定义信号量:wait=0:顾客信号量   barber=0:理发师信号量

                   custNum:当前顾客数量   mutex=1:互斥量

理发师操作:

Barber(){

while(1){

        P(wait);    //唤醒等待的一位顾客

        P(mutex);  //顾客被唤醒,准备理发,没有顾客,则睡觉

        custNum--;    //当前店里顾客数减1

         V(barber);   //有顾客来了,醒来理发

        V(mettux):   //释放互斥信号量

}

}

顾客操作:

Customer(){

while(1){

P(mutex);    //顾客想要理发

if(custNum<N){   //店里人没有满

     custNum++;

     V(wait);     //理发师睡觉的话,唤醒他理发

     V(mutex);    //释放互斥量,理发这一动作成功

     P(baber);    //理发师进行理发操作

}

else

{

       V(metux);    //释放互斥量,打消进店理发的举动

}

}

}

睡眠理发师问题

阅读数 1028

没有更多推荐了,返回首页