Процессам часто нужно взаимодействовать друг с другом, например, один процесс может пере-давать данные другому процессу, или несколько процессов могут обрабатывать данные из общего файла. Во всех этих случаях возникает проблема синхронизации процессов, которая может решаться приостановкой и активизацией процессов, организацией очередей, блокированием и освобождением ресурсов. Одной из важных характеристик ОС является возможность одновременного выполнения взаи-мосвязанных процессов. Надо сказать, что в распараллеливаниии процессов состоит один из основ-ных резервов повышения быстродействия и эффективности ЭВМ. Процессы называются параллельными, если они существуют одновременно. Одновременно вы-полняющиеся и не взаимосвязанные процессы называются параллельными процессами. Одновремен-но выполняющиеся, взаимодействующие и совместно использующие общие ресурсы, называются асинхронными параллельными процессами. При управлении асинхронными параллельными процессами возникает две проблемы: 1. проблема синхронизации параллельных процессов; 2.проблема взаимной блокировки – тупика (“смертельное объятие”-dead lock) Пример 1. Писатели – читатели. Пренебрежение вопросами синхронизации процессов, выполняющихся в режиме мультипро-граммирования, может привести к их неправильной работе или даже к краху системы. Рассмотрим, например (рисунок.1), программу печати сообщений (принт-сервер). Эта программа печатает по оче-реди все сообщения, которые последовательно в порядке поступления записывают в специальный общедоступный файл другие программы. Особая переменная N, также доступная всем процессам-клиентам, содержит номер первого свободного для записи сообщения. Процессы-клиенты читают эту переменную, записывают в соответствующую позицию сообщение и наращивают значение N на единицу. Предположим, что в некоторый момент процесс R решил распечатать сообщение, для этого он прочитал значение переменной N, значение которой для определенности предположим равным 4. Процесс запомнил это значение, но поместить сообщение не успел, так как его выполнение было прервано (например, вследствие исчерпания кванта). Очередной процесс S, желающий распечатать сообщение, прочитал то же самое значение переменной N, поместил в четвертую позицию свое сооб-щение и нарастил значение переменной на единицу. Когда в очередной раз управление будет переда-но процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет сообщение также в позицию 4, поверх сообщения процесса S
Особенности взаимодействия: 1. Процессы автономны, но должны кооперироваться во время выполнения работы - (пи-сать - читать). Проблема: очередь пустая / буфер заполнен. 2. Для правильной работы они должны быть синхронизированы друг с другом. На участке работ с общим ресурсом процессы должны взаимоисключать друг друга (блокировать друг друга), иначе результат может быть неверным и непредсказуемым. В связи с рассмотренной ситуацией важным понятием процессов является понятие "критическая секция" программы. Критическая секция - это часть программы, в которой осуществляется доступ к разделяемым данным синхронизации. Чтобы исключить ситуацию, когда два или более процессов обрабатывают разделяемые данные, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением. Пример 2. Распределение ресурсов между параллельными процессами (рисунок 2) Простая тупиковая ситуация возникает для группы общих ресурсов (тупик - "смертельное объя-тие"). Программа 1, захватив ресурс 1, для продолжения работы нуждается в ресурсе 2, который за-хватила и удерживает программа 2, для завершения работы которой, в свою очередь, требуется ресурс 1, удерживаемый программой 1.
Таким образом, подсистема УП aсинхронными параллельными процессами должна обеспечить решение двух следующих задач: 1.Синхронизацию и кооперирование процессов. 2.Предотвращение взаимной блокировки процессов по ресурсам. Задача синхронизации АПП в ОС решается методом взаимоисключения процессов при выпол-нении их на критических участках. Для взаимоисключения процессов на критических участках существует три средства: 1.Примитивы взаимоисключения. 2.Семафоры. 3.Мониторы. Примитивы взаимоисключения используются для обработки критических участков програм-мы и представляют собой совокупность логической переменной I, представляющей общий ресурс и принимающей два значения: 0 - свободен, 1 - занят, а также команды (проверить и установить) - TS (TS,I,B01). а) читает логическую переменную I б) проверяет ее значение в) устанавливает новое значение I. Следует заметить, что операция проверки и установки блокирующей переменной должна быть неделимой. Поясним это. Пусть в результате проверки переменной процесс определил, что ресурс свободен, но сразу после этого, не успев установить переменную в 0, был прерван. За время его при-остановки другой процесс занял ресурс, вошел в свою критическую секцию, но также был прерван, не завершив работы с разделяемым ресурсом. Когда управление было возвращено первому процессу, он, считая ресурс свободным, установил признак занятости и начал выполнять свою критическую секцию. Таким образом, был нарушен принцип взаимного исключения, что потенциально может привести к не желаемым последствиям. На примере ниже перед входом в критическую секцию процесс проверяет, свободен ли ресурс. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной I уста-навливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной I снова устанавливается равным 0.
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(); /* Обработать запись */ } } Достоинства: 1.Пассивное ожидание (постановка в очередь и автоматическая выдача ресурсов) 2.Возможность управления группой однородных ресурсов.
Недостатки: Неправильное, либо умышленное использование операций на семафоре допускает нарушение работоспособности параллельных систем. Действительно, если в рассмотренном примере переставить местами операции P(e) и P(b) в про-грамме "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно забло-кировать друг друга. Так, пусть "писатель" первым войдет в критическую секцию и обнаружит отсут-ствие свободных буферов; он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писатели". Монитор - это механизм организации параллелизма высокого уровня, который содержит мно-жество переменных состояний, очередей и множество процедур, необходимых для реализации дина-мического распределения и доступа к общим ресурсам.
Монитор представляет собой централизованный семафор или совокупность семафоров, спря-танных от пользователей процессов в одном системном процессе, и потому, недоступным пользова-тельским программам, которые не могут их нарушить. Процессы, которые использует монитор для синхронизации, не имеют прямого доступа к переменным состояния, и могут воспользоваться ресур-сами только путем вызова процедур монитора (или макрокоманд). Монитор при создании автоматически инициирует число ресурсов и включает процедуры, по-зволяющие блокировать и активизировать процессы. Вход в монитор находится под жестким контро-лем системы и только через монитор осуществляется взаимоисключение процессов. Если процесс обращается к монитору и требуемый ресурс занят, то процесс переводится в состояние ожидания. Со временем некоторый процесс обращается к монитору для возвращения ресурса и монитор оповещает процесс о том, что может выделить ресурс и покинуть очередь. Режимом ожидания управляет сам монитор, который для гарантии получения ресурса процессом повышает приоритеты процессов кри-тических областей. Достоинства монитора: 1. Логические возможности не меньше, чем у семафоров. 2. Упрощение написания параллельных программ. Достаточно знать процедуры организации па-раллельных вычислений. 3. Повышение надежности параллельных систем, так как полностью защищает управление ре-сурсом. 4. Обеспечение гарантированного получения ресурса.
