Микросхема I8259 (устройство управления прерываниями) для I8086 имеет 8 уровней приоритетов (IRQ0 - IRQ7) (для старших моделей МП - 16).

Можно запретить аппаратные прерывания. Запрет (блокировка) может выполняться для ускорения критической части кода целиком.

Для маскирования аппаратного прерывания необходимо использовать порт 24H. В 1’В’ устанавливаются биты, соответствующие номеру прерывания.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.Семафоры.

3.Мониторы.

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

а) читает логическую переменную 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,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.Возможность управления группой однородных ресурсов.

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

Недостатки:

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

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

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

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