Здесь приведены последовательные хронологические версии программной реализации упомянутого алгоритма Деккера. Детальный анализ выполнения каждой из программ предлагается провести читателю. 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» войти в свой критический участок. Проблема бесконечного откладывания –разобраться самим.
