Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


Механизм синхронизации процессов. Сообщения, эквивалентность механизмов синхронизации.



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

Критическая секция (КС) — часть кода программы, которая может привести к конфликтам.

Для избежания данного явления применяют различные механизмы взаимоисключений, т.е. один процесс при работе в КС блокирует другой.

Структура КС: пролог, КС, эпилог.

Требования к алгоритмам взаимоисключений:

1. Решение программным путем.

2. Отсутствие предположений о количестве процессоров и их быстродействии.

3. Условие взаимоисключения, т.е. в КС находится только один процесс.

4. Условие прогресса — если процесс находится вне КС, он не должен препятствовать другим процессам входить в свои КС.

5. Условие ограниченного ожидания — если процесс захотел войти в КС это не должно откладываться бесконечно долго.

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

Сообщения.

Наиболее простой механизм синхронизации. Реализуется с использованием 2х примитивов:

send(Q, mess) — отправить сообщение mess, процессу/объекту Q.

receive(Q, mess) — получить сообщение mess, от процесса/объекта Q.

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

-: медленно.

+: возможно использование для общения удаленных процессов.

Эквивалентность механизмов синхронизации.

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

Реализация мониторов с помощью семафоров.

Для этого нам нужно реализовывать взаимоисключения при входе в монитор и условные переменные. Возьмем семафор mutex с начальным значением 1 для реализации взаимоисключения при входе в монитор и по одному семафору ci для каждой условной переменной. Кроме того, для каждой условной переменной заведем счетчик fi для индикации наличия ожидающих процессов. Когда процесс входит в монитор, компилятор будет генерировать вызов функции monitor_enter, которая выполняет операцию P над семафором mutex для данного монитора. При нормальном выходе из монитора (то есть при выходе без вызова операции signal для условной переменной) компилятор будет генерировать вызов функции monitor_exit, которая выполняет операцию V над этим семафором.

Для выполнения операции wait над условной переменной компилятор будет генерировать вызов функции wait, которая выполняет операцию V для семафора mutex, разрешая другим процессам входить в монитор, и выполняет операцию P над соответствующим семафором ci, блокируя вызвавший процесс. Для выполнения операции signal над условной переменной компилятор будет генерировать вызов функции signal_exit, которая выполняет операцию V над ассоциированным семафором ci (если есть процессы, ожидающие соответствующего события), и выход из монитора, минуя функцию monitor_exit.

Код:

01 Semaphore mutex = 1;

02   void monitor_enter()

03   {

04                       P(mutex);

05   }

06   void monitor_exit()

07   {

08                       V(mutex);

09   }

10   Semaphore ci = 0;

11   int fi = 0;

12   void wait(i)

13   {

14                       fi=fi + 1;

15                       V(mutex);

16                       P(ci);

17                       fi=fi - 1;

18   }

19   void signal_exit(i)

20   {

21                       if(fi)

22                                           V(ci);

23                       else

24                                           V(mutex);

25   }

Заметим, что при выполнении функции signal_exit, если кто-либо ожидал этого события, процесс покидает монитор без увеличения значения семафора mutex, не разрешая тем самым всем процессам, кроме разбуженного, войти в монитор. Это увеличение совершит разбуженный процесс, когда покинет монитор обычным способом или когда выполнит новую операцию wait над какой-либо условной переменной.

Реализация сообщений через семафоры.

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

Процесс, желающий получить сообщение.

Процесс-получатель с номером i прежде всего выполняет операцию P(mutex), получая в монопольное владение разделяемую память. После чего он проверяет, есть ли в буфере сообщения. Если нет, то он заносит себя в список процессов, ожидающих сообщения, выполняет V(mutex) и P(ci). Если сообщение в буфере есть, то он читает его, изменяет счетчики буфера и проверяет, есть ли процессы в списке процессов, ожидающих записи. Если таких процессов нет, то выполняется V(mutex), и процесс-получатель выходит из КС. Если такой процесс есть (с номером j), то он удаляется из этого списка, выполняется V для его семафора cj, и выходим из КС. Проснувшийся процесс начинает выполняться в КС, так как mutex имеет значение 0 и никто более не может попасть в КС. При выходе из КС разбуженный процесс производит вызов V(mutex).

Работа процесса-отправителя (номером i). Процесс, посылающий сообщение, ждет, пока не сможет иметь монополию на использование разделяемой памяти, выполнив операцию P(mutex). Далее он проверяет, есть ли место в буфере, и если да, то помещает туда сообщение, изменяет счетчики и смотрит, есть ли процессы, ожидающие сообщения. Если нет, выполняет V(mutex) и выходит из КС, если есть, то "будит" один из них (с номером j), вызывая V(cj), с одновременным удалением этого процесса из списка процессов, ожидающих сообщений, и выходит из КС без вызова V(mutex), предоставляя тем самым возможность разбуженному процессу прочитать сообщение. Если места в буфере нет, то процесс-отправитель заносит себя в очередь процессов, ожидающих возможности записи, и вызывает V(mutex) и P(ci).

Реализация семафоров с помощью мониторов

Самый простой способ такой реализации выглядит следующим образом. Заведем внутри монитора переменную-счетчик, связанный с эмулируемым семафором списком блокируемых процессов и по одной условной переменной на каждый процесс. При выполнении операции P над семафором вызывающий процесс проверяет значение счетчика. Если оно больше нуля, уменьшает его на 1 и выходит из монитора. Если оно равно 0, процесс добавляет себя в очередь процессов, ожидающих события, и выполняет операцию wait над своей условной переменной. При выполнении операции V над семафором процесс увеличивает значение счетчика, проверяет, есть ли процессы, ожидающие этого события, и если есть, удаляет один из них из списка и выполняет операцию signal для условной переменной, соответствующей процессу.

Реализация семафоров с помощью очередей сообщений.

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

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

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

 


Поделиться:



Последнее изменение этой страницы: 2019-05-08; Просмотров: 176; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.023 с.)
Главная | Случайная страница | Обратная связь