Стр. 2 - Ил.С. Свирин, П.А. Силин, В.В. Сюзев, Е.А. Зарецкая - Математическая модель взаимных блокировок. Корректное использование исключающих семафоров

Рис. 1. Пример системы субъектов
ния взаимодействия со средствами синхронизации. На рис. 1 приведен
пример графического изображения субъектов доступа.
Для каждого субъекта определены два выделенных состояния —
состояние покоя, соответствующее началу произвольного пути выпол-
нения субъекта, и завершающее состояние, соответствующее заверше-
нию произвольного пути выполнения субъекта (см. рис. 1, окружность
с символом “0” внутри). В рамках модели состояние покоя и завер-
шенное состояние отождествлены, т.е. субъекты доступа являются ци-
клическими.
Рассмотрим всевозможные конечные пути выполнения субъекта,
каждый из которых представлен как упорядоченная последователь-
ность различных состояний субъектов (каждое изменение состояния
субъекта обусловливается актом взаимодействия со средством син-
хронизации). Субъекты, изображенные на рис. 1, имеют единственный
путь выполнения. Такие субъекты будем называть линейными.
Отметим, что анализируемая система представляет собой произ-
вольную конечную совокупность субъектов доступа.
Средства синхронизации. В данной модели выделяются четыре
примитива синхронизации: рекурсивный исключающий семафор, не-
рекурсивный (обычный) исключающий семафор, сигнальная перемен-
ная с памятью и сигнальная переменная без памяти. В данной статье
будут рассмотрены взаимные блокировки в системах линейных субъ-
ектов, взаимодействующих только с исключающими семафорами.
Время выполнения субъектом оператора взаимодействия полагает-
ся равным нулю, поскольку не является существенным параметром с
точки зрения модели.
Взаимные блокировки. В системе, изображенной на рис. 1, участ-
вуют два субъекта: “Субъект 1” и “Субъект 2”. Пунктирной стрелкой
показана последовательность выполнения операторов субъектами до-
ступа. После выполнения шагов, показанных на рис. 1, оба субъекта
находятся в состоянии ожидания — “Субъект 1” не может освободить
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012 113