Главная » Просмотр файлов » Операционные системы 2011

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

Файл №1114689 Операционные системы 2011 (Операционные системы 2011) 36 страницаОперационные системы 2011 (1114689) страница 362019-05-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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-блока. Дальнейшая работа будет некорректной.Задача «читателей и писателей».

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

Тип файла
PDF-файл
Размер
2,98 Mb
Тип материала
Высшее учебное заведение

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

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6551
Авторов
на СтудИзбе
299
Средний доход
с одного платного файла
Обучение Подробнее