Критическая область. Основные модификации

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

«Критическая область»

var V:shared <Type>;

region V do S;

Во вторых, эти механизмы реализованы парными примитивами (для семафор, закрыт и открыт) что подразумевает четкую последовательность их вызова.

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

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

Однако получаемые решения будут неэквивалентны с их практической точки зрения, т. е. С точки зрения проектирования и реализации.

Основной концепцией монитора подобных средств синхронизации является возможность организации контроля правильности установления взаимосвязи между программами.

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

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

Механизм «критической области»

При описании кеременной используется следующая нотация:

var V: shared<Type>;

region V do S;

Устанавливается, что обращение к переменной V допускается только в рамках специальной конструкции region.

Конструкция region определяет критическую область по отношению к переменной V соответственно при использовании // проц. Реализуется режим взаимного исключения по отношению к переменной V.

Преимущества:

1. Ошибки используемого ресурса выявляются на этапе компиляции программы.

2. Преобразование этой конструкции с использованием базовых механизмов синхонизации. Может быть выполнено компилятором безошибочно

«Услованя критическая область»

var V:shared<Type>;

region V do S;

В рамках конструкции region допускается использование оператора await таким образом вводится возможность рабьоты с критическим ресурсом, при условии что он находится в пределах сост. В качества параметра примитива используется логическое выражение.

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

Если при выполнении операции await значение переменной становится истинным, данный процесс временно покидает критическую область. Это дает возможность другим процессам (одному) войти в критическую область и поменять компонент логического выражения.

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

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

Описанный механизм может быть реализован компилятором с использованием двоичного семафора.

 

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

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

Б. Хансен — 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. Счетчики для условных переменных (длины очереди)

 

Распределенное программирование. Основные понятия

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

П1 <=> П2

| |

ЛП1 ЛП2

В распределенных системах для построения механизмов синхронизации вместо разделяемых переменных используются средства передачи сообщений. Для поддержки механизма обмена сообщениями узлы распределённой системы «соединяются» с помощью специальных аппаратно-программных средств, называемых каналами. Каналы бывают разные...;)

Передача сообщений:

Обмен сообщениями может быть осуществлён в 2 режимах: синхронная передача сообщений и асинхронная передача сообщений.

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

При асинхронной передаче такое подтверждение не требуется.

Соответственно для отправки сообщения используется примитив SEND, для получения сообщения RECIEVE.

SEND — поддерживает асинхронный режим передачи и является неблокирующим примитивом. Для синхронной передачи применяется SYNCH_SEND.

При блокировке — приостановка процесса.

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

 

Каналы и передача сообщений

Канал

Для описания каналов используется следующая нотация:

chan ch(type1id1,...,typeNidN)

В скобках описываем имена полей и их типы

chan input(char)

chan disk_a(int cyl, int block, int count, char* buf)

chan result[n](int)

Процесс управляет сигналами используя send ch (expr1,...,expr n) //поле сообщ.

Recieve ch (var1,...,varn)

empty(ch)

Так как recieve является блокир. Вводится режим проверки в случае если сообщение в канале отсутствует.

Каналы являются глобальными для всех процессов, тоесть канал можнт и читать и писать данные в V канал.

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