Dining Philosophers Problem III

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

Lesezeit: 10 Min.
In Pocket speichern
vorlesen Druckansicht Kommentare lesen 4 Beiträge
Von
  • Rainer Grimm
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.

// 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.

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?

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]

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-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!!

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. ()