В статье 1991 года «Масштабируемая синхронизация устройства чтения-записи для мультипроцессоров с общей памятью» Джона М. Меллора-Крамми и Майкла Л. Скотта имеется справедливая блокировка RW на основе алгоритма блокировки билета (https://www.cs.rochester.edu/u/scott/papers/1991_PPoPP_read_write.pdf).
В псевдокоде это выглядит так (http://www.cs.rochester.edu/research/synchronization/pseudocode/rw.html):
type counter = unsigned integer
// layout of counter
// 31 ... 16 15 ... 0
// +------------------------------+
// | reader count | writer count |
// +------------------------------+
const RC_INCR = 0x10000 // to adjust reader count
const WC_INCR = 0x1 // to adjust writer count
const W_MASK = 0xffff // to extract writer count
// mask bit for top of each count
const WC_TOPMSK = 0x8000
const RC_TOPMSK = 0x80000000
type lock = record
requests : counter := 0
completions : counter := 0
procedure start_write (L : ^lock)
counter prev_processes :=
fetch_and_clear_then_add (&L->requests, WC_TOPMSK, WC_INCR)
repeat until completions = prev_processes
procedure start_read (L : ^lock)
counter prev_writers :=
fetch_and_clear_then_add (&L->requests, RC_TOPMSK, RC_INCR) & W_MASK
repeat until (completions & W_MASK) = prev_writers
procedure end_write (L: ^lock)
clear_then_add (&L->completions, WC_TOPMSK, WC_INCR)
procedure end_read (L : ^lock)
clear_then_add (&L->completions, RC_TOPMSK, RC_INCR)
Используются примитивы fetch_and_clear_then_add и clear_then_add, которые не реализованы в современном оборудовании. Очевидно, что их можно эмулировать с помощью программного CAS-цикла.
Однако мне пришло в голову, что обоснование использования этих примитивов (предотвращение переполнения) исходит из чистой интуиции, чтобы держать счетчики читателей и писателей раздельными и точными. Но, как это бывает, интуиция может быть неправильной. Я считаю, логика предотвращения переполненияможно удалить без какого-либо вреда для алгоритма подчиненного.
Я пытался найти похожие результаты в Google, но пока ничего не нашел. Возможно, я что-то упускаю.
Итак, позвольте мне объяснить мою идею вболее подробно. Я думаю, что стандартная инструкция fetch_add будет работатьпросто отлично с этим алгоритмом.
Количество читателей содержится в верхней половине слова.Если fetch_add (0x10000) приводит к переполнению, лишний бит будет молча выпадать из границы слова.Здесь нет проблем.
Количество писателей содержится в нижней половине мира.Если fetch_add (1) приводит к переполнению, дополнительный бит будет перетекать в счетчик считывателей.К сожалению.Один из 2 ^ 16 авторов нарушает наши правила, это портит счет читателя.Но подождите, это действительно проблема?Что у нас после этого?Посмотрим.В слове requests мы имеем следующий переход:
(0xYYYY, 0xFFFF) -> (0xYYYY + 1, 0x0000) // 0xYYYY обозначает неизвестный счетчик чтения, 0xFFFF представляет счетчик записи перед переполнением
В то же время слово completions содержит значение, меньшее или равное ( 0xYYYY, 0xFFFF ).И поток 'нарушителя' начинает опрашивать слово completions, пока оно не станет точно равным требуемому значению.Любые читатели или писатели, которые начинали раньше, не могут создать какое-либо запутанное значение в слове completions.По мере того, как они прогрессируют и делают разблокировку, они неизменно достигнут требуемой величины.После этого запускается поток «нарушителя».
С другой стороны, любой новый поток, который появится позже, также не увидит никакого сбивающего с толку значения.Писатели увеличивают нижнюю половину слова, читатели увеличивают верхнюю половину.Они остаются заказанными друг против друга.И не может продолжаться до тех пор, пока поток «нарушителя» не выполнит свою работу и не разблокируется.
Разблокировка, выполненная «нарушителем», полностью компенсирует его нарушение.Это приведет к симметричному переполнению счетчика писателей в слове completions и добавит 1 к счетчику читателей.Таким образом, следующий поступивший поток начнется точно по расписанию, так как ожидал именно этого «просчитанного» значения.Все это будет работать без сучка.
Таким образом, общий результат состоит в том, что при 2 ^ 16 блокировках записи число блокировок чтения становится искаженным на 1. Все остальное выглядит хорошо.
ЛегкоНеофициальной иллюстрацией этому является ситуация, когда вообще нет взломанных считывателей.В этом случае RW-блокировка со стандартными инструкциями fetch_add () будет вести себя как обычная блокировка билета.Количество читателей будет постоянно увеличиваться на одну каждые 2 ^ 16 блокировок писателя.Но это различие мы делаем в нашем уме.На уровне машины это всего лишь шаг в 2 ^ 32 слова.На данный момент нет разницы с блокировкой простого билета.
Теперь читатели добавлены к картинке.Я не могу придумать никакого графика, когда прибывающие читатели, увеличивая только верхнюю половину слова, могут испортить всю картину.С точки зрения писателя прибытие читателя выглядит как внезапное прибытие 2 ^ 16 писателей одновременно.С этой точки зрения он по-прежнему работает как обычная блокировка билетов.
Теперь с точки зрения читателя все по-другому.Они выглядяттолько по количеству писателей и вообще не заботятся о любых переполнениях в верхнюю половину слова.Когда читатель прибывает, он вспоминает о последнем прибывшем писателе и отгоняет любых будущих писателей этим огромным шагом 2 ^ 16.Затем он ждет, пока запомнившийся писатель закончит и продолжит свою собственную работу.Когда это сделано, он делает еще один огромный шаг 2 ^ 16, так что любой, возможно, ожидающий ничего не подозревающий и наивный писатель может прийти к выводу, что это целая куча из 2 ^ 16 одновременно работающих писателей.
Пожалуйста, исправьте меня, если янеправильно с моими рассуждениями.
Реализация этого на C ++ выглядит следующим образом:
class shared_ticket_lock : non_copyable
{
public:
void lock() noexcept
{
base_type tail = tail_.fetch_add(exclusive_step, std::memory_order_relaxed);
for (;;) {
base_type head = head_.load(std::memory_order_acquire);
if (tail == head)
break;
}
}
void unlock() noexcept
{
base_type head = head_.load(std::memory_order_relaxed);
head_.store(head + exclusive_step, std::memory_order_release);
}
void lock_shared() noexcept
{
base_type tail = tail_.fetch_add(shared_step, std::memory_order_relaxed);
for (tail &= exclusive_mask;;) {
base_type head = head_.load(std::memory_order_acquire);
if (tail == (head & exclusive_mask))
break;
}
}
void unlock_shared() noexcept
{
head_.fetch_add(shared_step, std::memory_order_release);
}
private:
using base_type = std::uint32_t;
static constexpr base_type shared_step = 1 << 16;
static constexpr base_type exclusive_mask = shared_step - 1;
static constexpr base_type exclusive_step = 1;
std::atomic<base_type> head_ = ATOMIC_VAR_INIT(0);
std::atomic<base_type> tail_ = ATOMIC_VAR_INIT(0);
};
ПРИМЕЧАНИЕ: в оригинальной статье отмечается, что можно реализовать справедливую блокировку RW с обычным fetch_add, нокод будет немного сложнее.Непонятно, что имели в виду авторы.Я предполагаю что-то другое (например, поддержание счетчиков чтения и записи в отдельных словах), потому что, насколько я вижу, это абсолютно НЕ сложнее.
ОБНОВЛЕНИЕ: Рабочий код и простой тест можно найти здесь: