Войти
В информатике проблемы читателей-писателей являются примерами общей вычислительной проблемы в параллелизме. Существует по крайней мере три варианта проблем, которые связаны с ситуациями, в которых множество параллельных потоков выполнения пытаются одновременно получить доступ к одному и тому же общему ресурсу.
Некоторые потоки могут читать, а некоторые писать, с ограничением, что ни один поток не может обращаться к общему ресурсу для чтения или записи, пока другой поток выполняет запись в него. (В частности, мы хотим предотвратить одновременное изменение общего ресурса более чем одним потоком и позволить двум или более читателям получать доступ к общему ресурсу одновременно). блокировка чтения-записи - это структура данных, которая решает одну или несколько проблем чтения-записи.
Основная проблема читателя-писателя была впервые сформулирована и решена Куртуа и др.
Предположим, у нас есть общая область памяти (критическая секция) с основными ограничениями, описанными выше. Можно защитить совместно используемые данные с помощью взаимного исключения мьютекс, и в этом случае никакие два потока не могут получить доступ к данным одновременно. Однако это решение является неоптимальным, поскольку возможно, что устройство считывания R 1 может иметь блокировку, а затем другой считыватель R 2 запрашивает доступ. Для R 2 было бы глупо ждать, пока R 1 не будет завершено, прежде чем начинать свою собственную операцию чтения; вместо этого R 2 должно быть разрешено читать ресурс вместе с R 1, потому что чтения не изменяют данные, поэтому одновременные чтения безопасны. Это мотивирует проблему первых читателей-писателей, в которой добавлено ограничение, что ни один читатель не должен ждать, если общий ресурс открыт для чтения. Это также называется предпочтение читателей, с его решением:
1 семафорный ресурс = 1; 2 семафор rmutex = 1; 3 readcount = 0; 4 5 / * 6 resource.P () эквивалентно wait (resource) 7 resource.V () эквивалентно signal (resource) 8 rmutex.P () эквивалентно wait (rmutex) 9 rmutex.V () равно эквивалент signal (rmutex) 10 * / 11 12 writer () {13 resource.P (); // Заблокировать общий файл для записи 14 15 16 // Запись завершена 17 18 19 resource.V (); // Освободить общий файл для использования другими читателями. Писатели допускаются, если нет читателей, запрашивающих это. 20} 21 22 reader () {23 rmutex.P (); // Убедитесь, что ни один другой читатель не может выполнить раздел , пока вы в нем 24 25 readcount ++; // Указываем, что вы читатель, пытающийся войти в Критический раздел 26 if (readcount == 1) // Проверяет, являетесь ли вы первым читателем, пытающимся войти в CS 27 resource.P (); // Если вы первый читатель, заблокируйте ресурс от писателей. Ресурсы остаются зарезервированными для последующих читателей 28 29 rmutex.V (); // Выпуск 30 31 // Считываем 32 33 rmutex.P (); // Убедитесь, что ни один другой читатель не может выполнить раздел , пока вы в нем 34 35 readcount--; // Указываем, что вам больше не нужен общий ресурс. На один читатель меньше 36 if (readcount == 0) // Проверяет, являетесь ли вы последним (единственным) читателем, который читает общий файл 37 resource.V (); // Если вы последний читатель, то можете разблокировать ресурс. Это делает его доступным для писателей. 38 39 rmutex.V (); // Выпуск 40} В этом решении проблемы чтения / записи первый считыватель должен заблокировать ресурс (общий файл), если он доступен. После того, как файл заблокирован от авторов, он может быть использован многими последующими читателями без необходимости повторной блокировки его.
Перед входом в критическую секцию каждый новый читатель должен пройти через секцию ввода. Однако в разделе ввода одновременно может быть только один читатель. Это сделано для того, чтобы избежать состояний гонки для считывателей (в этом контексте состояние гонки - это состояние, при котором два или более потока одновременно просыпаются и пытаются войти в критическую секцию; без дополнительных ограничений поведение не является детерминированным (например, два считывателя одновременно увеличивают счетчик чтения, и оба пытаются заблокировать ресурс, в результате чего блокируется один считыватель). Для этого каждый читатель, вводящий
Как только первый считыватель окажется в разделе ввода, он заблокирует ресурс. Это предотвратит доступ к нему писателей. Последующие читатели могут просто использовать заблокированный (от авторов) ресурс. Читатель, закончивший последним (обозначенный переменной readcount), должен разблокировать ресурс, тем самым сделав его доступным для писателей.
В этом решении каждый писатель должен запрашивать ресурс индивидуально. Это означает, что поток читателей может впоследствии заблокировать всех потенциальных писателей и морить их голодом. Это так, потому что после того, как первый считыватель заблокирует ресурс, ни один писатель не может заблокировать его, прежде чем он будет освобожден. И он будет выпущен только самым последним читателем. Следовательно, это решение не удовлетворяет справедливости.
Первое решение является неоптимальным, потому что возможно, что читатель R 1 может иметь блокировку, а писатель W ждет lock, а затем считыватель R 2 запрашивает доступ. Было бы несправедливо, если бы R 2 немедленно прыгнул вперед, опередив W; если бы это происходило достаточно часто, W умрет с голоду. Вместо этого следует как можно скорее запустить W. Это является мотивацией для второй задачи читателей-писателей, в которой добавлено ограничение, согласно которому ни один писатель, однажды добавленный в очередь, не должен ждать дольше, чем это абсолютно необходимо. Это также называется предпочтение писателей .
Решение для сценария предпочтения писателей:
1 int readcount, writecount; // (начальное значение = 0) 2 семафора rmutex, wmutex, readTry, resource; // (начальное значение = 1) 3 4 // ЧИТАТЕЛЬ 5 reader () {6 7 readTry.P (); // Указывает, что читатель пытается ввести 8 rmutex.P (); // заблокировать раздел записи, чтобы избежать состояния гонки с другими считывателями 9 readcount ++; // сообщаем о себе как о читателе 10 if (readcount == 1) // проверяем, являетесь ли вы первым читателем 11 resource.P (); // если вы первый читатель, заблокируйте ресурс 12 rmutex.V (); // освобождаем раздел ввода для других читателей 13 readTry.V (); // указывает, что вы закончили попытки доступа к ресурсу 14 15 16 // выполняется чтение 17 18 19 rmutex.P (); // резервный выход из раздела - избегает состояния гонки с читателями 20 readcount--; // указываем, что вы оставляете 21 if (readcount == 0) // проверяет, являетесь ли вы последним читателем, покинувшим 22 resource.V (); // если последний, вы должны освободить заблокированный ресурс 23 rmutex.V (); // освобождаем раздел выхода для других читателей 24} 25 26 // WRITER 27 writer () {28 29 wmutex.P (); // резервируем раздел записи для писателей - избегаем состояния гонки 30 writecount ++; // сообщаем о себе как о писателе, вводящем 31 if (writecount == 1) // проверяем, являетесь ли вы первым писателем 32 readTry.P (); // если вы первый, то вы должны заблокировать читателей. Запретить им войти в CS 33 wmutex.V (); // освобождаем раздел 34 записи resource.P (); // резервируем ресурс для себя - предотвращает одновременное редактирование разделяемого ресурса другими писателями 35 36 // выполняется запись 37 resource.V (); // освобождаем файл 38 39 40 wmutex.P (); // резервный выход из раздела 41 writecount--; // указываем, что вы оставляете 42 if (writecount == 0) // проверяет, являетесь ли вы последним писателем 43 readTry.V (); // если вы последний писатель, вы должны разблокировать читателей. Позволяет им попробовать войти в CS для чтения 44 wmutex.V (); // освобождаем раздел выхода 45} В этом решении предпочтение отдается авторам. Это достигается путем принуждения каждого считывателя индивидуально блокировать и освобождать семафор чтения. С другой стороны, писателям не нужно блокировать его индивидуально. Только первый писатель блокирует попытку чтения, а затем все последующие писатели могут просто использовать ресурс по мере того, как он освобождается предыдущим писателем. Самый последний писатель должен освободить семафор чтения, таким образом открывая ворота для читателей, чтобы попытаться прочитать.
Ни один читатель не может войти в раздел ввода, если семафор попыток чтения был установлен писателем ранее. Читатель должен дождаться, пока последний писатель разблокирует ресурс и сделает попытку чтения семафоров. С другой стороны, если конкретный считыватель заблокировал семафор попытки чтения, это будет указывать любому потенциальному параллельному записывающему устройству, что в секции ввода есть считыватель. Таким образом, писатель будет ждать, пока читатель выпустит повторную попытку, а затем писатель немедленно заблокирует его для себя и всех последующих писателей. Однако писатель не сможет получить доступ к ресурсу, пока текущий читатель не освободит ресурс, что происходит только после того, как читатель завершит работу с ресурсом в критической секции.
Семафор ресурса может быть заблокирован как писателем, так и читателем в их секции ввода. Они могут сделать это только после первой блокировки семафора чтения, что может быть сделано только одним из них за раз.
Если нет писателей, желающих получить доступ к ресурсу, как указано читателю статусом семафора чтения, то считыватели не будут блокировать ресурс. Это сделано для того, чтобы писатель мог немедленно взять под контроль ресурс, как только текущий читатель закончит чтение. В противном случае писатель должен будет дождаться завершения очереди считывателей, прежде чем последний сможет разблокировать семафор чтения. Как только появляется писатель, он попытается установить повторную попытку и повесит трубку, ожидая, пока текущий читатель освободит повторную попытку. Затем он получит контроль над ресурсом, как только текущий читатель закончит чтение, и заблокирует всех будущих читателей. Все последующие читатели будут зависать от семафора readtry, ожидая, пока писатели закончат работу с ресурсом и откроют ворота, выпуская readtry.
rmutex и wmutex используются точно так же, как и в первом решении. Их единственная цель - избежать гонок на читателях и писателях, пока они находятся в своих входных или выходных секциях.
Фактически, решения, подразумеваемые обеими формулировками задачи, могут привести к голоду - первая может голодать писателей в очереди, а вторая может голодать читателей. Поэтому иногда предлагается третья задача читателей-писателей, которая добавляет ограничение, что ни один поток не должен зависать от голода; то есть операция получения блокировки общих данных всегда завершается через ограниченный промежуток времени. Справедливое решение как для читателей, так и для писателей может быть следующим:
1 int readcount; // инициализация до 0; количество читателей, в настоящее время обращающихся к ресурсу 2 3 // все семафоры инициализированы как 1 4 семафорный ресурс; // контролирует доступ (чтение / запись) к семафору ресурса 5 rmutex; // для синхронизации изменений в общей переменной readcount 6 семафор serviceQueue; // СПРАВЕДЛИВОСТЬ: сохраняет порядок запросов (сигнализация должна быть FIFO) 7 8 // ЧИТАТЕЛЬ 9 reader () {10 11 serviceQueue.P (); // ждем очереди на обслуживание 12 rmutex.P (); // запрашиваем монопольный доступ к счетчику чтения 13 readcount ++; // обновить количество активных читателей 14 if (readcount == 1) // если я первый читатель 15 resource.P (); // запрашиваем доступ к ресурсам для читателей (писатели заблокированы) 16 serviceQueue.V (); // пусть обслуживается следующий в очереди 17 rmutex.V (); // освобождаем доступ к счетчику чтения 18 19 20 // выполняется чтение 21 22 23 rmutex.P (); // запрашиваем монопольный доступ к счетчику чтения 24 readcount--; // обновляем счетчик активных читателей 25 if (readcount == 0) // если читателей не осталось 26 resource.V (); // освобождаем доступ к ресурсам для всех 27 rmutex.V (); // освобождаем доступ к счетчику чтения 28} 29 30 // WRITER 31 writer () {32 33 serviceQueue.P (); // ждем очереди на обслуживание 34 resource.P (); // запрашиваем монопольный доступ к ресурсу 35 serviceQueue.V (); // пусть обслуживается следующий в строке 36 37 38 // выполняется запись 39 40 41 resource.V (); // освобождаем доступ к ресурсам для следующего чтения / записи 42} Это решение может удовлетворять только условию, что «ни одному потоку не должно быть позволено голодать» тогда и только тогда, когда семафоры сохраняют порядок «первым пришел - первым вышел» при блокировании и освобождении потоков. В противном случае заблокированный модуль записи, например, может оставаться заблокированным на неопределенное время, а цикл других модулей записи будет уменьшать семафор до этого.
Простейшая задача считывающего устройства и записывающего устройства, в которой используются только два семафора и не требуется массив считывающих устройств для чтения данных в буфере.
Обратите внимание, что это решение становится проще, чем в общем случае, потому что оно эквивалентно проблеме Ограниченный буфер, и поэтому только Nсчитывателей разрешено вводить параллельно, N- размер буфера.
do {ожидание (чтение)............ чтение данных............ сигнал (запись)} while (TRUE);do {wait (запись)............. запись данных............. signal (чтение)} while (TRUE) ;В модуле записи значение семафора записи дается для семафора чтения, а в модуле чтения значение семафора записи задается для записи по завершении цикла.
