# Dining Philosophers Problem III

Contents[Show]

This post ends the mini-series about the dining philosophers problem by Andre Adrian. Today, he applies powerful locks and semaphores.

By Benjamin D. Esham / Wikimedia Commons, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=56559

Here is a quick reminder about where Andre's analysis ended last time.

## `std::lock_guard` and Synchronized Output with Resource Hierarchy

```// dp_10.cpp
#include <iostream>
#include <thread>
#include <chrono>
#include <mutex>

int myrand(int min, int max) {
return rand()%(max-min)+min;
}

std::mutex mo;

void phil(int ph, std::mutex& ma, std::mutex& mb) {
while(true) {
int duration=myrand(1000, 2000);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<ph<<" thinks "<<duration<<"ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));

std::lock_guard<std::mutex> ga(ma);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<"\t\t"<<ph<<" got ma\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(1000));

std::lock_guard<std::mutex> gb(mb);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<"\t\t"<<ph<<" got mb\n";
}

duration=myrand(1000, 2000);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}
}

int main() {
std::cout<<"dp_10\n";
srand(time(nullptr));

std::mutex m1, m2, m3, m4;

std::thread t1([&] {phil(1, m1, m2);});
std::thread t2([&] {phil(2, m2, m3);});
std::thread t3([&] {phil(3, m3, m4);});
std::thread t4([&] {phil(4, m1, m4);});

t1.join();
t2.join();
t3.join();
t4.join();
}
```

The global mutex mo controls the console output resource. Every cout statement is in its block and the` lock_guard(`) template ensures that console output is not garbled.

## Modernes C++ Mentoring

Be part of my mentoring programs:

Do you want to stay informed about my mentoring programs: Subscribe via E-Mail.

## A `std::unique_lock` using deferred locking

C++ offers alternative solutions next to resource hierarchy. We currently have two separate operations to acquire the two resources. If there is only one operation to acquire the two resources, there is no longer the danger of deadlock. The first "all or nothing" solution used` unique_lock()` with `defer_lock`. The actual resource acquire happens in the `lock()` statement. See `dp_12.cpp:`

```int myrand(int min, int max) {
static std::mt19937 rnd(std::time(nullptr));
return std::uniform_int_distribution<>(min,max)(rnd);
}

std::mutex mo;

void phil(int ph, std::mutex& ma, std::mutex& mb) {
while(true) {
int duration=myrand(1000, 2000);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<ph<<" thinks "<<duration<<"ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));

std::unique_lock<std::mutex> ga(ma, std::defer_lock);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<"\t\t"<<ph<<" got ma\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(1000));

std::unique_lock<std::mutex> gb(mb,std::defer_lock);
std::lock(ga, gb);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<"\t\t"<<ph<<" got mb\n";
}

duration=myrand(1000, 2000);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}
}
```

So far, we have generated random numbers using the` rand()` function. This function is not reentrant. Not reentrant means not threadable. This error is fixed with a modified` myrand()` function. The static function object `rnd` is a Mersenne Twister random number generator. With static, we avoid a global function object. Scaling to a value between `min` and `max` is now done with `uniform_int_distribution<>`. Using the library is better than writing your code. Who would have thought simple things like cout output and the random number are so tricky in programs with threads?

## A `std::scoped_lock `with Resource Hierarchy

The second "all or nothing" solution is even more straightforward. The C++17 function` scoped_lock()` allows acquiring multiple resources. This powerful function gives us the shortest dining philosophers solution. See `dp_13.cpp`:

```void phil(int ph, std::mutex& ma, std::mutex& mb) {
while(true) {
int duration=myrand(1000, 2000);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<ph<<" thinks "<<duration<<"ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));

std::this_thread::sleep_for(std::chrono::milliseconds(1000));
std::scoped_lock sco(ma, mb);

{
std::lock_guard<std::mutex> g(mo);
std::cout<<"\t\t"<<ph<<" got ma, mb\n";
}

duration=myrand(1000, 2000);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}
}
```

There are more solutions. The original Dijkstra solution used one mutex, one semaphore per philosopher, and one state variable per philosopher. [ref 1971; Dijkstra; EWD310 Hierarchical Ordering of Sequential Processes; https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD310.html]. Andrew S. Tanenbaum provided a C language solution. [ref 2006; Tanenbaum; Operating Systems. Design and Implementation, 3rd edition; chapter 2.3.1]

## The Original Dining Philosopher's Problem using Semaphores

File `dp_14.cpp` is the Tanenbaum solution rewritten in C++20:

```// dp_14.cpp
#include <iostream>
#include <chrono>
#include <thread>
#include <mutex>
#include <semaphore>
#include <random>

int myrand(int min, int max) {
static std::mt19937 rnd(std::time(nullptr));
return std::uniform_int_distribution<>(min,max)(rnd);
}

enum {
N=5,                  // number of philosophers
THINKING=0,           // philosopher is thinking
HUNGRY=1,             // philosopher is trying to get forks
EATING=2,             // philosopher is eating
};

#define LEFT (i+N-1)%N  // number of i's left neighbor
#define RIGHT (i+1)%N   // number of i's right neighbor

int state[N];           // array to keep track of everyone's state
std::mutex mutex_;      // mutual exclusion for critical regions
std::binary_semaphore s[N]{0, 0, 0, 0, 0};
// one semaphore per philosopher

void test(int i)        // i: philosopher number, from 0 to N-1
{
if (state[i] == HUNGRY
&& state[LEFT] != EATING && state[RIGHT] != EATING) {
state[i] = EATING;
s[i].release();
}
}

void take_forks(int i)  // i: philosopher number, from 0 to N-1
{
mutex_.lock();        // enter critical region
state[i] = HUNGRY;    // record fact that philosopher i is hungry
test(i);              // try to acquire 2 forks
mutex_.unlock();      // exit critical region
s[i].acquire();       // block if forks were not acquired
}

void put_forks(int i)   // i: philosopher number, from 0 to N-1
{
mutex_.lock();        // enter critical region
state[i] = THINKING;  // philosopher has finished eating
test(LEFT);           // see if left neighbor can now eat
test(RIGHT);          // see if right neighbor can now eat
mutex_.unlock();      // exit critical region
}

std::mutex mo;

void think(int i) {
int duration = myrand(1000, 2000);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<i<<" thinks "<<duration<<"ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}

void eat(int i) {
int duration = myrand(1000, 2000);
{
std::lock_guard<std::mutex> g(mo);
std::cout<<"\t\t\t\t"<<i<<" eats "<<duration<<"ms\n";
}
std::this_thread::sleep_for(std::chrono::milliseconds(duration));
}

void philosopher(int i) // i: philosopher number, from 0 to N-1
{
while (true) {        // repeat forever
think(i);           // philosopher is thinking
take_forks(i);      // acquire two forks or block
eat(i);             // yum-yum, spaghetti
put_forks(i);       // put both forks back on table
}
}

int main() {
std::cout<<"dp_14\n";

std::thread t0([&] {philosopher(0);});
std::thread t1([&] {philosopher(1);});
std::thread t2([&] {philosopher(2);});
std::thread t3([&] {philosopher(3);});
std::thread t4([&] {philosopher(4);});
t0.join();
t1.join();
t2.join();
t3.join();
t4.join();
}
```

By the way, the semaphore is the oldest thread synchronization primitive. Dijkstra defined the P() and V() operation in 1965: "It is the P-operation, which represents the potential delay, viz. when a process initiates a P-operation on a semaphore, that at that moment is = 0, in that case, this P-operation cannot be completed until another process has performed a V-operation on the same semaphore and has given it the value '1'." Today P() is called` release()` and V() is called` acquire()`. [ref 1965; Dijkstra; EWD123 Cooperating sequential processes; https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html]

## A C++20 Compatible Semaphore

You need  a C++20 compiler like LLVM (clang++) version 13.0.0 or newer to compile `dp_14.cpp`. Or you change the` #include <semaphore`> into `#include "semaphore.h"` and provide the following header file. Then a C++11 compiler is sufficient.

```// semaphore.h
#include <mutex>
#include <condition_variable>
#include <limits>

namespace std {
template <std::ptrdiff_t least_max_value
= std::numeric_limits<std::ptrdiff_t>::max()>
class counting_semaphore {
public:
counting_semaphore(std::ptrdiff_t desired) : counter(desired) {}

counting_semaphore(const counting_semaphore&) = delete;
counting_semaphore& operator=(const counting_semaphore&) = delete;

inline void release(ptrdiff_t update = 1) {
std::unique_lock<std::mutex> lock(mutex_);
counter += update;
cv.notify_one();
}

inline void acquire() {
std::unique_lock<std::mutex> lock(mutex_);
while (0 == counter) cv.wait(lock);
--counter;
}

private:
ptrdiff_t counter;
std::mutex mutex_;
std::condition_variable cv;
};

using binary_semaphore = counting_semaphore<1>;
}
```

The C++ semaphore consists of a counter, a `mutex`, and a `condition_variable.` After 14 program versions, we leave this topic. The programs versions 1 to 6 have problems. I presented them to show bad multi-thread programming. Don't copy that!

## What's next?

` constexpr` functions have much in common with templates and become more powerful with C++20. I will write about them in my next post.

Thanks a lot to my Patreon Supporters: Matt Braun, Roman Postanciuc, Tobias Zindl, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, John Wiederhirn, Yacob Cohen-Arazi, Florian Tischler, Robin Furness, Michael Young, Holger Detering, Bernd Mühlhaus, Matthieu Bolt, Stephen Kelley, Kyle Dean, Tusar Palauri, Dmitry Farberov, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, and Rob North.

Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, and Slavko Radman.

My special thanks to Embarcadero

My special thanks to PVS-Studio

My special thanks to Tipi.build

My special thanks to Take Up code

## Seminars

I'm happy to give online seminars or face-to-face seminars worldwide. Please call me if you have any questions.

### Standard Seminars (English/German)

Here is a compilation of my standard seminars. These seminars are only meant to give you a first orientation.

• C++ - The Core Language
• C++ - The Standard Library
• C++ - Compact
• C++11 and C++14
• Concurrency with Modern C++
• Design Pattern and Architectural Pattern with C++
• Embedded Programming with Modern C++
• Generic Programming (Templates) with C++

#### New

• Clean Code with Modern C++
• C++20

### Modernes C++,

#### Comments

0 #1 fred gannett 2023-04-19 09:20
I love the explanations of how parallel c++ works so sorry to ask the awkward questions but in all the examples up to and including dp_10.cpp there are only 4 or less dining philosophers. The original program description and the image you have at the start has 5 hungry thinkers.
The parallel nature of the answer changes when there are more than 4 diners chasing forks because there can, in a well ordered system, be 2 diners and 3 thinkers at one time. When there are only 4 diners someone will always be hungry and not thinking.
Also in dp_10.cpp there is a delay between a diner getting one fork and looking for the other.
std::this_thread::sleep_for(std::chrono::milliseconds(1000));

This seems unnecessary from the problem description and removing it allows for more parallelism.

### Subscribe to the newsletter (+ pdf bundle)

 Email Please enable the javascript to submit this form

### Visitors

Today 2169

Yesterday 4371

Week 37976

Month 168101

All 12055867

Currently are 177 guests and no members online

### Latest comments

• #### C++ Core Guidelines: Passing Smart Pointers

Hi, cure in 37 useless. If oldFunc somehow call 'delete wid' it does not help, cause oldFunc knows ...

• #### C++20: Extend std::format for User-Defined Types

For MSVC v17.5, the format() member function in a user defined std::formatter specialization does not ...

• #### Dining Philosophers Problem III

I love the explanations of how parallel c++ works so sorry to ask the awkward questions but in all ...

Конечно!

• #### Covariant Return Type

Nice article, you could also use the CRTP (Curiously Recurring Template Pattern) with std::unique_ptr ...