Самодел 1 (1114716), страница 26

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

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

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

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

• Мониторы

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

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

Тип данных, именуемый семафором. Семафор представляет собой переменную целого типа 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, а данных еще нет, то мы будем заблокированы до тех пор пока не появятся данные, удовлетворяющие условиям нашего вызова.

•Адресация

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

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

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

Классические задачи синхронизации процессов

«Обедающие философы»

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

Рассмотрим простейшее решение, использующее семафоры. Когда один из философов хочет есть, он берет вилку слева от себя, если она в наличии, а затем - вилку справа от себя. Закончив есть, он возвращает обе вилки на свои места. Данный алгоритм может быть представлен следующим способом:

#define N 5 /* число философов*/

void philosopher (int i) /* i – номер философа от 0 до 4*/

{

while (TRUE)

{

think(); /*философ думает*/

take_fork(i); /*берет левую вилку*/

take_fork((i+1)%N); /*берет правую вилку*/

eat(); /*ест*/

put_fork(i); /*кладет обратно левую вилку*/

put_fork((i+1)%N); /* кладет обратно правую вилку */

}

}

Функция take_fork() описывает поведение философа по захвату вилки: он ждет, пока указанная вилка не освободится, и забирает ее.

На первый взгляд, все просто, однако, данное решение может привести к тупиковой ситуации. Что произойдет, если все философы захотят есть в одно и то же время? Каждый из них получит доступ к своей левой вилке и будет находиться в состоянии ожидания второй вилки до бесконечности. Другим решением может быть алгоритм, который обеспечивает доступ к вилкам только четырем из пяти философов. Тогда всегда среди четырех философов по крайней мере один будет иметь доступ к двум вилкам. Данное решение не имеет тупиковой ситуации. Здесь определяется количество философов, далее идут макросы для определения номеров левой, правой вилки и три состояния философов: философ думает, философ голоден и философ ест. Определяется тип данных semaphore и массив состояний каждого из философов – массив state. Далее определяется один семафор для реализации критической секции и по одному семафору на каждого философа – это массив семафоров s. Вот, обратите внимание, они выделены цветом, и далее операции с этими семафорами тоже будут выделены цветом. Основная функция – это философы. Философ думает затем, когда он проголодается, он вызывает функцию take_forks(), затем происходит еда, и вызывается функция put_forks(). В функции take_forks() в первую очередь идет вход в критическую секцию одного конкретного философа. Критическая секция охраняется семафором mutex. В момент входа в критическую секцию семафор mutex охраняет массив состояний философа. Идет изменение состояния на голоден, и вызывается функция test(). Затем производится выход из критической секции: поднятие семафора mutex и опускание семафора конкретного философа. В функции test() происходит проверка: что делает левый сосед, и что делает правый сосед. Если состояние голоден и левый сосед не ест и правый сосед не ест, т.е. вилки свободны, то состояние философа меняется на состояние поедания и поднимается семафор этого философа. Итак опускание семафора происходит в take_forks(), а поднятие в test(). Т.е. если семафор не был поднят в test() (не выполнилось условие, что оба соседа не едят), то в момент down() на семафоре в функции take_forks() философ будет заблокирован и будет ожидать, пока один из соседей не освободит его состояние, что происходит в функции put_forks(). Здесь тоже самое: опускается семафор для хранения критической секции, которая охраняет массив состояний. Состояние изменяется на «думающий» и производится тест на левого и правого соседа. В этот момент, когда посылается тест для обоих соседей, если один из этих соседей был ранее заблокирован из-за того, что его вилка была занята нашим философом, то в этот момент он разблокируется и сможет взять вилку. Обращаю ваше внимание на то, что семафор mutex необходим для охраны массива состояний философов. Т.е. здесь массив состояний философов является разделяемым ресурсом, потому что эти состояния проверяются как самим философом так и его левым и правым соседом (функция test()). Поэтому необходимо охранять их, потому что если доступ к ним будет осуществляться со стороны двух или более процессов одновременно, то один из процессов может проверить это состояние, в то время как другой процесс будет его изменять. Чтобы такого не происходило необходимо сделать этот ресурс критическим и охранять его семафором, что и делает семафор mutex. Массив семафоров s используется для того, чтобы блокировать философов, которые не могут в данный момент взять вилку и разблокирование философов происходит в тот момент, когда сосед вилки освобождает. Т.е. это решение уже более сложное, однако, оно позволяет избежать тупиковых ситуаций, но не гарантирует отсутствие дискриминации, т.е. здесь возможно ситуация, что поскольку в момент когда разблокируется один из соседей всегда возможна ситуация, что вилку захватит другой сосед, соответственно второй сосед может остаться без вилок.

Алгоритм решения может быть представлен следующим образом:

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

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