Синхронизация с помощью элементарных приемов нижнего уровня.

1. Блокировка памяти.

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

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

Поскольку скорости обоих процессов – произвольны, указанные выше условия должны выполняться каковы бы ни были скорости работы каждого процесса относительно другого.

Казалось бы, ничего проще нет, как предложить следующее решение:

Boolean : Переключатель_1, Переключатель_2;

Begin

Переключатель_1:=False;

Переключатель_2:=False;

Parbegin

Процесс_1: do while (True);

Цикл_1: do while (Переключатель_2);

end;

Переключатель_1:=True;

/* Критический участок 1 */

Переключатель_1:=False;

/* Оставшаяся часть процесса 1*/

end;

Процесс_2: do while (True);

Цикл_2: do while (Переключатель_1);

end;

Переключатель_2:=True;

/* Критический участок 2 */

Переключатель_2:=False;

/* Оставшаяся часть процесса 2*/

end;

parend;

End.

Однако, поскольку скорости произвольны, допустим, что Процесс 2 работает гораздо быстрее, чем Процесс 1. Настолько быстрее, что фактически после того, как Процесс 1 обнаруживает, что в Переключателе 2 стоит ”ложь”, но прежде чем он успеет установить значение “истина”, в Переключателе 1, Процесс 2 пробегает свою оставшуюся часть и перескакивает через Цикл 2 (поскольку в Переключателе 1 все еще стоит значение “ложь”). Оба процесса в таком случае перейдут к выполнению (одновременно) своих критических участков, т.е. в таком переключательном случае система будет работать неправильно.

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

Мы же приведем вариант решения, предложенного Деккером.

Алгоритм Деккера:

integer: C1,C2,Очередь;

Begin

C1:=0;

C2:=0;

Очередь:=1;

Parbegin

Процесс_1: begin C1:=1;

do while (C2=1);

if Очередь=2 then

Begin

C1:=0;

do while (Очередь=2);

end;

C1:=1;

end;

end;

Критический участок Процесса 1;

C1:=0;

Очередь:=2;

Оставшаяся часть Процесса 1;

end;

Процесс_2: begin C2:=1;

do while (C1=1);

if Очередь=1 then

Begin

C2:=0;

do while (Очередь=1);

end;

C2:=1;

end;

end;

Критический участок Процесса 2;

C2:=0;

Очередь:=1;

Оставшаяся часть Процесса 2;

end;

parend;

end.

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

1. Проверка и установка.

Эта машинная операция значительно упрощает решение проблемы критического участка.

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

Главное свойство этой операции – ее неделимость. Когда процесс выполняет операцию “проверка и установка” никаких действий не может произойти между ее началом и концом.

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

Если “общий” = 1, это значит, что какой-то процесс находится в своем критическом участке. Начальное значение переменной “общий” = 0.

Приведем решение проблемы методом “проверка и установка”. В этом решени предпологается, что в машине предусмотрена блокировка памяти, т.е. операция “общий” := 0 неделима.

Алгоритм проверки и установки:

integer: ОБЩИЙ;

Begin

ОБЩИЙ:=0;

Parbegin

integer: ЛОКАЛЬНЫЙ1;

Процесс_1: begin do while (True);

ЛОКАЛЬНЫЙ1:=1;

do while (ЛОКАЛЬНЫЙ1=1)

Проверка и установка(ЛОКАЛЬНЫЙ1,ОБЩИЙ)

end;

Критический участок 1;

ОБЩИЙ:=0;

Оставшаяся часть Процесса 1;

end;

end;

integer: ЛОКАЛЬНЫЙ2;

Процесс_2: begin do while (True);

ЛОКАЛЬНЫЙ2:=1;

do while (ЛОКАЛЬНЫЙ2=1)

Проверка и установка(ЛОКАЛЬНЫЙ2,ОБЩИЙ)

end;

Критический участок 2;

ОБЩИЙ:=0;

Оставшаяся часть Процесса 2;

end;

end;

parend;

end.

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

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

Одним из приемов, позволяющих избежать активного избежания является “семафор”.

Семафор – целая переменная, значения которой могут менять только операции P и V. Пусть S – семафор. Когда процесс выполняет операцию P(S), S уменьшается на единицу и

1. Если S³0, то процесс продолжает работу.
2. Если S<0, то процесс останавливается и становится в очередь ожидания, связанную с S. Он остается заблокированным до тех пор, пока операция V(S), выполненная другим процессом, не освободит его.

Когда процесс выполняет V(S), S увеличивается на единицу и

1. Если S>0, процесс продолжает работу.
2. Если S£0, то один процесс изымается из очереди ожидания и получает разрешение продожить работу. Процесс, который обратился к операции V(S), тоже может продолжать работу.

Кроме того, операции P и V – неделимы. В каждый момент времени только один процесс может выполнять операцию P или V над данным семафором. Поэтому если, S=1 и два процесса одновременно попытаются выполнить операцию P(S), то только одному из них будет позволено продолжить работу. Другой процесс будет заблокирован и поставлен в очередь к семафору S.

Ранее мы говорили о том, что стержень системы – это механизм, который реализует процессы. Стержень должен выделять процессам и отбирать у них процессоры. Операции P и V можно реализовать внутри стержня. Таким образом, обеспечивается неделимость этой операции.

Семафор, максимальное значение которого равно единице, называется двоичным семафором.

С помощью двоичного семафора процессы могут организовать взаимное исключение с помощью операций P(S) и V(S).

Пример:

integer: СВОБОДНЫЙ;

Begin

СВОБОДНЫЙ:=1;

Parbegin

Процесс_1: begin do while (True);

Начало Процесса 1;

P(СВОБОДНЫЙ);

Критический участок 1;

V(СВОБОДНЫЙ);

Оставшаяся часть Процесса 1;

end;

end;

Процесс_2: begin do while (True);

Начало Процесса 2;

P(СВОБОДНЫЙ);

Критический участок 2;

V(СВОБОДНЫЙ);

Оставшаяся часть Процесса 2;

end;

end;

parend;

end.

Здесь S принимает значения 1, 0, -1. Если S=1, это значит, что ни один процесс не находится в своем критическом участке. Если S=0 –один процесс находится в своем критическом участке. Если S=-1 – один процесс находится в своем критическом участке, а второй – в очереди ожидания.

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

С помощью общих семафоров легко решается проблема “Поставщик–Потребитель”.

Переменная “наличие” – семафор, значение которого равно числу свободных буферов в пуле.

Переменная “заполн” – семафор, значение которого равно числу заполненных буферов, которые были отосланы потребителю.

Семафор “взаиск” (взаимное исключение) – двоичный. Он гарантирует, что в каждый момент только один процесс сможет работать с буферными стрелками.

integer: НАЛИЧИЕ,ЗАПОЛН,ВЗАИСК;

Begin

НАЛИЧИЕ:= количество свободных буферов;

ЗАПОЛН := 0;

ВЗАИСК := 1;

Parbegin

ПОСТАВЩИК: begin do while (True);

Приготовить сообщение;

P(НАЛИЧИЕ);

P(ВЗАИСК);

Послать сообщение;

V(ЗАПОЛН);

V(ВЗАИСК);

end;

end;

ПОТРЕБИТЕЛЬ: begin do while (True);

P(ЗАПОЛН);

P(ВЗАИСК);

Получить сообщение;

V(НАЛИЧИЕ);

V(ВЗАИСК);

Обработать сообщение;

end;

end;

parend;

end.

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

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

Если значение семафора S становится отрицательным, это значит, что очереди, связанной с S, ожидает один или несколько процессов.

Когда выполняется очередная операция V(S), стержень должен выбрать, какой процесс надо взять из очереди. Стержень системы может обслуживать очередь в порядке поступления или использовать приоритетную схему обслуживания. Порядок обслуживания очереди должен обуславливаться целями, для которых применяется данный семафор. Вопрос определения дисциплины обслуживания при проектировании ОС тесно связан с моделированием вычислительных процессов, для чего могут быть эффективно использованы модели массового обслуживания.

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

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

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