Dining Philosophers Problem III
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(); }
lock_guard(
) template ensures that console output is not garbled.
Modernes C++ Mentoring
Do you want to stay informed: Subscribe.
A std::unique_lock
using deferred locking
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
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)); } }
The Original Dining Philosopher’s Problem using Semaphores
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(); }
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
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>; }
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, Jozo Leko, John Breland, Venkat Nandam, Jose Francisco, Douglas Tinkham, Kuchlong Kuchlong, Robert Blanch, Truels Wissneth, 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, Stephen Kelley, Kyle Dean, Tusar Palauri, Juan Dent, George Liao, Daniel Ceperley, Jon T Hess, Stephen Totten, Wolfgang Fütterer, Matthias Grün, Phillip Diekmann, Ben Atakora, Ann Shatoff, Rob North, Bhavith C Achar, Marco Parri Empoli, Philipp Lenk, Charles-Jianye Chen, Keith Jeffery,and Matt Godbolt.
Thanks, in particular, to Jon Hess, Lakshman, Christian Wittenhorst, Sherhy Pyton, Dendi Suhubdy, Sudhakar Belagurusamy, Richard Sargeant, Rusty Fleming, John Nebel, Mipko, Alicja Kaminska, Slavko Radman, and David Poole.
My special thanks to Embarcadero | |
My special thanks to PVS-Studio | |
My special thanks to Tipi.build | |
My special thanks to Take Up Code | |
My special thanks to SHAVEDYAKS |
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++
- Clean Code with Modern C++
- C++20
Contact Me
- Mobil: +49 176 5506 5086
- Mail: schulung@ModernesCpp.de
- German Seminar Page: www.ModernesCpp.de
- Mentoring Page: www.ModernesCpp.org
Modernes C++ Mentoring,
Leave a Reply
Want to join the discussion?Feel free to contribute!