Способы организации взаимного исключения

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

Семафоры Дейкстры — это формальная модель организации доступа, предложенная голландским ученым Дейкстрой, которая основывается на следующей концепции. Имеется специальный тип данных — семафор. Переменная типа семафор может иметь целочисленные значения. Над этими переменными определены следующие операции: down(S) (или P(S)) и up(S) (или V(S)). Оригинальные обозначения P и V, данные Дейкстрой и получившие широкое распространение в литературе, являются сокращениями голландских слов proberen — проверить и verhogen — увеличить.

Операция down(S) проверяет значение семафора S, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем связанная с заблокированным процессом операция down считается незавершенной.

Операция up(S) увеличивает значение семафора на 1. При этом, если в системе присутствуют процессы, блокированные ранее при выполнении down на этом семафоре, один из них разблокировывается и завершает выполнение операции down, т.е. вновь уменьшает значение семафора. Выбор процесса никак не оговаривается.

При этом операции up и down являются атомарными (неделимыми), т.е. их выполнение не может быть прервано прерыванием.

Для иллюстрации рассмотренного механизма приведем следующий пример. Рассмотрим некий универсам. Вход в торговый зал магазина возможен лишь для посетителей, имеющих тележку. В магазине имеется N тележек. Итак, в начальный момент (когда магазин открывается) имеется N свободных тележек. Каждый очередной посетитель берет тележку и проходит в зал. Так продолжается, пока не появится N+1 посетитель, которому тележки уже не хватает. Он войти не может и ждет свободной тележки перед входом в торговый зал. Если приходят еще покупатели, то они также ожидают свободной тележки. Поскольку рассматриваемый формализм, как упоминалось выше, ничего не говорит о выборе очередного заблокированного процесса, то будем считать, что прибывающие в магазин покупатели не становятся в очередь, а стоят в неком «беспорядке» (толпой). Как только один из покупателей с тележкой покидает торговый зал, происходит операция up: появляется одна свободная тележка. Эту тележку берет один из ожидающих посетителей и проходит в торговый зал. Это означает, что один из заблокированных клиентов разблокировался и продолжил работу, остальные же продолжают ждать в заблокированном состоянии.

Если тележка была бы одна, то это было бы иллюстрацией организации доступа в режиме взаимного исключения, т.е. в любой момент времени в торговом зале может оказаться лишь один покупатель. Это пример т.н. двоичного семафора — семафора, максимальное значение которого равно 1. Этот тип семафоров обеспечивает взаимное исключение.

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