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

В информатике проблемы читателей и писателей являются примерами общей вычислительной проблемы в условиях параллелизма . ^{[ 1 ]} Существует как минимум три варианта проблем, связанных с ситуациями, когда множество параллельных потоков выполнения пытаются одновременно получить доступ к одному и тому же общему ресурсу.

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

Основная проблема читателя и писателя была впервые сформулирована и решена Куртуа и др. ^{[ 2 ]}^{[ 3 ]}

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

Предположим, у нас есть общая область памяти (критическая секция) с основными ограничениями, подробно описанными выше. Можно защитить общие данные с помощью мьютекса взаимного исключения , и в этом случае никакие два потока не смогут получить доступ к данным одновременно. Однако это решение неоптимально, поскольку возможно, что считыватель может _R1 иметь блокировку, а затем другой считыватель R2 _{запрашивает} доступ. Было бы глупо, бы R2 _если дождался завершения R1 _, прежде чем начинать собственную операцию чтения; вместо этого R ₂ должно быть разрешено читать ресурс вместе с R ₁ , поскольку чтение не изменяет данные, поэтому параллельные чтения безопасны. Это мотивация для первой проблемы чтения-записи , в которой добавляется ограничение, согласно которому ни один читатель не должен ждать, если общий ресурс в данный момент открыт для чтения. Это также называется предпочтением читателей , и его решение:

semaphore resource=1;
semaphore rmutex=1;
readcount=0;

/*
   resource.P() is equivalent to wait(resource)
   resource.V() is equivalent to signal(resource)
   rmutex.P() is equivalent to wait(rmutex)
   rmutex.V() is equivalent to signal(rmutex)
*/

writer() {
    resource.P();          //Lock the shared file for a writer

    <CRITICAL Section>
    // Writing is done

    <EXIT Section>
    resource.V();          //Release the shared file for use by other readers. Writers are allowed if there are no readers requesting it.
}

reader() {
    rmutex.P();           //Ensure that no other reader can execute the <Entry> section while you are in it
    <CRITICAL Section>
    readcount++;          //Indicate that you are a reader trying to enter the Critical Section
    if (readcount == 1)   //Checks if you are the first reader trying to enter CS
        resource.P();     //If you are the first reader, lock the resource from writers. Resource stays reserved for subsequent readers
    <EXIT CRITICAL Section>
    rmutex.V();           //Release

    // Do the Reading

    rmutex.P();           //Ensure that no other reader can execute the <Exit> section while you are in it
    <CRITICAL Section>
    readcount--;          //Indicate that you no longer need the shared resource. One fewer reader
    if (readcount == 0)   //Checks if you are the last (only) reader who is reading the shared file
        resource.V();     //If you are last reader, then you can unlock the resource. This makes it available to writers.
    <EXIT CRITICAL Section>
    rmutex.V();           //Release
}

В этом решении проблемы чтения/записи первый читатель должен заблокировать ресурс (общий файл), если таковой доступен. После того как файл заблокирован для авторов, он может использоваться многими последующими читателями без необходимости повторно блокировать его.

Прежде чем войти в критический раздел , каждый новый читатель должен пройти входной раздел. Однако в разделе ввода одновременно может находиться только один читатель. Это делается для того, чтобы избежать состояния гонки на читателях (в этом контексте состояние гонки — это состояние, при котором два или более потоков одновременно просыпаются и пытаются войти в критическую секцию; без дополнительных ограничений поведение является недетерминированным. Например, два считыватели одновременно увеличивают счетчик чтений, и оба пытаются заблокировать ресурс, что приводит к блокировке одного читателя). Для этого каждый читатель, входящий в <Раздел ВХОД>, блокирует <Раздел ВХОД> для себя до тех пор, пока не закончит с ним работу. На данный момент читатели не блокируют ресурс. Они только блокируют раздел входа, чтобы ни один другой читатель не мог войти в него, пока он там находится. Как только считыватель завершит выполнение раздела ввода, он разблокирует его, подав сигнал о мьютексе. Сигнализация эквивалентна: mutex.V() в приведенном выше коде. То же самое справедливо и для <Раздел ВЫХОД>. В разделе «Выход» одновременно может находиться не более одного читателя, поэтому каждый читатель должен заявить и заблокировать для себя раздел «Выход», прежде чем использовать его.

Как только первый читатель окажется в разделе входа, он заблокирует ресурс. В этом случае авторы не смогут получить к нему доступ. Последующие читатели могут просто использовать заблокированный (от авторов) ресурс. Читатель, который финиширует последним (на что указывает переменная readcount), должен разблокировать ресурс, тем самым сделав его доступным для авторов.

В этом решении каждый писатель должен заявить права на ресурс индивидуально. Это означает, что поток читателей может впоследствии заблокировать всех потенциальных писателей и уморить их голодом. Это так, потому что после того, как первый читатель заблокирует ресурс, ни один писатель не сможет его заблокировать до того, как он будет освобожден. И его выпустит только последний читатель. Следовательно, такое решение не удовлетворяет справедливости.

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

Первое решение неоптимально, поскольку возможно, что читатель R ₁ может иметь блокировку, писатель W ожидает блокировки, а затем читатель R ₂ запрашивает доступ. Было бы несправедливо, если бы R ₂ вскочил сразу перед W ; если бы это происходило достаточно часто, W умер бы от голода . Вместо этого W должен начать как можно скорее. Это мотивация для второй проблемы чтения-записи , в которой добавляется ограничение, согласно которому ни один писатель, добавленный в очередь, не должен ждать дольше, чем это абсолютно необходимо . Это также называется предпочтением писателей .

Решение сценария предпочтений писателей следующее: ^{[ 2 ]}

int readcount, writecount;                   //(initial value = 0)
semaphore rmutex, wmutex, readTry, resource; //(initial value = 1)

//READER
reader() {
<ENTRY Section>
  readTry.P();                 //Indicate a reader is trying to enter
  rmutex.P();                  //lock entry section to avoid race condition with other readers
  readcount++;                 //report yourself as a reader
  if (readcount == 1)          //checks if you are first reader
    resource.P();              //if you are first reader, lock  the resource
  rmutex.V();                  //release entry section for other readers
  readTry.V();                 //indicate you are done trying to access the resource

<CRITICAL Section>
//reading is performed

<EXIT Section>
  rmutex.P();                  //reserve exit section - avoids race condition with readers
  readcount--;                 //indicate you're leaving
  if (readcount == 0)          //checks if you are last reader leaving
    resource.V();              //if last, you must release the locked resource
  rmutex.V();                  //release exit section for other readers
}

//WRITER
writer() {
<ENTRY Section>
  wmutex.P();                  //reserve entry section for writers - avoids race conditions
  writecount++;                //report yourself as a writer entering
  if (writecount == 1)         //checks if you're first writer
    readTry.P();               //if you're first, then you must lock the readers out. Prevent them from trying to enter CS
  wmutex.V();                  //release entry section
  resource.P();                //reserve the resource for yourself - prevents other writers from simultaneously editing the shared resource
<CRITICAL Section>
  //writing is performed
  resource.V();                //release file

<EXIT Section>
  wmutex.P();                  //reserve exit section
  writecount--;                //indicate you're leaving
  if (writecount == 0)         //checks if you're the last writer
    readTry.V();               //if you're last writer, you must unlock the readers. Allows them to try enter CS for reading
  wmutex.V();                  //release exit section
}

В этом решении предпочтение отдается писателям. Это достигается за счет того, что каждый читатель принудительно блокирует и освобождает семафор повторной попытки индивидуально. С другой стороны, авторам не нужно блокировать его индивидуально. Только первая запись заблокирует попытку чтения, а затем все последующие записи смогут просто использовать ресурс по мере его освобождения предыдущим записывающим устройством. Самый последний записывающий должен освободить семафор попытки чтения, тем самым открывая читателям возможность попробовать прочитать.

Ни один читатель не может участвовать в разделе ввода, если семафор чтения был установлен записывающим устройством ранее. Читатель должен дождаться, пока последний писатель разблокирует ресурс и повторит попытку семафоров. С другой стороны, если конкретный читатель заблокировал семафор повторной попытки, это укажет любому потенциальному одновременному писателю, что в разделе ввода есть читатель. Таким образом, модуль записи будет ждать, пока читатель освободит попытку чтения, а затем модуль записи немедленно заблокирует ее для себя и всех последующих авторов. Однако автор не сможет получить доступ к ресурсу до тех пор, пока текущий читатель не освободит ресурс, что происходит только после того, как читатель завершит работу с ресурсом в критическом разделе.

Семафор ресурса может быть заблокирован как автором, так и читателем в их разделе ввода. Они могут сделать это только после первой блокировки семафора повторной попытки, что может сделать только один из них одновременно.

Затем он возьмет на себя контроль над ресурсом, как только текущий читатель завершит чтение, и заблокирует всех будущих читателей. Все последующие считыватели зависнут на семафоре readtry, ожидая, пока писатели закончат работу с ресурсом и откроют шлюз, выпустив readtry.

rmutex и wmutex используются точно так же, как и в первом решении. Их единственная цель — избежать гонок среди читателей и писателей, пока они находятся в своих разделах входа или выхода.

Третья проблема читателей и писателей

Фактически, решения, подразумеваемые обеими постановками задачи, могут привести к голоданию — первое может привести к голоданию авторов в очереди, а второе — к голоданию читателей. Поэтому иногда предлагается третья проблема чтения-записи , которая добавляет ограничение: ни одному потоку не должно быть позволено голодать ; то есть операция получения блокировки общих данных всегда будет завершаться через ограниченный промежуток времени. Решение, справедливое как для читателей, так и для писателей, может быть следующим:

int readcount;                // init to 0; number of readers currently accessing resource

// all semaphores initialised to 1
semaphore resource;           // controls access (read/write) to the resource. Binary semaphore.
semaphore rmutex;             // for syncing changes to shared variable readcount
semaphore serviceQueue;       // FAIRNESS: preserves ordering of requests (signaling must be FIFO)

//READER
reader() {
<ENTRY Section>
  serviceQueue.P();           // wait in line to be serviced
  rmutex.P();                 // request exclusive access to readcount
  readcount++;                // update count of active readers
  if (readcount == 1)         // if I am the first reader
    resource.P();             // request resource access for readers (writers blocked)
  serviceQueue.V();           // let next in line be serviced
  rmutex.V();                 // release access to readcount
    
<CRITICAL Section>
//reading is performed
    
<EXIT Section>
  rmutex.P();                 // request exclusive access to readcount
  readcount--;                // update count of active readers
  if (readcount == 0)         // if there are no readers left
    resource.V();             // release resource access for all
  rmutex.V();                 // release access to readcount
}

//WRITER
writer() {
<ENTRY Section>
  serviceQueue.P();           // wait in line to be serviced
  resource.P();               // request exclusive access to resource
  serviceQueue.V();           // let next in line be serviced
    
<CRITICAL Section>
// writing is performed
    
<EXIT Section>
  resource.V();               // release resource access for next reader/writer
}

Это решение может удовлетворять условию, что «ни одному потоку не должно быть позволено голодать» тогда и только тогда, когда семафоры сохраняют порядок «первым пришел — первым обслужен» при блокировке и освобождении потоков. В противном случае, например, заблокированный модуль записи может оставаться заблокированным на неопределенный срок, в то время как цикл других операций записи будет уменьшать семафор, прежде чем он сможет это сделать.

Простейшая задача чтения и записи

Простейшая задача чтения-записи, в которой используются только два семафора и не требуется массив читателей для чтения данных в буфере.

Обратите внимание, что это решение проще, чем общий случай, поскольку оно эквивалентно проблеме с ограниченным буфером , и поэтому только N читателей могут входить параллельно, где N — размер буфера.

Читатель

do {
    wait(read)
    ............
    reading data
    ............
    signal(write)
} while (TRUE);

Писатель

do {
    wait(write)
    .............
    writing data
    .............
    signal(read)
} while (TRUE);

Алгоритм

Reader будет работать после Writer из-за семафора чтения.
Writer прекратит запись, когда семафор записи достигнет 0.
Reader прекратит чтение, когда семафор чтения достигнет 0.

В Writer значение семафора записи передается для семафора чтения, а в Reader значение чтения передается для записи по завершении цикла.

См. также

Ссылки

^ Таненбаум, Эндрю С. (2006), Операционные системы – проектирование и реализация, 3-е издание [Глава: 2.3.2 Проблема читателей и писателей] , Pearson Education, Inc.
^ Jump up to: ^а ^б Куртуа, П.Дж.; Хейманс, Ф.; Парнас, Д.Л. (1971). «Параллельное управление с «Читателями» и «Писателями» » (PDF) . Коммуникации АКМ . 14 (10): 667–668. дои : 10.1145/362759.362813 . S2CID 7540747 .
^ Таубенфельд, Гади (2006). Алгоритмы синхронизации и параллельное программирование . Пирсон Образование. п. 301.

Моррис Дж. М. (1979). Решение проблемы взаимного исключения без голодания. Письмо о информационном процессе 8:76–80
Честное решение проблемы чтения-записи только с помощью семафоров. Х. Бальхаузен, arXiv 2003 г .: cs/0303005.
Более быстрое справедливое решение проблемы чтения-писателя. В. Попов, О. Мазонка 2013 arXiv : 1309.4507

Внешние ссылки

Алгоритмическое описание третьей проблемы читателей-писателей.

[1] Таненбаум, Эндрю С. (2006), Операционные системы – проектирование и реализация, 3-е издание [Глава: 2.3.2 Проблема читателей и писателей] , Pearson Education, Inc.

[courtois-2] Jump up to: ^а ^б Куртуа, П.Дж.; Хейманс, Ф.; Парнас, Д.Л. (1971). «Параллельное управление с «Читателями» и «Писателями» » (PDF) . Коммуникации АКМ . 14 (10): 667–668. дои : 10.1145/362759.362813 . S2CID 7540747 .

[3] Таубенфельд, Гади (2006). Алгоритмы синхронизации и параллельное программирование . Пирсон Образование. п. 301.

[ 1 ]

[ 2 ]

[ 3 ]

v т и Параллельные вычисления
General	Concurrency Concurrency control Concurrent data structures Concurrent hash tables Concurrent users Indeterminacy Linearizability
Process calculi	CSP CCS ACP LOTOS π-calculus Ambient calculus API-Calculus PEPA Join-calculus
Classic problems	ABA problem Cigarette smokers problem Deadlock Dining philosophers problem Producer–consumer problem Race condition Readers–writers problem Sleeping barber problem
Category: Concurrent computing