操作系统

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

2019-04-17 22:39 CST
2019-06-06 23:24 CST
CC BY-NC 4.0

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

生产者/消费者问题

  • 生产者等待空信号；
  • 消费者等待满信号；
  • 内部（上面的等待结束后）用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会发出tobaccoReady和paperReady两个信号，同时唤醒两个pusher。
  2. 接下来，两个pusher会去抢互斥锁，假设烟草对应的pusher先抢到了：抢到锁的那个发现两个if没一个满足的，就把isTobacco设置成true然后睡觉去了。
  3. 然后，卷纸对应的pusher开始工作，发现isTobacco竟然已经被设置成了true，那么他会把拥有火柴的烟民叫起来抽烟。

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

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

References