【OS小班】SleepingBarberPromblem

前言

本来昨晚写了个框架在这边，结果不小心把Git本地commit给删掉了，文章直接无了，这篇还好，另一篇要不是发了Npm包直接哭死。

这题内容是第六次小班的内容，第六次小班讨论主题是并发控制，内容小组四选一：

以一种程序设计语言，如C/C++或Java或Python等为例，介绍其为实现并发控制提供的各种锁机制，要求进行代码运行演示，班级内使用同一语言进行汇报的小组不超过两组
生产者-消费者问题，并进行代码演示
哲学家就餐问题，并进行代码演示
其它经典的并发控制问题，要求进行代码演示

本来打算选第三个哲学家就餐问题的，填表的时候发现已经有两个小组选了，一个选题最多两个小组选，所以后面就改选4了，查资料的时候发现了这个Sleeping Barber Problem^[1]，感觉也挺有意思，就决定做这个了。

前提准备

因为是要上代码的，所以我这边查了一些资料，C++^[2]的、Java^[3]的，甚至还看到Go的（这里感谢smallnest的repo提供的ppt^[4]），

然后发现C++11标准才开始支持多线程实现，然后个人查到相关C++的资料也没有说具体版本，与之对应的Java则是在JDK1.1.0就支持多线程，所以…还是写C++吧。

CLion捆绑的编译环境是真的方便…自己下的mingw32、mingw64、cmake环境调了半天还不如一个“捆绑的MinGW”T_T。

题目分析

维基百科^[5]上面的英文版本有兴趣的可以自行跳转到文末链接，这边放上查到的中文版本^[1:1]：

有这么一个理发店，有一位理发师和几个让顾客等待的座位：

如果没有顾客，这位理发师就躺在理发椅上睡觉
顾客必须唤醒理发师让他开始理发
如果一位顾客到来，理发师正在理发
- 如果还有顾客用来等待的座位，则此顾客坐下
- 如果座位都满了，则此顾客离开
理发师理完头发后，需要检查是否还有等待的顾客
- 如果有，则请一位顾客起来开始理发
- 如果没有，理发师则去睡觉

先用伪代码写一下题目过程：

Barber: // 对于理发师而言
  if(!Guest) // 如果没有顾客
  	Sleep(); // 睡觉
  else // 否则
  	if(!Cuting) // 如果没有在剪头发||在睡觉
        Cut(); // 理发
	else // 否则
        Dosomething(); //这边的是对于顾客的处理
        
Guest: // 对于顾客而言
  if(!Guest||!Wait) // 如果前面没人或者等待队列轮到自己
      Cut(); // 理发
  else if(Seats) // 否则，如果有位置
      Wait(); // 等待
  else // 否则
      Away(); // 离开

所以比较明确的是，得有一个seat，一个wait_queue，用来存储和椅子数量跟等待队列，并根据情况进行相应处理。

然后理发师跟顾客是两个进程barber_process跟consumer_process。

至于剩下的一些细节，比如理发师状态，在睡觉还是在理发，顾客唤醒理发师之类的…可以慢慢完善。

思路借鉴的CSDN^[6]上面的文章。

代码编写

参考CSDN^[7]上面一个比较完整的代码：

#include <iostream>
#include <pthread.h> // 多线程接口
#include <ctime>
#include <unistd.h>
#include <queue> // 等待队列
#include <semaphore.h> //信号量

using namespace std;

typedef sem_t semaphore;
queue<int> wait_queue;

#define SEATS 5 // 有界缓冲区-椅子数初始化
int waiting = 0; // 目前缓冲区大小记录初始化

/*
 * 关于 semaphore，参考 https://blog.csdn.net/qq_46615150/article/details/114519037
 */
semaphore barber;
semaphore consumers;
semaphore mutex_lock; // 互斥信号量

void *barber_process(void *) {
    while (1) {
        int id;
        sem_wait(&consumers);
        sem_wait(&mutex_lock);
        waiting=waiting-1;
        id = wait_queue.front();
        wait_queue.pop();
        sem_post(&barber);
        sem_post(&mutex_lock);
        cout << "理发师正在给第" << id << "位等待的顾客理发" << endl;
        srand(time(0));
        sleep(rand()%3+2);
    }
}

void* consumer_process(void *p) {
    int i = *(int *) p;
    sem_wait(&mutex_lock);
    if (waiting < SEATS) {
        wait_queue.push(i);
        waiting=waiting+1;
        sem_post(&consumers);
        sem_post(&mutex_lock);
        sem_wait(&barber);
        cout << "第" << i << "位顾客来了，正在接受理发师的服务" << endl;
        cout << "正在等待理发师理发的顾客还有" << waiting << "位" << endl << endl;
    } else {
        sem_post(&mutex_lock);
        cout << "门外的第" << i << "位顾客因为没有椅子走了。" << endl << endl;
    }
    pthread_exit(0);
}

int main() {
    pthread_t p_barber;
    pthread_t p_consumers[10];

    int num_consumers = 20;

    sem_init(&barber, 0, 0);
    sem_init(&consumers, 0, 0);
    sem_init(&mutex_lock, 0, 1);

    pthread_create(&p_barber, nullptr, barber_process, nullptr);

    for (int i = 0; i < num_consumers; i++) {
        pthread_create(&p_consumers[i], nullptr, consumer_process, &i);
        srand(time(0));
        sleep(rand() % 2 + 1);
    }

    for (int i = 0; i < num_consumers; i++) {
        pthread_join(p_consumers[i], nullptr);
    }

    sleep(5);

    return 0;
}

跑了一遍，结果奇奇怪怪的：

理发师正在给第第00位等待的顾客理发位顾客来了，正在接受理发师的服务

正在等待理发师理发的顾客还有0位

理发师正在给第1位等待的顾客理发
第1位顾客来了，正在接受理发师的服务
正在等待理发师理发的顾客还有1位

第2位顾客来了，正在接受理发师的服务
理发师正在给第正在等待理发师理发的顾客还有12位位等待的顾客理发


理发师正在给第3位等待的顾客理发
第3位顾客来了，正在接受理发师的服务
正在等待理发师理发的顾客还有2位

理发师正在给第第44位顾客来了，正在接受理发师的服务位等待的顾客理发

正在等待理发师理发的顾客还有3位

门外的第10位顾客因为没有椅子走了。

理发师正在给第5位等待的顾客理发
第5位顾客来了，正在接受理发师的服务
正在等待理发师理发的顾客还有4位

理发师正在给第第66位顾客来了，正在接受理发师的服务位等待的顾客理发

正在等待理发师理发的顾客还有4位

门外的第13位顾客因为没有椅子走了。

第理发师正在给第77位等待的顾客理发位顾客来了，正在接受理发师的服务

正在等待理发师理发的顾客还有4位

理发师正在给第8位等待的顾客理发
第8位顾客来了，正在接受理发师的服务
正在等待理发师理发的顾客还有3位

理发师正在给第9位等待的顾客理发
第9位顾客来了，正在接受理发师的服务
正在等待理发师理发的顾客还有2位

第理发师正在给第1111位顾客来了，正在接受理发师的服务位等待的顾客理发

正在等待理发师理发的顾客还有1位

理发师正在给第12位等待的顾客理发
第12位顾客来了，正在接受理发师的服务
正在等待理发师理发的顾客还有0位


进程已结束,退出代码-1073741819 (0xC0000005)

然后在Github上面找到了两个C++实现，一个是比较基础的^[8]，一个支持多理发师的^[9]。

不过也不是完全跟我的需求一致，姑且参考着开写。

因为上午肯定是写不完了，所以先这样吧。

下午参考着先写了一个框架：

#include <iostream>
#include <thread> // 多线程接口
#include <queue> // 等待队列
#include <mutex> //互斥
#include <condition_variable>

using namespace std;

mutex seatLock; // lock barbers seat
mutex mutexPrint;  // allows only 1 print
mutex mutexSleep;  // control the barber awake or not
queue<int> waitList; //create a queue for the waiting customers

int totalSeats = 5;
int barberSleeping = 1;
int waitConsumer = 0;
int lastConsumer = 20;
string noPlace;
condition_variable cv;

class Barber{
    int currConsumer=0; // Cutting consumer id
    int cutTime=1;

public:
    static void barberLock(){ // This is to lock the barber when he starts working on 1 customer
        unique_lock<mutex> lock(mutexSleep);
        while(barberSleeping&&waitList.empty()){
            cout << "\nBarber sleeping" << "\n";
            cout << "Waiting room : " << "\n";
            cv.wait(lock);
        }
    }

    void Working(){
        lock_guard<mutex> lock(seatLock);
        currConsumer = waitList.front();

        if(!waitList.empty()){
            waitList.pop();
        }

        this_thread::sleep_for(chrono::milliseconds(cutTime*1000));
    }

    void start(){
        while(true){
            // won't allow barber to do anything except sleep
            barberLock();
            //wakes up barber and he starts cutting hair of customer
            Working();
            // updates are sent
            lock_guard<mutex> lock(mutexPrint);
            cout << "\nBarber is cutting the hair of customer " << currConsumer << "\n";
            cout << "Waiting room : ";
            queue<int>tempQ = waitList;
            for (int i = 0;  i < waitList.size(); i++) {
                int a = tempQ.front();
                cout <<  a << "\t";
                tempQ.pop();
            }
            cout << "\n" << noPlace;
            noPlace = "";

            if (waitList.empty() && currConsumer == lastConsumer) {
                cout << "\nNo more customers. Barber sleeps now";
            }
        }
    }

};


class Consumer{
    int ID; // set the id of consumer

    static void waitIn(int queueNum){ //consumer added to queue if place in queue
        unique_lock<mutex> lock(mutexSleep);
        waitConsumer = waitConsumer + 1;

        if(waitConsumer > 0){
            waitList.push(queueNum); // push client in wait list
        }
    }

    static void leave(int consumerNum){ // consumer leaves if no place to wait
        lock_guard<mutex> lock(mutexPrint);
        int last=waitList.back();

        if(consumerNum-last>1) {
            noPlace = "Customer " + to_string(last + 1) + " to " + to_string(consumerNum) + " are leaving\n";
        }
        else{
            noPlace = "Customer " + to_string(consumerNum) + " is leaving\n";
        }
    }

    void checkStatus(int id){ // Decides whether the client should wait or leave depending upon the seats available
        ID=id;
        if(waitConsumer >= totalSeats){
            leave(ID);
        }
        else{
            waitIn(ID);
            cv.notify_all();
        }
    }

public:
    static void  getConsumer(int threadNum) {
        thread clientThreads[lastConsumer];
        Consumer consumer{};
        for (int i = 0; i < lastConsumer; i++) {
            this_thread::sleep_for(chrono::milliseconds((rand()%3+1)*1000)); // this generates a client every 3 secs
            clientThreads[i] = thread(&Consumer::checkStatus, consumer, i + 1, threadNum); //generates thread i
        }
        for (int i = 0; i < lastConsumer; i++) {
            clientThreads[i].join();
        }
    }
};

int main() {
    Barber barber;
    Consumer consumer;

    thread barberThread(&Barber::start, barber);
    thread consumerThread(&Consumer::getConsumer,consumer,totalSeats);
    barberThread.join();
    consumerThread.join();

    return 0;
}

目前是会报错，跑不通的那种，后面有时间再改吧。