Лекции по операционным системам (1114738), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

1. Схема работы пользователя с ОС Unix.

2.3Планирование

2.4Взаимодействие процессов

2.4.1Разделяемые ресурсы и синхронизация доступа к ним

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

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

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

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

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

Рассмотрим пример (Рис. 83.). Пусть имеется некоторая общая переменная (разделяемый ресурс) in и два процесса, которые работают с этой переменной. Пусть в некоторый момент времени процесс A присвоил переменной in значение X. Затем в некоторый момент процесс B ввел значение Y этой же переменной in. Далее оба процесса читают эту переменную, и в обоих случаях процессы прочтут значение Y. Возможно, что процессы могли совершить эти действия в ином порядке (поскольку по-другому могли быть обработаны на процессоре), и результат был бы отличным от этого. Соответственно, подобная ситуация, когда процессы конкурируют за разделяемый ресурс, называются гонкой процессов (race conditions).

1. Гонка процессов.

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

Блокировка — это ситуация, когда доступ к разделяемому ресурсу одного из взаимодействующих процессов не обеспечивается за счет активности более приоритетных процессов. Отметим следующее. Рассмотрим некоторую модель доступа к разделяемому ресурсу, построенную на приоритетах, когда более приоритетный запрос на обращение к ресурсу будет обработан быстрее, чем менее приоритетный. И пусть в этой модели работают два процесса, у которого приоритеты доступа к разделяемому ресурсу разные. Тогда, если более приоритетный процесс будет «часто» выдавать запросы на обращение к ресурсу, может возникнуть ситуация, когда второй процесс будет «вечно» (или достаточно долго) ожидать обработки каждого своего запроса, т.е. этот менее приоритетный процесс будет блокирован.

Тупик, или deadlock, — это ситуация «клинчевая», когда из-за некорректной организации доступа к разделяемым ресурсам происходит взаимоблокировка. Рассмотрим пример тупиковой ситуации (Рис. 84.).

1. Пример тупиковой ситуации (deadlock).

Предположим, что есть два процесса A и B, а также пара критических ресурсов. Пускай в некоторый момент времени процесс A вошел в критическую секцию работы с ресурсом 1. Это означает, что доступ любого другого процесса к данному ресурсу будет блокирован. Пусть также в это время процесс B войдет в критическую секцию ресурса 2. И этот ресурс также будет блокирован для доступа другим процессам. Пускай процесс A, не выходя из критической секции ресурса 1, пытается захватить ресурс 2. Но последний уже захвачен процессом B, и процесс A блокируется. Аналогично, пускай процесс B, не освобождая ресурс 2, пытается захватить ресурс 1 и также блокируется. Это пример простейшего тупика. Из него процессы никогда не смогут выйти. Соответственно, решением в данном случае может быть перезапуск системы или уничтожение обоих или одного из процессов.

2.4.2Способы организации взаимного исключения

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

Семафоры Дейкстры — это формальная модель организации доступа, предложенная голландским ученым Дейкстрой, которая основывается на следующей концепции. Имеется специальный тип данных — семафор. Переменная типа семафор может иметь целочисленные значения. Над этими переменными определены следующие операции: down(S) (или P(S)) и up(S) (или V(S)). Оригинальные обозначения P и V, данные Дейкстрой и получившие широкое распространение в литературе, являются сокращениями голландских слов proberen — проверить и verhogen — увеличить.

Операция down(S) проверяет значение семафора S, и если оно больше нуля, то уменьшает его на 1. Если же это не так, процесс блокируется, причем связанная с заблокированным процессом операция down считается незавершенной.

Операция up(S) увеличивает значение семафора на 1. При этом, если в системе присутствуют процессы, блокированные ранее при выполнении down на этом семафоре, один из них разблокировывается и завершает выполнение операции down, т.е. вновь уменьшает значение семафора. Выбор процесса никак не оговаривается.

При этом операции up и down являются атомарными (неделимыми), т.е. их выполнение не может быть прервано прерыванием.

Для иллюстрации рассмотренного механизма приведем следующий пример. Рассмотрим некий универсам. Вход в торговый зал магазина возможен лишь для посетителей, имеющих тележку. В магазине имеется N тележек. Итак, в начальный момент (когда магазин открывается) имеется N свободных тележек. Каждый очередной посетитель берет тележку и проходит в зал. Так продолжается, пока не появится N+1 посетитель, которому тележки уже не хватает. Он войти не может и ждет свободной тележки перед входом в торговый зал. Если приходят еще покупатели, то они также ожидают свободной тележки. Поскольку рассматриваемый формализм, как упоминалось выше, ничего не говорит о выборе очередного заблокированного процесса, то будем считать, что прибывающие в магазин покупатели не становятся в очередь, а стоят в неком «беспорядке» (толпой). Как только один из покупателей с тележкой покидает торговый зал, происходит операция up: появляется одна свободная тележка. Эту тележку берет один из ожидающих посетителей и проходит в торговый зал. Это означает, что один из заблокированных клиентов разблокировался и продолжил работу, остальные же продолжают ждать в заблокированном состоянии.

Если тележка была бы одна, то это было бы иллюстрацией организации доступа в режиме взаимного исключения, т.е. в любой момент времени в торговом зале может оказаться лишь один покупатель. Это пример т.н. двоичного семафора — семафора, максимальное значение которого равно 1. Этот тип семафоров обеспечивает взаимное исключение.

В приведенном ниже (Рис. 85.) примере двоичного семафора рассмотрены два процесса, каждый из которых имеет критическую секцию. За счет использования двоичного семафора обеспечивается безопасная работа в критической секции любого из процессов, т.е. если один из них вошел в критическую секцию, то гарантируется, что второй при попытке также войти в свою критическую секцию будет блокирован до тех пор, пока первый не покинет оную.

1. Пример двоичного семафора.

Заметим, что требование атомарности операций down и up накладывает ограничения на реализацию семафоров Дейкстры, и зачастую это сложная задача. Существуют программные реализации, но в них атомарность не всегда присутствует.

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

• данные монитора доступны только через процедуры и функции этого монитора;

• считается, что процесс занимает (или входит) монитор тогда, когда он начинает использовать одну из процедур или функций монитора;

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

Иллюстрацией монитора может служить кабина таксофонного аппарата.

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

Механизм передачи сообщений основан на двух функциональных примитивах: send (отправить сообщение) и receive (принять сообщение). Данные операции можно разделить по трем критериям: синхронизация, адресация и длина сообщения.

Синхронизация. Операции посылки/приема сообщений могут быть блокирующими и неблокирующими. Рассмотрим различные комбинации.

Блокирующий send: процесс-отправитель будет блокирован до тех пор, пока посланное им сообщение не будет получено.

Блокирующий receive: процесс-получатель будет блокирован до тех пор, пока не будет получено соответствующее сообщение.

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

Итак, комбинируя различные операции send и receive, мы получаем 4 различных модели синхронизации. Отметим одно важное свойство аппарата сообщений, заключающееся в том, что в нем явно совмещены средства передачи информации и синхронизации, таким образом, механизм передачи сообщений можно использовать для достижения двух целей.

Адресация может быть прямой, когда указывается конкретный адрес получателя и/или отправителя (например, когда получатель ожидает сообщения от конкретного отправителя, игнорируя сообщения других отправителей), или косвенной. В случае косвенной адресации не указывается адрес получателя при отправке или отправителя при получении; сообщение «бросается» в некоторый общий пул, в котором могут быть реализованы различные стратегии доступа (FIFO, LIFO и т.д.). Этим пулом может выступать очередь сообщений (FIFO) или почтовый ящик, в котором может быть реализована любая модель доступа.

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

Иллюстрацией данной модели может выступать модель MPI — интерфейсы передачи сообщений, на основе которых строятся почти все кластерные системы, т.е. системы с распределенной ОП, но точно также MPI может работать в системах с общей памятью.

2.4.3Классические задачи синхронизации процессов

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

Характеристики

Список файлов лекций