Семафоры-счетчики

Мониторы.

Межпроцессное взаимодействие с применением семафора реализуется довольно просто, но требует особого контроля за исследованием процедур down и up. Чтобы упростить описание программ в 1974 году Хоар и Хансен предложили примитив синхронизации более высокого уровня получившего название монитора.

Монитор – это набор процедур, переменных и других структур данных, объединенных в один модуль. Процессы могут вызывать процедуры монитора, но у них нет доступа к его внутренним структурам данных. При обращении к монитору активным может быть только один процесс. Мониторы являются структурным компонентом языка программирования, поэтому компилятор обрабатывает вызовы процедур монитора иначе, чем вызовы остальных процедур. При вызове монитора сначала проверяется нет ли в мониторе активного процесса. Для реализации мониторов обычно используется мьютекс или бинарный семафор. Так же монитор содержит переменные состояния, две процедуры: Wait и Signal. Когда монитор обнаруживает, что он не в состоянии продолжать работу он выполняет операцию Wait на одной из переменных состояния. Это приводит к блокировке вызывающего процессора и позволяет другому процессу войти в монитор, который в свою очередь может активизировать ожидающий процесс, выполнив операцию Signal на блокирующей его переменной состояния. Для обхода ситуации, когда в мониторе оказывается два активных процесса одновременно, используются правила обработки вызова Signal.

Первый вариант правила: запуск запущенного процесса и остановка вызывавшего.

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

Третий вариант правила: позволить процессу, вызывавшему Signal, продолжать работу, запустить ждущий процесс только после того как первый покинет монитор.

В отличие от семафоров переменные состояния мониторов не являются счетчиками и таким образом не аккумулируют (накапливают) Signal. Это означает, что выполнение Signal’а на переменной, которой не связанно заблокированных процессов приведет к потере. Таким образом операция Wait должна выполняться прежде чем Signal.

Исторически, семафоры-счетчики были одним из первых примитивов синхронизации. В старых учебниках они известны под названием "семафоры Дийкстры". Семафор представляет собой целочисленную переменную, над которой определены две операции, post и wait.

Операция wait пытается вычесть единицу из флаговой переменной семафора. Если значение флаговой переменной больше 0, то происходит обычное вычитание и нить, выполнившая операцию wait, продолжает исполнение. Если значение флаговой переменной было равно 0, то wait блокируется до тех пор, пока кто-то (скорее всего, другая нить) не увеличит значение этой переменной.

Операция post добавляет единицу к флаговой переменной семафора. Если при этом на семафоре ждала нить, операция post пробуждает эту нить.

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

Семафоры также можно использовать для обхода проблемы инверсии приоритета. Если высокоприоритетная и низкоприоритетная нить должны взаимодействовать, иногда удается реализовать соглашение, что только низкоприоритетная нить может выполнять над семафором операцию wait, а высокоприоритетная нить может делать только post. Такое взаимодействие обычно похоже на схему производитель-потребитель с тем отличием, что производитель может терять некоторые порции данных, если потребитель за ним не успевает. При этом условии в примере 7.3 можно избавиться от семафора p.

Лекция 23

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-06