If q(s) очередь не пуста?
THEN вывести процесс из очереди выдать ресурс
ELSE S:=S+1 освободить ресурс;
Если семафор управляет одним ресурсом, то это двоичный семафор, и S принимает значение {0,1}. Если он управляет группой ресурсов, то в переменной S устанавливается число ресурсов. Для работы семафора необходимо один раз инициировать процесс и обрабатывать критические участки операциями P(S) и V(S).
Рассмотрим использование семафоров на классическом примере взаимодействия двух процессов, выполняющихся в режиме мультипрограммирования, один из процессов пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. Процесс "писатель" должен приостанавливаться, когда все буфера оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, процесс "читатель" приостанавливается, когда все буферы пусты, и активизируется при появлении хотя бы одной записи.
Введем два семафора: e - число пустых буферов и f - число заполненных буферов. Предположим, что запись в буфер и считывание из буфера являются критическими секциями (как в примере с принт-сервером в начале данного раздела). Введем также двоичный семафор b, используемый для обеспечения взаимного исключения. Тогда процессы могут быть описаны следующим образом:
// Глобальные переменные
#define N 256
int e = N, f = 0, b = 1;
void Writer ()
{
while(1)
{
PrepareNextRecord(); /* подготовка новой записи */
P(e); /* Уменьшить число свободных буферов, если они есть */
/* в противном случае ждать, пока они освободятся */
P(b); /* Вход в критическую секцию */
AddToBuffer(); /* Добавить новую запись в буфер */
V(b); /* Выход из критической секции */
V(f); /* Увеличить число занятых буферов */
}
}
void Reader ()
{
while(1)
{
P(f); /* Уменьшить число занятых буферов, если они есть */
/* в противном случае ждать, пока они появятся */
P(b); /* Вход в критическую секцию */
GetFromBuffer(); /* Взять запись из буфера */
V(b); /* Выход из критической секции */
V(e); /* Увеличить число свободных буферов */
ProcessRecord(); /* Обработать запись */
}
}
Общая схема использования семафоров на критических участках для двух процессов приведена на рис.4.3.
Достоинства использования операций на семафоре:
1.Пассивное ожидание (постановка в очередь и автоматическая выдача ресурсов)
2.Возможность управления группой однородных ресурсов.
Рис.4.3. Критические участки с использованием операций на семафоре
Недостатки:
Неправильное либо умышленное использование операций на семафоре приводит к нарушению работоспособности параллельных систем.
Действительно, если в рассмотренном примере переставить местами операции P(e) и P(b) в программе "писатель", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Так, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов; он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писатель".
Монитор - это механизм организации параллелизма высокого уровня, который содержит множество переменных состояний, очередей и множество процедур, необходимых для реализации динамического распределения и доступа к общим ресурсам.
Монитор представляет собой централизованный семафор или совокупность семафоров, спрятанных от пользователей процессов в одном системном процессе, и потому, недоступным пользовательским программам, которые не могут их нарушить. Процессы, которые использует монитор для синхронизации, не имеют прямого доступа к переменным состояния, и могут воспользоваться ресурсами только путем вызова процедур монитора (или макрокоманд).
Монитор при создании автоматически инициирует число ресурсов и включает процедуры, позволяющие блокировать и активизировать процессы. Вход в монитор находится под жестким контролем системы и только через монитор осуществляется взаимоисключение процессов. Если процесс обращается к монитору и требуемый ресурс занят, то процесс переводится в состояние ожидания. Со временем некоторый процесс обращается к монитору для возвращения ресурса и монитор оповещает процесс о том, что может выделить ресурс и покинуть очередь. Режимом ожидания управляет сам монитор, который для гарантии получения ресурса процессом повышает приоритеты процессов критических областей. На рис.4.4 критический участок программируется в мониторе
Рис. 4.4. Схема использования монитора.
Достоинства монитора:
-
Логические возможности не меньше, чем у семафоров.
-
Упрощение написания параллельных программ. Достаточно знать процедуры организации параллельных вычислений.
-
Повышение надежности параллельных систем, так как полностью защищает управление ресурсом.
-
Обеспечение гарантированного получения ресурса.
Первая рассмотренная нами проблема, возникающая для асинхронных параллельных процессов, работающих с общим ресурсом - это проблема синхронизации процессов.
Вторая проблема - это проблема тупика, возникающая при выполнении асинхронных параллельных процессов, работающих с монопольными ресурсами (взаимоблокировка). Тупиком называется ситуация, когда процесс ждет наступления события (выделения ресурса), которое никогда не произойдет или может бесконечно откладываться.
Для возникновения тупика необходимо наличие 4-х условий:
1.Взаимоисключение, когда процессы требуют монопольного предоставления ресурса.
2.Ожидание дополнительного ресурса, когда процессы удерживают ресурсы и требуют дополнительных ресурсов.
3.Неперераспределяемости ресурсов, когда ресурсы нельзя отобрать у процессов до завершения их работы.
4.Кругового ожидания, когда существует кольцо процессов, удерживающих ресурсы друг друга.
Для решения проблемы тупиков должны выполняться определенные задачи:
1.Предотвращение тупиков.
Путем исключения одного из необходимых условий возникновения тупиков, кроме условий взаимоисключения (это объективное условие).
-
условие ожидания дополнительных ресурсов можно нарушить, если потребовать, чтобы процессы запрашивали сразу все ресурсы. (Недостаток - снижение уровня мультипрограммирования и нерациональное использование ресурсов);
-
условие неперераспределяемости можно нарушить, если потребовать, чтобы процесс, который не получил дополнительных ресурсов, сам освобождал удерживаемые;
-
условие кругового ожидания можно предотвратить, если процессы запрашивают ресурсы в заранее определенном порядке, то есть ресурсы имеют уникальные упорядоченные номера, которые распределяются в соответствии с некоторым планом (планирование распределения ресурсов).
Путем обхода тупиков. Это решение основывается на том, что все процессы заранее указывают максимальное число требуемых ресурсов, и ОС контролирует возможность их совместного удовлетворения.
2.Обнаружение тупиков, когда возникающие тупики анализируются и прогнозируются с выдачей соответствующей информации операторам. Возможные тупики анализируются по графам распределения ресурсов. Существуют формальные, программно-реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки.
3.Восстановление после тупиков осуществляется путем вывода из системы одного или N процессов, вовлеченных в тупик и почти всегда с потерей полученных результатов работы. Не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них, при этом освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть некоторые процессы в область свопинга, можно совершить "откат" некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика.
В настоящее время проблема тупика является критическим фактором по следующим причинам:
-
широкое распространение получают мультипроцессорные и параллельные вычисления;
-
в системах выполняется преимущественно динамическое распределение ресурсов;
-
тенденция рассмотрения данных как ресурса приводит к возрастанию числа управляемых ресурсов.