爱问知识人 爱问共享资料 医院库

理发师问题算法如何实现

首页 >
生活
美容/塑身
美发/护发

理发师问题算法如何实现


	 	
	 

全部答案

    2018-10-30 01:17:48
  •   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[]
    数组不能是无限的。而为理发师编号,则只需要三个元素即可。

类似问题

换一换
  • 美发/护发相关知识

  • 生活
  • 日常生活
最新资料 推荐信息 热门专题 热点推荐
热点检索
确定举报此问题
举报原因(必选):
报告,这不是个问题
报告原因(必选):
返回
顶部