36252

Аппаратная реализация взаимоисключения: команда test and set. Семафоры. Обеспечение взаимоисключения при помощи семафоров

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-09-23

50 KB

12 чел.

4

PAGE  4

38.Аппаратная реализация взаимоисключения: команда test&set. Семафоры.
    Обеспечение взаимоисключения при помощи семафоров.

Аппаратная реализация взаимоисключения

Алгоритм Деккера — это программное решение проблемы взаимоисключения. В данном разделе мы приводим аппаратное решение данной проблемы.

Главным фактором, обеспечивающим успех в этом случае, является наличие одной аппаратной команды, которая осуществляет чтение переменной, запись ее значения в область сохранения и установку нужного конкретного значения этой переменной. Подобная команда, обычно называемая testandset (проверить-и-установить), после запуска выполняет все эти действия до конца без прерывания. Неделимая команда

testandset (а, b)

читает значение логической переменной b, копирует его в а, а затем устанавливает для b значение «истина» — и все это в рамках одной непрерываемой операции. Пример использования команды проверки и установки для реализации взаимоисключения приведен на рис. 1.

program npимeptestandset var активный: логический;

procedure процессодин;

   var первомувходитьнельзя: логический;

begin

while истина do

begin

первомувходитьнельзя : = истина;

while первомувходитьнельзя do

testandset (первомувходитьнельзя, активный);

                     критическийучастокодин;

активный : = ложь;

прочиеоператорыодин

end

end;

procedure процессдва;

   var второмувходитьнельзя: логический;

begin

while истина do

begin

второмувходитьнельзя : = истина;

while второмувходитьнельзя do

testandset (второмувходитьнельзя, активный);

критическийучастокдва;

активный : = ложь;

прочиеоператорыдва

            end

end;

begin

активный : = ложь;

parbegin

процессодин;

          процессдва parend

end;

Рис. 1. Реализация взаимоисключения при помощи команды testandsef

           (ПРОВЕРИТЬ И УСТАНОВИТЬ).

Переменная «активный» логического типа имеет значение «истина», когда любой из процессов находится в своем критическом участке, и значение «ложь» в противном случае. «Процессодин» принимает решение о входе в критический участок в зависимости от значения своей локальной логической переменной «первомувходитьнельзя». Он устанавливает для переменной «первомувходитьнельзя» значение «истина», а затем многократно выполняет команду проверки и установки для глобальной логической переменной «активный». Если «процессдва» находится вне критического участка, переменная «активный» будет иметь значение «ложь». Команда проверки и установки запишет это значение в «первомувходитьнельзя» и установит] значение «истина» для переменной «активный». При проверке в цикле while будет получен результат «ложь», и «процессодин» войдет в свой критический участок. Поскольку для переменной «активный» установлено значение «истина», «процессдва» в свой критический участок войти не может.

Предположим теперь, что «процессдва» уже находится в своем критическом участке, когда «процессодин» хочет войти в критический участок. «Процессодин» устанавливает значение «истина» для переменной «первомувходитьнельзя», а затем многократно проверяет значение переменной «активный» по команде testandset. Поскольку «процессдва» находится в своем критическом участке, это значение остается истинным. Каждая команда проверки и установки обнаруживает, что «активный» имеет значение «истина», и устанавливает это значение для переменных «первомувходитьнельзя» и «активный». Таким образом, «процессодин» продолжает находиться в цикле активного ожидания, пока «процессдва» в конце концов не выйдет из своего критического участка и не установит значение «ложь» для переменной «активный». В этот момент команда проверки и установки, обнаружив это значение переменной «активный» (и установив для нее истинное значение, чтобы «процессдва» не мог больше войти в свой критический участок), установит значение «ложь» для переменной «первомувходитьнельзя», что позволит, чтобы «процессодин» вошел в свой критический участок.

Этот способ реализации взаимоисключения не исключает бесконечного откладывания, однако здесь вероятность такой ситуации весьма мала, особенно если в системе имеется несколько процессоров. Когда процесс, выходя из своего критического участка, устанавливает значение «ложь» переменной «активный», команда проверки и установки testandset другого процесса, вероятнее всего, сможет «перехватить» переменную «активный» (установив для нее значение «истина») до того, как первый процесс успеет пройти цикл, чтобы снова установить значение «истина» для этой переменной.

Семафоры

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

Операция Р над семафором записывается как P(S) и выполняется следующим образом:

если S > О

то S: =S— 1

иначе (ожидать на S)

Операция V над семафором S записывается как V(S) и выполняется следующим образом: если (один или более процессов ожидают на S)

       то (разрешить одному из этих процессов продолжить работу)

        иначе S : = S + 1

  Будем предполагать, что очередь процессов, ожидающих на обслуживается в соответствии с дисциплиной «первый пришедший обслуживается первым» (FIFO).

Подобно операции проверки и установки testandset, операции Р и V являются неделимыми. Участки взаимоисключения по семафору S в процессах обрамляются операциями P(S) и V(S). Если одновременно несколько процессов попытаются выполнить операцию P(S), это будет разрешено только одному из них, а остальным придется ждать.

Семафоры и операции над ними могут быть реализованы как программно, так и аппаратно. Как правило, они реализуются в ядре операционной системы, где осуществляется управление сменой состояния процессов.

На рис. 2 приводится пример того, каким образом можно обеспечить взаимоисключение при помощи семафоров. Здесь примитив Р (активный) — эквивалент для «входвзаимоисключения», а примитив V (активный) — для «выходвзаимоисключения».

           

program примерсемафораодин;

    var активный: семафор;

procedure процессодин;

begin

while истина do begin

предшествующиеоператорыодин;

           Р(активный);

           критическийучастокодин;

           V(активный);

прочиеоператорыодин;

           end

end;

procedure процессдва;

begin

while истина do begin

предшествующиеоператорыдва Р(активный);

           критическийучастокдва;

           V(активный);

           прочиеоператорыдва

           еnd

end;

begin

инициализациясемафора(активный,1);

parbegin

процессодин;

           процессдва parend

end;

Рис. 2. Обеспечение взаимоисключения при помощи семафора и примитивов Р и V.

Синхронизация процессов при помощи семафоров

Когда процесс выдает запрос ввода-вывода, он блокирует себя в ожидании завершения соответствующей операции ввода-вывода. Заблокированный процесс должен быть активизирован каким-либо другим процессом. Подобное взаимодействие может служить примером функций, относящихся к протоколу блокирования/возобновления.

Рассмотрим более общий случай, когда одному процессу необходимо, например, чтобы он получал уведомление о наступлении некоторого события. Предположим, что какой-либо другой процесс может обнаружить, что данное событие произошло. Программа рис. 3 показывает, каким образом при помощи семафора можно реализовать простой механизм синхронизации (блокирования/возобновления) для двух процессов.

program блокированиевозобновления;

     var событие: семафор;

procedure процессодин;

begin

предшествующиеоператорыодин;

Р(событие);

прочиеоператорыодин

end;

procedure процессдва;

begin

предшествующиеоператорыдва;

V(событие);

прочиеоператорыдва

end;

begin

инициализациясемафора(событие,0);

parbegin

процессодин;

процессдва parend

end;

Рис. 3. Синхронизация блокирования/возобновление процессов при помощи семафоров.

Здесь «процессодин» выполняет некоторые «предшествующие операторыодин», а затем операцию Р (событие). Ранее при инициализации семафор был установлен в нуль, так что «процессодин» будет ждать. Со временем «процессдва» выполнит операцию V (событие), сигнализируя о том, что данное событие произошло. Тем самым «процессодин» получает возможность продолжить свое выполнение.

Отметим, что подобный механизм будет выполнять свои функции даже в том случае, если «процессдва» обнаружит наступление события и просигнализирует об этом еще до того, как «процессодин» выполнит операцию Р (событие); при этом семафор переключится из 0 в 1, так что операция Р (событие) просто произведет обратное Переключение, из 1 в 0, и «процессодин» продолжит свое выполнение без ожидания.


 

А также другие работы, которые могут Вас заинтересовать

21456. Системы линейных дифференциальных уравнений с постоянными коэффициентами 282 KB
  Системы линейных дифференциальных уравнений с постоянными коэффициентами. Итак общее решение однородной системы 1 имеет вид 6 причем векторы 7 частные решения системы 1 которые могут быть получены следующим образом. Итак решения линейно...
21457. Матричная экспонента 394 KB
  а матрица j й столбец которой есть решение системы 1а с начальными условиями т. матрица имеет вид и удовлетворяет уравнению Тогда вектор t решение системы 1а с начальным условием может быть записан в виде т. Запишем теперь jе решение уравнения 1а удовлетворяющее начальному условию где диагональная матрица вектор столбец коэффициентов и положим где матрица коэффициентов . Теперь окончательно имеем...
21458. Спектральные приборы 519 KB
  различаются методами спектрометрии приёмниками излучения исследуемым рабочим диапазоном длин волн и др. Форма отверстия в равномерно освещенном экране 1 соответствует функции f описывающей исследуемый спектр распределение энергии излучения по длинам волн . группа 2 информация об исследуемом спектре получается путём одновременной регистрации без сканирования по  несколлькими приёмниками потоков излучения разных длин волн    .
21459. Управление света светом 870.5 KB
  ставит очень амбициозную задачу создание устройств выполняющих функции управления характеристиками оптического излучения с помощью другого оптического излучения. Предлагается воспользоваться свойствами поляризованного электромагнитного оптического излучения а именно использовать эффект оптического гашения который описан например в [3]. 1 Если четвертьволновую пластинку P1 установить так чтобы её быстрая ось была ориентирована под углом к оси OX то для излучения прошедшего через пластинку P1 получим = 1 = . 2 Согласно [4]...
21460. Применение лазерного излучения для управления движением атомами и ионами 789.5 KB
  Этот эффект называется охлаждением атомов давлением лазерного излучения. Методы позволяющие с помощью лазерного излучения охлаждать атомы основаны на эффекте вязкой жидкости оптическая патока в которой атомы медленно перемещаются. При охлаждении вещества его энергия и энтропия понижаются поэтому процесс охлаждения возможен если энергия и энтропия излучения после взаимодействия с веществом повышаются.
21461. Лазерный пинцет 957 KB
  Сила с которой свет действует на окружающие объекты невелика но ее оказывается достаточно чтобы ловить и контролируемо перемещать частицы размером от 10 нм до 10 мкм. В дальнейшем Эшкин и его коллеги продемонстрировали возможности оптической ловушки на основе инфракрасного лазера захватывать удерживать и перемещать в пространстве различные биологические объекты такие как вирусные частицы одиночные бактериальные и дрожжевые клетки и органеллы в живых клетках водорослей. Как будет вести себя частица в поле после Пишейпера В случаях...
21462. Прецизионные волоконно-оптические датчики 333 KB
  100 Мрад Последовательного и параллельного типа Распределение температуры и деформации Обратное рассеяние Релея Интенсивность обратного рассеяния Релея Многомодовое Разрешающая способность 1 м Условия реализации волоконных датчиков связаны с наличием оптической комплектации: оптическое волокно в различных спектральных диапазонах. Соединительные и разделительные фильтры Многослойники дифракционные решетки; модуляторы интенсивности на основе электрооптического эффекта ниобат лития обладающий электрооптическими свойствами которые...
21463. Импульсный оптический рефлектометр 479 KB
  Введение Импульсные оптические рефлектометры OTDR Opticl Time Domin Reflectometer различных типов широко используются практически на всех этапах создания волоконнооптических систем связи: от производства волокна и оптического кабеля до строительства волоконнооптических линий связи ВОЛС и их эксплуатации. Измерять средние потери оптического волокна на катушках равномерность распределения потерь в волокне и выявлять наличие локальных дефектов при производстве волокна. Обнаруживать постепенное или внезапное ухудшение качества волокна...
21464. Анализ современного состояния техники ранней диагностики ВОЛП 706 KB
  Очевидно что длины волн используемые для передачи данных и для рефлектометрического контроля волокна в этом случае должны быть разными. В этой точке устанавливается оптический коммутатор OTU который по очереди включает волокна всех направлений в оптический путь сигналов рефлектометра RTU. Другой подход предполагает одновременное распространение сигнала рефлектометра по всем ответвляющимся волокнам. Согласно данным фирмы Fujikur по степени опасности для волокна можно выделить три диапазона значений его относительного удлинения.