2011. Машбук (1114722), страница 35
Текст из файла (страница 35)
Как только один из покупателей с тележкой покидает торговыйзал, происходит операция up – появляется одна свободная тележка. Эту тележку беретодин из ожидающих посетителей и проходит в торговый зал. Это означает, что один иззаблокированных клиентов разблокировался и продолжил работу, остальные жепродолжают ждать в заблокированном состоянии.Если тележка была бы одна, то это было бы иллюстрацией организации доступа врежиме взаимного исключения, т.е. в любой момент времени в торговом зале можетоказаться лишь один покупатель.
Это пример т.н. двоичного семафора — семафора,максимальное значение которого равно 1. Этот тип семафоров и обеспечивает взаимноеисключение.В приведенном ниже (Рис. 93) примере двоичного семафора рассмотрены двапроцесса, каждый из которых имеет критическую секцию.
За счет использованиядвоичного семафора обеспечивается безопасная работа в критической секции любого изпроцессов, т.е. если один из них вошел в критическую секцию, то гарантируется, чтовторой при попытке также войти в свою критическую секцию будет блокирован до техпор, пока первый не покинет оную.процесс 1int semaphore;...down(semaphore);/* критическая секцияпроцесса 1 */...up(semaphore);...процесс 2int semaphore;...down(semaphore);/* критическая секцияпроцесса 2 */...up(semaphore);...Рис. 93.
Пример использования двоичного семафора для организации взаимногоисключения.Заметим, что требование атомарности операций down и up накладываетограничения на реализацию семафоров Дейкстры, и зачастую это сложная задача.Существуют различные программные реализации этих операций, но в них атомарность невсегда присутствует.Таким образом, семафоры Дейкстры — это низкоуровневые средствасинхронизации, для корректной практической реализации которых необходимо наличиеспециальных атомарных семафорных машинных команд.123Рассмотрим теперь модель синхронизации, в которой, в частности, предпринятапопытка обойти требование аппаратной поддержки атомарности упомянутых вышеопераций.
Идея монитора была впервые сформулирована в 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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
