Методы синхронизации процессов

Презентацию к данной лекции Вы можете скачать здесь.

Введение

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

История синхронизации

Методы синхронизации процессов рассматривались еще в 1960-х гг. в пионерской работе Э. Дейкстры . Было отмечено, что совместный доступ параллельных процессов к общим данным может привести к нарушению их целостности. Поддержание целостности общих данных требует реализации и использования механизмов упорядочения работы взаимодействующих процессов (или потоков).

Анализ проблемы производитель – потребитель с точки зрения синхронизации по общему буферу

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

Вспомним представление ограниченного буфера на языке Си (см. ) и расширим его переменной counter :

#define BUFFER_SIZE 1000 /* или другое конкретное значение */

typedef struct {

	. . .

} item;

item buffer[BUFFER_SIZE];

int in = 0;

int out = 0;

int counter = 0;

Теперь модифицируем реализации процесса-производителя и процесса-потребителя (см. ) , добавив соответствующие изменения переменной counter:

Процесс-производитель:

item nextProduced; /* следующий генерируемый элемент */

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

	while (counter == BUFFER_SIZE)

		; /* ждать, пока буфер переполнен */

	buffer[in] = nextProduced; /* генерация элемента */

	in = (in + 1) % BUFFER_SIZE;

	counter++;

}

Процесс-потребитель:

item nextConsumed; /* следующий используемый элемент */

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

	while (counter == 0)

		; /* ждать, пока буфер пуст */

	nextConsumed = buffer[out]; /* использование элемента */

	out = (out + 1) % BUFFER_SIZE;

	counter--;

}

Возникает вопрос: насколько корректны модифицированные алгоритмы, использующие переменную counter ? Не вполне. Проблема в том, что counter фактически является общим ресурсом, к которому одновременно обращаются два параллельных процесса. Если при этом обращение произойдет одновременно, то переменная counter может в итоге оказаться в некорректном состоянии. Поэтому необходимо, чтобы каждый из процессов при увеличении или уменьшении ее значения имел бы к ней монопольный доступ, и другой процесс не мог бы в это время "испортить" значение переменной. Иными словами, операции counter++ и counter— должны выполняться атомарно (см. лекцию 9). Напомним, что атомарная операция – это такая операция, которая должна быть выполнена полностью, без каких-либо прерываний; при этом операция, выполняемая одним из процессов, должна быть неделимой, с точки зрения другого процесса.

Операции count++ и count— могут быть реализованы на языке ассемблерного уровня следующим образом:

count++:

register1 = counter

register1 = register1 + 1

counter = register1

count--:

register1 = counter

register1 = register1 - 1

counter = register1

где register1 – регистр аппаратуры.

Проблема в том, что если и производитель, и потребитель пытаются изменить переменную counter одновременно, то указанные ассемблерные операторы тоже должны быть выполнены совместно (interleaved).

Конкретная реализация такого совместного выполнения зависит от того, каким образом происходит планирование для процессов – производителя и потребителя, а также от применения (или неприменения) в каждом из случаев аппаратных оптимизаций, например, увеличения (уменьшения) значения регистра одной командой за один такт ( increment / decrement).

Рассмотрим эффект interleaving на конкретном примере. Предположим, что начальное значение переменной counter в некоторый момент равно 5. Исполнение процессов в совместном режиме (interleaving) может привести к следующему эффекту:

производитель: register1 = counter (register1 = 5)

производитель: register1 = register1 + 1 (register1 = 6)

потребитель: register2 = counter (register2 = 5)

потребитель: register2 = register2 – 1 (register2 = 4)

производитель: counter = register1 (counter = 6)

потребитель: counter = register2 (counter = 4)

Таким образом, значение counter в итоге может оказаться равным 6 или 4, в то время как правильное значение counter равно 5.

Ситуация, при которой взаимодействующие процессы могут параллельно (одновременно) обращаться к общим данным, называется конкуренцией за общие данные (race condition).Для предотвращения подобных ситуаций процессы следует синхронизировать.

Синхронизация процессов по критическим секциям

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

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

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

Алгоритм решения проблемы критической секции

Пусть для простоты имеется только два процесса – P0 и P1. Общая структура i - го процесса должна иметь вид:

do {

 вход в критическую секцию

	критическая секция

 выход из критической секции

	остальная часть кода

} while (1)

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

Алгоритм 1.Предпримем первую попытку решения проблемы. Введем целую переменную turn (очередь), значение которой turn == i будет обозначать, что наступила очередь процесса номер i войти в свою критическую секцию. Первоначально turn == 0.

Алгоритм процесса Pi имеет вид:

do {

 while (turn != i);

	критическая секция

 turn = j; /* j != i: если i == 0, j == 1; если i == 1, j == 0 */

	остальная часть кода

} while (1)

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

Алгоритм 2.Будем хранить не номер процесса, допущенного к критической секции, а массив булевских флагов flag [2], такой, что flag[i] == true, если i -й процесс готов войти в свою критическую секцию. Алгоритм процесса Pi примет вид:

do {

 flag[i] = true;

 while (flag[j]); /* j!=i: если i==0, j==1; если i == 1, j == 0 */

 	критическая секция

 flag[i] = false;

 	остальная часть кода

} while (1)

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

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

Алгоритм 3.Модифицируем алгоритм, используя в нем одновременно и переменную turn, и массив флагов flag. Алгоритм процесса примет вид:

do {

 flag[i] = true;

 turn = j;

 while (flag[j] and turn == j);

 	критическая секция

 flag[i] = false;

 	остальная часть кода

} while (1)

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

Алгоритм булочной (bakery algorithm)

Автор данного алгоритма – Л. Лампорт (L. Lamport). Рассмотрим другой алгоритм, решающий проблему синхронизации по критическим секциям. Происхождение названия следующее: алгоритм как бы воспроизводит стратегию автомата в (американской) булочной, где каждому клиенту присваивается его номер в очереди. В нашей российской реальности, данный алгоритм более уместно было бы назвать по этой же причине "алгоритм Сбербанка".

В алгоритме для n процессов используется булевский массив choosing[n]:значение choosing[i] == true будет означать, что в данный момент система определяет номер в очереди i -го процесса. Используется также целочисленный массив number[n]: number[i] будет обозначать вычисленный порядковый номер в очереди (приоритет) i- го процесса.

Алгоритм булочной (для i -го процесса) имеет вид:

do {

 choosing[i] = true;

 number [i] = max (number[0], number[1], …, number[n-1]) + 1;

 choosing[i] = false;

 for (j = 0; j < n; j++) {

	while (choosing[j]);

	while ((number[j] != 0)  (number[j] < number[i]));

 }

 	критическая секция

 number [i] = 0; 

 	остальная часть кода

} while (1)

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

Синхронизация на основе аппаратной поддержки атомарных операций

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

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

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

boolean TestAndSet (boolean  target) {

	boolean rv = target;

	target = true;

	return rv;

}

С помощью данной операции реализовать синхронизацию процессов по критическим секциям очень просто. Введем в качестве блокировщика общую булевскую переменную:

boolean lock = false;

Код i -го процесса будет иметь вид:

do {

 while (TestAndSet (lock));

	критическая секция

 lock = false;

	остальная часть кода

} while (1)

Значение переменной lock, равное true,означает, что вход в критическую секцию заблокирован. Каждый процесс ждет, пока он не разблокируется, затем, в свою очередь, выполняет блокировку и входит в критическую секцию. При ее завершении процесс разблокирует критическую секцию присваиванием lock значения false.

Другое распространенное аппаратное решение для синхронизации – атомарная операция Swap, выполняющая перестановку значений двух переменных:

void Swap (Boolean * a, Boolean * b) {

	Boolean temp = * a;

a = * b;

* b = temp;

 }

Взаимное исключение по критическим секциям с помощью атомарной операции Swap реализуется следующим образом (приведен код i -го процесса) :

/* общие данные */

boolean lock = false;

Boolean key = false;

/* код процесса i */

do {

 key = true;

 while (key) {

	Swap (lock, key);

 }

	критическая секция

 lock = false;

	остальная часть кода

} while (1)

При данной реализации, условием ожидания процесса перед входом в критическую секцию является условия (key == true),которое фактически означает то же, что и в предыдущей реализации, - закрытое состояние блокировщика, т.е., то, что другой процесс находится в своей критической секции. Когда критическая секция освободится (освобождение осуществляется присваиванием lock = false после завершения критической секции в исполнившем ее процессе), ее начнет исполнять текущий процесс.

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

Мы уже начали рассматривать семафоры Дейкстры как средство синхронизации в обзорной части курса. Здесь мы рассмотрим их более подробно в общем виде. Общий семафор (counting semaphore),по Э. Дейкстре, - это целая переменная S, над которой определены две атомарных семафорных операции wait (S) и signal (S) со следующей семантикой:

wait (S):

	while (S <= 0) do no-op;

	S--;

signal (S):

	S++;

Фактически, если начальное значение общего семафора равно n (> 0), то это число задает количество процессов, которые могут беспрепятственно выполнить над семафором операцию wait.

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

/* общие данные */

semaphore mutex = 1;

do {

 wait (mutex);

	критическая секция

 signal (mutex);

	остальная часть кода

} while (1)

Реализация семафоров

Семафор, по существу, является структурой из двух полей – целого значения и указателя на список ждущих процессов:

typedef struct {

	int value;

	struct process * L;

} semaphore;

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

block - задерживает исполнение процесса, выполнившего эту операцию;

wakeup (P) – возобновляет исполнение приостановленного процесса P.

Определим семафорные операции следующим образом:

wait (S):

	S.value--;

	if (S.value < 0) {

		добавление текущего процесса к S.L;

		block;

	}

signal (S):

	S.value++;

	if (S.value <= 0) {

		удаление процесса P из S.L;

		wakeup (P);

	}

Семафоры как общее средство синхронизации

Наиболее простой вид синхронизации действий, выполняемых в двух процессах, - это исполнение действия B в процессе Pj после того, как действие A исполнено в процессе Pi . Рассмотрим, как такую синхронизацию осуществить с помощью семафоров.

Используем семафор flag, инициализированный 0.

Код процесса Pi:

. . . 

A;

signal (flag);

Код процесса Pj:

. . . 

wait (flag);

B;

Общие и двоичные семафоры

Из рассмотренного ясно, что имеется два вида семафоров: общий - целая переменная с теоретически неограниченным значением - и двоичный - целая переменная, значениями которой могут быть только 0 или 1. Преимуществом двоичного семафора является его возможная более простая аппаратная реализация. Например, в системах "Эльбрус" и Burroughs 5000 реализованы команды атомарного семафорного считывания с проверкой семафорного бита.

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

Вариант операции wait (S) для системных процессов ("Эльбрус")

Для системного процесса лишние прерывания нежелательны, и может оказаться важным удерживать процессор за собой некоторое время (например, для быстрого выполнения планирования и диспетчеризации процессов). С этой целью в системе "Эльбрус" реализована, в дополнение к операции ждать (S) русифицированной версии wait(S),операция жуж(S) - "жужжать" на процессоре, т.е. ждать на закрытом семафоре, но не прерываться и не отдавать процессор, пока семафор не будет открыт операцией открыть(S)

Реализация общего семафора с помощью двоичных семафоров

Общий семафор может быть представлен тройкой из двух двоичных семафоров и целой переменной:

binary-semaphore S1 = 1;

binary-semaphore S2 = 0;

int C = начальное значение общего семафора S;

Операция wait:

wait (S1);

C--;

if (C < 0) {

	signal (S1);

	wait (S2);

}

signal (S1);

Операция signal:

wait (S1);

C++;

if (C >= 0) {

	signal (S2);

	};

signal (S1);

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

Решение классических задач синхронизации с помощью семафоров

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

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

Будем использовать три общих семафора:

semaphore full = n;

semaphore empty = 0;

semaphore mutex = 1;

Семафор full сигнализирует о переполнении буфера, empty – об исчерпании буфера, mutex – используется для взаимного исключения действий над буфером.

Код процесса-производителя имеет вид:

do {

	. . . 

	сгенерировать элемент в nextp

	. . . 

	wait (full);

	wait (mutex);

	. . .

	добавить nextp к буферу

	. . . 

	signal (mutex);

	signal (empty);

} while (1);

Код процесса-потребителя:

do {

	wait (empty);

	wait (mutex);

	. . .

	взять и удалить элемент из буфера в nextc

	. . . 

	signal (mutex);

	signal (full);

	. . .

	использовать элемент из nextc

	. . .

} while (1);

Поясним использование семафоров. Семафор mutex используется "симметрично"; над ним выполняется пара операций: wait … signal – семафорные скобки. Его роль – чисто взаимное исключение критических секций. Семафор empty сигнализирует об исчерпании буфера. В начале он закрыт, так как элементов в буфере нет. Поэтому при закрытом семафоре empty потребитель вынужден ждать. Открывает семафор empty производитель, после того, как он записывает в буфер очередной элемент. Семафор full сигнализирует о переполнении буфера. В начале он равен n – максимальному числу элементов в буфере. Производитель перед записью элемента в буфер выполняет операцию wait (full),гарантируя, что, если буфер переполнен, записи нового элемента в буфер не будет. Открывает семафор full потребитель, после того, как он освободил очередной элемент буфера.

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

Решение с помощью семафоров задачи "читатели – писатели"

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

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

semaphore mutex = 1;

semaphore wrt = 1;

int readcount = 0;

Семафор mutex используется читателями для взаимного исключения операций над переменной readcount (счетчиком читателей). Семафор wrt используется для взаимного исключения писателей.

Реализация процесса-писателя особых комментариев не требует:

wait (wrt);

. . .

изменение ресурса

. . . 

signal (wrt);

Реализация процесса-читателя несколько более сложна:

wait (mutex);

readcount++;

if (readcount == 1) {

	wait (wrt);

}

signal (mutex);

. . .

чтение ресурса 

. . .

wait (mutex);

readcount--;

if (readcount == 0) {

	signal (wrt);

}

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

Решение с помощью семафоров задачи "обедающие философы"

Суть задачи обедающие философы в следующем. Имеется круглый стол, за которым сидят пять философов (впрочем, их число принципиального значения не имеет – для другого числа философов решение будет аналогичным). Перед каждым из них лежит тарелка с едой, слева и справа от каждого – две китайские палочки. Философ может находиться в трех состояниях: проголодаться, думать и обедать. На голодный желудок философ думать не может. Но начать обедать он может, только если обе палочки слева и справа от него свободны. Требуется синхронизировать действия философов. В данном случае общим ресурсом являются палочки. Иллюстрацией условий задачи является рис 12.1.

(рис 12.1) Задача "обедающие философы".

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

При решении задачи будем использовать массив семафоров chopstick, описывающий текущее состояние палочек: chopstick[i] закрыт, если палочка занята, открыт – если свободна:

semaphore chopstick [5] = { 1, 1, 1, 1, 1};

Алгоритм реализации действий философа i имеет вид:

do {

	wait (chopstick [i]); /* взять левую палочку */

	wait (chopstick [(i + 1) % 5]); /* взять правую палочку */

	. . . 

	обедать

	. . .

	signal (chopstick [i]); /* освободить левую палочку */

	signal (chopstick [(i+1) % 5]); /* освободить правую палочку */

	. . . 

	думать

	. . .

while (1);

Решение данной задачи с помощью семафоров оказывается особенно простым и красивым.

Критические области

Критические области (critical regions) – более высокоуровневая и надежная конструкция для синхронизации, чем семафоры. Общий ресурс описывается в виде особого описания переменной:

v: shared T

Доступ к переменной v возможен только с помощью специальной конструкции:

region v when B do S

где v – общий ресурс; B – булевское условие, S – оператор (содержащий действия над v ).

Семантика данной конструкции следующая. Пока B ложно, процесс, ее исполняющий, должен ждать. Когда B становится истинным, процесс получает доступ к ресурсу v и выполняет над ним операции S. Пока исполняется оператор S, больше ни один процесс не имеет доступа к переменной v.

Решение с помощью критических областей задачи "ограниченный буфер"

Опишем буфер как структуру:

struct buffer {

	int pool [n];

	int count, in, out

}

buf: shared buffer;

Алгоритм процесса-производителя:

region buf when (count < n) {

	pool [in] = nextp;

	in = (in+1) % n;

	count++;

}

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

Алгоритм процесса-потребителя:

region buf when (count > 0) {

	nextc = pool [out];

	out = (out+1) % n;

	count--;

}

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

Схема реализации критических областей с помощью семафоров

Будем использовать для реализации конструкции region x when B do S следующие семафоры и целые переменные:

semaphore mutex, first-delay, second-delay;

int first-count, second-count;

Семафор mutex используется для взаимного исключения доступа к критической секции S. Семафор first-delay используется для ожидания процессов, которые не могут войти в критическую секцию S, так как условие B ложно. Число таких процесов хранится в переменной first-count. Семафор second-delay используется для ожидания тех процессов, которые вычислили условие B один раз и ожидают, когда им будет позволено повторно вычислить B ( second-count – счетчик таких процессов). Реализация предоставляется студентам в качестве упражнения.

Мониторы

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

Описание монитора имеет вид:

monitor monitor-name

{

	описания общих переменных

	procedure body P1 ( … ) {

		. . . 

	}

	procedure body P2 ( … ) {

		. . . 

	}

	. . .

	procedure body Pn( … ) {

		. . . 

	}

	{

		код инициализации монитора

	}

}

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

По сути дела, концепция монитора явилась развитием предложенной также Ч. Хоаром концепции абстрактного типа данных (АТД) – определения типа данных как совокупности описания его конкретного представления и абстрактных операций над ним (в виде процедур). Концепция монитора добавляет к АТД возможность синхронизации процессов по общим данным.

Для реализации ожидания внутри монитора по различным условиям, вводятся условные переменные (condition variables) – переменные с описаниями вида condition x,y, доступ к которым возможен только операциями wait и signal: например, x.wait(); x.signal(). Операция x.wait() означает, что выполнивший ее процесс задерживается до того момента, пока другой процесс не выполнит операцию x.signal(). Операция x.signal() возобновляет ровно один приостановленный процесс. Если приостановленных процессов нет, она не выполняет никаких действий.

Схематическое изображение монитора приведено на рис 12.2.

(рис 12.2) Схематическое изображение монитора.

Схема монитора с условными переменными приведена на рис 12.3.

(рис 12.3) Монитор с условными переменными.

Решение задачи "обедающие философы" с помощью мониторов

Реализуем решение задачи "обедающие философы" (см. Решение с помощью семафоров задачи "обедающие философы") с помощью монитора. Для каждого философа определим состояния (голодный, обедает, думает), и для их хранения будем использовать массив state. Для управления переходом философа из состояния в состояние используем массив условных переменных self. Для каждого философа определим операции pickup – взять палочку; putdown – освободить палочку ; test – проверить состояние философа и, если это возможно и если он голоден, перевести его в состояние eating.

Код монитора, реализующего решение задачи:

monitor dp

{

	enum {thinking, hungry, eating} state [5];

	condition self [5];

	void pickup (int i) {

		state [i] = hungry;

		test (i);

		if (state[i] != eating) {

			self[i].wait ();

		}

	} /* pickup */

	void putdown (int i) {

		state [i] = thinking;

		test ((i+4) % 5));

		test ((i-1) % 5));

		/* когда палочка свободна, проверить соседей */

	} /* putdown */

	void test (int i) {

		if (state((i+4)%5) != eating 

 state [i] = hungry 

 		 state((i+1)%5) != eating)) {

			state[i] = eating;

			self[i].signal;

 

	void init () {

		for (int i = 0; i < 5; i++) {

			state[i] = thinking;

	}

}

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

Используем семафоры mutex – для взаимного исключения процессов, next – для реализации очереди входа в монитор; переменную next-count – счетчик процессов в очереди на вход:

semaphore mutex = 1;

semaphore next = 0;

int next-count = 0;

Каждую внешнюю процедуру монитора F реализуем следующим кодом:

wait (mutex);

. . . 

тело F;

. . . 

if (next-count > 0) {

	signal next;

} else { 

	signal mutex;

}

Таким образом, будет обеспечено взаимное исключение внутри монитора.

Каждую условную переменную x реализуем следующим образом:

semaphore x-sem = 0;

int x-count = 0;

Реализация операции x.wait():

x-count++;

if (next-count > 0) {

	signal (next);

} else {

	signal (mutex);

}

wait(x-sem);

x-count--;

Реализация операции x.signal():

if (x-count > 0) {

	next-count++;

	signal (x-sem);

	wait (next);

	next-count--;

}

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

Дополнительная операция над монитором, обеспечивающая организацию очереди к условной переменной по приоритетам, - x.wait(с),где c – целочисленный параметр, играющий роль приоритета. При выполнении операции signal первым будет освобожден из очереди процесс с меньшим значением приоритета.

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

Синхронизация в ОС Solaris

Система Solaris предоставляет разнообразные виды блокировщиков для поддержки многозадачности, многопоточности (включая потоки реального времени) и мультипроцессирования. Используются адаптивные мюьтексы (adaptive mutexes) – эффективное средство синхронизации доступа к данным при их обработке короткими сегментами кода. Для более длинных сегментов кода используются условные переменные и блокировщики читателей-писателей (reader-writer locks; rwlocks).Для синхронизации потоков используются "вертушки" (turnstiles) – синхронизирующие примитивы, которые позволяют использовать либо adaptive mutex, либо rwlock.

Синхронизация в Windows 2000

Для защиты доступа к данным на однопроцессорных системах используются маски прерываний. Для многопроцессорных систем используются spinlocks (" вертящиеся замки. В системе реализованы также объекты-диспетчеры, которые могут функционировать как мьютексы и как семафоры. Объекты-диспетчеры генерируют события, семантика которых аналогична семантике условной переменной.

Ключевые термины

Interleaving – одновременное выполнение нескольких машинных команд, работающих с общими данными.

Абстрактный тип данных (АТД) – определение типа данных как совокупности описания его конкретного представления и абстрактных операций над ним.

Адаптивный мюьтекс (adaptive mutex) – эффективное средство синхронизации доступа к данным при их обработке короткими сегментами кода в операционной системе Solaris.

Алгоритм булочной (bakery algorithm) – алгоритм синхронизации процессов (Л. Лампорт), основанный на присвоении каждому процессу уникального номера в очереди (приоритета).

Блокировщик читателей-писателей (reader-writer lock; rwlock) – средство синхронизации в ОС Solaris для поддержки схем синхронизации типа " читатели-писатели ".

"Вертушка" (turnstile) – синхронизирующий примитив в ОС Solaris, который позволяет использовать для синхронизации, при необходимости, либо адаптивный мьютекс, либо блокировщик читателей-писателей.

"Вертящийся замок" (spinlock) - средство синхронизации в ОС Windows 2000, используемое в многопроцессорных системах.

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

жуж - В системе "Эльбрус": "жужжать" на процессоре; Специализированная операция (для системных процессов) ожидания на закрытом семафоре без прерываний; занятие процессора, пока семафор не будет открыт операцией открыть(S).

Конкуренция за общие данные (race condition) - ситуация, при которой взаимодействующие процессы могут параллельно (одновременно) обращаться к общим данным без какой-либо синхронизации.

Критическая область (critical region) – высокоуровневая конструкция для синхронизации, основанная на описаниях разделяемых (shared) ресурсов и конструкции region, обеспечивающей взаимное исключение при работе с общим ресурсом.

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

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

Общий семафор (counting semaphore) - целая переменная S, над которой определены две атомарных семафорных операции wait (S) и signal (S).

Объект-диспетчер (dispatcher object) – средство синхронизации в ОС Windows 2000, которое может функционировать как мьютекс и как семафор; генерирует события, семантика которых аналогична семантике условной переменной.

Ограниченный буфер (bounded buffer):схема взаимодействия процессов, при которой имеются процесс-производитель и процесс-потребитель, взаимодействующие с помощью циклического буфера ограниченной длины; производитель генерирует элементы информации и записывает в буфер; потребитель использует информационные элементы из буфера и удаляет их.

Семафорный бит – В вычислительных комплексах Burroughs 5000 и "Эльбрус": особый бит слова, над которым выполняется команда семафорного считывания; по определенному значению бита (например, 1) происходит прерывание.

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

Условная переменная (condition variable) – часть конструкции монитор:Переменная с описанием вида condition x, доступ к которой возможен только операциями wait и signal ; операция x.wait() задерживает выполнивший ее процесс до момента, пока другой процесс не выполнит операцию x.signal().

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

Краткие итоги

Синхронизация процессов – актуальная задача, исследование которой началось с работ Э. Дейкстры в 1960-х гг. Совместный доступ процессов к общим данным (race condition) может привести к нарушению их целостности, поэтому необходима их синхронизация.

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

В общем случае, если имеется n процессов, у каждого из них есть своя критическая секция – фрагмент кода, работающий с общим ресурсом, и необходимо обеспечить взаимное исключение исполнения критических секций. Для решения проблемы критических секций необходимо выполнение трех условий: взаимное исключение, прогресс (выбор системой за конечное время одного из процессов для исполнения критической секции), ограниченное ожидание (ограничение на время ожидания от момента заявки процесса на исполнение критической секции до момента ее удовлетворения).

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

Алгоритм булочной – еще один подход к решению проблемы критических секций. Использует присвоение уникального номера в очереди (приоритета) каждому процессу.

Алгоритмы синхронизации более просты, если они используют аппаратную поддержку атомарных операций – проверка и установка (test-and-set) и перестановка значений двух переменных (swap). Приведена реализация синхронизации процессов с использованием обеих операций.

Общий семафор (по Э. Дейкстре) – синхронизирующий примитив: целая переменная, над которой определены семафорные операции wait и signal. Приведено решение проблемы критических секций с помощью семафоров. Семафор реализуется в виде структуры из двух полей: счетчик и ссылка на список ждущих процессов. Для реализации операций над семафором достаточно двух примитивов: block – блокировка текущего процесса, wakeup(P) – разблокировка процесса P.

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

Используются две разновидности семафоров – общие (с целым значением) и двоичные (значениями могут быть только 0 и 1). Общий семафор может быть реализован с помощью двоичных семафоров.

В системе "Эльбрус" имеется вариант операции ожидания жуж (жужжать на процессоре) для системных процессов – без прерывания, с удержанием процессора до момента разблокировки.

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

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

Монитор (по Ч. Хоару) – высокоуровневая конструкция для синхронизации: многовходовый модуль, содержащий описание общих данных и операций над ними в виде процедур. Обеспечивается взаимное исключение исполнения мониторных операций. Монитор может также содержать условные переменные, для которых определены операции wait и signal для организации дополнительных очередей процессов. Рассмотрено решение задачи "обедающие философы" с использованием монитора. Описана реализация монитора и условных переменных с помощью семафоров.

В системе Solaris для синхронизации используются адаптивные мьютексы, блокировщики читателей-писателей, условные переменные и "вертушки" (turnstiles), позволяющие сочетать применение адаптивных мьютексов и блокировщиков читателей-писателей.

В системе Windows 2000 для синхронизации используются вертящиеся замки (spinlocks) и объекты-диспетчеры, генерирующие события (аналогичные условным переменным).

Набор для практики

Вопросы

Упражнения

Темы для курсовых работ, рефератов, эссе