C++ Threading Issues

Question

I'm trying to solve the following problem: " The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber's chair in a cutting room and a waiting room containing a number of chairs in it. When the barber finishes cutting a customer's hair, he dismisses the customer and goes to the waiting room to see if there are others waiting. If there are, he brings one of them back to the chair and cuts their hair. If there are none, he returns to the chair and sleeps in it.

Each customer, when they arrive, looks to see what the barber is doing. If the barber is sleeping, the customer wakes him up and sits in the cutting room chair. If the barber is cutting hair, the customer stays in the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits their turn. If there is no free chair, the customer leaves. "

My entire code is the following:

// Example program
#include <iostream>
#include <string>
#include <mutex>
#include <thread>
#include <chrono>
#include <atomic>
#include <deque>
#include <vector>
#include <condition_variable>
using namespace std;

const unsigned int NUM_CHAIRS = 2;
const unsigned int NUM_CUSTOMERS = 1;

// In a barbershop, customers are coming in and there is only one barber. If the barber is cutting a
// customers hair, the customer will wait. There are only a limited amount of chairs for the customer
// to wait on. If the chairs are full, then the customer will leave and try again later.
    
struct Barbershop
{
    public:
        Barbershop(): num_waiting(0){};
        condition_variable cv; // Acts like a receptionist
        atomic<int> num_waiting; // Number of customers waiting on chairs
        mutex cout_mtx;

};


class Barber
{
    public:
        Barber(Barbershop& shop): mem_shop(shop), hislife(&Barber::work, this){};
        void work()
        {
            unique_lock<mutex> lk(b_mu);
            if(mem_shop.num_waiting == 0)
            {
                mem_shop.cout_mtx.lock();
                cout << "Barber sleeping...\n";
                mem_shop.cout_mtx.unlock();
            }
            mem_shop.cv.wait(lk, [this]{return mem_shop.num_waiting > 0;}); // []{return mem_shop.num_waiting}
            mem_shop.cout_mtx.lock();
            cout << "Time to cut some hair!\n";
            mem_shop.cout_mtx.unlock();
            lk.unlock();
            mem_shop.cv.notify_one();
            this_thread::sleep_for(chrono::milliseconds(100));
            mem_shop.num_waiting--;
        };
        ~Barber()
        {
            hislife.join();
        }
        int jn;
        mutex b_mu;
        Barbershop& mem_shop;
        thread hislife;
        
};

class Customer
{
    public:
        Customer(Barbershop& shop, int name_id): mem_shop(shop), name(name_id), hislife(&Customer::tryGetHaircut, this){};
        void tryGetHaircut()
        {
            if(mem_shop.num_waiting == NUM_CHAIRS)
            {
                mem_shop.cout_mtx.lock();
                cout << name <<"'s wait was too long. Leaving!\n";
                mem_shop.cout_mtx.unlock();
            }
            else
            {
                mem_shop.num_waiting++;
                std::unique_lock<mutex> lk(c_mu);
                mem_shop.cv.wait(lk);
                mem_shop.cout_mtx.lock();
                cout << name << " is getting haircut!\n";
                mem_shop.cout_mtx.unlock();
            }
        };
        ~Customer()
        {
            hislife.join();
        }
        mutex c_mu;
        Barbershop& mem_shop;
        thread hislife;
        unsigned int name;

};

int main()
{
    Barbershop mybarbershop;
    Barber dan();
    vector<Customer*> customers;
    customers.reserve(NUM_CUSTOMERS-1);
    for(unsigned int i=0; i<NUM_CUSTOMERS; i++)
    {
        customers.push_back(new Customer(mybarbershop, i+1));
    }

    for(auto s : customers)
    {
        delete s;
    }
    cout << "Program Finished!\n";
    return 0;
}

However, my code isn't even making it into the Barbers thread and seems to get locked on the condition variables. Are there any blatant issues I've made in logic/syntax in solving this problem?

I am still a beginner so any help on the topic would be greatly appreciated.

Answer 1

You have a few problems:

1. There's a data race beteween if(mem_shop.num_waiting == NUM_CHAIRS) and mem_shop.num_waiting++ are not protected under a lock. Therefore two customers can join the barbershop at the same time, see a chair and both using the same chair. Hence it is possible that num_waiting > NUM_CHAIRS and more clients will join the queue when it is too long. You need to either use an atomic compare and swap or just protect the variable access with a lock.

2. mem_shop.cv.wait(lk, [this]{return mem_shop.num_waiting > 0;}); makes the barber to wait if there is people waiting. Shouldn't the condition be the opposite (wait if no one's waiting)? [this]{return !mem_shop.num_waiting;}. Also there's a data race accessing num_waiting because the barber and the clients are not accessing the same lock. Either turn num_waiting into atomic or make the barber and clients share the mutex through barbershop (so accessing both count and conditional variable is protected using the same mutex).

Note: the fact that num_waiting is atomic, does not make every operation atomic. If you do two atomic operations they won't be atomic as a whole, so if (waiting == MAX) is reading a value, then taking a decission, then waiting++ is updating the value. Using a compare and swap here may be a solution to do both things in one atomic access:

atomic_uint waiting;
unsigned expected = waiting.load();
do {
  desired = expected + 1;
} while (desired < MAX_WAITING &&
         waiting.compare_exchange_weak(expected, desired));

Here, compare_exchange_weak checks that the value in memory matches desired and returns true if that's the case. Otherwise it will return false and update expected with the last value. In that case you just need to recheck that the value you want to store still meets the boundaries (< MAX) and if it does not then you just quit.