Как позволить писателю нить голодать

Я написал реализацию проблемы читателей-писателей, используя shared_timed_mutex из C ++ 14. По моему мнению, следующий код должен привести к тому, что Writer будет голодать, так как слишком много потоков читателей работают с базой данных (в данном примере это простой массив) все время: 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), потоки писателя каким-то образом находят способ получить мьютекс. Как мне заставить писателя голодать тогда?

4

Решение

Качественная реализация 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следующий поток для входа определяется ОС, а не этим алгоритмом. Таким образом, вы можете думать об этом как о броске костей. Если у вас такое же количество читателей, как у авторов, соревнующихся за gate1, это шанс 50/50, будь то читатель или писатель следующий, чтобы пройти gate1,

6

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]