Проблема читателей-писателей
Проблема читателей-писателей — одна из важнейших задач параллельного программирования. Формулируется она так.
 |
Есть область памяти, позволяющая чтение и запись. Несколько потоков имеют к ней доступ, при этом одновременно могут читать сколько угодно потоков, но писать — только один. Как обеспечить такой режим доступа? |  |
Можно обойтись обычным мьютексом, но это неоптимально — компьютерная память, как правило, устроена так, что несколько потоков могут свободно читать и писать её (единственная проблема — нет гарантии, что в процессе обработки переменная внезапно не изменится). У этой проблемы есть несколько вариантов, разные и решения. Кому отдавать приоритет — читателю или писателю — остаётся за программистом.
Содержание |
Первая проблема читателей-писателей (приоритет читателя) [править]
Проблема формулируется так.
|
Пока память открыта на чтение, давать читателям беспрепятственный доступ. Писатели могут ждать сколько угодно. | |
Вторая проблема читателей-писателей (приоритет писателя) [править]
Проблема формулируется так.
|
Как только появился хоть один писатель, читателей больше не пускать. При этом читатели могут простаивать. | |
Примерное решение:[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.
