УПРАВЛЕНИЕ АСИНХРОННЫМИ ПАРАЛЛЕЛЬНЫМИ
ПРОЦЕССАМИ
Процессам часто нужно взаимодействовать друг с другом, например, один процесс может передавать данные другому процессу, или несколько процессов могут обрабатывать данные из общего файла. Во всех этих случаях возникает проблема синхронизации процессов, которая может решаться приостановкой и активизацией процессов, организацией очередей, блокированием и освобождением ресурсов.
Одной из важных характеристик ОС является возможность одновременного выполнения взаимосвязанных процессов. Надо сказать, что в распараллеливании процессов состоит один из основных резервов повышения быстродействия и производительности ЭВМ.
Процессы называются параллельными, если они существуют одновременно. Одновременно выполняющиеся и не взаимосвязанные процессы называются параллельными процессами. Одновременно выполняющиеся, взаимодействующие и совместно использующие общие ресурсы, называются асинхронными параллельными процессами.
При управлении асинхронными параллельными процессами возникает две проблемы:
1. Проблема синхронизации параллельных процессов;
2.Проблема взаимной блокировки – тупика («смертельное объятие»-deadlock)
Пример 1. Писатели – читатели.
Пренебрежение вопросами синхронизации процессов, выполняющихся в режиме мультипрограммирования, может привести к их неправильной работе или даже к краху системы. Рассмотрим, например, программу печати сообщений (принт-сервер) (рис.4.1). Эта программа печатает по очереди все сообщения, которые последовательно в порядке поступления записывают в специальный общедоступный файл другие программы. Особая переменная N, также доступная всем процессам-клиентам, содержит номер первого свободного для записи сообщения. Процессы-клиенты читают эту переменную, записывают в соответствующую позицию сообщение и наращивают значение N на единицу.
Предположим, что в некоторый момент процесс R решил распечатать сообщение, для этого он прочитал значение переменной N (для определенности сделаем его равным 4). Процесс запомнил это значение, но поместить сообщение не успел, так как его выполнение было прервано (например, вследствие исчерпания кванта).
Очередной процесс S, желающий распечатать сообщение, прочитал то же самое значение переменной N, поместил в четвертую позицию свое сообщение и нарастил значение переменной на единицу. Когда в очередной раз управление будет передано процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет сообщение также в позицию 4, поверх сообщения процесса S.
Таким образом, процесс S никогда не увидит свое сообщение распечатанным.
Особенности взаимодействия:
1.
Процессы автономны, но должны кооперироваться во время выполнения работы (писать - читать). Проблема: очередь пустая / буфер заполнен.
2. Для правильной работы процессы должны быть синхронизированы друг с другом. На участке работ с общим ресурсом онидолжны взаимоисключать друг друга (блокировать друг друга), иначе результат может быть неверным и непредсказуемым.
Рис. 4.1. Кооперация программ при работе с общим ресурсом.
В связи с рассмотренной ситуацией важным понятием процессов является понятие "критическая секция" программы. Критическая секция - это часть программы, в которой осуществляется доступ к разделяемым данным синхронизации. Чтобы исключить ситуацию, когда два или более процессов обрабатывают разделяемые данные, необходимо сделать так, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением.
Пример 2. Распределение ресурсов между параллельными процессами
Простая тупиковая ситуация возникает для группы общих ресурсов (тупик - "смертельное объятие"). Программа 1, захватив ресурс 1, для продолжения работы нуждается в ресурсе 2, который захватила и удерживает программа 2, для завершения работы которой, в свою очередь, требуется ресурс 1, удерживаемый программой 1 (рис.4.2).
Рис.4.2. Тупиковая ситуация
Таким образом, подсистема УП асинхронными параллельными процессами должна обеспечить решение двух следующих задач:
1.Синхронизацию и кооперирование процессов.
2. Предотвращение взаимной блокировки процессов по ресурсам.
Задача синхронизации АПП в ОС решается методом взаимоисключения процессов при выполнении их на критических участках. Для взаимоисключения процессов на критических участках используется три средства:
1.Примитивы взаимоисключения.
2.Семафоры.
3.Мониторы.
Примитивы взаимоисключения используются для обработки критических участков программы и определяются совокупностью логической переменной I, представляющей общий ресурс и принимающей два значения: 0 - свободен, 1 - занят, и командой TS, TS,I,B01
(проверить и установить).
а) читает логическую переменную I;
б) проверяет ее значение;
в) устанавливает новое значение I.
Следует заметить, что операция проверки и установки блокирующей переменной должна быть неделимой. Поясним это. Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его приостановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом, был нарушен принцип взаимного исключения, что потенциально может привести к нежелаемым последствиям.
Ниже в примере 3 перед входом в критическую секцию процесс проверяет, свободен ли ресурс. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной I устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной I снова устанавливается равным 0.
Пример 3.
A. B.
Do while (TS I,B’1’) Do while (TS I,B’1’)
END END
<критический участок> <критический участок>
TS I,B’0’ TS I,B’0’
Обеспечивается исключительное право доступа к разделяемым ресурсам. При этом другим процессам приходится ожидать освобождения ресурса. Естественно, что процессы должны быстрее проходить критические участки и не должны блокироваться системой. Примитив взаимоисключения - самое простое решение.
Недостатки:
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).
Над переменной определено три операции:
- инициализация ресурса I(S) - задает число доступных ресурсов;
- P(S) - захват ресурса;
- V(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(); /* Обработать запись */
}
}
Общая схема использования семафоров на критических участках для двух процессов приведена на рис.4.3.
Достоинства использования операций на семафоре:
1.Пассивное ожидание (постановка в очередь и автоматическая выдача ресурсов)
2.Возможность управления группой однородных ресурсов.
Рис.4.3. Критические участки с использованием операций на семафоре
Недостатки:
Неправильное либо умышленное использование операций на семафоре приводит к нарушению работоспособности параллельных систем.
Действительно, если в рассмотренном примере переставить местами операции P(e) и P(b) в программе "писатель", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Так, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов; он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писатель".
Монитор - это механизм организации параллелизма высокого уровня, который содержит множество переменных состояний, очередей и множество процедур, необходимых для реализации динамического распределения и доступа к общим ресурсам.
Монитор представляет собой централизованный семафор или совокупность семафоров, спрятанных от пользователей процессов в одном системном процессе, и потому, недоступным пользовательским программам, которые не могут их нарушить. Процессы, которые использует монитор для синхронизации, не имеют прямого доступа к переменным состояния, и могут воспользоваться ресурсами только путем вызова процедур монитора (или макрокоманд).
Монитор при создании автоматически инициирует число ресурсов и включает процедуры, позволяющие блокировать и активизировать процессы. Вход в монитор находится под жестким контролем системы и только через монитор осуществляется взаимоисключение процессов. Если процесс обращается к монитору и требуемый ресурс занят, то процесс переводится в состояние ожидания. Со временем некоторый процесс обращается к монитору для возвращения ресурса и монитор оповещает процесс о том, что может выделить ресурс и покинуть очередь. Режимом ожидания управляет сам монитор, который для гарантии получения ресурса
процессом повышает приоритеты процессов критических областей. На рис.4.4 критический участок программируется в мониторе
Рис. 4.4. Схема использования монитора.
Достоинства монитора:
1. Логические возможности не меньше, чем у семафоров.
2. Упрощение написания параллельных программ. Достаточно знать процедуры организации параллельных вычислений.
3. Повышение надежности параллельных систем, так как полностью защищает управление ресурсом.
4. Обеспечение гарантированного получения ресурса.
Первая рассмотренная нами проблема, возникающая для асинхронных параллельных процессов, работающих с общим ресурсом - это проблема синхронизации процессов.
Вторая проблема - это проблема тупика, возникающая при выполнении асинхронных параллельных процессов, работающих с монопольными ресурсами (взаимоблокировка). Тупиком
называется ситуация, когда процесс ждет наступления события (выделения ресурса), которое никогда не произойдет или может бесконечно откладываться.
Для возникновения тупика необходимо наличие 4-х условий:
1.Взаимоисключение, когда процессы требуют монопольного предоставления ресурса.
2.Ожидание дополнительного ресурса, когда процессы удерживают ресурсы и требуют дополнительных ресурсов.
3.Неперераспределяемости ресурсов, когда ресурсы нельзя отобрать у процессов до завершения их работы.
4.Кругового ожидания, когда существует кольцо процессов, удерживающих ресурсы друг друга.
Для решения проблемы тупиков должны выполняться определенные задачи:
1.Предотвращение тупиков.
Путем исключения одного из необходимых условий возникновения тупиков, кроме условий взаимоисключения (это объективное условие).
– условие ожидания дополнительных ресурсов можно нарушить, если потребовать, чтобы процессы запрашивали сразу все ресурсы. (Недостаток - снижение уровня мультипрограммирования и нерациональное использование ресурсов);
- условие неперераспределяемости можно нарушить, если потребовать, чтобы процесс, который не получил дополнительных ресурсов, сам освобождал удерживаемые;
- условие кругового ожидания можно предотвратить, если процессы запрашивают ресурсы в заранее определенном порядке, то есть ресурсы имеют уникальные упорядоченные номера, которые распределяются в соответствии с некоторым планом (планирование распределения ресурсов).
Путем обхода
тупиков. Это решение основывается на том, что все процессы заранее указывают максимальное число требуемых ресурсов, и ОС контролирует возможность их совместного удовлетворения.
2.Обнаружение тупиков, когда возникающие тупики анализируются и прогнозируются с выдачей соответствующей информации операторам.
Возможные тупики анализируются по графам распределения ресурсов. Существуют формальные, программно-реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки.
3.Восстановление после тупиков осуществляется путем вывода из системы одного или N процессов, вовлеченных в тупик и почти всегда с потерей полученных результатов работы. Не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них, при этом освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть некоторые процессы в область свопинга, можно совершить "откат" некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика.
В настоящее время проблема тупика является критическим фактором по следующим причинам:
- широкое распространение получают мультипроцессорные и параллельные вычисления;
- в системах выполняется преимущественно динамическое распределение ресурсов;
- тенденция рассмотрения данных как ресурса приводит к возрастанию числа управляемых ресурсов.
