三个并发编程问题:生产者、理发师和吸烟者

分类:Operating System, 发布于:2019-04-17 22:39:51, 更新于:2019-04-19 00:12:14。 评论

如果你发现下面的实现有问题请立即提出来。

生产者/消费者问题

  • 生产者等待空信号;
  • 消费者等待满信号;
  • 内部(上面的等待结束后)用mutex保证数据原子性。
  • 如果mutex放在等待外面会死锁。
sem_init(&empty, 0, MAX); // 初始值为最大商品数
sem_init(&full, 0, 0);    // 有人消费就可以继续生产

void producer() {
  while (true) {
    sem_wait(&empty); // 等待空信号
    sem_wait(&mutex); // 进入临界区
    produce();        // 我,再生产(误
    sem_post(&mutex); // 退出临界区
    sem_post(&full);  // 发出满信号
  }
}

void customer() {
  while (true) {
    sem_wait(&full);  // 等待满信号
    sem_wait(&mutex); // 进入临界区
    consume();        // 消费
    sem_post(&mutex); // 退出临界区
    sem_post(&empty); // 发出空信号
  }
}

沉睡的毛利小五郎理发师问题

理发店有$n$把椅子,没人理发的时候理发师就会昏睡睡着;没理发师空的时候顾客就会找椅子坐下来,如果椅子满了顾客就直接离开理发店(不理发)。

核心问题:顾客必须先判断椅子空不空,所以比生产者/消费者问题中的消费者会提前进入临界区。

sem_init(&customerReady, 0, 0); // 一有人来理发师就去理发了
sem_init(&barberReady, 0, 0);   // 理发师必须被唤醒才能去理发(注意区别)

void barber() {
  while (true) {
    sem_wait(&customerReady); // 等待顾客到来(理发师进入昏睡状态)
    sem_wait(&mutex);         // 进入临界区
    get_next_customer();      // 选一个顾客(注意:此时还没有理发)
    sem_post(&mutex);         // 退出临界区
    sem_post(&barberReady);   // 告知顾客可以理发了
    cur_hair();               // 给顾客理发
  }
}

void customer() {
  while (true) {                // (其实顾客不可能一直在理发)
    sem_wait(&mutex);           // 进理发店时马上进入临界区
    if (freeSeats > 0) {
      /* 有位置 */
      --freeSeats;
      sitDown();                // 不管有没有理发师,顾客先坐下来
      sem_post(&mutex);         // 退出临界区
      sem_post(&customerReady); // 告知理发师顾客来了
      sem_wait(&barberReady);   // 等待理发师醒来,或者有理发师空下来
      sem_wait(&mutex);         // 再次进入临界区
      ++freeSeats;              // 从椅子上起来
      sem_post(&mutex);         // 退出临界区
      have_hair_cut();          // (站着?)理发
    } else {
      /* 没位置,顾客直接走了 */
      sem_post(&mutex);         // 离开临界区,然后离开理发店
    }
  }
}

脑残烟民问题

哲学家鬼畜吃饭大战豪华版吸一根烟需要三种材料:卷纸(怎么听着怪怪的)、烟草、火柴。

  • 有三个人围着坐,每个人拥有无限数量的某一种材料(三个人合起来拥有所有材料,不然没烟可抽)。
  • 同时,有一个不抽烟的脑残工具人(英文版称为agent,果然是工具人不断重复随机的把两种材料放到桌上,此时拥有第三种材料的人就可以制造出烟,然后他们可以快乐的吸烟工具人享受二手烟
谁有材料谁做烟,这么弱智困难的问题哪来的死锁?

抽烟就抽烟嘛,你吼那么大声干什么?

假设有烟草的人会先把桌上的卷纸和火柴拿走,再用自己的烟草合体做出一根烟。

有烟草的人把卷纸拿走之后,还没来得及拿火柴,有卷纸的那个人横空出世把火柴抢走了,然后他们俩就🔒了。

哇,那给烟民上把🔒不就好了?

嗯,有烟草的人先上锁进了临界区,然后有卷纸的也来上锁了;之后有烟草的把东西拿走去抽烟了,拥有卷纸的人苦苦等来了锁,然后就💣了。

哇,那让烟民加个while检查一下不就好了?

……(为什么没人这么解决问题呢?)

更新:此题原题题意是不允许修改agent的行为,且不允许使用条件变量的,这么做实际就是摆了3个CV上来,违反题意。

为了解决烟民相互打架的问题,Parnas(1975年的某论文,见Wikipedia)提出的解决方案是:增加三个幕后推手工具人(pushers),来响应agent发出的信号,满足条件后再发出信号唤醒对应的吸烟者。

void tobaccoPusher() {
  while (true) {
    sem_wait(&tobaccoReady);       // 等待agent把烟草摆上来
    sem_wait(&mutex);              // 进入临界区
    if (isPaper) {                 // 黑人问号.jpg
      isPaper = false;
      sem_post(&matchSmokerReady);
    } else if (isMatch) {
      isMatch = false;
      sem_post(&paperSmokerReady);
    } else {
      isTobacco = true;            // 这TM又是在干嘛?
    }
    sem_post(&mutex);              // 退出临界区
  }
}

吸烟问题的最大区别在于:一个吸烟者必须要两个信号同时满足才可以被唤醒。

  1. 假设agent又把烟草和卷纸端上来了,这时agent会发出tobaccoReadypaperReady两个信号,同时唤醒两个pusher。
  2. 接下来,两个pusher会去抢互斥锁,假设烟草对应的pusher先抢到了:抢到锁的那个发现两个if没一个满足的,就把isTobacco设置成true然后睡觉去了。
  3. 然后,卷纸对应的pusher开始工作,发现isTobacco竟然已经被设置成了true,那么他会把拥有火柴的烟民叫起来抽烟。

全局只有1把互斥锁,两个pusher会先后执行,只会唤醒1个烟民,没有任何进程会互相打架陷入死锁,问题得到了完美地解决。

这个问题解决之后实现其他工具人和烟民的进程就很简单了。(注意烟民抽烟之后要进临界区把所有的isXXX都设置成false,然后唤醒agent继续给他们端材料。可怜的工具人

References

评论