【操作系统】嗜睡的理发师问题

【操作系统】嗜睡的理发师问题

一个理发店有N张沙发和一张理发椅。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。试用信号量完成这一过程。

 理发师理发为主动   在理发师进程 ++

 

 chair是共享变量，修改操作，临界资源，使用信号量mutex=1进行管理

 

 

int wait = 0; //顾客等待的数量
semaphore mutex = 1; //互斥访问 wait
semaphore barber = 0; //理发师信号量
semaphore customer = 0; //顾客的信号量
//理发师
void barber() {while (true) {P(customer); //等待顾客来理发P(mutex); //申请互斥访问waitwait = wait - 1; // 等待人数减少一人V(mutex);//释放临界资源V(barber);//让理发师去理发进行理发;}
}
//顾客
void customer () {while (true) {P(mutex);//申请互斥访问waitif (wait < 10) { //代表10把椅子没有坐满 还可以坐人wait = wait + 1 ;V(mutex);V(customer );P(barber);//等待理发师来理发去理发;} else {//人满了 顾客直接离开V(mutex);}}
}

---

4.1 进程间的相互作用

管程部分 了解即可

 

 

---

生产者消费者问题

例1  有一个生产者和一个消费者共享容量为n的缓冲器(n均大于1)，生产者把生产的物品存入缓冲器，而消费者从缓冲器中取出物品去消费。要求用wait,signal操作对生产者和消费者进行正确管理。

第一步  根据题目要求将每个进程的执行过程一步一步描述出来：

生产者进程

  L1: 生产一件产品；

Wait( empty)

产品放入缓冲；//空缓冲

goto L1；

消费者进程

  L2: Wait( full)

从缓冲中取走产品；//缓冲中的产品

消费一件产品；

goto L2；

第二步  分析每个进程每一步的执行条件，将条件一一记录：

生产者进程：

生产一件产品的条件是有生产产品的原料，在题目中不曾提及，所以该条件不考虑，认为这一步骤没有限制条件；

产品放入缓冲条件是要有产品、缓冲，由于前一步骤已经生产出产品，所以这一步骤执行是肯定有产品，这一步骤的限制条件是有缓冲；

消费者进程：

从缓冲中取走产品条件是缓冲中有产品和，这一步骤的限制条件是缓冲中的产品；

消费产品的条件是应该是已获得产品，由于前一步骤已经获得产品，所以这一步骤执行是肯定有产品的，所以这一步骤没有限制条件；

第三步  比较各个条件，将同一条件归为一个，设置一个信号量表示；

根据第二步分析，本题中有四个限制条件：

一个是缓冲，定义信号量empty；

一个是产品，定义信号量full；

第四步  设置信号量初值：

empty，full是资源数量，系统初始状态应该是缓冲均空，无产品，所以empty=n，full=0。

第五步 重新分析每个进程的每个步骤，加入wait,signal操作：

生产者进程：

生产一件产品，无限制条件，且对上述四个信号量无影响；

产品放入缓冲条件是缓冲，所以这条语句前加上wait(empty)，这条语句执行完后，应该缓冲中产品会增加一个，所以这条语句后应加入signal(full)；

消费者进程：

从缓冲中取走产品条件是缓冲中有产品和无消费者从缓冲中取产品，所以这条语句前加上wait(full))，这条语句执行完后，缓冲会增加一个，所以这条语句后应加入signal(S1)；

消费产品无限制条件，且对上述四个信号量无影响。

这样生产者和消费者进程的过程修改为：

生产者进程

  L1: 生产一件产品；

      wait(empty);

产品放入缓冲；

signal(full);

goto L1；

消费者进程

  L2: wait(full);

从缓冲中取走产品；

signal(empty);

消费一件产品；

goto L2；

用一个数组B描述缓冲，k指示放产品的位置，t指示取产品的位置，则完整的生产者消费者算法描述如下：

semaphore empty=n,full=0;item buffer[n];int in=out=0;void producer(){while (1){…produce an item in nextp;...wait(empty);buffer[in]=nextp;in=(in+1) mod n;signal(full);}}void consumer(){while (1){...wait(full);nextc=buffer[out];out=(out+1) mod n;signal(empty);...consume the item in nextc;…}}main(){cobegin {producer();consumer();}}

---

此外还应有哲学家进餐问题、读者写者问题