ライタースレッドが飢えさせる方法

Question

C++のshared_timed_mutexを使用して、reader-writersの問題の実装を記述しました。私の意見では、次のコードは、あまりにも多くのリーダースレッドがデータベース（この例では単純な配列）で常に作業しているため、ライターが飢えてしまう原因となるはずです：ライターはロックを取得する機会がありません。

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

    } 
} 

スレッドが読んでいるとき、私はブロックされたモードまたはtry_lock()方法のいずれかを介してロックを取得しようとすると、書き込み、標準出力にいくつかの出力を追加しましたが、私は明確化のために出力を削除しました。メインメソッドでスレッドをさらに開始します。私がプログラムを実行すると、ライターは常に配列に書き込む機会を得ます（読者のスレッドはすべてブロックされますが、これは大丈夫です）。しかし、上記のように、ライターはアクセス権を得ることができないはずです配列から読み取る多くのリーダースレッド読者のスレッドをまったくスリープ状態にしていなくても（引数0）、ライタースレッドは何とかmutexを取得する方法を見つけます。どのようにして作家に飢えさせるのですか？

Answer 1

品質実装std::shared_timed_mutexは、読者も作家も飢えていません。しかし、リーダの数/ライタの数が増加するにつれて、ライタがロックを獲得する可能性は低くなる。あなたの現在の設定（1人のライターから10人の読者）で、私は、ライターが約9％の時間をかけてロックを取得していると推測しています。その比率を上げると、作者はロックを少なくしますが、決して100％飢えてしまうことはありません。

ライターのみtry_lockの下で取得させる場合、100％飢餓の可能性が大幅に増加します。

std::shared_timed_mutexが読者やライターを飢えさせることなく実装できるアルゴリズムの存在は、std::shared_timed_mutexにリーダー優先順位またはライター優先順位を指示できるAPIがない理由があります。

アルゴリズム

ミューテックス内の二つのゲートがあることを想像：gate1とgate2が。

gate1を取得するには、あなたが読者でも作家でも（ほとんど）問題ではありません。 gate1の中に別の作家がいれば、あなたは入り込むことができません。実際には遊びに来ないという追加のルールに従わなければなりません。すでに最大読者数がgate1であれば、

gate1を一度超えると、リーダーは共有ロックを所有します。

一度、gate1を過ぎると、ライターはではなく、独自のロックを所有します。共有ロックを保持しているリーダーがなくなるまで、彼はさらにgate2の外に待たなければなりません。一度gate2を過ぎると、ライターは一意のロックを所有します。

このアルゴリズムは、リーダライターがgate1を取得する場合にはほとんど差がないという点で「公平」です。 gate1の外部に多数のリーダとライタがある場合、次のスレッドはこのアルゴリズムではなく、OSによって決定されます。だからあなたはそれをサイコロのロールと考えることができます。 gate1のために競合する作家と同じ数の読者を持っている場合は、読者または作家が次の回答者であるかどうかは、50/50のチャンスです。gate1。