8.1.1. Взаимные исключения

В листинге 8.2 показано простое решение задачи взаимоисключений с использованием семафора S. Пусть у нас имеется N процессов, идентифицируемых массивом P(i). В каждом из процессов перед входом в критический раздел выполняется вызов Wait(S). Если значение S становится отрицательным, процесс приостанавливается. Если же значение S равно 1, оно уменьшается до нуля и процесс немедленно входит в критический раздел. Поскольку S больше не является положительным, ни один другой процесс не может войти в критический раздел.

Листинг 8.2. Взаимоисключения с использованием семафоров

/* Программа взаимного исключения */

const int n = /* Количество процессов */;

semaphore s = 1;

void P(int i)

{

while(true)

{

wait(s);

/* Критический раздел */

signal(s);

/* Остальной код */

}

}

void main()

{

perbegin(P(1),P(2),…,P(n));

}

Семафор инициализируется значением 1. Следовательно, первый процесс, выполняющий инструкцию Wait, сможет немедленно попасть в критический раздел, устанавливая значение семафора, равным 0. Любой другой процесс при попытке войти в критический раздел обнаружит, что он занят. Соответственно, произойдет блокировка процесса, а значение семафора будет уменьшено до –1. Пытаться войти в критический раздел может любое количество процессов; каждая неуспешная попытка уменьшает значение семафора.

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

8.1.2. Задача “производителя-потребителя” ("писатель-читатель")

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

Блокировка:	Деблокирование:
Производитель: вставка в полный буфер	Производитель: вставка элемента в буфер
Потребитель: удаление из пустого буфера	Потребитель: удаление элемента из буфера

Функции производителя и потребителя при этом могут быть записаны следующим образом (in и out инициализированы значением 0):

Производитель: (AddToBuffer()) Потребитель: (GetFromBuffer())

While (true) While (true)

{ {

/* Производство элемента v /; while (in == out); /* ждать */

while ((in+1) % n == out); /*ждать*/ w = b[out];

b[in] = v; out = (out+1) % n;

in = (in+1) % n; /* потребление элемента w */

} }

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

Листинг 8.4. Решение задачи производитель-потребитель с ограниченным циклическим буфером

const int SizeBuffer = /* Размер буфера */;

semafore s = 1;

semafore n = 0; /* число занятых буферов */

semafore e = SizeBuffer; /* число пустых буферов */

void Writer ()

{

while(1)

{

PrepareNextRecord(); /* подготовка новой записи */

Wait(e); /* Уменьшить число свободных буферов, если они есть */

/* в противном случае - ждать, пока они освободятся */

Wait(s); /* Вход в критическую секцию */

AddToBuffer(); /* Добавить новую запись в буфер */

Signal(s); /* Выход из критической секции */

Signal(n); /* Увеличить число занятых буферов */

}

}

void Reader ()

{

while(1)

{

Wait(n); /* Уменьшить число занятых буферов, если они есть */

/* в противном случае ждать, пока они появятся */

Wait(s); /* Вход в критическую секцию */

GetFromBuffer(); /* Взять запись из буфера */

Signal(s); /* Выход из критической секции */

Signal(e); /* Увеличить число свободных буферов */

ProcessRecord(); /* Обработать запись */

}

}

void main()

{

parbegin (Writer, Reader);

}

Предположим теперь, что при переписывании этой программы произошла ошибка: программист переставил операции Signal(s) и Signal(n) в процедуре Writer (). Это приведет к тому, что операция Signal(n) будет выполняться в критическом разделе производителя без прерывания потребителя. Повлияет ли это на выполнение программы? Нет, потребитель в любом случае должен ожидать установки обоих семафоров перед продолжением работы.

Теперь предположим, что переставлены операции Wait(n) и Wait(s) в процедуре Reader (). Это приведет к фатальным последствиям. Если потребитель войдет в критический раздел, когда буфер пуст (n = 0), то производитель не сможет добавить данные в буфер и система окажется в состоянии взаимной блокировки. Это хороший пример тонкости работы с семафорами и сложности корректной разработки параллельно работающих процессов.

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

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

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

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