如何讓作者線程餓死

Question

我已經使用C++ 14的shared_timed_mutex編寫了讀寫器問題的實現。在我看來，下面的代碼應該會導致Writer餓死，因爲太多的讀取線程一直在數據庫上工作（在這個例子中是一個簡單的數組）：作者沒有機會獲得鎖。

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），作者線程也會找到一種方法來獲得互斥鎖。那我該如何讓作家餓死？

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的作者相同，讀者或作者是否是下一個獲得gate1的機會是50/50。