Процессы. Взаимодействия процессов. Семафоры

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

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

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

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

Рассмотрим, например, программу печати файлов (рисунок 2). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записывают в специальный общедоступный файл "заказов" другие программы. Особая переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции файла "заказов". Процессы-клиенты читают эту переменную, записывают в соответствующую позицию файла "заказов" имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT = 4. Процесс запомнил это значение, но поместить имя файла не успел, так как его выполнение было прервано (например, вследствие исчерпания кванта). Очередной процесс S, желающий распечатать файл, прочитал то же самое значение переменной NEXT, поместил в четвертую позицию имя своего файла и нарастил значение переменной на единицу. Когда в очередной раз управление будет передано процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет имя файла также в позицию 4, поверх имени файла процесса S. Таким образом, процесс S никогда не увидит свой файл распечатанным.

Рис. 2

В данном случае разделяемыми данными являются переменная NEXT и файл «заказов», причем в роли критического ресурса выступает переменная NEXT.

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

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

Блокирующая переменная — это двоичная переменная, связанная с разделяемым ресурсом. Она принимает значение 0, если в критической секции, связанной с данным ресурсом находится некоторый процесс и 1, если процесс свободен.

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

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

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

Для решения этой проблемы могут использоваться, например, примитивы sleep и wakeup. Примитив sleep — системный запрос, в результате которого вызывающий процесс блокируется, пока его не запустит другой процесс. Системный запрос wakeup запускает заблокированный процесс.

В 1965 г. Дейкстра предложил обобщающее средство для синхронизации процессов.

Семафор — неотрицательная целочисленная переменная, связанная с критической областью. Над семафором могут выполняться две неделимые операции:

P(S) уменьшает семафор S на 1, если его значение больше нуля. Если S = 0, процесс, вызвавший операцию P(S) переводится в состояние ожидания.

V(S) увеличивает значение семафора на 1. Если S = 0 и с ним связано несколько заблокированных процессов, один из них выбирается и запускается (но при этом S по-прежнему остается равным 0).

В частном случае, если S может принимать только значения 0 и 1, он является блокирующей переменной, а операции P и V представляют собой примитивы sleep и wakeup.

Классический пример использования семафоров — проблема производителя и потребителя. Два процесса используют совместный буфер ограниченного размера. Один процесс может помещать данные в буфер, а второй — забирать их оттуда. Если буфер заполнен, процесс-производитель должен быть заблокирован до тех пор, пока процесс-потребитель не возьмет из буфера данные и не «разбудит» его. Аналогично, если буфер пуст, должен быть заблокирован потребитель в ожидании новых данных.

Для решения задачи (см. пример 1) используются три семафора. Один (EMPTY) используется для подсчета пустых элементов в буфере, а другой (FULL) — для подсчета заполненных элементов. Третий, двоичный семафор, запрещает одновременный доступ производителя и потребителя в критическую область.

 

Пример 1. Решение задачи производителя и потребителя (язык С).

int e = 256 /* размер буфера */, f = 0, b = 1;

// Код производителя

void Writer() {

while (true) {

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

P(EMPTY);

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

P(b); // Вход в критическую секцию

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

V(b); // Выход из критической секции

V(FULL); // Увеличить число занятых эл-в

}

}

// Код потребителя

void Reader () {

while (true) {

P(FULL);

/* Уменьшить число занятых элементов буфера, если они есть, в противном случае ждать, пока они появятся */

P(b); // Вход в критическую секцию                     

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

V(b); // Выход из критической секции

V(EMPTY); // Увеличить число свободных эл-в             

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

}

}

В приведенной программе две процедуры Writer() и Reader() работают параллельно, причем каждая из них осуществляет бесконечный цикл. В начале своего цикла писатель Writer() вырабатывает некоторую порцию информации. Этим занимается процедура PrepareNextRecord(), причем ее назначение может быть любым в зависимости от функциональности программы (например, данные могут быть получены по сети). Затем писатель пытается выполнить операцию P над семафором EMPTY. Ему удастся это сделать только в том случае, если значение семафора положительно. В противном случае процедура писателя блокируется до тех пор, пока писатель, работающий параллельно с ним, не увеличит данный семафор.

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

Процедура читателя тоже представляет собой бесконечный цикл while и работает аналогично. Функция ProcessRecord обрабатывает взятую из буфера порцию информации в соответствии с назначением программы.