Реализация двоичных семафоров на основе функциональных блоков( draft )

Кратко рассмотрим семафорную технику синхронизации и упорядочения процессов, предложенную Дейкстрой []. Семафор–переменная специального вида, которая доступна параллельным процессам для проведения над ней только двух видов операций «закрытия» и «открытия», названных соответственно Р- и V-операциями. Они являются примитивами в отношении семафора, который указывается в качестве параметра операций. Если несколько процессов одновременно запрашивают Р- или V-операции над одним и тем же семафором, то эти операции будут выполняться последовательно в произвольном порядке. Установка начального значения семафора осуществляется с помощью специальной операции инициализации семафора. Существенно, что операции P и V считаются «неделимыми». Неделимость заключается в том, что с самого начала выполнения этой операции до ее завершения доступ к семафору запрещен для всех других операций. Реализация Р- и V-примитивов как критических областей (для достижения прежде всего свойства их неделимости) требует использования средств взаимного исключения низкого (аппаратного) уровня.

Обычно семафоры используются для решения проблемы взаимного исключения, при этом P-операция предшествует критическому интервалу процесса, а V-операция его завершает.

Существует несколько типов семафоров: двоичные, считающие, счетные, множественные и др. Двоичный семафор может принимать два значения: 0 (семафор закрыт) и 1 (семафор открыт). Рассмотрим алгоритмы Р- и V- операций для двоичных семафоров.

Р(S) - операция закрытия семафора

––––––––––––––––––––––––

ЕСЛИ S = 1, ТО S:=0;

ИНАЧЕ <Остановить процесс и поместить в очередь ожидания к семафору S>;

V (S) – операция открытия семафора

––––––––––––––––––––––––

ЕСЛИ <Один или более процессов “ожидают на S ” >,

ТО <Разрешить одному из ожидающих процессов продолжить работу>,

ИНАЧЕ S=1;

Очередь ожидания обслуживается в соответствии с дисциплиной FIFO.

Реализация Р- и V-примитивов как критических областей (для достижения прежде всего свойства их неделимости) требует использования в вычислительных системах с традиционной архитектурой средств взаимного исключения низкого (аппаратного) уровня.

Предлагается использовать аналог семафорной техники для организации взаимодействий ФБ, в частности, для организации работы с разделяемыми ресурсами. Организация семафоров на основе event-driven модели отличается от организации семафоров для вычислительных систем и комплексов с архитектурой фон Неймана. Реализация Р- и V-примитивов как критических областей (для достижения прежде всего свойства их неделимости) требует использования в вычислительных системах с традиционной архитектурой средств взаимного исключения низкого (аппаратного) уровня. На многих ЭВМ семафорные операции реализуются на базе команды «Проверить и установить» (test and set).

Интерпретация понятий семафорной техники при работе с ФБ будет следующей. Процессу языков программирования будет соответствовать некоторый функциональный блок, инициирующий запрос на выполнение P- и V-операций, называемый в дальнейшем ФБ-процессом, а также запрос, представляющий этот ФБ. Кроме того, ФБ-процесс должен пользоваться результатами своего запроса. Использование семафора в ФБ-процессе можно представить в виде следующей части ЕСС (рис.)

На представленном рисунке Pi – запрос на выполнение операции закрытия семафора, Vi – запрос на выполнение операции открытия семафора, Ei – разрешение продолжать выполнение.

Семафору в языках программирования будет соответствовать некоторый функциональный блок, реализующий саму переменную, хранящую значение семафора, а также определенные действия над ней. Данный блок будем называть в дальнейшем ФБ-семафором (рис.)

Диаграмма переходов состояний (ECC) ФБ-семафора представлена на рис.

На рис. представлена модель ФБ-семафора в виде сети Петри [].

Особенности организации двоичного семафора на основе ФБ представлены ниже:

1) Функциональный блок, реализующий функции семафора (ФБ-семафор), имеет несколько входных линий для запросов на закрытие семафора (P-запросов), соответствующие им выходные линии, подтверждающие возможность ФБ-процесса продолжить свое выполнение, и одну входную линию для запроса на открытие семафора (V-запроса). Число линий первого и второго типов равны между собой и соответствуют максимальному числу ФБ-процессов, использующих ФБ-семафор. Считается, что в соответствии с логикой работы системы, использующей двоичный семафор, только один из процессов может выполнить V-операцию. Так что возможная потеря одного из нескольких одновременно пришедших V-запросов не угрожает работе системы.

2) Помещение процесса в очередь ожидания к семафору интерпретируется как (автоматическая) фиксация заявки в соответствующей переменной входного события (event inputvariable)

3) Значение семафора (0 или 1) интерпретируется как нахождение ФБ-семафора в определенном состоянии. Нахождение ЕСС в начальном состоянии S0 определяет значение семафора 1 (открыт), а в остальных состояниях – значение 0 (закрыт).

4) Изменение значения семафора с 1 на 0 интерпретируется как переход из состояния S0 в любое другое состояние. Изменение значения перехода с 0 на 1 интерпретируется как переход в состояние S0.

5) Неделимость выполнения P-операции обеспечивается тем, что в один момент времени возможен только один из возможных переходов из начального состояния в одно из состояний из множества {S1,S2,…,SN}. Таким образом, одновременное выполнение нескольких P-операций взаимоисключается. Неделимость V-операции обеспечивается тем, что в один момент времени только из одного состояния из множества {S1,S2,…,SN} может произойти переход в начальное состояние S0. Этот переход определяет V-операцию целиком.

6) Операция P реализуется как операция типа «запрос-ответ», то есть для выполнения операции закрытия семафора необходимо послать соответствующий запрос. Если операция прошла успешно (семафор в результате выполнения запроса закрылся), через соответствующий выход ФБ-процессу посылается разрешение продолжить выполнение. Это разрешение он может использовать для вхождения в критическую область. Если семафор уже был закрыт, никакого ответа не посылается. Таким образом ФБ-процесс входит в состояние ожидания (включается в состав “заснувших” процессов). V-операция реализуется посылкой только запроса к ФБ-семафору.

7) Дисциплина выбора “разбуженного” процесса из множества “спящих” определяется конкретной реализацией ФБ в инструментальной системе.

Как использовать семафоры для синхронизации по событиям? Как используются семафоры для решения проблемы критических секций? Как реализуется решение задачи обедающие философы с использованием семафоров? Что такое критические области? (ПК-12)