如何让作者线程饿死

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。