Курынин Р.В., Машечкин И.В., Терехин А.Н. - Конспект лекций по ОС (1114685), страница 30
Текст из файла (страница 30)
Тогда, если более приоритетныйпроцесс будет «часто» выдавать запросы на обращение к ресурсу, может возникнуть ситуация,когда второй процесс будет «вечно» (или достаточно долго) ожидать обработки каждого своегозапроса, т.е. этот менее приоритетный процесс будет блокирован.Тупик, или deadlock, — это ситуация «клинчевая», когда из-за некорректной организациидоступа к разделяемым ресурсам происходит взаимоблокировка. Рассмотрим пример тупиковойситуации (2.4.1).106Процесс BПроцесс ASTOPSTOPДоступ закрытДоступ закрытРесурс 1Ресурс 2Рис.
84.Пример тупиковой ситуации (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 посетитель, которому тележки уже не хватает. Он войти не107может и ждет свободной тележки перед входом в торговый зал.
Если приходят еще покупатели, тоони также ожидают свободной тележки. Поскольку рассматриваемый формализм, какупоминалось выше, ничего не говорит о выборе очередного заблокированного процесса, то будемсчитать, что прибывающие в магазин покупатели не становятся в очередь, а стоят в неком«беспорядке» (толпой). Как только один из покупателей с тележкой покидает торговый зал,происходит операция up: появляется одна свободная тележка. Эту тележку берет один изожидающих посетителей и проходит в торговый зал.
Это означает, что один из заблокированныхклиентов разблокировался и продолжил работу, остальные же продолжают ждать взаблокированном состоянии.Если тележка была бы одна, то это было бы иллюстрацией организации доступа в режимевзаимного исключения, т.е. в любой момент времени в торговом зале может оказаться лишь одинпокупатель. Это пример т.н. двоичного семафора — семафора, максимальное значение которогоравно 1. Этот тип семафоров обеспечивает взаимное исключение.В приведенном ниже (2.4.2) примере двоичного семафора рассмотрены два процесса,каждый из которых имеет критическую секцию.
За счет использования двоичного семафораобеспечивается безопасная работа в критической секции любого из процессов, т.е. если один изних вошел в критическую секцию, то гарантируется, что второй при попытке также войти в своюкритическую секцию будет блокирован до тех пор, пока первый не покинет оную.процесс 1int semaphore;...down(semaphore);/* критическая секцияпроцесса 1 */...up(semaphore);...процесс 2int semaphore;...down(semaphore);/* критическая секцияпроцесса 2 */...up(semaphore);...Рис. 85.Пример двоичного семафора.Заметим, что требование атомарности операций down и up накладывает ограничения нареализацию семафоров Дейкстры, и зачастую это сложная задача.
Существуют программныереализации, но в них атомарность не всегда присутствует.Мониторы Хоара — модель синхронизации, в которой, в частности, предпринята попыткаобойти требование аппаратной поддержки атомарности упомянутых выше операций. Мониторявляется высокоуровневой конструкцией (можно говорить, что это конструкция уровня языкапрограммирования), реализация которой поддерживается системой программирования(компилятором). Монитор — это специализированный модуль, включающий в себя некиепроцедуры и функции, а также данные, с которыми работают эти процедуры и функции.
При этомданный модуль обладает следующими свойствами:− данные монитора доступны только через процедуры и функции этого монитора;− считается, что процесс занимает (или входит) монитор тогда, когда он начинает использоватьодну из процедур или функций монитора;− в любой момент времени внутри монитора может находиться не более одного процесса,остальные процессы в зависимости от используемой стратегии поведения либо получает отказ,либо блокируется, становясь в очередь.Иллюстрацией монитора может служить кабина таксофонного аппарата.Повторим, что монитор — это языковая конструкция с централизованным управлением (вотличие от семафоров, которые не обладают централизацией).
Семафоры и мониторы являютсясредствами организации работы в основном в однопроцессорных системах либомногопроцессорных системах с общей памятью. В многопроцессорных системах с108распределенной памятью эти средства не очень подходят. Для них в настоящий момент частоиспользуется механизм передачи сообщений.Механизм передачи сообщений основан на двух функциональных примитивах: send(отправить сообщение) и receive (принять сообщение). Данные операции можно разделить по тремкритериям: синхронизация, адресация и длина сообщения.Синхронизация. Операции посылки/приема сообщений могут быть блокирующими инеблокирующими. Рассмотрим различные комбинации.Блокирующий send: процесс-отправитель будет блокирован до тех пор, пока посланное имсообщение не будет получено.Блокирующий receive: процесс-получатель будет блокирован до тех пор, пока не будетполучено соответствующее сообщение.Соответственно, неблокирующие операции, как следует из названия, происходят безблокировок.Итак, комбинируя различные операции send и receive, мы получаем 4 различных моделисинхронизации.
Отметим одно важное свойство аппарата сообщений, заключающееся в том, что внем явно совмещены средства передачи информации и синхронизации, таким образом, механизмпередачи сообщений можно использовать для достижения двух целей.Адресация может быть прямой, когда указывается конкретный адрес получателя и/илиотправителя (например, когда получатель ожидает сообщения от конкретного отправителя,игнорируя сообщения других отправителей), или косвенной. В случае косвенной адресации неуказывается адрес получателя при отправке или отправителя при получении; сообщение«бросается» в некоторый общий пул, в котором могут быть реализованы различные стратегиидоступа (FIFO, LIFO и т.д.).
Этим пулом может выступать очередь сообщений (FIFO) илипочтовый ящик, в котором может быть реализована любая модель доступа.Итак, повторимся, что данный механизм совмещает два средства: средство передачиданных и синхронизации. Этот аппарат является базовым средством организации взаимодействияпроцессов в многопроцессорных системах с распределенной памятью.Иллюстрацией данной модели может выступать модель MPI — интерфейсы передачисообщений, на основе которых строятся почти все кластерные системы, т.е. системы сраспределенной ОП, но точно также MPI может работать в системах с общей памятью.2.4.3Классические задачи синхронизации процессовКлассические задачи синхронизации процессов отражают разные модели взаимодействия идемонстрируют использование механизма семафоров для организации такого взаимодействия.Обедающие философы (2.4.3). Пускай существует круглый стол, за которым сидит группафилософов: они пришли пообщаться и покушать.
Кушают они спагетти, которое находится вобщей миске, стоящей в центре стола. Для приема пищи они пользуются двумя вилками: одна влевой руке, другая — в правой. Вилки располагаются по одной между каждыми двумяфилософами. Любой философ может взять обе вилки, покушать, затем положить вилки на стол,после этого вилки может взять его сосед и повторить эти действия.
Если мы организуем работутаким образом, что любой философ, желающий поесть, берет сначала левую вилку, затем правую,после чего начинает кушать, то в какой-то момент может возникнуть ситуация тупика (когдакаждый возьмет по одной левой вилке, а правая будет захвачена соседом).109Рис. 86.Обещающие философы.Итак, данная задача иллюстрирует модель доступа равноправных процессов к общемуресурсу, и ставится вопрос, как организовать корректную работу такой системы.Рассмотрим элементарное решение данной задачи.#define N 5void Philosopher(int i){while(TRUE){Think();/* взятие левой вилки */TakeFork(i);/* взятие правой вилки */TakeFork((i + 1) % N);Eat();/* освобождение левой вилки */PutFork(i);/* освобождение правой вилки */PutFork((i + 1) % N);}}Как было показано выше, в данном случае возможно появление ситуации, когдапроизойдет взаимоблокировка философов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
