The Sleeping Barber

Sleeping barber

The Sleeping Barber is a classic synchronization problem. It was used by Edsger W. Dijkstra as an example in his lecture notes, illustrating the use of semaphores.

Imagine a barbershop that has a waiting room, separated from the room where the barber works. The waiting room has an entry and next to it an exit to the room with the barber’s chair. When the barber has finished a haircut, he opens the door to the waiting room and inspects it. If the waiting room is not empty, he invites the next customer, otherwise he goes to sleep in one of the chairs in the waiting room. The complementary behaviour of the customers is as follows: when they find zero or more customers in the waiting room, they just wait their turn, when they find, however, the sleeping barber — they wake him up.

Barber Shop

In order to shape the problem further, we are going to assume that the barbershop has a limited number of chairs in the waiting room. If a customer enters the shop and all chairs are occupied, he leaves the shop. Furthermore, before going to sleep, the barber sets an alarm clock that wakes him up when it’s time to close the shop.

Race conditions

Although the concept may be familiar, I find it useful to start by giving a brief explanation of what exactly a race condition is, as it brings us into a problem-solving mindset. A race condition may occur when two or more processes access and change shared data simultaneously. The outcome of the program depends on the relative timing of these processes, which can cause unexpected results. When the correct functioning of the system relies on a specific order of execution, but the order in which the events occur is unpredictable, we have a race condition. In our case, the barber and the customers are processes that access and change the same data - the waiting room.
While it may not be immediately apparent, the barbershop is affected by two race conditions:

  1. The barber may fall asleep while there are customers in the waiting room. Imagine a customer walks in to an empty waiting room - an indication that the barber is currently giving a haircut. The customer proceeds towards one of the chairs. In the meantime, the barber finishes the haircut and goes to check the waiting room. If the customer is slow, he might not make it to his seat before the barber checks the waiting room. In that case, the barber gets to inspect the waiting chairs first, finds them empty, and comes to the conclusion that nobody is waiting for him. Hence, he falls asleep, leaving the slow customer waiting forever. The customer will sit down waiting indefinitely for the barber to invite him into the working room.
  2. Two or more customers may enter the waiting room and try to sit down at the same time. If there’s only one free chair available, they end up bumping into each other indefinitely, like stuck characters in a video game.

Classic solution

We need to synchronize access to the waiting room, so that only one process can access it at a time. We can achieve this with a simple mutex. Whenever a process (a customer or the barber) wants to check and modify the state of the shared resource (the waiting room), it has to acquire the mutex first. When it’s done, it releases the mutex, allowing other processes to access the resource. That would be the equivalent of a sliding door, which only allows one person in or out at a time.

Sliding Door

As for “waking up the barber” and “waiting for the barber to finish a haircut”, we can use a C++20 semaphore.

17
18
19
20
21
22
constexpr static auto CHAIRS = 5;      // number of chairs in the waiting room
std::atomic_bool shuttingDown{false};  // true when the barbershop is closing
auto waiting = 0;                      // number of waiting customers
std::mutex mx;                         // protection for the waiting room
std::counting_semaphore<CHAIRS> cs{0}; // signals when a customer arrives
std::binary_semaphore bs{0};           // signals when the barber is ready

When the barber comes to work, he opens the shop and executes the barber function. Note that we had to use try_acquire_for, checking periodically that the shop is still open. Otherwise, if the barber doesn’t get any customers before closing time, he never wakes up, thus leaving the shop open indefinitely. This is how we simulate the “alarm clock”.

41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void barber() {
  std::unique_lock lock(mx, std::defer_lock);
  while (!shuttingDown.load()) {
    // "sleep" until a customer arrives, or until the barbershop is closing
    bool arrived = cs.try_acquire_for(std::chrono::seconds(5));
    if (!arrived) {
      continue;
    }
    lock.lock();   // protect the waiting room
    --waiting;     // invite a customer
    lock.unlock(); // let others use the waiting room
    haircut();     // cut hair
    bs.release();  // let the customer go
  }
}

When customers arrive, they execute the customer function. The customer does not have to loop, as it only needs to get a haircut and leave. Notice that there’s an artificial delay introduced before a customer enters the shop, as to randomize the order in which customers arrive.

60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
void customer(int id, int delay) {
  std::this_thread::sleep_for(std::chrono::seconds(delay));
  std::unique_lock lock(mx);
  if (waiting < CHAIRS) {
    std::cout << "Customer " << id << " enters the barbershop.\n";
    ++waiting;     // enter the waiting room
    lock.unlock(); // let others use the waiting room
  } else {
    std::cout << "Customer " << id << " leaves the barbershop.\n";
    return;        // leave the barbershop
  }
  cs.release();    // wake up the barber
  bs.acquire();    // wait until the barber finishes the haircut
  std::cout << "Customer " << id << " got a haircut.\n";
}

The full code, together with the main function I used for testing, can be found here.

Using only atomics

Since C++20, it is possible to solve the problem using only atomics. We no longer need the mutex nor any of the semaphores. However, the barber will have to rely on his best friend coming in to wake him up before the shop closes, instead of using an alarm clock.

15
16
17
18
constexpr static auto CHAIRS = 5;     // number of chairs in the waiting room
std::atomic_bool shuttingDown{false}; // true when the barbershop is closing
std::atomic_int waiting{0};           // number of waiting customers
std::atomic_bool bs{false};           // signals when the barber is ready

The barber can call wait on the atomic_int, which will block until a customer comes in and calls notify_one on it. For a comparison, this if very similar to the way Object can be used in Java as a basic synchronization mechanism. It is the root of the class hierarchy, so essentially every object in Java can provide this functionality. However, wait and notify_one are not enough to solve the problem. We need the guarantee that any modifications to the waiting and bs variables happen atomically.

37
38
39
40
41
42
43
44
45
46
47
void barber() {
  while (true) {
    waiting.wait(0); // "sleep" until a customer arrives
    if (shuttingDown.load()) {
      break;
    }
    haircut();       // cut hair
    bs.store(true);  // barber is ready
    bs.notify_one(); // let the customer go
  }
}

As for the customers, we have to be careful not to end up with more of them than there are waiting chairs, after updating the state of the waiting room. Since waiting is no longer protected by a mutex, two or more clients may attempt to modify it at the same time. Although the updates themselves would happen atomically, the comparison at line 56 could evaluate to true for all of them. There is no guarantee that between the comparison and the update, other customers won’t come in and fill up the waiting room. Hence, we have to use a compare_exchange function, which only updates the value of waiting if it remains unchanged. Note that if the compare-exchange operation succeeds, it does not mean that everyone stood still in the waiting room. Other customers are still free to come and go in the meantime, it’s just that we’re making sure the waiting room is not full when we try to sit down. However, this ABA problem will not affect the correct functioning of the barbershop.

52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
void customer(int id, int delay) {
  std::this_thread::sleep_for(std::chrono::seconds(delay));
  while (!shuttingDown.load()) {
    auto w = waiting.load();
    if (w < CHAIRS) {
      if (waiting.compare_exchange_strong(w, w + 1)) {
        std::cout << "Customer " << id << " enters the barbershop.\n";
        waiting.notify_one(); // wake up the barber
        break;
      }
    } else {
      std::cout << "Customer " << id << " leaves the barbershop.\n";
      return;
    }
  }
  bs.wait(false); // wait until the barber finishes the haircut
  std::cout << "Customer " << id << " got a haircut.\n";
}

Find the complete cpp file here.

FIFO barbershop

In the previous solutions, the customers are not necessarily served in the order they arrive. For example, if the barber comes to the waiting room and finds it full, he picks a random customer to invite into the working room. However, we can easily modify the classic code to make sure the customers are served in a first-in-first-out manner. We need to maintain a queue of customers waiting to get their haircuts. Each customer has its own semaphore, which is used to notify it when the haircut is done. Access to the queue is synchronized through a mutex, same as we did before with the waiting room.

19
20
21
22
23
24
25
typedef std::queue<std::shared_ptr<std::binary_semaphore>> waiting_queue;

constexpr static auto CHAIRS = 5;      // number of chairs in the waiting room
std::atomic_bool shuttingDown{false};  // true when the barbershop is closing
waiting_queue waiting;                 // customers queue
std::mutex mx;                         // protection for the waiting room
std::counting_semaphore<CHAIRS> cs{0}; // signals when a customer arrives

The barber picks the first customer in the queue and invites him into the working room.

44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
void barber() {
  std::unique_lock lock(mx, std::defer_lock);
  while (!shuttingDown.load()) {
    // "sleep" until a customer arrives, or until the barbershop is closing
    bool arrived = cs.try_acquire_for(std::chrono::seconds(5));
    if (!arrived) {
      continue;
    }
    lock.lock();                         // protect the waiting room
    auto customer_sem = waiting.front(); // invite the first customer in-line
    waiting.pop();                       // free the seat
    lock.unlock();                       // let others use the waiting room
    haircut();                           // cut hair
    customer_sem->release();             // let the customer go
  }
}

The customer takes a sit in the waiting queue and waits for the barber to finish the haircut. Both the barber and the customer share a pointer to the same semaphore, which is unique to the customer. This way, the barber can use the semaphore to signal a particular customer that the haircut is done.

64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
void customer(int id, int delay) {
  std::this_thread::sleep_for(std::chrono::seconds(delay));
  std::unique_lock lock(mx);
  if (waiting.size() < CHAIRS) {
    std::cout << "Customer " << id << " enters the barbershop.\n";
    auto customer_sem = std::make_shared<std::binary_semaphore>(0);
    waiting.emplace(customer_sem); // take a seat
    lock.unlock();                 // let others use the waiting room
    cs.release();                  // wake up the barber
    customer_sem->acquire();       // wait until the barber finishes the haircut
  } else {
    std::cout << "Customer " << id << " leaves the barbershop.\n";
    return;                        // leave the barbershop
  }
  std::cout << "Customer " << id << " got a haircut.\n";
}

See the full code here.

Catching data-races with TSan

Clang’s ThreadSanitizer (TSan) is a tool that detects data races and other threading-related issues at runtime. It is quite useful, consisting of a compiler instrumentation module and a run-time library. It can help us find bugs that are very hard to detect otherwise. To use ThreadSanitized with Clang, you need to enable it by adding the -fsanitize=thread flag during compilation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
 * Program used to illustrate a data-race.
 * Compile it with ThreadSanitizer enabled:
 * clang++ -Wall -O2 -std=c++20 -fsanitize=thread -o data-race data-race.cpp -pthread
 */

#include <iostream>
#include <thread>

int shared_data = 0;

void increment() {
  for (int i = 0; i < 100000; ++i) {
    ++shared_data;
  }
}

int main() {
  std::thread t1(increment);
  std::thread t2(increment);

  t1.join();
  t2.join();

  std::cout << "Shared data: " << shared_data << '\n';
  return 0;
}

When running it, TSan prints the following warning (I trimmed it a bit for the sake of brevity):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
==================
WARNING: ThreadSanitizer: data race (pid=2206)
  Write of size 4 at 0x5637e35656ac by thread T2:
    #0 increment() <null> (data-race+0xd4421) ...
    #1 std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (*)()> > >::_M_run() <null> (data-race+0xd46a9) ...
    #2 <null> <null> (libstdc++.so.6+0xd44a2) ...

  Previous write of size 4 at 0x5637e35656ac by thread T1:
    #0 increment() <null> (data-race+0xd4421) ...
    #1 std::thread::_State_impl<std::thread::_Invoker<std::tuple<void (*)()> > >::_M_run() <null> (data-race+0xd46a9) ...
    #2 <null> <null> (libstdc++.so.6+0xd44a2) ...

  Location is global 'shared_data' of size 4 at 0x5637e35656ac (data-race+0x14fb6ac)
  ...
==================
Shared data: 200000
ThreadSanitizer: reported 1 warnings

It reports a data-race involving two threads, T1 and T2, both trying to modify the same global location, shared_data. The essential information is at lines 4, 9 and 13. These indicate the places from which the threads are accessing the shared data (in this case, both do it from the increment function), and the location of the shared data itself (a global variable).
Implementing a fix is simple, as we just have to declare shared_data as std::atomic_int, and the warning goes away. The point was to illustrate the ease with which one can make use of TSan in order to check for races in multi-threaded code. Note that using it may slow down the execution of the program and introduce significant memory overhead. Nevertheless, it’s generally worth it during the development and testing phase.

References and Further Reading