如何让作家线程挨饿

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()方法获取锁定时,我向标准输出添加了一些输出,但为了清楚起见,我删除了输出.我在main方法中进一步向下启动线程.当我运行程序时,编写器总是有机会写入数组(导致所有读取器线程都被阻塞,这没关系)但正如我上面所说的那样,编写器根本不应该能够访问许多读者线程从数组中读取.即使我不会让读者线程在所有(参数0)睡眠作家线程不知何故找到一种方式来获得互斥.我怎么让作家挨饿呢？

Answer 1

高质量的实施std::shared_timed_mutex不会让读者和作家们挨饿.然而,随着读者数量/作者数量的增加,作者获得锁定的可能性越小.根据您当前的设置(1位作者到10位读者),我猜测作者在9%的时间内获得锁定.随着你增加这个比例,作家将减少锁定,但永远不会100%饿死.

如果你只让作家获得a 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.