Мониторы Хоара

Монитор — высокоуровневое языковое средство синхронизации процессов.

Б. Хансен — 1973

С. Хоар — 1974

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

Нотации монитора:

<name>: MONITOR;

begin // В описании локальных данных монитора

var... // h набор процедур монитора Y

procedure <name1> (…);

begin... end;

….

procedure <namen> (…);

begin... end;

В инициализации локальных данных} end

В рамках монитора допускается использование специальных переменных называемых условными. Такие переменные описываются как конечные.

Условная переменная М:condition реализует некоторую очередь процессы в которой выполняются при М.WAIT. Если какой-то процесс выполнил примитив M.SIGNAL, то первый процесс из очереди переходит в состояние готовности.

Подразумевается, что все процессы монитора работают в режиме взаимного исключения. Если 1 процесс обратился к какой либо процедуре монитора, никакой другой процесс не может обратится к другой процедуре монитора, до тех пор, пока текущий процесс не закончит использование монитора, либо не останавливается на WAIT.

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

Соответственно после выхода из монитора процесс, который был в очереди ожидания, передает управление «разбудившему» процессу (кот. Выполнил SIGNAL)

Для реализации монитора:

В составе локальных переменных используется ФЛАГ (двоич. Перем.), которая означает есть или нет шифрование (0-пусто, 1-инф. Занес.)

DATA:monitor;

BEGIN

var БАЗА<данные>

флаг:0...1

непуст, пусто: condition

и 2 условные переменные для организации очереди ожидания.

При попытке записи в непустую область процесс переводит в очередь ожидания. При попытке чтения из пустой области, процесс помещается в очередь ожидания.

Реализация монитора:

Любое высокоуровневое средство синхронизации при взаимодействии процессов может быть построено с помощью низкуровневых средств.

Рассмотрим реализацию монитора с использованием семафора:

1. Если в состав монитора входит n процедур m-условных переменных и k-локальных переменных. Потребуется: один двоичный семафор для реализации взаимного исключения. Начальное значение одно.

2. Один двоичный семафор для решения задачи сигнализации (SIGM)

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

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

3. По одному двоичному семафору на каждый из n условных переменных для организации очередей процессов, остановившихся на операции WAIT.

4. Счетчики для условных переменных (длины очереди)