.RU

Проблемы организации взаимного исключения - Конспект по курсу лекций Операционные системы Граур Светлана


^ Проблемы организации взаимного исключения

•Тупики (deadlocks)


•Блокирование (дискриминация)



^ Тупики (deadlocks)
При организации взаимного исключения могут возникнуть тупики (deadlocks), ситуации в которой конкурирующие за критический ресурс процессы вступают в клинч – безвозвратно блокируются.



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


В тупике могут «участвовать» произвольное количество ресурсов.

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


• Запрещение прерываний и специальные инструкции

• Алгоритм Петерсона

• Активное ожидание

• Семафоры Дейкстры

• Мониторы

• Обмен сообщениями

^ Семафоры Дейкстры

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


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

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


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

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

 

Семафоры – это низкоуровневые средства синхронизации, для корректной практической реализации которых необходимо наличие специальных, атомарных семафорных машинных команд.


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

Пример.

Представим себе супермаркет, посетители которого прежде чем войти в торговый зал должны обязательно взять себе инвентарную тележку. В момент открытия магазина на входе имеется N свободных тележек – это начальное значение семафора. Каждый посетитель забирает одну из тележек (уменьшая тем самым количество оставшихся на 1) и проходит в торговый зал – это аналог операции down. При выходе посетитель возвращает тележку на место, увеличивая количество тележек на 1 – это аналог операции up. Теперь представим себе, что очередной посетитель обнаруживает, что свободных тележек нет – он вынужден блокироваться на входе в ожидании появления тележки. Когда один из посетителей, находящихся в торговом зале, покидает его, посетитель, ожидающий тележку, разблокируется, забирает тележку и проходит в зал. Таким образом, наш семафор в виде тележек позволяет находиться в торговом зале (аналоге критической секции) не более чем N посетителям одновременно. Положив N=1, получим реализацию взаимного исключения. Семафор, начальное (и максимальное) значение которого равно 1, называется двоичным семафором (т. к. имеет только 2 состояния: 0 и 1).

 

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

Здесь мы видим условную переменную типа int – она здесь семафор, но на самом деле она не int, а типа данных семафор. Значит каждый из процессов, перед тем как работать с критическим ресурсом, т.е. перед тем как войти в свою критическую секцию делает операцию down() на семафор (семафор для всех один и тот же) и на выходе из своей критической секции он делает операцию up(). Представьте себе, что процесс 1 подошел к своей критической секции в то время, как семафор свободен (ресурс свободен). Он выполняет операцию down(), тем самым значение семафора становится равным 0 (т.к. вначале было равно 1), и процесс 1 получает возможность работать в своей критической секции. Если в этот момент процесс 2 захочет попасть в свою критическую секцию, т.е. тоже поработать с нашим ресурсом, то при попытке выполнить операцию down() он будет заблокирован, поскольку значение семафора 0 и уменьшиться оно уже не может. Соответственно он будет ожидать до тех пор, пока процесс 1 не выйдет из своей критической секции, после чего процесс 2 будет автоматически разблокирован в тот момент, когда процесс 1 выполнит up(), и тем самым попадет в свою критическую секцию. Понятно, что это реализует взаимное исключение.





Семафоры – это мощное средство синхронизации, но проблемы с ними тоже есть, потому что при написании программ с использованием семафоров велика вероятность возникновения ошибок (т.е. средство достаточно низкоуровневое), т.к. достаточно в одном месте перепутать местами down() и up() или поставить не в том месте down(), не в том месте up(), и получается ситуация тупика. Кроме того, семафоры являются средством, которое требует поддержки со стороны ОС. Это выражается в том, что операции down() и up() должны быть атомарными, т.е. не должно происходить переключение контекстов. Иначе возможно, что в том момент, когда процесс проверил состояние семафора, но еще не изменил его значение, в этот момент произойдет переключение контекста, другой процесс изменит значение семафора, а 1-й процесс об этом уже не узнает и будет считать, что он прав и пойдет в свою критическую секцию, в то время как там уже находится другой процесс, поэтому требование атомарности оно принципиально важно. А раз говорится о том, что должно быть запрещено переключение контекстов, это требует естественно поддержки со стороны ОС.


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


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


^ Три основных свойства монитора:

1.      структуры данных, входящие в монитор, могут быть доступны только для процедур, входящих в этот монитор (таким образом, монитор представляет собой некоторый аналог объекта в объектно-ориентированных языках и реализует инкапсуляцию данных);

2.процесс «входит» в монитор путем вызова одной из его процедур;

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


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

Несмотря на все эти плюсы, широкого распространения мониторы не получили. Т.е. мониторы реализованы в некоторых языках программирования, таких как Modula 2, но к сожалению эти языки программирования не очень широко распространены, и тем самым красивая идея осталась также осталась далека от широкого распространения.


^ Обмен сообщениями


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

Основная функциональность метода обеспечивается двумя примитивами (являющимися, как и семафоры, в отличие от мониторов, системными вызовами, а не конструкциями языка) :

send (destination, message)

receive (source, message)


^ Основные особенности, которыми может обладать та или иная система обмена сообщениями:

•Синхронизация

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

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

•Адресация

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

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

•^ Длина сообщения


programma-dopolnitelnogo-obrazovaniya-stranica-2.html
programma-dopolnitelnogo-obrazovaniya-v-predkadetskom-klasse-osnovi-voennih-znanij.html
programma-dopolnitelnogo-platnogo-kursa-.html
programma-dopolnitelnogo-professionalnogo-obrazovaniya-povisheniya-kvalifikacii.html
programma-dopolnitelnogo-professionalnogo-obrazovaniya-vrachej-po-specialnosti-plasticheskaya-hirurgiya.html
programma-dopolnitelnogo-vstupitelnogo-ispitaniya-tvorcheskoj-napravlennosti-na-napravlenie-podgotovki-031300-62-zhurnalistika.html
  • exchangerate.bystrickaya.ru/greyhound-racing-right-or-wrong-essay-research.html
  • paragraph.bystrickaya.ru/kokin-av-d-g-m-n-prof-skagskotov-sa-ivankova-ea-rosprirodnadzor-po-ro.html
  • education.bystrickaya.ru/342-balans-massi-energoaudit-posobie-dlya-slushatelej-obrazovatelnih-kursov-po-energeticheskomu-menedzhmentu.html
  • control.bystrickaya.ru/doc-sherbakova-on-prezidentskaya-programma-podgotovki-upravlencheskih-kadrov-specialnost-menedzhment-missiya.html
  • lesson.bystrickaya.ru/radiopriemnie-ustrojstva.html
  • abstract.bystrickaya.ru/1-obshie-voprosi-mezhdunarodnoj-pravosubektnosti-stranica-22.html
  • klass.bystrickaya.ru/a-a-erlihman-organizaciya-tehnika-i-buhgalterskij-uchet-tovarnih-operacii-optovaya-torgovlya-m-ekspertnoe-byuro-m-1998-400-s-stranica-9.html
  • exchangerate.bystrickaya.ru/51-dzhataka-o-muzhe-dobrodetelnom-sutta-pitaka-khuddaka-nikya-jtaka-eka-nipata-1-apannaka-jataka.html
  • pisat.bystrickaya.ru/standart-kachestva-predostavleniya-municipalnih-byudzhetnih-uslug-v-oblasti-fizicheskoj-kulturi-sporta-i-turizma-v-gorode-orske.html
  • composition.bystrickaya.ru/participle-i-atika-v-uprazhneniyah-ch-infinitiv-gerundij-prichastie-sbornik-uprazhnenij-po-grammatike-anglijskogo.html
  • shpargalka.bystrickaya.ru/voprosi-k-ekzamenu-po-discipline-makroekonomika.html
  • writing.bystrickaya.ru/analiz-otdachi-investicij-v-chelovecheskij-kapital-na-primere-obrazovaniya-v-rossii-stranica-2.html
  • books.bystrickaya.ru/bilet-9-otveti-na-bileti-po-biologii-9-klass-2011.html
  • portfolio.bystrickaya.ru/otkuda-v-nash-dom-prihodit-voda-stranica-5.html
  • uchenik.bystrickaya.ru/informacionnaya-radiokorrespondenciya-7-radioveshanie-istoriya-razvitiya-izobrazitelnie-sredstva-radiozhurnalistika.html
  • kolledzh.bystrickaya.ru/5-po-specialnosti-09010365-organizaciya-i-tehnologiya-zashiti-informacii-i-po-napravleniyam-podgotovki-magistrov.html
  • predmet.bystrickaya.ru/spravka-o-rezultatah-samoobsledovaniya-kafedri-istorii-po-specialnosti-032600-050401istoriya-po-sostoyaniyu-na-12-maya-2008-goda.html
  • uchebnik.bystrickaya.ru/uchebno-metodicheskij-kompleks-po-akusherstvu-i-ginekologii-naimenovanie-disciplini-dlya-specialnosti-.html
  • doklad.bystrickaya.ru/uchebno-metodicheskij-kompleks-dpp-f-02-istoriya-russkogo-yazika-chast-1-istoricheskaya-grammatika-russkogo-yazika.html
  • tasks.bystrickaya.ru/1-umejte-zadavat-voprosi.html
  • universitet.bystrickaya.ru/tyumenskaya-oblast-centralnij-federalnij-okrug-cfo-belgorodskaya-oblast.html
  • literature.bystrickaya.ru/ects-informacionnij-paket-stranica-7.html
  • thesis.bystrickaya.ru/prilozhenie-tehnicheskie-harakteristiki-rukovodstvo-polzovatelya-i.html
  • otsenki.bystrickaya.ru/sabati-tairibi-himiyali-reakciyalardi-tipter-orinbasu-almasu-sabati-masati.html
  • portfolio.bystrickaya.ru/organizaciya-processa-osushestvlyaetsya-na-osnove-resheniya-ryada-zadach-programma-fgos-nachalnoe-obrazovanie-municipalnogo.html
  • teacher.bystrickaya.ru/glava-38-obyasnyayushaya-pochemu-vse-chego-dostigaet-zhenshina-ona-dostigaet-v-pervie-godi.html
  • shkola.bystrickaya.ru/primenenie-elektroliza.html
  • laboratornaya.bystrickaya.ru/realizaciya-kompetentnostnogo-podhoda-v-obrazovatelnom-processe-tradicii-innovacii-perspektivi-22-23-aprelya-2012g-informacionnoe-pismo.html
  • predmet.bystrickaya.ru/rekomendacii-po-razrabotke-dolzhnostnih-reglamentov-federalnih-gosudarstvennih-grazhdanskih-sluzhashih-v-federalnih.html
  • gramota.bystrickaya.ru/zadanie-2-reshit-pismenno-zadachi-uchebno-metodicheskij-kompleks-uchebnoj-disciplini-opd-f-07-grazhdanskoe-pravo.html
  • universitet.bystrickaya.ru/tablica-2-shtatnoe-raspisanie-sekretariata-strategicheskogo-podhoda-po-mezhdunarodnomu-regulirovaniyu-himicheskih-veshestv-na-period.html
  • doklad.bystrickaya.ru/usloviya-v-kotorih-protekaet-zhiznedeyatelnost-sovremennogo-cheloveka-chasto-po-pravu-nazivayut-ekstremalnimi-i-stimuliruyushimi-razvitie-stressa-eto-svyazano-so.html
  • urok.bystrickaya.ru/programma-disciplini-sociologiya-delovih-organizacij.html
  • paragraph.bystrickaya.ru/kombinirovannaya-predusmatrivaet-vozmozhnost-podachi-predlozhenij-kak-na-bumazhnom-nositele-tak-i-v-elektronnom-vide-v-sootvetstvii-s-ukazannimi-v-nastoyashej.html
  • university.bystrickaya.ru/glava-iv-lechebnaya-fizkultura-pri-zabolevaniyah-organov-dihaniya-fizicheskaya-kultura.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.