Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 58
Текст из файла (страница 58)
Действительно, возможна ситуация, когда оба процесса одновременно установят свои флагив значение true и войдут в бесконечный цикл. В этом случае будет нарушено требование отсутствия бесконечного ожидания входа в свою критическую секцию. Тоесть, предположив, что скорости исполнения процессов произвольны, мы получили такую последовательность событий, при которой процессы вообще перестанутнормально выполняться.Все рассмотренные попытки решить задачу взаимного исключения при выполнении критических секций иллюстрируют нам некоторые тонкие моменты, лежащие в основе этой проблемы, и показывают, что не все так просто.Последний рассматриваемый вариант решения задачи взаимного исключения,опирающийся только на блокировку памяти, — это известный алгоритм, предложенный математиком Деккером.Алгоритм ДеккераАлгоритм Деккера основан на использовании трех переменных (листинг 7.4): перекл1, перекл2 и ОЧЕРЕДЬ.
Пусть по-прежнему переменная перекл1 устанавливается в true тогда, когда процесс ПР1 хочет войти в свою критическую секцию (дляПР2 аналогично), а значение переменной ОЧЕРЕДЬ указывает, чье сейчас право сделать попытку входа при условии, что оба процесса хотят выполнить свои критические секции.Листинг 7.4.
Алгоритм Деккераlabel 1. 2;varперекл1. перекл2: boolean;ОЧЕРЕДЬ : integer;Begin nepe^l:=false: nepew2:=false:ОЧЕРЕДЬ:=1;Parbeginwhile true dobegin перекл!: =true;продолжение&220Глава 7. Организация параллельных взаимодействующих вычисленииЛистинг 7.4 (продолжение)1: if перекл2=1гие thenif 0ЧЕРЕДЬ=1 then go to 1else begin nepewil:=false;while 0ЧЕРЕДЬ=2 dobeginendendelse beginCS1 { критическая секция ПР1 }ОЧЕРЕДЬ: =2; nepeiuil:=falseendendandwhile true dobegin перекл2:=1;2: if rtepeitfil=true thenif 0ЧЕРЕДЬ=2 then go to 2else begin nepeiui2:=false;while 0ЧЕРЕДЬ=1 dobeginendendelse begn'nCS2 { критическая секция ПР2 }ОЧЕРЕДЬ:=1: перекл2-falseendendpa rendend.Если перекл2 = true и перекл1 = false, то выполняется критическая секция процесса ПР2 независимо от значения переменной ОЧЕРЕДЬ.
Аналогично для случая перекл2 = false и перекл1 = true.Если же оба процесса хотят выполнить свои критические секции, то есть перекл2 == true и перекл1 = true, то выполняется критическая секция того процесса, на который указывает значение переменной ОЧЕРЕДЬ, независимо от скоростей развитияобоих процессов. Использование переменной ОЧЕРЕДЬ совместно с переменнымиперекл1 и перекл2 в алгоритме Деккера позволяет гарантированно решать проблему критических секций. То есть переменные перекл1 и перекл2 гарантируют, чтовзаимное выполнение не может иметь места; переменная ОЧЕРЕДЬ гарантирует, чтоне может быть взаимной блокировки, так как переменная 04 ЕРЕДЬ не меняет своего значения во время выполнения программы принятия решения о том, кому жесейчас проходить свою критическую секцию.Тем не менее реализаций критических секций на основе описанного алгоритмапрактически не встречается из-за их чрезмерной сложности, особенно тогда, когдтребуется обобщить алгоритм Деккера с двух до N процессов.Синхронизация процессов с помощью операциипроверки и установкиОперация проверки и установки является, так же как и блокировка памяти, од№ из аппаратных средств, которые могут быть использованы для решения задачи в I,,пйаства С И нхронизации и связи взаимодействующих процессов221того исключения при выполнении критической секции.
Данная операция реа"изована во многих компьютерах. Так, в знаменитой машине IBM 360 (370) этаоманда называлась TS (Test and Set — проверка и установка). Команда TS являетдвухадресной (двухоперандной). Ее действие заключается в том, что процессоряприсваивает значение второго операнда первому, после чего второму операндуприсваивается значение, равное единице.
Команда TS является неделимой операцией, то есть между ее началом и концом не могут выполняться никакие другиекоманды.Чтобы использовать команду TS для решения проблемы критической секции, свяжем с ней переменную common, которая будет общей для всех процессов, использующих некоторый критический ресурс. Данная переменная будет принимать единичное значение, если какой-либо из взаимодействующих процессов находитсяв своей критической секции.
Кроме того, с каждым процессом свяжем свою локальную переменную, которая принимает значение, равное единице, если данныйпроцесс хочет войти в свою критическую секцию. Операция TS будет присваиватьзначение common локальной переменной и устанавливать common в единицу. Соответствующая программа решения проблемы критической секции на примере двухпараллельных процессов приведена в листинге 7.5.Л и с т и н г 7 .
5 . Взаимное исключение с помощью операции проверки и установкиvaг common, l o c a l l , I o c a l 2 : i n t e g e r ;begincommon:=0;parbeginПР1: w h i l e t r u e dobeginlocal1:-1:w h i l e l o c a l 1=1 do TSOocall.common);CS1; { критическая секция процесса ПР1 }common;=0;PR1; { ПР1 после критической секции }endandПР2: w h i l e t r u e dobeginlocal2:=l:w h i l e l o c a l 2 = l do TS(local2.common);CS2; { критическая секция процесса ПР2 }common:=0;PR2; { ПР2 после критической секции }endparendend.Редположим, что первым хочет войти в свою критическую секцию процесс ПР1.' э т ° м случае значение LocaLl сначала установится в единицу, а после цикла проб к и с помощью команды TS(locall,common) — в нуль.
При этом значение commonанет равным единице. Процесс ПР1 войдет в свою критическую секцию. Послеполнения критической секции переменная common примет значение, равноею, что даст возможность второму процессу ПР2 войти в свою критическую сек-222Глава 7. Организация параллельных взаимодействующих вычисли -Безусловно, мы предполагаем, что в компьютере реализована блокировка па.мятто есть операция common := 0 неделима. Команда проверки и установки зиачител 'но упрощает решение проблемы критических секций. Главная черта этой команды — ее неделимость.Основной недостаток использования команд типа проверки и установки состоит Rследующем: находясь в цикле проверки переменной common, процессы впустуюпотребляют время центрального процессора и другие ресурсы.
Действительно, ее аипредположить, что произошло прерывание процесса ПР1 во время выполнениясвоей критической секции в соответствии с некоторой дисциплиной обслуживания, и начал выполняться процесс ПР2, то он войдет в цикл проверки, впустуютратя процессорное время. В этом случае, до тех пор пока диспетчер супервизоране поставит на выполнение процесс ПР1 и не даст ему закончиться, процесс ПР2не сможет войти в свою критическую секцию.В микропроцессорах архитектуры ia32, с которыми мы теперь сталкиваемся постоянно, работая на персональных компьютерах, имеются специальные командыВТС, BTS, BTR, которые как раз и являются вариантами реализации команды проверки и установки. Рассмотрим одну из них — BTS.Команда BTS (Bit Test and Reset — проверка и установка бита) является двухадресной [20].
По этой команде процессор сохраняет значение бита из первого операндасо смещением, указанным вторым операндом, во флаге CF (Carry Flag — флаг переноса) 1 регистра флагов, а затем устанавливает указанный бит в 1. Значение индекса выбираемого бита может быть представлено постоянным непосредственнымзначением в команде BTS или значением в общем регистре. В этой команде используется только 8-разрядное непосредственное значение. Значение этого операндаберется по модулю 32, таким образом, смещение битов находится в диапазоне от 0до 31. Это позволяет выбрать любой бит внутри регистра. Для битовых строк впамяти это поле непосредственного значения дает только смещение внутри словаили двойного слова.С учетом изложенного можно привести фрагмент кода, в котором данная командаиспользуется для решения проблемы взаимного исключения (листинг 7.6).Л и с т и н г 7 .
6 . Фрагмент программы с критической секцией на ассемблереL:ВТС М ЛJC L; критическая секцияAND M.OBОднако здесь следует заметить, что некоторые ассемблеры поддерживают значения битовых смещений больше 31, используя поле непосредственного зна1Располагается в слове состояния программы.с т в асинхронизации и связи взаимодействующих процессов223мбинации с полем смещения операнда в памяти.
В этом случае младшие 3 или\ битов (3 - для 16-разрядных операндов, 5 - для 32-разрядных операндов), опл я ю Щ И е смещение бита (второй операнд команды), сохраняются в поле не* педственного операнда, а старшие биты сдвигаются и комбинируются с полемП°ешения. Процессор же игнорирует ненулевые значения старших битов поля вто•о операнда [20]. При доступе к памяти процессор обращается к четырем байтам\ я 32-разрядного операнда), начинающимся по полученному следующим образом адресу:Effective Address + (4 х (BitOffset DIV 32))Либо (для 16-разрядного операнда) процессор обращается к двум байтам, начинающимся по адресу:Effective Address + (2 х (BitOffset DIV 16))Такое обращение происходит, даже если необходим доступ только к одному байту.Поэтому избегайте ссылок к областям памяти, близким к «пустым» адресным пространствам.
В частности, избегайте ссылок на распределенные в памяти регистрыввода-вывода. Вместо этого используйте команду M0V для загрузки и сохранениязначений по таким адресам и регистровую форму команды BTS для работы с данными.Несмотря на то, что и алгоритм Деккера, основанный только на блокировке памяти, и операция проверки и установки пригодны для реализации взаимного исключения, оба эти приема очень неэффективны. Всякий раз, когда один из процессоввыполняет свою критическую секцию, любой другой процесс, который пытаетсявойти в свою критическую секцию, попадает в цикл проверки соответствующихпеременных-флагов, регламентирующих доступ к критическим переменным. Притаком неопределенном пребывании в цикле, которое называется активным ожиданием, напрасно расходуется процессорное время, поскольку процесс имеет доступ к тем общим переменным, которые и определяют возможность или невозможность входа в критическую секцию.
При этом процесс отнимает ценное времяцентрального процессора, на самом деле ничего реально не выполняя. Как результат мы получаем общее замедление работы вычислительной системы.До тех пор пока процесс, занимающий в данный момент критический ресурс, нерешит его уступить, все другие процессы, ожидающие этого ресурса, могли бы вообще не конкурировать за процессорное время. Для этого их нужно перевести всостояние ожидания (заблокировать).
Когда вход в критическую секцию сновасвободится, можно будет опять перевести заблокированный процесс в состояниеоговности к выполнению и дать ему возможность получить процессорное время.амьщ простой способ предоставить процессорное время только одному вычистельному процессу — отключить систему прерываний, поскольку тогда никакоееШнее событие не сможет прервать выполняющийся процесс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
