Примеры использования различных объектов синхронизации

Пример 1. Организуем синхронизацию двух процессов (0 и 1) на основе использования блокирующих переменных.

Одно из возможных решений задачи, предложенное математиком Петерсоном, следующее /7,8/:

#define FALSE 0

#define TRUE 1

#defwe N 2 /* Количество процессов */

int turn; /* Чья сейчас очередь? */

int interested[N]; /* Все переменные изначально равны 0 (FALSE) */

void enter regiont(int process); /* Процесс 0 или 1 */

{

int other; /* Номер второго процесса */

other = 1 – process; /* Противоположный процесс */

interested[process] = TRUE; /* Индикатор интереса*/

turn = process; /* Установка флага*/

while (turn == process && interested[other] == TRUE) /* Пустой оператор */; }

void leave regiont(int process) /* process: процесс, покидающий критическую область */ {

interested[process] = FALSE: /* Индикатор выхода из критической области */ }

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

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

Рассмотрим работу алгоритма более подробно.

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

Теперь, если процесс 1 вызовет enter_region, ему придется подождать, пока interested [0] примет значение FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет процедуру leave_region, чтобы покинуть критическую область.

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

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

Пример 2. Разработаем систему синхронизации группы потоков на основе использования блокирующих переменных.

Одно из возможных решений задачи, основанное на алгоритме Деккера, следующее.

Алгоритм Деккера основан на использовании трех переменных: перекл1, перекл2 и ОЧЕРЕДЬ.

Пусть переменная перекл1 устанавливается в true тогда, когда процесс ПР1 хочет войти в свою критическую секцию (для ПР2 аналогично), а значение переменной ОЧЕРЕДЬ указывает, чье сейчас право сделать попытку входа при условии, что оба процесса хотят выполнить свои критические секции.

Тогда:

label 1. 2;

var перекл1, перекл2: boolean;

ОЧЕРЕДЬ: integer;

Begin перекл1: = false; перекл2: = false;

ОЧЕРЕДЬ: = 1

parbegin

while true do

begin перекл1: = true;

1: if перекл2 = true then

If ОЧЕРЕДЬ = 1 then go to 1

else begin перекл1: = false;

while ОЧЕРЕДЬ = 2 do

begin end

end

else begin

CS1

ОЧЕРЕДЬ:=2; перекл1:=false

end

end

end

while true do

begin перекл2:=1

begin перекл2:=1

2: if перекл1 = true then

If ОЧЕРЕДЬ = 2 then go to 2

else begin перекл2: = false

while ОЧЕРЕДЬ = 1 do

begin end

end

else begin

CS2

ОЧЕРЕДЬ: = 1; перекл2: = false

end

end

parend

end.

Если перекл2 = true и перекл1 = false, то выполняется критическая секция процесса ПР2 независимо от значения переменной ОЧЕРЕДЬ.

Аналогично для случая перекл2 = false и перекл1 = true.

Если же оба процесса хотят выполнить свои критические секции, то есть перекл2 = true и перекл1 = true, то выполняется критическая секция того процесса, на который указывает значение переменной ОЧЕРЕДЬ, независимо от скоростей развития обоих процессов.

Использование переменной ОЧЕРЕДЬ совместно с переменными перекл1 и перекл2 в алгоритме Деккера позволяет гарантировано решать проблему критических секций.

Действительно, переменные перекл1 и перекл2 гарантируют, что взаимное выполнение не может иметь места. В свою очередь переменная ОЧЕРЕДЬ гарантирует, что не может быть взаимной блокировки, так как переменная ОЧЕРЕДЬ не меняет своего значения во время выполнения программы принятия решения о том, кому же сейчас проходить свою критическую секцию.

Пример 3. Разработаем программу взаимной синхронизации процесса-писателя и процесса-читателя при доступе к буферному пулу. Задачу решить на основе семафоров.

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

#define N 100 /* количество сегментов в буфере */

typedef int semaphore; /* семафоры - особый вид целочисленных переменных */

semaphore mutex - 1: /* контроль доступа в критическую область */

semaphore empty - N; /* число пустых сегментов буфера */

semaphore full - 0: /* число полных сегментов буфера */

void producer(void)

{

int item;

while (TRUE) { /* TRUE - константа, равная 1*/

item - produce_item(); /* создать данные, помещаемые в буфер */

down(Sempty); /* уменьшить счетчик пустых сегментов буфера */

down(&mutex); /* вход в критическую область */

insert_item(item); /* поместить в буфер новый элемент */

up(&mutex); /* выход из критической области */

upC&fulI): /* увеличить счетчик полных сегментов буфера */}}

void consumer(void)

{

int item;

while (TRUE) { /* бесконечный цикл */

down(SfuTI); /* уменьшить числа полных сегментов буфера */

down(&mutex): /* вход в критическую область */

item = remove_item(); /* удалить элемент из буфера */

up(&mutex); /* выход из критической области */

up(&empty): /* увеличить счетчик пустых сегментов буфера */

consume_item(item); /* обработка элемента */

} }

В представленном решении используются три семафора: один для подсчета заполненных сегментов буфера {full), другой для подсчета пустых сегментов {empty), а третий предназначен для исключения одновременного доступа к буферу производителя и потребителя {mutex). Значение счетчика full исходно равно нулю, счетчик empty равен числу сегментов в буфере, a mutex равен 1. Семафоры, исходное значение которых равно 1, используемые для исключения одновременного нахождения в критической области двух процессов, называются двоичными семафорами. Взаимное исключение обеспечивается, если каждый процесс выполняет операцию down перед входом в критическую область и up после выхода из нее.

Пример 4. Разработаем программу взаимной синхронизации процесса-производителя и процесса-потребителя при доступе к буферному пулу. Задачу решить на основе программного объекта монитор.

В 1974 году Хоар и Бринч Хансен предложили примитив синхронизации более высокого уровня, называемый монитором /11-12 /.

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

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

Монитор – набор процедур, переменных и других структур данных, объединенных в особый модуль или пакет. Внутренние данные монитора могут быть либо глобальными (относящимися ко всем процедурам монитора), либо локальными (относящимися только к одной конкретной процедуре). Процессы могут вызывать процедуры монитора, но у процедур, объявленных вне монитора, нет прямого доступа к внутренним структурам данных монитора.

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

Решение заключается во введении переменных состояния и двух операций wait и signal. Когда процедура монитора обнаруживает, что она не в состоянии продолжать работу (например, производитель выясняет, что буфер заполнен), она выполняет операцию wait на какой-либо переменной состояния, скажем full. Это приводит к блокировке вызывающего процесса и позволяет другому процессу войти в монитор.

Например, процесс-потребитель может активизировать ожидающий процесс, выполнив операцию signal на той переменной состояния, на которой этот процесс был заблокирован. Чтобы в мониторе не оказалось двух активных процессов одновременно, необходимо правило, определяющее последствия операции signal. Хоар предложил запуск «разбуженного» процесса и остановку второго. Бринч Хансен предложил другое решение: процесс, выполнивший signal, должен немедленно покинуть монитор. Иным словами, операция signal выполняется только в самом конце процедуры монитора. Кроме этого, существует третье решение, не основывающее на предложениях Хоара и Бринча Хансена: позволить процессу, выполнившему signal, продолжать работу и запустить ждущий процесс только после того, как первый процесс покинет монитор.

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

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

monitor ProducerConsumer

condition full, empty;

integer count;

procedure insert(item: integer);

begin

if count = N then wait(full);

insert_item(item);

count:= count+1;

if count:= l then signal(empty)

end;

function remove: integer;

begin

if count = 0 then wait(empty);

remove = remove_item;

count:= count-1;

if count:= N-l then signal(full)

end;

count:= 0;

end monitor;

procedure producer;

begin

while true do

begin

item = produce_item;

ProducerConsumer.insert(item)

end

end;

procedure consumer;

begin

while true do

begin

item = ProducerConsumer.remove;

consume_item(item)

end

end;

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

Пример 5. Разработаем программу синхронизации на основе объекта Semaphore ОС Windows XP.

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

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