Dining Philosophers Problem III

Inhaltsverzeichnis

Mit diesem Beitrag endet die Miniserie zu dem Dining Philiosophers Problem von Andre Adrian. Heute wendet der Autor mächtige Locks und Semaphoren an.

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

Hier eine kurze Erinnerung, wo die Analyse des Autors beim letzten Mal endete.

std::lock_guard mit synchronisierter Ausgabe und Resourcenhierarchie

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

Der globale Mutex mo kontrolliert die Ressource für die Konsolenausgabe. Jede cout-Anweisung befindet sich in ihrem Block und der lock_guard() sorgt dafür, dass die Konsolenausgabe nicht verstümmelt wird.

std::unique_lock mit verzögertem Locken

C++ bietet neben dem Ressourcenhierarchie-Ansatz weitere Umsetzungen an. Im Moment haben wir zwei separate Operationen, um die beiden Ressourcen zu erwerben. Wenn es nur eine Operation gibt, um die beiden Ressourcen zu beschaffen, besteht keine Deadlock-Gefahr mehr. Die erste "alles oder nichts"-Lösung verwendet unique_lock() mit defer_lock. Der eigentliche Ressourcenerwerb erfolgt in der lock()-Anweisung. Siehe 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));
  }
}

Bis jetzt haben wir die Zufallszahlen mit der Funktion rand() erzeugt. Diese Funktion ist nicht reentrant, also nicht für Threads geeignet. Das ist bei Programmstart gut zu sehen. Die ersten vier Zufallszahlen nach "thinks" sind gleich. Mit einer geänderten myrand() Funktion wird dieser Fehler behoben. Das static Funktionsobjekt rnd ist ein Mersenne-Twister-Zufallszahlengenerator. Durch static vermeiden wir ein globales Funktionsobjekt. Die Skalierung auf einen Wert zwischen min und max erfolgt nun mit uniform_int_distribution<>. Die Bibliothek zu benutzen ist besser als eigenen Quelltext zu schreiben.

Wer hätte gedacht das so einfache Sachen wie cout Ausgabe und Zufallszahl bei Thread Programmen so schwierig sind?

std::scoped_lock

Die zweite "alles oder nichts"-Lösung ist noch einfacher: Die C++17-Funktion scoped_lock() ermöglicht den Erwerb mehrerer Ressourcen. Diese leistungsstarke Funktion bietet uns die kürzeste Lösung für das speidende Philosophen Problem. Siehe 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 scop(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));
  }
}

Es gibt mehrere Lösungen. Die ursprüngliche Dijkstra-Umsetzung verwendet einen Mutex, einen Semaphor pro Philosoph und eine Zustandsvariable pro Philosoph. [ref Dijkstra; 1971; EWD310 Hierarchical Ordering of Sequential Processes; https://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD310.html]
Andrew S. Tanenbaum lieferte eine Lösung in C. [ref Tanenbaum; 1990; Betriebssysteme Entwurf und Realisierung, Kapitel 2.3.1 Das Problem der speisenden Philosophen]

Das ursprüngliche Dining Philosphers Problem mit Semaphoren

Die Datei dp_14.cpp ist die in C++20 umgeschriebene Tanenbaum-Lösung:

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

Übrigens ist der Semaphor das älteste Primitiv für die Thread-Synchronisation. Dijkstra definierte die Operationen P() und V() im Jahr 1965: "Es ist die P-Operation, die die potentielle Verzögerung darstellt, d.h. wenn ein Prozess eine P-Operation an einem Semaphor initiiert, der in diesem Moment den Wert = 0 hat, kann diese P-Operation in diesem Fall nicht abgeschlossen werden, bis ein anderer Prozess eine V-Operation an demselben Semaphor durchgeführt hat und ihm den Wert '1' gegeben hat." Heute heißt P() release() und V() heißt acquire(). [ref Dijkstra; 1965; EWD123 Cooperating sequential processes; https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html]

Ein C++20-kompatible Semaphore

Ein C++20-Compiler wie LLVM (clang++) Version 13.0.0 oder neuer ist erforderlich, um dp14.cpp zu kompilieren. Alternativ kann man #include <semaphore> in #include "semaphore.h" ändern und die folgende Header-Datei benutzen. In dem Fall genügt ein C++11-Compiler.

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

Das C++-Semaphor besteht aus einem Zähler, einem Mutex und einer Bedingungsvariablen. Nach 14 Programmversionen verlassen wir dieses Thema. Die Programmversionen 1 bis 6 haben Probleme. Ich habe sie vorgestellt, um schlechte Multi-Thread-Programmierung zu zeigen. Bitte nicht kopieren!!

Wie geht's weiter?

constexpr-Funktionen haben viel mit Template gemeinsam und werden mit C++20 noch mächtiger. Ich werde sie in meinem nächsten Artikel genauer vorstellen. ()