В этом разделе речь пойдет о способах, позволяющих обеспечить работу с критическими ресурсами, т.е. тот способ работы с разделяемым ресурсом, при котором в любой момент времени с ним может работать не более одного процесса, остальные процессы будут заблокированы. В настоящий момент известно множество механизмов, среди которых мы рассмотрим семафоры Дейкстры, мониторы Хоара и аппарат передачи сообщений.
Семафоры Дейкстры — это формальная модель организации доступа, предложенная голландским ученым Дейкстрой, которая основывается на следующей концепции. Имеется специальный тип данных — семафор. Переменная типа семафор может иметь целочисленные значения. Над этими переменными определены следующие операции: 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) примере двоичного семафора рассмотрены два процесса, каждый из которых имеет критическую секцию. За счет использования двоичного семафора обеспечивается безопасная работа в критической секции любого из процессов, т.е. если один из них вошел в критическую секцию, то гарантируется, что второй при попытке также войти в свою критическую секцию будет блокирован до тех пор, пока первый не покинет оную.
Рис. 85. Пример двоичного семафора.
Заметим, что требование атомарности операций down и up накладывает ограничения на реализацию семафоров Дейкстры, и зачастую это сложная задача. Существуют программные реализации, но в них атомарность не всегда присутствует.
Мониторы Хоара — модель синхронизации, в которой, в частности, предпринята попытка обойти требование аппаратной поддержки атомарности упомянутых выше операций. Монитор является высокоуровневой конструкцией (можно говорить, что это конструкция уровня языка программирования), реализация которой поддерживается системой программирования (компилятором). Монитор — это специализированный модуль, включающий в себя некие процедуры и функции, а также данные, с которыми работают эти процедуры и функции. При этом данный модуль обладает следующими свойствами:
— данные монитора доступны только через процедуры и функции этого монитора;
— считается, что процесс занимает (или входит) монитор тогда, когда он начинает использовать одну из процедур или функций монитора;
— в любой момент времени внутри монитора может находиться не более одного процесса, остальные процессы в зависимости от используемой стратегии поведения либо получает отказ, либо блокируется, становясь в очередь.
Иллюстрацией монитора может служить кабина таксофонного аппарата.
Повторим, что монитор — это языковая конструкция с централизованным управлением (в отличие от семафоров, которые не обладают централизацией). Семафоры и мониторы являются средствами организации работы в основном в однопроцессорных системах либо многопроцессорных системах с общей памятью. В многопроцессорных системах с распределенной памятью эти средства не очень подходят. Для них в настоящий момент часто используется механизм передачи сообщений.
Механизм передачи сообщений основан на двух функциональных примитивах: send (отправить сообщение) и receive (принять сообщение). Данные операции можно разделить по трем критериям: синхронизация, адресация и длина сообщения[R15] .
Синхронизация. Операции посылки/приема сообщений могут быть блокирующими и неблокирующими. Рассмотрим различные комбинации.
Блокирующий send: процесс-отправитель будет блокирован до тех пор, пока посланное им сообщение не будет получено.
Блокирующий receive: процесс-получатель будет блокирован до тех пор, пока не будет получено соответствующее сообщение.
Соответственно, неблокирующие операции, как следует из названия, происходят без блокировок.
Итак, комбинируя различные операции send и receive, мы получаем 4 различных модели синхронизации. Отметим одно важное свойство аппарата сообщений, заключающееся в том, что в нем явно совмещены средства передачи информации и синхронизации, таким образом, механизм передачи сообщений можно использовать для достижения двух целей.
Адресация может быть прямой, когда указывается конкретный адрес получателя и/или отправителя (например, когда получатель ожидает сообщения от конкретного отправителя, игнорируя сообщения других отправителей), или косвенной. В случае косвенной адресации не указывается адрес получателя при отправке или отправителя при получении; сообщение «бросается» в некоторый общий пул, в котором могут быть реализованы различные стратегии доступа (FIFO, LIFO и т.д.). Этим пулом может выступать очередь сообщений (FIFO) или почтовый ящик, в котором может быть реализована любая модель доступа.
Итак, повторимся, что данный механизм совмещает два средства: средство передачи данных и синхронизации. Этот аппарат является базовым средством организации взаимодействия процессов в многопроцессорных системах с распределенной памятью.
Иллюстрацией данной модели может выступать модель MPI — интерфейсы передачи сообщений, на основе которых строятся почти все кластерные системы, т.е. системы с распределенной ОП, но точно также MPI может работать в системах с общей памятью.
