Читатели и писатели: безопасность и очередь

Если механизм уже знаком - листай до «Теперь сам».

Как думаешь: что нужно сохранить

Кеш почти всегда читают и лишь иногда перестраивают. Обычный замок заставляет чтения ждать друг друга, хотя они ничего не меняют. Разрешим им входить вместе. Что произойдёт, если читатели приходят быстрее, чем завершаются старые чтения, а писатель ждёт нулевого счётчика? Ни одной гонки может не быть, а запись так и не выполнится.

На что это похоже

Представь выставочный зал. Посетители могут осматривать его вместе, но на время перестановки экспонатов зал нужно закрыть. Если пускать нового посетителя всякий раз, когда внутри уже кто-то есть, работники могут не дождаться пустого зала до вечера. Нумерованная очередь заявок делает границу явной: посетители до заявки на перестановку проходят, после неё ждут.

Механизм: от определения к алгоритму

Блокировка читателей-писателей поддерживает два режима. В состоянии readers>0 писатель отсутствует, при writer=True счётчик читателей равен нулю. Эти инварианты обеспечивают безопасность, но ничего не говорят о сроке ожидания. Читательский режим допустим лишь для операций, которые действительно не меняют общее состояние: ленивая запись кеша или скрытое обновление статистики уже требуют защиты.

Вариант с предпочтением читателей допускает новый вход, пока активного писателя нет. Он удобен при редких коротких чтениях, но писатель способен голодать. Вариант с предпочтением писателей дополнительно запрещает новые чтения, если есть ожидающий писатель. Это устраняет обгон записи свежими читателями, однако непрерывные писатели могут задерживать читателей неограниченно. Называть такой вариант безусловно справедливым неверно.

Для очереди FIFO каждому запросу выдаётся билет. Следующим допускается только билет turn. Читатель увеличивает счётчик и сразу передвигает turn: следующий читатель тоже может войти. Писатель входит лишь при нуле активных читателей и отсутствии писателя; на время его секции новые входы блокируются. Читатель за писателем не обгонит его, потому что указатель turn остановился на писательской заявке. Несколько соседних читательских заявок обслуживаются группой.

Справедливость здесь условна: допущенный поток в конце концов получает процессор и освобождает блокировку, секции конечны, ожидающий не исчезает без обработки отмены. FIFO не заставит операционную систему запланировать остановленный поток. Таймаут требует убрать билет из очереди корректно, иначе оставленный пропуск остановит всех последующих.

Нельзя просто повысить читательский режим до писательского, удерживая свою читательскую блокировку: два таких потока будут ждать друг друга. Для обновления нужен специально спроектированный протокол, отдельный режим upgrade или освобождение с повторной проверкой условия после получения записи.

Правило

Доказывай отдельно исключение писателя, совместимость читателей и порядок допуска; предпочтение одной категории само по себе не гарантирует справедливость всем.

Разбор: проследим вычисление

Реализуем очередь билетов с Condition. Билеты и счётчики меняются только под её замком. Это учебный вариант без отмены и таймаутов. Внешние данные меняются под писательским режимом; читатели проверяют инвариант пары чисел. Вывод содержит только окончательный результат, поскольку число промежуточных наблюдений зависит от расписания.

from threading import Condition, Thread

class RWLock:
    def __init__(self):
        self.cv = Condition()
        self.next = self.turn = self.readers = 0
        self.writer = False

    def acquire(self, write):
        with self.cv:
            ticket = self.next
            self.next += 1
            while (ticket != self.turn or self.writer
                   or (write and self.readers)):
                self.cv.wait()
            if write:
                self.writer = True
            else:
                self.readers += 1
            self.turn += 1
            self.cv.notify_all()

    def release(self, write):
        with self.cv:
            if write:
                self.writer = False
            else:
                self.readers -= 1
            self.cv.notify_all()

lock = RWLock()
pair = [0, 0]

def reader():
    for _ in range(100):
        lock.acquire(False)
        try:
            assert pair[1] == 2 * pair[0]
        finally:
            lock.release(False)

def writer():
    for _ in range(100):
        lock.acquire(True)
        try:
            pair[0] += 1
            pair[1] = 2 * pair[0]
        finally:
            lock.release(True)

threads = [Thread(target=reader) for _ in range(3)]
threads.append(Thread(target=writer))
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print("итог", pair)
assert pair == [100, 200]

итог [100, 200]

Разбор: где проходит граница

Рассмотри заявки R₁,R₂,W₁,R₃. В FIFO первые два читателя входят вместе. Писатель ждёт обоих, после их выхода входит один. Третий читатель не может пройти перед ним, даже если готов немедленно завершиться. В варианте с предпочтением читателей R₃ мог бы войти первым, затем R₄, R₅ и так далее. Результаты чтений при этом остаются согласованными: сбой проявляется как отсутствие прогресса писателя, а не как испорченное значение.

Что ломается без этого

Освобождение замка до завершения чтения даёт читателю частично обновлённую пару. Попытка сделать read-lock вокруг операции, которая меняет контейнер, превращает нескольких читателей в конкурирующих писателей. FIFO без удаления отменённых билетов зависает на дыре. А если замерить лишь суммарную пропускную способность, голодание редкой записи легко спрячется за высоким количеством успешно завершённых чтений.

Зачем это в работе

Используй такой режим для таблиц маршрутизации или конфигурации, где чтение действительно долго относительно затрат на синхронизацию. Очень короткие чтения иногда быстрее с обычным замком: сложный протокол увеличивает накладные расходы. При требованиях к задержкам измеряй время ожидания обеих категорий отдельно, включая непрерывную нагрузку противоположной категории. Гарантия порядка важнее среднего времени на спокойном тесте.

Теперь сам

В очереди R₁,W₁,R₂,R₃,W₂ первый читатель уже работает. Какие две читательские заявки могут затем войти совместно, и кто обязательно выполнится перед ними?