Заходи
Гость

Хостинг

Статистика
Яндекс.Метрика Счетчик PR-CY.Rank
Онлайн всего: 1
Гостей: 1
Пользователей: 0

Ccылки

Свежак

Главная » Статьи » Все статьи » Операционные системы

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

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

program версияодин;

var номерпроцесса: целое;

procedure процессодин;

begin

while истина do

begin

while номерпроцесса = 2 do;

критическийучастокодин;

номерпроцесса :=2;

прочиеоператорыодин

end

end;

procedure процессдва;

begin

while истина do

begin

while номерпроцесса = 1 do;

критическийучастокдва;

номерпроцесса :=1;

прочиеоператорыдва

end

end;

begin

номерпроцесса:=1;

parbegin

процессодин;

процессдва

parend

end.

Эта программа  гарантирует взаимоисключение дорогой ценой. «Процессодин» должен выполняться первым, т. о. если «процессдва» готов ко входу в свой критический участок, он может получить разрешение на это со значительной задержкой. После того, как «процессодин» войдет в свой критический участок и затем выйдет из него, должен будет снова выполняться «процессдва», даже если «процессодин» хочет вновь войти в свой критический участок, а «процессдва» еще не готов. Т.о. процессы должны входить и выходить из своих участков строго поочередно. Если одному процессу приходится это делать во много раз чаще, чем другому, то он вынужден работать с гораздо меньшей скоростью, чем это необходимо. Достоинство этой программы в том, что она не может оказаться в состоянии полного тупика; если оба процесса одновременно пытаются войти в свои критические участки, то по крайней мере одному из них удается продолжить свою работу. Недостатком этой программы является тот факт, что если один из процессов со временем завершится, то со временем другой окажется не в состоянии продолжить выполнение. В этой программе имеется только одна внешняя переменная и, таким образом возникает проблема жесткой синхронизации процессов.

program версиядва;

var п1внутри, п2внутри: логический;

procedure процессодин;

begin

while истина do

begin

while п2внутри do;

п1внутри := истина;

критическийучастокодин;

п1внутри := ложь;

прочиеоператорыодин

end

end;

procedure процессдва;

begin

while истина do

begin

while п1внутри do;

п2внутри := истина;

критическийучастокодин;

п2внутри := ложь;

прочиеоператорыдва

end

end;

begin

п1внутри := ложь;

п2внутри := ложь;

parbegin

процессодин;

процессдва

parend

end.

 

Вторая версия алгоритма Деккера (рис. 2) свободна от этого за счет наличия двух глобальных логических переменных (флагов-признаков) «п1внутри» и «п2внутри», которые имеют истинное значение, если «процессодин» или «процессдва» находятся

внутри своих критических участков соответственно.

Слабым местом этой версии программы является то, что между моментом, когда

процесс, находящийся в цикле ожидания, определяет, что он может идти дальше и

моментом, когда этот процесс устанавливает флаг-признак, говорящий о том, что он

вошел в свой критический участок, проходит достаточно времени, чтобы другой процесс

успел проверить еще не установленный флаг-признак и войти в свой критический участок.

Поэтому необходимо, чтобы в то время как один процесс выполняет свой цикл

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

место этой программы – возможность одновременного входа в свои критические

участки.

program версиятри;

var п1хочетвойти, п2хочетвойти: логический;

procedure процессодин;

begin

while истина do

begin

п1хочетвойти := истина;

while п2хочетвойти do;

критическийучастокодин;

п1хочетвойти := ложь;

прочиеоператорыодин

end

end;

procedure процессдва;

begin

while истина do

begin

п2хочетвойти := истина;

while п1хочетвойти do;

критическийучастокдва;

п2хочетвойти := ложь;

прочиеоператорыдва

end

end;

begin

п1хочетвойти := ложь;

п2хочетвойти := ложь;

parbegin

процессодин;

процессдва

parend

end.

Программа версии 3 (рис. 3) позволила решить одну задачу, однако сразу же появилась другая. Здесь взаимоисключение регулируется при помощи двух глобальных логических переменных (флагов-признаков) «п1хочетвойти» и «п2хочетвойти», которые принимают истинное значение перед попыткой входа в свой критический участок. Если каждый процесс перед переходом на цикл проверки будет устанавливать свой флаг, то каждый процесс будет обнаруживать, что флаг другого процесса установлен и будет бесконечно оставаться в цикле while. Эта версия программы может служить примером тупика для двух процессов. Главный недостаток этой программы это, то, что каждый из процессов может заблокироваться в своем цикле ожидания while. Нужно найти способ «разорвать» эти циклы.

program версиячетыре;

var п1хочетвойти, п2хочетвойти!_u_[_(: логический;

procedure процессодин;

begin

while истина do

begin

п1хочетвойти := истина;

while п2хочетвойти do

begin

п1хочетвойти := ложь;

задержка (случайная, несколькотактов);

п1хочетвойти := истина

end;

критическийучастокодин;

п1хочетвойти := ложь;

прочиеоператорыодин

end

end;

procedure процессдва;

begin

while истина do

begin

п2хочетвойти := истина;

while п1хочетвойти do

begin

п2хочетвойти := ложь;

задержка (случайная, несколькотактов);

п2хочетвойти := истина

end;

критическийучастокдва;

п2хочетвойти := ложь;

прочиеоператорыдва

end

end;

begin

п1хочетвойти := ложь;

п2хочетвойти := ложь;

parbegin

процессодин;

процессдва

parend

end.

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

1. На сколько сократится время откладывания?

2. Какой процесс активизируется?

3. Как очередность исполнения критического участка зависит от процедуры?

4. Какова реализация (программный код) этой процедуры?

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

program алгоритмДеккера;

var избранныйпроцесс: (первый, второй);

п1хочетвойти, п2хочетвойти: логический;

procedure процессодин;

begin

while истина do

begin

п1хочетвойти := истина;

while п2хочетвойти do

if избранныйпроцесс = второй then

begin

п1хочетвойти := ложь;

while избранныйпроцесс = второй do;

п1хочетвойти := истина

end

критическийучастокодин;

избранныйпроцесс := второй;

п1хочетвойти := ложь;

прочиеоператорыодин

end

end;

procedure процессдва;

begin

while истина do

begin

п2хочетвойти := истина;

while п1хочетвойти do

if избранныйпроцесс = первый then

begin

п2хочетвойти := ложь;

while избранныйпроцесс = первый do;

п2хочетвойти := истина

end

критическийучастокдва;

избранныйпроцесс := первый;

п2хочетвойти := ложь;

прочиеоператорыдва

end

end;

begin

п1хочетвойти := ложь;

п2хочетвойти := ложь;

избранныйпроцесс := первый;

parbegin

процессодин;

процессдва

parend

end.

Алгоритм Деккера исключает недостаток программы версии 4 – бесконечное откладывание входа в свой критический участок. Рассмотрим, как это делается. Процесс «п1» уведомляет о своем желании войти в свой критический участок, устанавливая свой флаг (п1хочетвойти := истина). Затем он переходит к циклу, в котором проверяет, не хочет ли также войти в свой критический участок и процесс «п2» (while п2хочетвойти do…). Если флаг «п2» не установлен т. е. п2хочетвойти = ложь, то «п1» пропускает тело цикла ожидания и входит в свой критический участок. Предположим, что «п1» при выполнении цикла проверки обнаруживает, что флаг «п2» установлен. Это заставляет «п1» войти в тело своего цикла ожидания. Здесь он анализирует значение переменной «избранный процесс» ( if избранныйпроцесс = второй then …), которая используется для разрешения конфликтов, возникающих в случае, когда оба процесса одновременно хотят войти в свой критический участок. Если избранным процессом является «п1», он пропускает тело своего цикла if и повторно выполняет цикл проверки (while п2хочетвойти do…) в ожидании момента, когда «п2» сбросит свой флаг. Если процесс «п1» определяет, что преимущественное право принадлежит процессу «п2», он входит в тело своего цикла if, где сбрасывает свой собственный флаг(п1хочетвойти := ложь), а затем блокируется в цикле ожидания, пока избранным процессом остается «п2». Сбрасывая свой флаг, «п1» дает возможность «п2» войти в свой критический участок. Со временем «п2» выйдет из своего критического участка и выполнит свой код «выходвзаимоисключения» Операторы этого кода обеспечат возврат преимущественного права процессу «п1» (избранныйпроцесс := первый) и сброс флага «п2» (п2хочетвойти := ложь). Теперь у «п1» появляется возможность выйти из внутреннего цикла ожидания while (while избранныйпроцесс = второй do;) и установить собственный флаг (п1хочетвойти := истина). Затем «п1» выполняет внешний цикл проверки (while п2хочетвойти do…). Если флаг «п2» (недавно сброшенный) по-прежнему сброшен, то «п1» входит в свой критический участок. Если, однако, «п2» сразу же пытается войти в свой критический участок, то его флаг будет установлен, и «п1» снова придется войти в тело внешнего цикла while. Однако на этот раз «бразды правления» находятся уже у процесса «п1», поскольку сейчас именно он является избранным процессом (напомним, что «п2», выходя из своего критического участка, установил для переменной «избранный процесс» значение «первый»). Поэтому «п1» пропускает тело условной конструкции if и многократно выполняет внешний цикл проверки, пока «п2» «смиренно» не сбросит собственный флаг, позволяя процессу «п1» войти в свой критический участок. Проблема бесконечного откладывания –разобраться самим.

Категория: Операционные системы | Добавил: Iron (04.08.2012)
Просмотров: 593 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Поиск

Статьи
[Менеджмент]
Факторы микросреды организации
[Операционные системы]
Диаграмма перехода процесса
[Устронение ошибок систем]
Сообщения об ошибках AMI BIOS (часть 2)
[Менеджмент]
Факторы микросреды организации
[Прогараммирование]
Как работает CSS?
[Информатика]
Кэш-память
[Операционные системы]
Особенности применения технологий Lotus Domino и Notes в современных информационных системах
[Прогараммирование]
ДОКУМЕНТИРОВАНИЕ ПРОГРАММ
[Устронение ошибок систем]
Устранение неполадок при возникновении (синего экрана) Blue Screen Of Death (BSOD) (2)
[Прогараммирование]
ПОДПРОГРАММЫ. ПРОЦЕДУРЫ И ФУНКЦИИ

Категории
Операционные системы [30]
Устронение ошибок систем [13]
Безопасность систем [9]
Прогараммирование [32]
Технологические [0]
Информатика [23]
Бухгалтерский учет [3]
Ценообразование [0]
Экономика [0]
Менеджмент [3]
Психология [0]
Разное [4]

Популярный софт
Iron Kaspersky Internet Security 2015
Kaspersky Internet Security 2015
Iron Virtual DJ
Virtual DJ
Iron SoundForge 11
SoundForge 11
Iron Alcohol 120
Alcohol 120
Iron Norton Internet Security 2014
Norton Internet Security 2014
Iron Loaris Trojan Remover
Loaris Trojan Remover

Жми

Copyright MyCorp © 2019Конструктор сайтов - uCoz