Семафоры

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

Первой большой работой, посвященной вопросам параллельных вычислений, стала монография Дейкстры [DIJK65], который рассматривал разработку операционной системы как построение множества сотрудничающих последовательных процессов и создание эффективных и надежных механизмов поддержки этого сотрудничества. Эти же механизмы легко применяются и пользовательскими процессами — если процессор и операционная система делают их общедоступными.
Фундаментальный принцип заключается в том, что два или большее количество процессов могут сотрудничать посредством простых сигналов, так что в определенном месте процесс может приостановить работу до тех пор, пока не дождется соответствующего сигнала. Требования кооперации любой степени сложности могут быть удовлетворены соответствующей структурой сигналов. Для сигнализации используются специальные переменные, называющиеся семафорами. Для передачи сигнала через семафор s процесс выполняет примитив signal (s), а для получения сигнала— примитив wait(s). В последнем случае процесс приостанавливается до тех пор, пока не осуществится передача соответствующего сигнала.2

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

• Семафор может быть инициализирован неотрицательным значением.
• Операция wait уменьшает значение семафора. Если это значение становится отрицательным, процесс, выполняющий операцию wait, блокируется.
• Операция signal увеличивает значение семафора. Если это значение не положительно, то заблокированный операцией wait процесс деблокируется.

Не имеется никаких иных способов получения информации о значении семафора или изменения его значения, кроме перечисленных.

В листинге 5.5 приведено более формальное определение примитивов семафоров. Предполагается, что примитивы wait и signal атомарны, т.е. они не могут быть прерваны, и каждая из подпрограмм может рассматриваться как единый шаг. Более ограниченная версия семафора, известная как бинарный семафор, представлена в листинге 5.6. Бинарный семафор может принимать только значения 0 или 1. В принципе реализация бинарного семафора должна быть более простой задачей; можно также показать, что все задачи, решаемые с применением обычных семафоров, могут быть решены и с использованием лишь бинарных семафоров (см. задачу 5.13).

Листинг 5.5. Определение семафорных примитивов

struct semaphore
{
int count;
queueType queue;
}
void wait(semaphore s)
{
s.count--;
if (s. count < 0)
{
Поместить процесс в  s.queue
Заблокировать процесс
}
}
void signal(semaphore s)
{
s.count++;
if (s.count <= 0)
{
Удалить процесс Р из S.queue
Поместить процесс Р в список активных
}
}
Листинг 5.6. Определение примитивов бинарного семафора
struct binary_semaphore
{
enum { zero, one } value;
queueType queue;
}
void waitB(binary_semaphore s)
{
if (s.value == 1)
s.value = 0;
else
{
Поместить процесс в  s.queue
Заблокировать процесс
}
}
void signalB(binary_semaphore s)
{
if (s.queue.is_empty())
s.value = 1;
else
{
Удалить процесс Р из S.queue
Поместить процесс Р в список активных
}
}

Для хранения процессов, ожидающих как обычные, так и бинарные семафоры, используется очередь. При этом возникает вопрос о порядке извлечения процессов из данной очереди. Наиболее корректный способ — использование принципа "первым вошел — первым вышел" (first-in-first-out — FIFO). При этом первым из очереди освобождается процесс, который был заблокирован дольше других. Семафор, использующий данный метод, называется сильным семафором (strong semaphore). Семафор, порядок извлечения процессов из очереди которого не определен, называется слабым семафором (weak semaphore). На рис. 5.2 (из [DENN84]) приведен пример работы сильного семафора. Здесь процессы А, В и С зависят от результатов работы процесса D. Изначально работает процесс А (®); процессы В, С и D находятся в списке активных процессов, ожидая своей очереди. Значение семафора равно 1, это указывает на то, что один из результатов работы процесса D имеется в наличии. Когда процесс А выполняет инструкцию wait, он тут же получает разрешение на дальнейшую работу и вновь становится в очередь на выполнение в списке активных процессов. Затем приступает к работе процесс В (©), который в конечном счете также выполняет инструкцию wait, в результате чего процесс приостанавливается, давая возможность приступить к работе процессу D (®). Когда процесс D завершает работу над получением нового результата, он выполняет инструкцию signal, которая позволяет процессу В перейти из списка приостановленных процессов в список активных (®). Процесс D присоединяется к списку активных процессов, и к выполнению приступает процесс С (©), но тут же приостанавливается при выполнении инструкции wait. Точно так же приостанавливается и выполнение процессов А и В, давая возможность процессу D приступить к работе (©). После того как получается новый результат процесса D, им выполняется инструкция signal, которая и переводит процесс С из списка приостановленных в список активных. Последующие циклы выполнения процесса D переведут в список активных процессы А и В.

Рис. 5.2. Пример работы механизма семафоров

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

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

В листинге 5.7 показано простое решение задачи взаимоисключений с использованием семафора s (сравните с листингом 5.1). Пусть у нас имеется п процессов, идентифицируемых массивом Р(0- В каждом из процессов перед входом в критический раздел выполняется вызов wait(s). Если значение s становится отрицательным, процесс приостанавливается. Если же значение равно 1, оно уменьшается до нуля и процесс немедленно входит в критический раздел; поскольку s больше не является положительным, ни один другой процесс не может войти в критический раздел.

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

/* Программа взаимного исключения */
const int n = /* Количество процессов */;
semaphore s = 1;
void P(int i)
{
while(true)
{
wait (s);
/* Критический раздел */;
signal(s);
/* Остальной код */;
}
}
void main ()
{
parbegin(Pd), P(2), . . ., P(n) );
}

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

На рис. 5.3 показана возможная последовательность действий трех процессов при использовании технологии взаимоисключений, представленной в листинге 5.7. В этом примере три процесса (А, В, С) обращаются к разделяемому ресурсу, защищенному семафором lock. Процесс А выполняет wait (lock); поскольку в этот момент семафор имеет значение 1, процесс А может немедленно войти в критический раздел и значение семафора становится равным 0. Пока А находится в критическом разделе, и В, и С выполняют операцию wait, после чего в заблокированном состоянии ожидают доступности критического раздела. Когда процесс А покидает критический раздел и выполняет операцию signal (lock), процесс В (являющийся первым в очереди) получает возможность войти в критический раздел.

Примеры:

Задача производителя потребителя

Задача о парикмахерской