В информатике задачи «читатели -писатели» являются примерами распространённой вычислительной проблемы в параллелизме . [1] Существует по крайней мере три варианта задач, которые имеют дело с ситуациями, в которых множество параллельных потоков выполнения пытаются получить доступ к одному и тому же общему ресурсу одновременно.
Некоторые потоки могут читать, а некоторые могут писать, с ограничением, что ни один поток не может получить доступ к общему ресурсу для чтения или записи, пока другой поток находится в процессе записи в него. (В частности, мы хотим предотвратить одновременное изменение общего ресурса более чем одним потоком и разрешить двум или более читателям получать доступ к общему ресурсу одновременно). Блокировка чтения-записи — это структура данных , которая решает одну или несколько проблем чтения-записи.
Основная проблема «читатель-писатель» была впервые сформулирована и решена Куртуа и др. [2] [3]
Предположим, у нас есть общая область памяти (критическая секция) с основными ограничениями, подробно описанными выше. Можно защитить общие данные с помощью взаимного исключения mutex , в этом случае два потока не смогут получить доступ к данным одновременно. Однако это решение не является оптимальным, поскольку возможно, что читатель R 1 может иметь блокировку, а затем другой читатель R 2 запросит доступ. Было бы глупо для R 2 ждать, пока R 1 не будет завершена, прежде чем начать свою собственную операцию чтения; вместо этого R 2 должно быть разрешено читать ресурс вместе с R 1 , поскольку чтение не изменяет данные, поэтому параллельное чтение безопасно. Это мотивация для первой проблемы читателей–писателей , в которой добавлено ограничение, что ни один читатель не должен ждать, если общий ресурс в данный момент открыт для чтения. Это также называется readers-preference , и его решение:
ресурс семафора = 1 ; семафор rmutex = 1 ; количество прочтений = 0 ;/* resource.P() эквивалентно wait(resource) resource.V() эквивалентен сигналу(ресурс) rmutex.P() эквивалентно wait(rmutex) rmutex.V() эквивалентен сигналу(rmutex)*/писатель () { resource . P (); //Блокируем общий файл для записи < КРИТИЧЕСКИЙ Раздел > // Написание завершено < Раздел ВЫХОД > resource . V (); //Освобождаем общий файл для использования другими читателями. Писатели разрешены, если нет читателей, запрашивающих его. }читатель () { rmutex . P (); // Убедитесь, что никакой другой читатель не сможет выполнить раздел <Entry>, пока вы в нем находитесь < КРИТИЧЕСКИЙ Раздел > readcount ++ ; // Укажите, что вы читатель, пытающийся войти в критическую секцию if ( readcount == 1 ) // Проверяет, являетесь ли вы первым читателем, пытающимся войти в CS resource . P (); //Если вы первый читатель, заблокируйте ресурс от писателей. Ресурс остается зарезервированным для последующих читателей < ВЫХОД ИЗ КРИТИЧЕСКОГО РАЗДЕЛА > rmutex.V ( ); // Освобождение // Прочитайте rmutex . P (); // Убедитесь, что никакой другой читатель не сможет выполнить раздел <Exit>, пока вы в нем находитесь < КРИТИЧЕСКИЙ Раздел > readcount -- ; //Указывает, что вам больше не нужен общий ресурс. На одного читателя меньше if ( readcount == 0 ) // Проверяет, являетесь ли вы последним (единственным) читателем, читающим общий файл resource . V (); //Если вы последний читатель, то вы можете разблокировать ресурс. Это делает его доступным для писателей. < ВЫХОД ИЗ КРИТИЧЕСКОГО РАЗДЕЛА > rmutex.V ( ); // Освобождение }В этом решении проблемы читателей/писателей первый читатель должен заблокировать ресурс (общий файл), если таковой доступен. После того, как файл заблокирован от писателей, он может использоваться многими последующими читателями без необходимости их повторной блокировки.
Перед входом в критическую секцию каждый новый читатель должен пройти через секцию входа. Однако в секции входа может быть только один читатель за раз. Это делается для того, чтобы избежать состояния гонки для читателей (в этом контексте состояние гонки — это состояние, в котором два или более потоков просыпаются одновременно и пытаются войти в критическую секцию; без дополнительных ограничений поведение недетерминировано. Например, два читателя одновременно увеличивают счетчик чтения и оба пытаются заблокировать ресурс, в результате чего один читатель блокируется). Чтобы добиться этого, каждый читатель, который входит в <ENTRY Section>, заблокирует <ENTRY Section> для себя, пока не закончит с ним. В этот момент читатели не блокируют ресурс. Они блокируют только секцию входа, поэтому никакой другой читатель не может войти в нее, пока они находятся в ней. Как только читатель завершит выполнение секции входа, он разблокирует ее, сигнализируя мьютексу. Сигнализация эквивалентна: mutex.V() в приведенном выше коде. То же самое справедливо для <EXIT Section>. В зоне выхода не может находиться более одного считывателя одновременно, поэтому каждый считыватель должен зарезервировать и заблокировать зону выхода для себя, прежде чем использовать ее.
Как только первый читатель окажется в разделе ввода, он заблокирует ресурс. Это предотвратит доступ к нему любых писателей. Последующие читатели могут просто использовать заблокированный (от писателей) ресурс. Читатель, который закончит последним (указанный переменной readcount), должен разблокировать ресурс, тем самым сделав его доступным для писателей.
В этом решении каждый писатель должен заявлять на ресурс индивидуально. Это означает, что поток читателей может впоследствии заблокировать всех потенциальных писателей и лишить их возможности доступа. Это так, потому что после того, как первый читатель заблокирует ресурс, ни один писатель не сможет заблокировать его, прежде чем он будет освобожден. И он будет освобожден только последним читателем. Следовательно, это решение не удовлетворяет принципу справедливости.
Первое решение неоптимально, поскольку возможно, что читатель R 1 может иметь блокировку, писатель W будет ждать блокировки, а затем читатель R 2 запросит доступ. Было бы несправедливо, если бы R 2 немедленно включился, опередив W ; если бы это происходило достаточно часто, W бы умер . Вместо этого W должен начать как можно скорее. Это мотивация для второй проблемы читателей–писателей , в которой добавлено ограничение, что ни один писатель, добавленный в очередь, не должен ждать дольше, чем это абсолютно необходимо . Это также называется предпочтением писателей .
Решение сценария предпочтений писателей: [2]
int readcount , writecount ; //(начальное значение = 0) семафор rmutex , wmutex , readTry , resource ; //(начальное значение = 1) //ЧИТАТЕЛЬчитатель () { < Раздел ВХОД > readTry . P (); // Указывает, что читатель пытается войти rmutex . P (); //блокировка раздела записи для избежания состояния гонки с другими читателями readcount ++ ; //сообщить о себе как о читателе если ( readcount == 1 ) // проверяет, являетесь ли вы первым читателем ресурс . P (); //если вы первый читатель, заблокируйте ресурс rmutex . V (); //освобождаем раздел записи для других читателей readTry . V (); //указывает, что вы завершили попытку доступа к ресурсу < КРИТИЧЕСКИЙ Раздел > //чтение выполняется< Раздел ВЫХОД > rmutex . P (); //резервируем секцию выхода - избегаем состояния гонки с читателями readcount -- ; //указывает, что вы уходите если ( readcount == 0 ) // проверяет, являетесь ли вы последним читателем, покидающим страницу ресурс . V (); //если последний, то необходимо освободить заблокированный ресурс rmutex . V (); //освобождаем секцию выхода для других читателей }//ПИСАТЕЛЬписатель () { < Раздел ВХОД > wmutex . P (); //резервируем раздел записи для писателей - избегает состояний гонки writecount ++ ; //сообщить о себе как о писателе, входящем если ( writecount == 1 ) //проверяет, являетесь ли вы первым писателем readTry . P (); //если вы первый, то вы должны заблокировать читателей. Не позволяйте им пытаться войти в CS wmutex . V (); //выпускаем раздел записи resource . P (); //зарезервировать ресурс для себя - не позволяет другим авторам одновременно редактировать общий ресурс < КРИТИЧЕСКИЙ Раздел > //запись выполняется ресурс . V (); //выпуск файла < Раздел ВЫХОД > wmutex . P (); //резервируем секцию выхода writecount -- ; //указывает, что вы уходите если ( writecount == 0 ) //проверяет, являетесь ли вы последним писателем readTry . V (); //если вы последний писатель, вы должны разблокировать читателей. Позволяет им попытаться войти в CS для чтения wmutex . V (); //освобождение выхода из раздела }В этом решении предпочтение отдается писателям. Это достигается путем принудительной блокировки и освобождения каждого читателя семафора readtry по отдельности. С другой стороны, писателям не нужно блокировать его по отдельности. Только первый писатель заблокирует readtry, а затем все последующие писатели могут просто использовать ресурс, поскольку он освобождается предыдущим писателем. Самый последний писатель должен освободить семафор readtry, тем самым открывая ворота для читателей, чтобы попытаться прочитать.
Ни один читатель не может участвовать в разделе входа, если семафор readtry был установлен писателем ранее. Читатель должен ждать, пока последний писатель разблокирует ресурс и семафоры readtry. С другой стороны, если конкретный читатель заблокировал семафор readtry, это укажет любому потенциальному параллельному писателю, что в разделе входа есть читатель. Поэтому писатель будет ждать, пока читатель освободит readtry, а затем немедленно заблокирует его для себя и всех последующих писателей. Однако писатель не сможет получить доступ к ресурсу, пока текущий читатель не освободит ресурс, что произойдет только после того, как читатель закончит работу с ресурсом в критической секции.
Семафор ресурса может быть заблокирован как писателем, так и читателем в их разделе входа. Они могут сделать это только после того, как сначала заблокируют семафор readtry, что может сделать только один из них за раз.
Затем он возьмет под контроль ресурс, как только текущий читатель закончит чтение, и заблокирует всех будущих читателей. Все последующие читатели будут зависать на семафоре readtry, ожидая, пока писатели закончат с ресурсом и откроют ворота, отпустив readtry.
Rmutex и wmutex используются точно так же, как и в первом решении. Их единственная цель — избежать состояния гонки на читателях и писателях, пока они находятся в своих секциях входа или выхода.
Фактически, решения, подразумеваемые обеими формулировками проблемы, могут привести к голоданию — первое может лишить писателей в очереди, а второе — читателей. Поэтому иногда предлагается третья проблема читателей–писателей , которая добавляет ограничение, что ни один поток не должен быть лишен возможности голодать ; то есть операция получения блокировки на общих данных всегда будет завершаться через ограниченное время. Решение, справедливое как для читателей, так и для писателей, может быть следующим:
int readcount ; // инициализация до 0; количество читателей, которые в данный момент обращаются к ресурсу // все семафоры инициализированы значением 1ресурс семафора ; // управляет доступом (чтение/запись) к ресурсу. Двоичный семафор. semaphore rmutex ; // для синхронизации изменений в общей переменной readcount semaphore serviceQueue ; // СПРАВЕДЛИВОСТЬ: сохраняет порядок запросов (сигнализация должна быть FIFO) //ЧИТАТЕЛЬчитатель () { < Раздел ВХОД > serviceQueue . P (); // ожидание в очереди на обслуживание rmutex . P (); // запросить эксклюзивный доступ к readcount readcount ++ ; // обновить количество активных читателей если ( readcount == 1 ) // если я первый читатель resource . P (); // запросить доступ к ресурсам для читателей (писатели заблокированы) serviceQueue . V (); // пусть следующий в очереди будет обслужен rmutex . V (); // освободить доступ к readcount < КРИТИЧЕСКИЙ Раздел > //чтение выполняется < Раздел ВЫХОД > rmutex . P (); // запросить эксклюзивный доступ к readcount readcount -- ; // обновить количество активных читателей if ( readcount == 0 ) // если не осталось читателей resource . V (); // освободить доступ к ресурсам для всех rmutex . V (); // освободить доступ к readcount }//ПИСАТЕЛЬписатель () { < Раздел ВХОД > serviceQueue . P (); // ожидание в очереди на обслуживание ресурс . P (); // запросить эксклюзивный доступ к ресурсу serviceQueue . V (); // пусть следующий в очереди будет обслужен < КРИТИЧЕСКИЙ Раздел > // запись выполняется < Раздел ВЫХОД > resource . V (); // освобождаем доступ к ресурсу для следующего читателя/писателя }Это решение может удовлетворить условию, что "ни один поток не должен голодать", если и только если семафоры сохраняют порядок "первым пришел - первым вышел" при блокировке и освобождении потоков. В противном случае заблокированный писатель, например, может оставаться заблокированным неопределенно долго, а цикл других писателей будет уменьшать семафор до того, как он сможет это сделать.
Простейшая задача чтения-записи, которая использует только два семафора и не требует массива читателей для чтения данных в буфере.
Обратите внимание, что это решение проще, чем общий случай, поскольку оно эквивалентно проблеме ограниченного буфера , и поэтому только N читателям разрешено входить параллельно, где N — размер буфера.
do { wait ( read ) ............ чтение данных ............ сигнал ( write ) } while ( TRUE ); do { wait ( write ) ............. запись данных ............. signal ( read ) } while ( TRUE ); В Writer значение семафора записи передается семафору чтения, а в Reader значение чтения передается семафору записи по завершении цикла.