Введение (стр. 6 )

Реализация критических секций с использованием блокирующих переменных имеет существенный недостаток: в течение времени, когда один процесс находится в критической секции, другой процесс, которому требуется тот же ресурс, будет выполнять рутинные действия по опросу блокирующей переменной, бесполезно тратя процессорное время. Для устранения таких ситуаций может быть использован так называемый аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события.

Задачи синхронизации.

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

Задача взаимного исключения – это фундаментальная задача. Любая ОС должна обеспечить тот или иной вариант реализации её решения. Необходимо согласовать работу n>=2 параллельных процессов при использовании некоторого критического ресурса таким образом, чтобы удовлетворить следующим требованиям:

а) одновременно внутри критической области должно находится не более одного процесса;

б) критические области не должны иметь приоритета в отношении друг друга;

в) остановка какого-либо процесса вне его критической области не должна влиять на дальнейшую работу процессов по использованию критического ресурса;

г) решение о вхождении процессов в их критические области при одинаковом времени поступления запросов на такое вхождение и равноприоритетности процессов не откладывается на неопределенный срок, а является конечным во времени;

д) относительные скорости развития процессов неизвестны и произвольны;

е) любой процесс может переходить в любое состояние, отличное от активного, вне пределов своей критической области;

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

Задача «производитель-потребитель».

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

а) выполнять требования задачи взаимного исключения по отношению к критическому ресурсу – обобщенной памяти для хранения сообщений.

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

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

Задача «читатель-писатель».

Эта задача также имеет много вариантов. Более всего используется для построения файловой системы.

Процессы – читатели. Они считывают одновременно информацию из области, если это допускается при работе с конкретным устройством памяти.

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

Задача «обедающие философы».

Синхронизация работы процессов, которые совместно используют пересекающие группы ресурсов.

Например есть три параллельных процесса x, y и z и три ресурса P1 – устройство ввода с клавиатуры, P2 – печать, P3 – накопитель на МД. Особенность процессов такая, что для пребывания x в активном состоянии ему требуется выделить одновременно ресурсы P1 и P2, а для процесса y – P2 и P3, а для z – P3 и P1. Скорости произвольны. Переходы из активного в другие состояния происходят в разные моменты времени. Необходимо обеспечить параллельную работу процессов. Синхронизация заключается в определенном упорядочении действий процессов по захвату ресурсов во избежание возможных блокировок одними процессами других. Возможны тупики при распределении ресурсов или неполучения ресурса длительное время.

Дейкстра описал эту задачу так.

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

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:

V(S) : переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S) : уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную. Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания, в то время как V-операция может при некоторых обстоятельствах активизировать другой процесс, приостановленный операцией P (сравните эти операции с системными функциями WAIT и POST).

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

Аппаратная реализация взаимоисключения.

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

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

При проверке (while) будет получен результат “ложь” и П1 войдёт в свой критический участок. Т. к. для “активный” установлено значение “истина”, П2 в свой критический участок войти не может.

Если П2 уже в своём критическом участке, когда П1хочет войти в него. П1 устанавливает переменной “первому входить нельзя” – “истина”, а затем многократно проверяет значение переменной “активный” по команде testandset, т. к. П2 в своём критическом участке. Это значение остаётся “истина” и переменные “первому входить нельзя” и “активный” (команда testandset) тоже устанавливаются в “истину” и П1 находится в цикле активного ожидания, пока П2 не выйдет из критического участка и не установит “ложь” для переменной “активный”. И в этот момент команда проверки у установки обнаружив это значение переменной “активный” и установив её в значение “истина”, чтобы П2 не мог больше войти в свой критический участок и установит значение “ложь” для переменной “первому входить нельзя”, что позволит чтобы П1 вошёл в свой критический участок.