Модуль 4. Управление асинхронными параллельными процессами


Тема 6. Синхронизация и кооперация процессов

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

Одной из важных характеристик ОС является возможность одновременного выполнения взаимосвязанных процессов. Надо сказать, что в распараллеливаниии процессов состоит один из основных резервов повышения быстродействия и эффективности ЭВМ.

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

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

1. проблема синхронизации параллельных процессов;

2.проблема взаимной блокировки – тупика (“смертельное объятие”-dead lock)

Пример 1. Писатели – читатели.

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

Image49.gif (8366 bytes)

Рисунок 1. Кооперация программ при работе с общим ресурсом.

Таким образом, процесс S никогда не увидит свой сообщение распечатанным.

Особенности взаимодействия:

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

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

Пример 2. Распределение ресурсов между параллельными процессами (рисунок 2)

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

Image50.gif (7465 bytes)

Рисунок 2. Тупиковая ситуация

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

1.Синхронизацию и кооперирование процессов.

2.Предотвращение взаимной блокировки процессов по ресурсам.

Задача синхронизации АПП в ОС решается методом взаимоисключения процессов при выполнении их на критических участках. Для взаимоисключения процессов на критических участках существует три средства:

1.Примитивы взаимоисключения.

2.Семафоры.

3.Мониторы.

Примитивы взаимоисключения используются для обработки критических участков программы и представляют собой совокупность логической переменной I, представляющей общий ресурс и принимающей два значения: 0 - свободен, 1 - занят, а также команды (проверить и установить) - TS (TS,I,B01).

а) читает логическую переменную I

б) проверяет ее значение

в) устанавливает новое значение I.

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

На примере ниже перед входом в критическую секцию процесс проверяет, свободен ли ресурс. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной I устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной I снова устанавливается равным 0.

A. B.

Do while (TS I,B’1’) Do while (TS I,B’1’)

END END

<критический участок> <критический участок>

TS I,B0’ TS I,B0’

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

Недостатки:

  1. Циклический опрос переменной I и бессмысленное расходование времени ЦП.
  2. Не исключено бесконечное ожидание ресурса, хотя вероятность невелика.
  3. Работает с одним ресурсом.

Для устранения расходования времени ЦП может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по - своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(I), здесь I обозначает событие, заключающееся в освобождении ресурса I. Функция WAIT(I) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события I. Процесс, который в это время использует ресурс I, после выхода из критической секции выполняет системную функцию POST(I), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события I, в состояние ГОТОВНОСТЬ

Семафор развивает механизм примитивов и обобщает его. Автор –Дейкстра. Семафор - это целочисленная неотрицательная переменная S – счетчик ресурса, которую можно менять и опрашивать при помощи операций P и V и очередь процессов к ресурсу Q(S). Над переменной определено три операции.

Операция P(S) выполняется следующим образом:

IF S>0 есть ресурс?

THEN S:=S-1 выдать ресурс

ELSE ожидать очереди Q(S)

Операция V(S):

IF Q(S)? 0 очередь не пуста?

THEN вывести процесс из очереди (выдать ресурс)

ELSE S:=S+1 освободить ресурс

Если семафор управляет одним ресурсом, то это двоичный семафор и S принимает значение {0,1}. Если он управляет группой ресурсов, то в переменной S устанавливается число ресурсов. Для работы семафора необходимо один раз инициировать процесс и обрабатывать критические участки операциями P(S) и V(S).

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

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

// Глобальные переменные

#define N 256

int e = N, f = 0, b = 1;

void Writer ()

{

while(1)

{

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

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

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

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

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

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

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

}

}

void Reader ()

{

while(1)

{

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

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

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

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

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

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

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

}

}

Достоинства:

1.Пассивное ожидание (постановка в очередь и автоматическая выдача ресурсов)

2.Возможность управления группой однородных ресурсов.

Image51.gif (3605 bytes)

Рисунок 3.  Критические участки с использованием операций на семафоре

Недостатки:

Неправильное, либо умышленное использование операций на семафоре допускает нарушение работоспособности параллельных систем.

Действительно, если в рассмотренном примере переставить местами операции P(e) и P(b) в программе "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Так, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов; он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писатели".

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

Image52.gif (13710 bytes)

Рисунок 4.  Схема использования монитора. Критический участок программируется в мониторе

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

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

Достоинства монитора:

  1. Логические возможности не меньше, чем у семафоров.
  2. Упрощение написания параллельных программ. Достаточно знать процедуры организации параллельных вычислений.
  3. Повышение надежности параллельных систем, так как полностью защищает управление ресурсом.
  4. Обеспечение гарантированного получения ресурса.