Главная
страница 1страница 2 ... страница 4страница 5

  1. Алгоритмы синхронизации (алгоритмы корректной организации взаимодействия процессов).

Критическая секция

Критическая секция – часть программы, результат выполнения которой может непредсказуемо меняться, если переменные, относящиеся к ней, изменяются другими потоками в то время, когда выполнение этой части еще не завершено. В примере критическая секция – файл “заказов”, являющийся разделяемым ресурсом для процессов R и S.



Алгоритм Деккера - первое известное корректное решение проблемы взаимного исключения.

Если два процесса пытаются перейти в критическую секцию одновременно, алгоритм позволит это только одному из них, основываясь на том, чья в этот момент очередь. Если один процесс уже вошёл в критическую секцию, другой будет ждать, пока первый покинет её. Это реализуется при помощи использования двух флагов (индикаторов "намерения" войти в критическую секцию) и переменной turn (показывающей, очередь какого из процессов наступила).

Процессы объявляют о намерении войти в критическую секцию; это проверяется внешним циклом «while». Если другой процесс не заявил о таком намерении, в критическую секцию можно безопасно войти (вне зависимости от того, чья сейчас очередь). Взаимное исключение всё равно будет гарантировано, так как ни один из процессов не может войти в критическую секцию до установки этого флага (подразумевается, что, по крайней мере, один процесс войдёт в цикл «while»). Это также гарантирует продвижение, так как не будет ожидания процесса, оставившего «намерение» войти в критическую секцию. В ином случае, если переменная другого процесса была установлена, входят в цикл «while» и переменная turn будет показывать, кому разрешено войти в критическую секцию. Процесс, чья очередь не наступила, оставляет намерение войти в критическую секцию до тех пор, пока не придёт его очередь (внутренний цикл «while»). Процесс, чья очередь пришла, выйдет из цикла «while» и войдёт в критическую секцию.

+ не требует специальных Test-and-set инструкций, по этому легко переносим на разные языки программирования и архитектуры компьютеров

-Действует только для двух процессов

Алгоритм Петерсона — программный алгоритм взаимного исключения потоков исполнения кода.

Перед тем как начать исполнение критической секции кода (то есть кода, обращающегося к защищаемым совместно используемым ресурсам), поток должен вызвать специальную процедуру (назовем ее EnterRegion) со своим номером в качестве параметра. Она должна организовать ожидание потока своей очереди входа в критическую секцию. После исполнения критической секции и выхода из нее, поток вызывает другую процедуру (назовем ее LeaveRegion), после чего уже другие потоки смогут войти в критическую область. Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу. При этом одно из предложений всегда следует после другого. Тем самым работу в критическом участке продолжит процесс, которому было сделано последнее предложение.

-Как и алгоритм Деккера, действует только для 2 процессов

+Более простая реализация, чем у алгоритма Деккера



Алгоритм булочной. Алгоритм Петерсона дает нам решение задачи корректной организации взаимодействия двух процессов. Давайте рассмотрим теперь соответствующий алгоритм для n взаимодействующих процессов.

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



  1. Специальные механизмы синхронизации – семафоры Дейкстры, мониторы Хора, очереди сообщений.

Семафоры

Для устранения этого недостатка во многих ОС предусматриваются специальные системные вызовы (аппарат для работы с критическими секциями.

В разных ОС аппарат событий реализован по своему, но в любом случае используются системные функции, которые условно называют WAIT(x) и POST(x), где x – идентификатор некоторого события (например, освобождение ресурса).

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел новые примитивы, обозначаемые V (“открытие”) и P (“закрытие”), оперирующие над целыми неотрицательными переменными, называемыми семафорами.

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

Смысл P(S) заключается в проверке текущего значения семафора S, и если S>0, то осуществляется переход к следующей за примитивом операции, иначе процесс переходит в состояние ожидания.

P(S):

Пока S==0



Процесс блокируется;

S=S-1;


Операция V(S) связана с увеличением значения S на 1 и переводом одного или нескольких процессов в состояние готовности к исполнению процессором.

V(S):


S=S+1;

В простом случае, когда семафор работает в режиме 2-х состояний (S>0 и S=0), ео алгоритм работы полностью совпадает с алгоритмом работs мьютекса, а S выполняет роль блокирующей переменной.

“+”: пассивное ожидание (постановка в очередь и автоматическая выдача ресурсов)


  • возможность управления группой однородных ресурсов

“-”: не указывают непосредственно на критический ресурс

  • некорректное использование операций может привести к нарушению работоспособности (например, переставив местами операции P(e) и P(b) в функции Writer()).

Мониторы

Для облегчения работы программистов при создании параллельных программ без усилий на доказательства правильности алгоритмов и отслеживание взаимосвязанных объектов (что характерно при использовании семафоров) предложено высокоуровневое средство синхронизации, называемое мониторами.

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

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

Доступ к мониторам в каждый момент времени имеет только один процесс.

Для организации не только взаимоисключений, но и очередности процессов, подобно семафорам f(full) и e(empty), было введено понятие условных переменных, над которыми можно совершать две операции wait и signal, отчасти похожие на операции P и V над семафорами.

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

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

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

Требуются специальные языки программирования и компиляторы (встречаются в языках, “параллельный Евклид”,”параллельный Паскаль”,Java).

Следует отметить, что условные переменные мониторов не запоминают предысторию, поэтому операцию signal всегда должна выполняться после операции wait(иначе выполнение операции wait всегда будет приводить к блокированию процесса).

Очереди сообщений

Механизм очередей сообщений позволяет процессам и потокам обмениваться структурированными сообщениями. Один или несколько процессов независимым образом могут посылать сообщения процессу – приемнику.

Очередь сообщений представляет возможность использовать несколько дисциплин обработки сообщений (FIFO, LIFO, приоритетный доступ, произвольный доступ).

При чтении сообщения из очереди удаления сообщения из очереди не происходит, и сообщение может быть прочитано несколько раз.

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

Основные функции управления очередью:



  • Создание новой очереди

  • Открытие существующей очереди

  • Чтение и удаление сообщений из очереди

  • Чтение без последующего удаления

  • Добавление сообщения в очередь

  • Завершение использование очереди

  • Удаление из очереди всех сообщений

  • Определение числа элементов в очереди




  1. Взаимоблокировки, тупиковые ситуации, "зависания" системы

следующая страница >>
Смотрите также:
Понятие и структура ос. Эволюция вычислительных и ос. Основные функции ос
765.68kb.
5 стр.
Критическая секция
604.6kb.
5 стр.
Терапевтическая секция хирургическая секция
337.68kb.
2 стр.
Секция 1: Северные ездовые собаки Секция
114.89kb.
1 стр.
Ежегодная научная конференция «ломоносовские чтения» секция экономических наук
79.13kb.
1 стр.
Критическая апология мультикультурализма
516.71kb.
3 стр.
Каб. №201 Секция №1 Отделение «История» Секция «История: от древности к современности»
237.51kb.
1 стр.
Секция «Маркетинг и менеджмент предприятия» 21 мая, 11. 30, ауд. 560/2 Секция «Проблемы современного бухгалтерского учета, анализа и аудита»
131.59kb.
1 стр.
Иванов Георгий Владимирович Поэзия и поэты: [Литературно-критическая статья
20.64kb.
1 стр.
Урок Русская литературно-критическая и философская мысль второй половины 19 века
302.36kb.
1 стр.
Экзаменационные вопросы по аэромеханике
32.96kb.
1 стр.
Секция общественные науки Основана в 1977 году Секция социологии и политологии
107.13kb.
1 стр.