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.

 An illustration of the dining philosophers problem

 

 

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.
 
dp 5
 

A std::unique_lock using deferred locking

 
C++ offers alternative solutions next to resource hierarchy. At the moment we 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 uses unique_lock() with defer_lock. The real 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 the 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 own code. Who would have thought that simple things like cout output and random number are so difficult 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 Philosophers 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 a lot 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, Marko, G Prvulovic, Reinhold Dröge, Abernitzke, Frank Grimm, Sakib, Broeserl, António Pina, Sergey Agafyin, Андрей Бурмистров, Jake, GS, Lawton Shoemake, Animus24, Jozo Leko, John Breland, Louis St-Amour, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, Kris Kafka, Mario Luoni, Neil Wang, Friedrich Huber, lennonli, Pramod Tikare Muralidhara, Peter Ware, Daniel Hufschläger, Alessandro Pezzato, Evangelos Denaxas, Bob Perry, Satish Vangipuram, Andi Ireland, Richard Ohnemus, Michael Dunsky, Leo Goodstadt, Eduardo Velasquez, 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, Ralf Holly, Juan Dent, George Liao, and Daniel Ceperley.

 

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

 

 

My special thanks to Embarcadero CBUIDER STUDIO FINAL ICONS 1024 Small

 

My special thanks to PVS-Studio PVC Logo

 

Mentoring Program

My new mentoring program "Fundamentals for C++ Professionals" starts on the 22nd of April. Get more information here: https://bit.ly/MentoringProgramModernesCpp.

Seminars

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

Bookable (Online)

German

Standard Seminars (English/German)

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

New

Contact Me

Modernes C++,

RainerGrimmSmall

 

My Newest E-Books

Course: Modern C++ Concurrency in Practice

Course: C++ Standard Library including C++14 & C++17

Course: Embedded Programming with Modern C++

Course: Generic Programming (Templates)

Course: C++ Fundamentals for Professionals

Interactive Course: The All-in-One Guide to C++20

Subscribe to the newsletter (+ pdf bundle)

Blog archive

Source Code

Visitors

Today 540

Yesterday 6623

Week 7163

Month 145555

All 9425578

Currently are 138 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments