Wie man einen Autor Thread verhungern lässt

Question

Ich habe eine Implementierung des Reader-Writer-Problems mit shared_timed_mutex von C++ 14 geschrieben. Meiner Meinung nach sollte der folgende Code den Writer verhungern lassen, da zu viele Leser-Threads die ganze Zeit an der Datenbank arbeiten (in diesem Beispiel ein einfaches Array): Der Schreiber hat keine Chance, die Sperre zu erhalten.

mutex cout_mtx;     // controls access to standard output 
shared_timed_mutex db_mtx;  // controls access to data_base 

int data_base[] = { 0, 0, 0, 0, 0, 0 }; 

const static int NR_THREADS_READ = 10; 
const static int NR_THREADS_WRITE = 1; 
const static int SLEEP_MIN = 10; 
const static int SLEEP_MAX = 20; 

void read_database(int thread_nr) { 
    shared_lock<shared_timed_mutex> lck(db_mtx, defer_lock); // create a lock based on db_mtx but don't try to acquire the mutex yet 
    while (true) { 
     // generate new random numbers 
     std::random_device r; 
     std::default_random_engine e(r()); 
     std::uniform_int_distribution<int> uniform_dist(SLEEP_MIN, SLEEP_MAX); 
     std::uniform_int_distribution<int> uniform_dist2(0, 5); 
     int sleep_duration = uniform_dist(e); // time to sleep between read requests 
     int read_duration = uniform_dist(e); // duration of reading from data_base 
     int cell_number = uniform_dist2(e);  // what data cell will be read from 
     int cell_value = 0; 

     // wait some time before requesting another access to the database 
     this_thread::sleep_for(std::chrono::milliseconds(sleep_duration)); 

     if (!lck.try_lock()) { 

      lck.lock(); // try to get the lock in blocked state 
     } 

     // read data 
     cell_value = data_base[cell_number]; 

     lck.unlock(); 

    } 
} 

void write_database(int thread_nr) { 
    unique_lock<shared_timed_mutex> lck(db_mtx, defer_lock); // create a lock based on db_mtx but don't try to acquire the mutex yet 
    while (true) { 
     // generate new random numbers 
     std::random_device r; 
     std::default_random_engine e(r()); 
     std::uniform_int_distribution<int> uniform_dist(SLEEP_MIN, SLEEP_MAX); 
     std::uniform_int_distribution<int> uniform_dist2(0, 5); 
     int sleep_duration = uniform_dist(e); // time to sleep between write requests 
     int read_duration = uniform_dist(e); // duration of writing to data_base 
     int cell_number = uniform_dist2(e);  // what data cell will be written to 

     // wait some time before requesting another access to the database 
     this_thread::sleep_for(std::chrono::milliseconds(sleep_duration)); 

     // try to get exclusive access 
     cout_mtx.lock(); 
     cout << "Writer <" << thread_nr << "> requesting write access." << endl; 
     cout_mtx.unlock(); 

     if (!lck.try_lock()) { 

      lck.lock(); // try to get the lock in blocked state 
     } 

     // write data 
     data_base[cell_number] += 1; 

     lck.unlock(); 

    } 
} 

I addiert eine Ausgabe auf der Standardausgabe, wenn ein Thread ist das Lesen, Schreiben und versucht, das Schloss entweder in blockierter Modus oder über die try_lock() Verfahren zu erwerben, aber ich die Ausgabe aus Gründen der besseren Übersichtlichkeit halber weggelassen. Ich starte die Threads weiter unten in der Hauptmethode. Wenn ich das Programm ausführe, erhält der Schreiber immer die Möglichkeit, in das Array zu schreiben (was bewirkt, dass alle Leser-Threads blockieren, was in Ordnung ist), aber wie oben erwähnt, sollte der Schreiber überhaupt keinen Zugriff bekommen, da es auch solche gibt viele Leser-Threads lesen aus dem Array. Selbst wenn ich die Leser-Threads überhaupt nicht schlafen lasse (Argument 0), finden die Autoren-Threads irgendwie einen Weg, den Mutex zu bekommen. Wie bekomme ich den Schriftsteller dann verhungern?

Answer 1

Eine Qualitätsimplementierung von std::shared_timed_mutex verhungert weder Leser noch Schreiber. Je kleiner jedoch die Anzahl der Leser/Anzahl der Writer wird, desto geringer ist die Wahrscheinlichkeit, dass die Writer die Sperre erhalten. Mit deiner aktuellen Einstellung (1 Autor zu 10 Lesern) vermute ich, dass der Autor die Sperre etwa 9% der Zeit bekommt. Wenn du dieses Verhältnis erhöhst, erhält der Schreiber die Sperre weniger, aber wird niemals zu 100% ausgehungert.

Wenn Sie nur den Schreiber unter einer try_lock erwerben, dann werden Ihre Chancen, es zu verhungern 100% stark erhöhen.

Die Existenz der Algorithmen, die ermöglichen, ohne hungernde Leser oder Writer implementiert werden, ist der Grund, hat keine API, mit der Sie Reader-Priorität oder Schreibpriorität diktieren können.

Der Algorithmus

Stellen Sie sich vor, dass es zwei Tore innerhalb der Mutex: gate1 und gate2.

Um über gate1 zu kommen, ist es (fast) egal, ob Sie ein Leser oder ein Schreiber sind. Wenn innerhalb von gate1 ein anderer Schreiber ist, können Sie nicht hinein. Leser müssen einer zusätzlichen Regel folgen, die in der Praxis nie ins Spiel kommt: Wenn es bereits die maximale Anzahl von Lesern nach gate1 gibt, können Sie nicht hinein.

Einmal hinter gate1, besitzt ein Leser die gemeinsame Sperre.

Einmal hinter gate1, ein Schriftsteller tut nicht besitzen die einzigartige Sperre. Er muss weiter draußen warten gate2, bis es keine Leser mehr gibt, die das geteilte Schloss halten. Nach gate2 besitzt der Schreiber das einzigartige Schloss.

Dieser Algorithmus ist "fair" in dem es wenig Unterschied macht, wenn Sie ein Leser oder Schreiber sind, über gate1 zu kommen. Wenn es außerhalb von gate1 eine Reihe von Lesern und Schreibern gibt, wird der nächste Thread durch das Betriebssystem entschieden, nicht durch diesen Algorithmus. Man kann sich das also als Würfelspiel vorstellen. Wenn Sie die gleiche Anzahl von Lesern haben wie Autoren, die um gate1 konkurrieren, ist es eine 50/50 Chance, ob ein Leser oder ein Schreiber als nächstes über gate1 hinauskommt.