如何让作家线程饿死

Question

我已经使用 C++14 的 shared_timed_mutex 编写了 reader-writers 问题的实现。在我看来，下面的代码应该会导致 Writer 饿死，因为有太多 reader 线程一直在处理数据库（在这个例子中是一个简单的数组）：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 方法中进一步启动线程。当我运行程序时，作者总是有机会写入数组（导致所有 reader 线程阻塞，这没关系）但正如我上面所说，作者不应该能够完全没有访问权限，因为有太多 reader 线程从数组中读取。即使我根本不让 reader 线程休眠（参数 0），编写器线程也会以某种方式找到获取互斥锁的方法。怎么才能让作者饿死呢？

Answer 1

std::shared_timed_mutex 的高质量实施不会让 reader 或作家挨饿。然而，随着 readers / 写入者数量的增长，写入者获得锁的可能性越小。根据您当前的设置（1 个写入器到 10 个 readers），我猜测写入器大约有 9% 的时间获得锁定。当您增加该比率时，作者将获得更少的锁，但永远不会 100% 饿死。

如果只让写手在try_lock下获取，那你100%饿死它的几率会大大增加。

允许 std::shared_timed_mutex 在不饿死 reader 或编写者的情况下实现的算法的存在是 std::shared_timed_mutex 没有允许 API 的原因你决定 reader-优先或作者优先。

算法

假设互斥体中有两个门：gate1 和 gate2。

要通过 gate1，无论您是 reader 还是作家，（几乎）都无关紧要。如果 gate1 里面有另一个作者，你就进不去。读者必须遵守一个额外的规则，这个规则在实践中永远不会发挥作用：如果已经有最大数量的 reader 过去了gate1，进不去

一旦超过 gate1，一个 reader 拥有共享锁。

一旦超过 gate1，写入者不拥有唯一锁。他必须在 gate2 之外进一步等待，直到不再有 reader 持有共享锁。一旦超过 gate2，作者便拥有唯一锁。

此算法是 "fair"，因为如果您是 reader 或通过 gate1 的作家，它几乎没有区别。如果在 gate1 之外有一堆 reader 和作者，那么下一个进入的线程是由 OS 决定的，而不是由这个算法决定的。所以你可以把它想象成掷骰子。如果您的 reader 数量与竞争 gate1 的作家相同，则 reader 或作家是下一个通过 [=14] 的机会是 50/50 =].

如何让作家线程饿死

How to let a writer thread starve

c++

multithreading

c++14

starvation