Проблема читателей-писателей

Проблема читателей-писателей — одна из важнейших задач параллельного программирования. Формулируется она так.

Есть область памяти, позволяющая чтение и запись. Несколько потоков имеют к ней доступ, при этом одновременно могут читать сколько угодно потоков, но писать — только один. Как обеспечить такой режим доступа?

Можно обойтись обычным мьютексом, но это неоптимально — компьютерная память, как правило, устроена так, что несколько потоков могут свободно читать и писать её (единственная проблема — нет гарантии, что в процессе обработки переменная внезапно не изменится). У этой проблемы есть несколько вариантов, разные и решения. Кому отдавать приоритет — читателю или писателю — остаётся за программистом.

Первая проблема читателей-писателей (приоритет читателя)

Проблема формулируется так.

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

Вторая проблема читателей-писателей (приоритет писателя)

Проблема формулируется так.

Как только появился хоть один писатель, читателей больше не пускать. При этом читатели могут простаивать.

Примерное решение:^[1]

Глобальные целые readcount=0, writecount=0;
Глобальные мютексы mutex1, mutex2, mutex3, w, r

ЧИТАТЕЛЬ
  mutex3.enter
    r.enter
      mutex1.enter
        readcount = readcount + 1
        if readcount=1 then w.enter
      mutex1.leave
    r.leave
  mutex3.leave

  ...читаем...

  mutex1.enter
    readcount = readcount - 1
    if readcount = 0 then w.leave
  mutex1.leave

ПИСАТЕЛЬ
  mutex2.enter
    writecount = writecount + 1
    if writecount=1 then r.enter
  mutex2.leave

  w.enter
    ...пишем...
  w.leave

  mutex2.enter
    writecount = writecount - 1
    if writecount = 0 then r.leave
  mutex2.leave

Третья проблема читателей-писателей (честное распределение ресурсов)

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

  Глобальные мютексы: no_writers, no_readers, counter_mutex
  Глобальные целые: nreaders=0
  Локальные целые:  prev, current

ПИСАТЕЛЬ:
  no_writers.enter
    no_readers.enter
  no_writers.leave
    ...пишем....
  no_readers.leave

ЧИТАТЕЛЬ:
  no_writers.enter
    counter_mutex.enter
      prev := nreaders
      nreaders := nreaders + 1
    counter_mutex.leave
    if prev = 0  then no_readers.enter
  no_writers.leave

    ...читаем...

  counter_mutex.enter
    nreaders := nreaders - 1;
    current := nreaders;
  counter_mutex.leave;
  if current = 0 then no_readers.leave

В обоих фрагментах псевдокода, если есть атомарные операции наподобие InterlockedIncrement/InterlockedDecrement, от мютексов, охраняющих счётчики, можно избавиться.

Применение в программировании

Зачастую простой мьютекс, защищающий память, неоптимален. Например, в онлайн-игре список игровых комнат изменяется нечасто — когда кто-то из игроков решает открыть новую комнату, например, раз в несколько секунд. Считывается же он за одну секунду десятки раз, и выстраивать клиентов в очередь для этого не имеет смысла.

Подобные механизмы (так называемая блокировка чтения-записи) существуют во многих языках программирования и библиотеках. Например.

• Embarcadero Delphi: IMultiReadExclusiveWrite.
• POSIX: pthread_rwlock_t.
• Java: ReadWriteLock, ReentrantReadWriteLock.
• .NET Framework: System.Threading.ReaderWriterLockSlim.
• Boost: boost::shared_mutex.

См. также

• Проблема потребителя
• Проблема обедающих философов
• Проблема спящего парикмахера
• Проблема курильщиков

Примечания

1. ↑ Communications of the ACM :Concurrent Control with «Readers» and «Writers» P.J. Courtois,* F. H, 1971 [1]