操作系统原理与Linux实践教程（第2版）课件 第30讲 睡眠理发师问题

睡眠理发师问题主要内容一、问题描述二、算法描述三、算法运行场景分析四、同步与互斥关系分析五、Linux系统中的同步互斥功能六、Linux进程同步与互斥实验：信号量解决生产者-消费者问题一、问题描述理发店有一位理发师、一把理发椅和n把椅子供顾客等候理发休息。如果没有顾客，理发师便在理发椅上睡觉。一个顾客到来时，他必须叫醒理发师。如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，顾客就坐下来等待，否则离开。理发师睡眠理发师问题同步互斥演示二、算法描述intwaiting=0;//等候理发的顾客数intCHAIRS=N;//供顾客坐的椅子总数semaphorecustomers,barbers,mutex;customers=0;barbers=0;mutex=1;cobeginprocessbarber() //理发师进程{while(true){P(customers);//有顾客可供消费吗？若无顾客，理发师睡眠P(mutex);//若有顾客时，以顾客当产品，取一个顾客消费waiting--;//等候顾客数少一个V(barbers);//理发师喊一个顾客来准备为他理发V(mutex);//退出临界区cut_hair();//理发师正在理发（非临界区）}}processcustomer_i() //顾客进程{ P(mutex); //进入临界区 if(waiting<CHAIRS) {//若有空椅子，则等候顾客数加1，否则顾客离开 waiting++; V(customers); //可用顾客数增1 V(mutex); //退出临界区 P(barbers);//理发师忙，顾客坐下等待 get_haircut(); //否则顾客坐下理发 } else V(mutex); //人满了，走吧！}coend三、算法运行场景分析假设现有一个理发师（b）、一把理发椅、2个顾客凳子。尚未有顾客到来。理发椅理发师各变量初值0customers=0barbers=1mutex=b0waiting=2CHAIRS=顾客凳子假设理发师进程首先调度运行理发师各变量当前值0customers=0barbers=1mutex=b0waiting=2CHAIRS=P(customers);-1(b)第1个顾客c1到来理发师各变量当前值0customers=0barbers=c1b0waiting=2CHAIRS=-1(b)P(mutex);if(waiting<CHAIRS){V(customers);V(mutex);waiting++;P(barbers);10-1(c1)理发师醒来，呼叫顾客理发理发师各变量当前值0customers=0barbers=c1b0waiting=2CHAIRS=-1P(mutex);waiting--；V(mutex);cut_hair();V(barbers);10-1(c1)00get_haircut();顾客c1正在理发，顾客c2到来理发师各变量当前值0customers=0barbers=c1b0waiting=2CHAIRS=-110-100c2P(mutex);if(waiting<CHAIRS){V(customers);V(mutex);waiting++;P(barbers);11-1(c2)顾客c1正在理发，顾客c2坐在凳子上等待，顾客c3到来理发师各变量当前值0customers=0barbers=c1b0waiting=2CHAIRS=-110-100c2c3P(mutex);if(waiting<CHAIRS){V(customers);V(mutex);waiting++;P(barbers);11-1(c2)22-2(c3)顾客c1正在理发，顾客c2、c3坐在凳子上等待，顾客c4到来理发师各变量当前值0customers=0barbers=c1b0waiting=2CHAIRS=-110-100c2c3c4P(mutex);if(waiting<CHAIRS)V(mutex);else11-1(c2)22-2(c3)最后，顾客c1正在理发，顾客c2、c3坐在凳子上等待，顾客c4离开理发师各变量当前值0customers=0barbers=c1b0waiting=2CHAIRS=-110-100c2c311-1(c2)22-2(c3)四、同步与互斥关系分析processbarber(){//理发师进程while(true){P(customers);P(mutex);waiting--;V(barbers);V(mutex);cut_hair();}}processcustomer_i(){//顾客进程 P(mutex); if(waiting<CHAIRS) { waiting++; V(customers); V(mutex); P(barbers); get_haircut(); } else V(mutex);}互斥互斥同步同步存在同步关系的进程理发师与顾客存在互斥关系的进程理发师与顾客顾客与顾客思考：为什么不存在理发师与理发师之间的同步、互斥关系？因为只有一个理发师。如果有多个理发师，该算法还适用吗？1、理发师可以唤醒顾客吗？请思考以下问题：2、顾客可以唤醒理发师吗？3、顾客可以唤醒顾客吗？每种唤醒属于同步操作还是互斥操作？分别使用哪个信号量执行唤醒动作？同步1、理发师可以唤醒顾客2、顾客可以唤醒理发师3、顾客可以唤醒顾客barbers同步customers互斥mutex互斥mutex互斥mutex互斥信号量mutexbarbers互斥信号量mutex同步信号量barberscustomers属于同步信号量属于有有customers同步信号量属于五、Linux系统中的同步互斥功能头文件：#include<semaphore.h>原型：intsem_init(sem_t*sem,intpshared,unsignedintvalue);说明：sem_init()初始化sem信号量。value参数指定信号量的初始值。pshared参数指明信号量由进程内线程共享，还是由进程之间共享。1、信号量初始化函数sem_init头文件：#include<semaphore.h>原型：intsem_wait(sem_t*sem);说明：sem_wait函数减小sem信号量的值。如果信号量的值大于0，则进行减一的操作，函数立即返回。如果信号量当前值为0，那么调用就会一直阻塞，直到信号量变得可以进行减一的操作（例如，信号量的值大于0）或者信号处理程序中断调用。2、信号量P操作函数sem_wait头文件：#include<semaphore.h>原型：intsem_post(sem_t*sem);说明：sem_post函数使sem信号量的值增1，并唤醒阻塞在这个信号