Операционные системы 2011 (1114689), страница 36

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

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

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

структуры данных монитора доступны только через обращения к процедурам илифункциям этого монитора (т.е. монитор представляет собой некоторый аналогобъекта в объектно-ориентированных языках и реализует инкапсуляцию данных);2. считается, что процесс занимает (или входит в) монитор, если он вызывает однуиз процедур или функций монитора;3. в каждый момент времени внутри монитора может находиться не более одногопроцесса.Если процесс пытается попасть в монитор, в котором уже находится другойпроцесс, то (в зависимости от используемой стратегии) он либо получает отказ, либоблокируется, становясь в очередь. Таким образом, чтобы защитить разделяемыеструктуры данных, их достаточно поместить внутрь монитора вместе с процедурами,представляющими критические секции для обработки этих структур данных.Монитор представляет собой конструкцию языка программирования икомпилятору известно о том, что входящие в него процедуры и данные имеют особуюсемантику, поэтому первое условие может проверяться еще на этапе компиляции, крометого, код для процедур монитора тоже может генерироваться особым образом, чтобыудовлетворялось третье условие.

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

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

Рассмотрим различные комбинации.Блокирующий send: процесс-отправитель будет заблокирован до тех пор, покапосланное им сообщение не будет получено.Блокирующий receive: процесс-получатель будет заблокирован до тех пор, пока небудет получено соответствующее сообщение.Соответственно, неблокирующие операции, как следует из названия, происходятбез блокировок.Итак, комбинируя различные операции send и receive, мы получаем 4 различныхмодели синхронизации.124Адресация может быть прямой или косвенной. При прямой адресацииуказывается конкретный адрес получателя и/или отправителя (например, когдаполучатель ожидает сообщения от конкретного отправителя, игнорируя сообщениядругих отправителей).В случае косвенной адресации не указывается адрес конкретного получателя приотправке или адрес конкретного отправителя при получении; сообщение «бросается» внекоторый общий пул, в котором могут быть реализованы различные стратегии доступа(FIFO, LIFO и т.д.).

Этим пулом может выступать очередь сообщений (FIFO) илипочтовый ящик, в котором может быть реализована любая модель доступа. Бытовымпримером косвенной адресации может служить модель обслуживающей системы(сотруднику ателье всё равно, чей пиджак он чистит).Итак, повторимся, что механизм передачи сообщений совмещает два средства:средство передачи информации и средство синхронизации.

Этот аппарат являетсябазовым средством организации взаимодействия процессов в многопроцессорныхсистемах с распределенной памятью.Механизм передачи сообщений реализуется на базе интерфейсов передачисообщений MPI. На основе этих интерфейсов строятся почти все кластерные системы (т.е.системы с распределенной памятью), а также MPI может работать и в системах с общейпамятью.2.4.3 Классические задачи синхронизации процессовКлассические задачи синхронизации процессов отражают разные моделивзаимодействия и демонстрируют использование механизма семафоров для организациитакого взаимодействия.Обедающие философы (Рис.

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

Философыдолжны совместно использовать имеющиеся у них вилки (ресурсы). Задача состоит ворганизации доступа к вилкам.Рис. 94. Обещающие философы.Итак, данная задача иллюстрирует модель доступа равноправных процессов кобщему ресурсу, и ставится вопрос, как организовать корректную работу такой системы.Рассмотрим простейшее решение данной задачи, использующее семафоры. Когдаодин из философов хочет есть, он берет вилку слева от себя, если она в наличии, а затем— вилку справа от себя. Закончив есть, он возвращает обе вилки на свои места. Данныйалгоритм может быть представлен следующим способом.125#define N 5 /* количество философов */void Philosopher(int i) /* i – номер философа от 0 до 4 */{while(TRUE){Think();/*философ думает */TakeFork(i); /* взятие левой вилки */TakeFork((i + 1) % N); /* взятие правой вилки */Eat();/* философ ест */PutFork(i); /* освобождение левой вилки */PutFork((i + 1) % N); /* освобождение правой вилки */}}Функция take_fork(i) описывает поведение философа по захвату вилки: он ждет, покауказанная вилка не освободится, и забирает ее.Однако вышеобозначенное решение может привести к тупиковой ситуации.

Чтопроизойдет, если все философы захотят есть в одно и то же время? Каждый из нихполучит доступ к своей левой вилке и будет находиться в состоянии ожидания второйвилки до бесконечности, т.е. возникнет ситуация тупика. Другим решением может бытьалгоритм, который обеспечивает доступ к вилкам только четырем из пяти философов. Вэтом случае всегда среди четырех философов по крайней мере один будет иметь доступ кдвум вилкам. Данное решение не имеет тупиковой ситуации. Алгоритм решения можетбыть представлен следующим образом.#define N 5 /* количество философов */#define LEFT (i-1)%N /* номер левого соседа для i-го философа */#define RIGHT (i+1)%N /*номер левого соседа для i-го философа *//* состояния философов:«думает»,«голоден»,«кушает»*/#define THINKING 0#define HUNGRY 1#define EATING 2/* определяем тип СЕМАФОР */typedef int semaphore;/*массив состояний каждого из философов, инициализированный нулями*/int state[N];/* семафор для доступа в критическую секцию */semaphore mutex = 1;/*массив семафоров по одному на каждого из философов,инициализированный нулями*/semaphore s[N];/* Процесс-философ (i = 0..N) */void Philosopher(int i)126{while(TRUE){Think();/* философ берёт обе вилки или блокируется */TakeForks(i);Eat();PutForks(i);}}/* получение вилок */void TakeForks(int i){/* вход в критическую секцию */down(&mutex);state[i] = HUNGRY;Test(i);/* выход из критической секции */up(&mutex);down(&s[i]);}/* освобождение вилок */void PutForks(int i){/* вход в критическую секцию */down(&mutex);state[i] = THINKING;Test(LEFT);Test(RIGHT);/* выход из критической секции */up(&mutex);}/* функция проверки возможности получения вилок –проверяется состояние соседей данного философа */void Test(int i){if(state[i] == HUNGRY &&state[LEFT] != EATING &&state[RIGHT] != EATING){state[i] = EATING;up(&s[i]);}}В этом решении каждый философ живет по аналогичному циклическомураспорядку: размышляет некоторое время, затем берет вилки, кушает, кладет вилки.Рассмотрим процедуру получения вилок (TakeForks).

Опускается семафор mutex, которыйиспользуется для синхронизации входа в критическую секцию. Внутри критическойсекции меняем состояние философа (помечаем его состоянием HUNGRY). Затемпредпринимается попытка начать есть (вызывается функция Test). Функция Test127проверяет, что если i-ый философ голоден, а его соседи в данный момент не едят (т.е.правая и левая вилки свободны), то этот философ начинает прием пищи (состояниеEATING), а его семафор поднимается (заметим, что изначально этот семафоринициализирован нулем). После этого мы возвращаемся обратно в функцию TakeForks, вкоторой далее происходит выход из критической секции (поднимаем семафор mutex), азатем опускаем семафор этого философа.

Если внутри функции Test философу удалосьначать прием пищи, то семафор поднят, и операция down обнулит его, не блокируясь.Если же функция Test не изменит состояние философа, а также не поднимет его семафор,то операция down (в функции TakeForks) в этой точке заблокируется до тех пор, пока обасоседа не освободят вилки.Внутри функции освобождения вилок PutForks сначала происходит опусканиесемафора mutex, происходит вход в критическую секцию. Затем меняется статусфилософа (на статус THINKING), после чего проверяем его соседей: если любой из нихбыл заблокирован лишь из-за того, что наш i-ый философ забрал его вилку, то мы егоразблокируем, и он начинает прием пищи.

После этого происходит выход из критическойсекции путем подъема семафора mutex.Заметим, что использование механизма взаимоисключающего нахождения внутрикритической секции (за счет семафора mutex) гарантирует, что не возникнет ситуация,когда два процесса, соответствующие соседним философам, будут так спланированы наобработку на процессоре, что функция Test в каждом из них проработает и разрешиткаждому из них начать прием пищи (что, конечно же, является ошибкой). Если же этогомеханизма не будет, то возможно, что один из процессов-соседей входит в Test, делаетпроверку на возможность начала приема пищи. Проверка дает истинное значение,управление переходит к первой команде внутри if-блока.

После этого происходит сменапроцесса на процессоре, управление получает сосед этого философа. Тот тоже делаетпроверку внутри функции Test и также получает положительный ответ, и управлениепереходит к первой инструкции if-блока. Дальнейшая работа будет некорректной.Задача «читателей и писателей».

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

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