Взаимное исключение при взаимодействии процессов

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

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

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

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

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

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

2.2. Задача "Производитель-потребитель"

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

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

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

Попытка процесса-производителя поместить очередное сообщение в область, из которой не было считано предыдущее сообщение процессом-потребителем, должна быть блокирована. Процесс-производитель должен быть либо оповещен о невозможности помещения сообщения, либо переведен в состояние ожидания возможности поместить очередное сообщение через некоторое время в область памяти, по мере ее освобождения. Аналогично должна быть блокирована попытка процесса-потребителя считать сообщение из области в ситуации, когда процесс-производитель не поместил туда очередного сообщения. Возможны также несколько вариантов реакции на данную ситуацию — сообщение о невозможности считывания либо перевод процесса-потребителя в состояние ожидания поступления очередного сообщения. Если используется вариант с ожиданиями изменения состояния обобщенной области для хранения сообщения, необходимо обеспечить перевод ожидающих процессов в состояние готовности всякий раз, когда изменится состояние области. Либо процесс-производитель поместит очередное сообщение в область. Оно теперь может быть считано ожидающим процессом-потребителем. Либо процесс-потребитель считал очередное сообщение из области и обеспечил возможность ожидающему процессу-производителю послать очередное сообщение.[1,140]

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

2.3. Задача "Читатели-писатели"

Задача "Читатели-писатели". Эта задача также имеет много вариантов. Наиболее характерная область использования этой задачи — при построении файловых систем ОС. В отношении некоторой области памяти, являющейся по смыслу критическим ресурсом для параллельных процессов, работающих с ней, выделяется два типа процессов.[1,143]

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

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

2.4. Задача "Обедающие философы"

Задача "Обедающие философы". Хотя и название, и формулировка задачи носят некоторый абстрактный характер, такая задача синхронизации также имеет место при построении систем распределения ресурсов в составе ОС. В рамках этой задачи формулируются требования на синхронизацию работы процессов, которые совместно используют пересекающиеся группы ресурсов.[1,145]

Пример. Пусть имеются три параллельных процесса X, Y, Z и три ресурса: Р1—устройство ввода с перфокарт; Р2—печатающее устройство, РЗ — накопитель на МД. Особенность развития процессов такова, что для пребывания процесса Х в активном состоянии ему требуется выделить одновременно ресурсы ?1 и ?2, для пребывания процесса Y в активном состоянии ему требуется выделить одновременно ресурсы ?2 и РЗ, для пребывания процесса Z в активном состоянии ему требуется выделить одновременно ресурсы РЗ и ?1. Скорости развития процессов произвольны. Переходы из активного в другие состояния происходят в непредсказуемые моменты. Необходимо обеспечить максимально параллельное и правильное развитие процессов. Синхронизация в данном случае заключается в определенном упорядочении действий процессов по захвату ресурсов во избежание возможных блокировок одними процессами других. В данном случае возможны две опасности: возникновение тупиковой ситуации при распределении ресурсов и возникновение ситуации “голодания” в отношении некоторого процесса при распределении ресурса. Для пояснения обратимся к формулировке задачи, изложенной в терминологии, предложенной впервые Э.Дейкстрой.

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

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

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

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

3. Семафоры

Семафор - это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций wait и signal и операции инициализации init. Двоичные семафоры могут принимать только значения 0 и 1. Семафоры со счетчиками могут принимать неотрицательные целые значения.[3,156]

Операция wait(s) над семафором s состоит в следующем: если s > 0 то s:=s-1 иначе (ожидать на s), а операция signal(s) заключается в том, что: если (имеются процессы, которые ожидают на s) то (разрешить одному из них продолжить работу) иначе s:=s+1

Операции являются неделимыми. Критические участки процессов обрамляются операциями wait(s) и signal(s). Если одновременно несколько процессов попытаются выполнить операцию wait(s), то это будет разрешено только одному из них, а остальным придется ждать.

Семафоры со счетчиками используются, если некоторые ресурс выделяется из множества идентичных ресурсов. При инициализации такого семафора в его счетчике указывается число элементов множества. Каждая операция wait(s) уменьшает значения счетчика семафора s на 1, показывая, что некоторому процессу выделен один ресурс из множества. Каждая операция signal(s) увеличивает значение счетчика на 1, показывая, что процесс возвратил ресурс во множество. Если операция wait(s) выполняется, когда в счетчике содержится нуль (больше нет ресурсов), то соответствующий процесс ожидает, пока во множество не будет возвращен освободившийся ресурс, то есть пока не будет выполнена операция signal.

4. Реализация приложения с использованием взаимного исключения.

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

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

- Любое число читателей могут одновременно читать файл.

- Записывать информацию в файл в определенный момент времени может только один писатель.

- Когда писатель записывает данные в файл, ни один читатель не может его читать.

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

Далее будет рассмотрено решение поставленной задачи.

4.2. Программная реализация

В листинге 1 приведено решение задачи с использованием семафоров для варианта, в котором имеются один читатель и один писатель (решение не требует изменений, если имеется много читателей и писателей).

Процесс писателя очень прост. Для обеспечения взаимного исключения используется семафор wsem. Когда один писатель записывает данные, ни другие писатели, ни читатели не могут получить к ним доступ. Процесс читателя также использует семафор wsem для обеспечения взаимоисключений. Однако чтобы обеспечить возможность одновременной работы многих читателей, состояние семафора проверяет только читатель, входящий в критический раздел, в котором нет других читателей. Если в критическом разделе уже находится хоть один читатель, то другой читатель приступает к работе, не ожидая семафора wsem. Для отслеживания количества читателей в критическом разделе используется глобальная переменная rcount, а для гарантии корректного ее обновления — семафор х.

Рисунок 3. Скриншот работающего приложени

На рисунке 3 представленна реализация решения задачи читатели-писатели. Код данной программы находится в листинге 2 (см.приложение).

Заключение

В ходе выполнения данной курсовой работы были изучены основные задачи синхронизации, такие как: взаимное исключение,  производители-потребители, читатели-писатели. Также была реализована задача с использованием «взаимного исключения». Т.к. перечисленное выше является задачами данной работы, то можно с уверенность сказать, что цель достигнута.