Dining Philosophers Problem II

Contents[Show]

In the last post "Dining Philosophers Problem I", Andre Adrian started his analysis of the classical dining philosophers' problem. Today, he uses atomics, mutexes, and locks.

 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

Let me give you a quick reminder about where Andre's analysis ended last time.

Still Erroneous Busy Waiting with Resource Hierarchy

 

// dp_5.cpp
#include <iostream>
#include <thread>
#include <chrono>
#include <atomic>

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

void lock(std::atomic<int>& m) {
  while (m)
    ; // busy waiting
  m=1;
}

void unlock(std::atomic<int>& m) {
  m=0;
}

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

    lock(ma);
    std::cout<<"\t\t"<<ph<<" got ma\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(1000));

    lock(mb);
    std::cout<<"\t\t"<<ph<<" got mb\n";

    duration=myrand(1000, 2000);
    std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(duration));

    unlock(mb);
    unlock(ma);
  }
}

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

  std::atomic<int> m1{0}, m2{0}, m3{0}, m4{0};

  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 program looks fine but has a tiny chance of misbehavior. The two operations "is a resource available" and "mark resource as in use" in the lock() function is atomic, but they are still two operations. Between these two operations, the scheduler can place a thread switch. And this thread switch at this most inconvenient time can produce very hard-to-find bugs in the program.

Optimized Busy Waiting with Resource Hierarchy

Thankfully all current computers have an atomic operation "test the resource and if the test is positive mark resource as in use". In the programming language C++, the atomic_flag type makes this special "test and set" operation available for us. File dp_6.cpp is the first correct solution for the dining philosophers problem:

// dp_6.cpp
#include <iostream>
#include <thread>
#include <chrono>
#include <atomic>

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

void lock(std::atomic_flag& m) {
  while (m.test_and_set())
    ; // busy waiting
}

void unlock(std::atomic_flag& m) {
  m.clear();
}

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

    lock(ma);
    std::cout<<"\t\t"<<ph<<" got ma\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(1000));

    lock(mb);
    std::cout<<"\t\t"<<ph<<" got mb\n";

    duration=myrand(1000, 2000);
    std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(duration));

    unlock(mb);
    unlock(ma);
  }
}

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

  std::atomic_flag m1, m2, m3, m4;
  unlock(m1);
  unlock(m2);
  unlock(m3);
  unlock(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 program version 6 output is similar to the last output. The dining philosophers' problem is good-natured. One resource is only shared between two threads. The atomic_flag spinlock is needed if several threads want to get the same resource.
 

Good low CPU load Busy Waiting with Resource Hierarchy

 
The spinlock disadvantage is the busy waiting. The while loop in lock() is a waste of CPU resources. A remedy to this problem is to put a sleep_for() function in the body of this while loop. The sleep_for() function performs waiting in the scheduler. This waiting is much better than waiting in the application. As always there is a price. The sleep_for() slows down the program's progress. File dp_7.cpp is the second correct solution:
 
// dp_7.cpp
void
lock(std::atomic_flag& m) { while (m.test_and_set()) std::this_thread::sleep_for(std::chrono::milliseconds(8)); }

 

Note: a std::this_thread::yield() instead of the sleep_for() does not reduce CPU load on the author's computer. The impact of yield() is implementation-dependent.

std::mutex with Resource Hierarchy

 
To completely avoid busy waiting we need more help from the scheduler. If every thread tells the scheduler the resource state, the scheduler can put a "wait for a resource" thread into the "waiting" state. After the scheduler gets a "resource is available" information, the waiting thread state changes to ready. The thread to scheduler information exchange is expensive. Because of this C++ offers both, spinlock and mutex. Spinlock is waiting in the thread and mutex is waiting in the scheduler.
File dp_8.cpp shows the mutex solution. Please note the #include <mutex> :
 
// dp_8.cpp
#include <iostream>
#include <thread>
#include <chrono>
#include <mutex>

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

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

    ma.lock();
    std::cout<<"\t\t"<<ph<<" got ma\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(1000));

    mb.lock();
    std::cout<<"\t\t"<<ph<<" got mb\n";

    duration=myrand(1000, 2000);
    std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n";
    std::this_thread::sleep_for(std::chrono::milliseconds(duration));
    mb.unlock(); // (9)
    ma.unlock();
  }
}

int main() {
  std::cout<<"dp_8\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();
}

 

Program version 8 is correct and uses very little CPU resources. C++ offers a wrapper to mutex to make life easier for programmers.

std::lock_guard with Resource Hierarchy

 
Using the lock_guard template, we put only the mutex into the lock. The mutex member function lock is automatically called in the locks constructor and unlock in its destructor at the end of the scope. unlock is also called if an exception is thrown.

 

The convenient version is dp_9.cpp:

 
// dp_9.cpp

void
phil(int ph, std::mutex& ma, std::mutex& mb) { while(true) { int duration=myrand(1000, 2000); std::cout<<ph<<" thinks "<<duration<<"ms\n"; std::this_thread::sleep_for(std::chrono::milliseconds(duration)); std::lock_guard<std::mutex> ga(ma); 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::cout<<"\t\t"<<ph<<" got mb\n"; duration=myrand(1000, 2000); std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms\n"; std::this_thread::sleep_for(std::chrono::milliseconds(duration)); } }

 

We get better and better. Program versions 8 and 9 are correct and are light on the CPU load. But look careful on the program output:
 
 dp 8

The program output is slightly garbled. Maybe you have seen this output distortion before. There is nothing wrong with the spinlock program versions 6 and 7 or the mutex program versions 8 and 9.
 

std::lock_guard and Synchronized Output with Resource Hierarchy

 
The console output itself is a resource. That is the reason for garbled output in multi-thread programs. The solution is to put a lock_guard around every console output. See dp_10.cpp:
 
 
// dp_10.cpp

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)); } }

 

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 no longer garbled.

std::lock_guard and Synchronized Output with Resource Hierarchy and a count

 
As a little bonus, I added dp_11.cpp. This program version counts the number of philosophers threads that are eating at the same time. Because we have 4 forks, there should be times where 2 philosopher threads eat concurrently. Please note that you need again #include <atomic>. See dp_11.cpp:
 
// dp_11.cpp

std::mutex mo; std::atomic<int> cnt = 0; 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); ++cnt; { std::lock_guard<std::mutex> g(mo); std::cout<<"\t\t\t\t"<<ph<<" eats "<<duration<<"ms "<<cnt<<"\n"; } std::this_thread::sleep_for(std::chrono::milliseconds(duration)); --cnt; } }

 

The program version 11 output is:
 
dp 11

 

The addition is the number 1 or 2 at the end of the "eats" logging.

What's next?

In his next installment of the dining philosophers problem, Andre uses std::unique_lock (C++11), std::scoped_lock (C++17), and std::semaphore (C++20).

 

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 431

Yesterday 6623

Week 7054

Month 145446

All 9425469

Currently are 133 guests and no members online

Kubik-Rubik Joomla! Extensions

Latest comments