Реализация семафоров и мониторов с помощью очередей сообщений

Покажем, наконец, как реализовать семафоры с помощью очередей сообщений. Для этого воспользуемся более хитрой конструкцией, введя новый синхронизирующий процесс. Этот процесс имеет счетчик и очередь процессов, ожидающих включения семафора. Для того чтобы выполнить операции P и V, процессы посылают синхронизирующему процессу сообщения, в которых говорится, чего они желают, после чего ожидают получения подтверждения от синхронизирующего процесса.

После прибытия сообщения синхронизирующий процесс проверяет значение счетчика, чтобы выяснить, можно ли совершить требуемую операцию. Операция V всегда может быть совершена, в то время как операция P может потребовать блокирования процесса. Если операция может быть совершена, то она выполняется, и синхронизирующий процесс посылает подтверждающее сообщение. Если процесс должен быть блокирован, то его идентификатор заносится в очередь блокированных процессов и подтверждение не посылается. Позднее, когда кто-либо из других процессов выполнит операцию V, один из блокированных процессов удаляется из очереди ожидания и получает соответствующее подтверждение.

Поскольку мы показали ранее, как из семафоров построить мониторы, мы доказали эквивалентность мониторов, семафоров и сообщений.

Резюме

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

Глава 7. Тупики

Предыдущая глава | Программа курса | Следующая глава

Введение

В предыдущих главах рассмотрены способы синхронизации процессов, которые позволяют процессам успешно кооперироваться. Однако если средствами синхронизации пользоваться неосторожно, то могут возникнуть непредвиденные затруднения. Предположим, что несколько процессов конкурируют за обладание конечным числом ресурсов. Если запрашиваемый процессом ресурс недоступен, процесс переходит в состояние ожидания. В случае если требуемый ресурс удерживается другим ожидающим процессом, то первый процесс не сможет сменить свое состояние. Такая ситуация называется тупиком. Говорят, что в мультипрограммной системе процесс находится в состоянии тупика, дедлока (deadlock) или клинча, если он ожидает события, которое никогда не произойдет. Системная тупиковая ситуация или зависание системы является следствием того, что один или более процессов находятся в состоянии тупика.

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

Рис. 7.1. Пример тупиковой ситуации.

Тупики также могут иметь место в ситуациях, не требующих выделенных ресурсов. Например, в системах управления базами данных процессы могут локализовывать записи, чтобы избежать гонок (см. главу "Синхронизация процессов"). В этом случае может получиться так, что один из процессов заблокировал записи, требуемые другому процессу и наоборот. Т.о. тупики могут иметь место, как на аппаратных, так и на программных ресурсах.

Другой пример возникновение тупика в системах спулинга. Режим спулинга ввод-вывод с буферизацией информации, предназначенной для печати, на диске и организации очереди на печать часто применяется для повышения производительности системы. Программа, осуществляющая вывод на печать должна полностью сформировать свои выходные данные в промежуточном файле, после чего начинается реальная распечатка. В итоге, несколько заданий может оказаться в тупиковой ситуации, если предусмотренная емкость буфера для промежуточных файлов будет заполнена до того, как одно из заданий закончит свою работу. Возможные решения: увеличить размер буфера, или не принимать дополнительные задания, если файл спулинга близок к какому то порогу насыщения, например, заполнен на 75%.

Определение. Множество процессов находится в тупиковой ситуации, если каждый процесс из множества ожидает события, которое только другой процесс данного множества может вызвать. Так как все процессы чего-то ожидают, то ни один из них не сможет инициировать событие, которое разбудило бы другого члена множества и, следовательно, все процессы будут спать вместе. Обычно событие, которого ждет процесс в тупиковой ситуации - освобождение ресурса.

Далее в тексте данной главы будут обсуждаться вопросы, обнаружения, предотвращения, обхода тупиков и восстановления после тупиков. Рассматривается также тесно связанная проблема бесконечного откладывания, которое может происходить из-за дискриминационной политики планировщика ресурсов. Во многих случаях цена борьбы с тупиками, которую приходится платить высока. Тем не менее, для ряда систем, например для систем реального времени, нет иного выхода.

Концепция ресурса

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

Как устройства, так и данные могут являться ресурсами.

Некоторые виды ресурсов допускают разделение между процессами, то есть являются разделяемыми устройствами. Например, память, процессор, диски коллективно используются процессами. Другие - нет, то есть являются выделенными, например, лентопротяжное устройство.Чаще всего тупики связаны с выделенными ресурсами, то есть тупики возникают, когда процессу дается эксклюзивный доступ к устройствам, файлам и другим ресурсам.

Последовательность событий, требуемых для использования ресурса такова:

1. запросить (request) ресурс,

2. использовать (use) ресурс,

3. освободить (release) ресурс.

Если ресурса нет в наличии, когда он требуется, то процесс вынужден ждать. В некоторых ОС процесс автоматически блокируется, когда получает отказ на запрос к ресурсу и просыпается, когда ресурс оказывается в наличии. В других системах отказ сопровождается возвратом ошибки и уже задача вызывающего процесса решить: подождать немного и попытаться осуществить запрос вновь.

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

Природа запроса сильно зависит от ОС. В некоторых системах имеется системный вызов request для прямого запроса на ресурс. В других - единственные ресурсы, о которых ОС знает - специальные файлы, которые только один процесс имеет право открывать за раз. Это делается обычным вызовом open. Если файл уже используется, вызывающий процесс блокируется, пока ресурс не освободится.