В. Столлингс - Операционные системы (1114679), страница 48
Текст из файла (страница 48)
",5.2.'В3АимОЙскшочения ффОГРА';„' Программный подход может быть реализован для параллельных про: которые выполняются как в однопроцессорной, так и в многопроцессо теме с разделяемой основной памятью. Обычно такие подходы предп элементарные взаимоисключения на уровне доступа к памяти ((1А также задачу 5.10) — т.е. одновременный доступ (чтение избили запись) и той же ячейке основной памяти упорядочивается при помощи неко ханизма (при этом порядок предоставления доступа не определяется поряд обращения процессов за доступом к памяти).
Никакой иной под ержки со ны аппаратного обеспечения, операционной системы или языка программ з них не предполагается ~дГоритм Деккера Дейкстра в 101*)К651 приводит алгоритм для взаимных исключений для ух процессов, предложенный голландским математиком Деккером (ВеЕЫег). Следуя Дейкстре, мы разработаем этот алгоритм постадийно. Главное преимущетво такого подхода — в демонстрации множества узких мест и возможных шибок при создании параллельно работающих программ. Первая попытка Как упоминалось ранее, любая попытка взаимного исключения должна опираться на некий фундаментальный механизм исключений аппаратного обес- печения.
Наиболее общим механизмом может служить ограничение, согласно которому к некоторой ячейке памяти в определенный момент времени может осуществляться только одно обращение. Воспользовавшись этим ограничением, зарезервируем глобальную ячейку памяти, которую назовем сигп. Процесс (РО или Р1), который намерен выполнить критический раздел, сначала проверяет содержимое ячейки памяти "цгп. Если значение ~цгг равно номеру процесса, то процесс может войти в критический раздел; в противном случае он должен ждать, постоянно опрашивая значение гцгп до тех пор, пока оно не позволит процессу войти в критический раздел.
Такая процедура известна как пережида- вие занятости (Ьцау юыЫпд), поскольку процесс вынужден, по сути, не делать ничего полезного до тех пор, пока не получит разрешение на вход в критический Раздел. Более того, он постоянно опрашивает значение переменной и тем самым потребляет процессорное время. После того как процесс, получивший право на вход в критический раздел, выходит из него по завершении работы, он должен обновить значение г.цгп, присвоив ему номер другого процесса.
Говоря Формально, имеется глобальная переменная 1п~ гцгп На Рис, 5.1,а показана программа для двух процессов. Это решение гаранРу т корректную работу взаимоисключения, однако имеет два недостатка. Во- первых и х при входе в критический раздел процессы должны строго чередоваться; тем самы мым ~корость работы диктуется более медленным из двух процессов. Если процессу РО О вход в критический раздел требуется раз в час, а процессору Р1— вторых, „, Раз в час, то темп работы Р1 будет таким же, как и у процесса РО.
Вогораздо более серьезная ситуация возникает в случае сбоя одного из Роцессов — при этом второй процесс оказывается заблокирован (при этом не- а4~во, и Роисходит ли сбой процесса в критическом разделе или нет) Описан ~энная конструкция представляет собой сопрограмму (согои$1пе). Со- Рогра~ - ы Разрабатываются таким образом, чтобы быть способными передавать Равление е друг другу. Однако хотя эта технология структурирования и весьма езна для отдельно взятого процесса, для поддержки параллельных вычисле"а не подходит. Часть 2.
аРаллальныю вычисления 933имоиоклиъчяян Вторая попытка /+ Процесс 1 +/ 'в Ф и);11е (оцгд ! = 1) У НичеГО не Делаем "'/у,. /" Критический раздел /» ГОГд =. 0; '% /~ Процесс О Я/ Проблема при первой попытке заключается в том, что в ней хранилось имя щ)о онесса, который имел право входа в критический раздел, в то время как в дейнтельности нам требуется информация об обоих процессах. По сути, каждый деес должен иметь собственный ключ к критическому разделу, так что если -кс Гроизойдет сбой одного процесса, второй все равно сможет получить доступ к . Итическому разделу.
Для удовлетворения этого условия определен логический -тор ! 1ад, в котором ~1аО(0) соответствует процессу РО, а й1ас.(1) — процессу Каждый процесс может ознакомиться с флагом другого процесса, но не может о изменить. Когда процессу требуется войти в критический раздел, он периоди„ски проверяет состояние флага другого процесса до тех пор, пока тот не примет знэченпе 1а1эе, указывающее, что другой процесс покинул критический раздел. Процесс немедленно устанавливает значение своего собственного флага равным ~где и входит в критический раздел.
По выходе из критического раздела процесс сбрасывает свой флаг, присваивая ему значение ~Гце. Теперь разделяемые переменные выглядят следующим образом: ~о~1 1е (сцгд . О) /* НичеГО не делаем */, ~* коитический раздел СОГД-- а) Первая попытка /» Процесс 0 +/ /* Процесс 1 */ 7:: ж1 11е ~Й1ао ~ О) ) /* НичеГО не делзем */Г Г) ЗЯ (1) = Ггце; *"е /* Критическии раздел "/; Ф, 11ас(1) = йа1эе; еч).«) е (й1зс (1) ) НичеГО не деласм */~ )аО(0) = Г.гце; Критический раздел */; 1'1ао(О) = Га1эе; езде ЬОО1езд ( ~а1эе = 0 ЬОО1енл Г1зд(2) = ( 1з1эе Этот алгоритм показан на рис. 5.1,б. Теперь если произойдет сбой одного из процессов вне критического раздела (включая код установки значения Флага), то второй процесс заблокирован не будет.
Этот второй процесс в таком случае сможет входить в критический раздел всякий раз, как только это потребуется, поскольку флаг другого процесса всегда будет иметь значение 1а1эе. Однако если сбой произойдет в критическом разделе (или перед входом в критический раздел, но после установки значения флага равным ГГОе), то другой процесс окажется навсегда заблокированным. Описанное решение, по сути, оказывается еще хуже предложенного ранее„ поскольку даже не гарантирует взаимного исключения. Рассмотрим такую последовательность действий: 10 выполняет инструкцию НМ1е и находит, что значение й1зд (1) равно йа1эе; ~1 выполняет инструкцию и)-.11е и находит, что значение Г 1зЧ (01 равно Га1эе; РО устанавливает значение ~1аа ( О) равным огне и входит в критический раздел; Р1 1 устанавливает значение ~1ао (1) равным ~ГОе и входит в критический раздел.
Поскольку после этого оба процесса одновременно оказываются в критическом ом разделе, программа некорректна. Проблема заключается в том, что предложен женное решение не является независимым от относительной скорости выполнен ния процессов„ 6) Вторая попытка /* Процесс 0 */ /* Процесс 1 я/ Э Х1аЧ (О) = Огнева ил11е (11зЯ(1) ) /* ничеГО не делаем "/' /" К)лГУический рзздел */г ~)ас(О) = 1а1эе; Г1ао(1) = ~гне; и'ГН11е (11ас (О) ) НичеГО не делзж4 * ° .'..
/* Критический разДел / ° Й1ас(1) =- Йз1зе; 'в) 'Третья попытка, /* Процесс 0 +/ /* Процесс 1 */ 11зс(0) = Г.ГОе; НЬ11е (11аЧ((1) ) ( е1ас( (1) /* Ээ держка * / ~1ас (1) е1аб [О) = 1а1эе; /" Эадержка П.зо(0) = Огне; / Критический разДел /ю Й1зо(0) = 1з1зе; /* Критический раздел +/> Й1ая(1) = 1а1эе; Ф .и (г/ Четвертая попытка рис. Б.1. Попытки взаимных исключений ретья попьггка оскольку процесс может изменить свое состояние после того, как другой ~р цесс ц сс ознакомится с ним, но до того, как этот другой процесс войдет в кри.. удастс '"" раздел, вторая попытка также оказалась неудачной. Возможно, нам . ~~ого я выправить ситуацию внесением в код небольшого изменения, показания рнс Как поч~ "к и ранее, если происходит сбой одного процесса в критическом разделе, аа код установки значения флага, то второй процесс окажется заблокиро- Часть 2.
о Параллельные вычисления: взаимоисключения... .ым (и соответс тственио если сбой произойдет вне критического ра Э й процесс блокирован не будет). Далее провер« им гарантированность взаимоисключения, проследив ом РО. После того как процесс РО установит й1ад(0) равным г.г««е,", ет войти в критический раздел до тех пор, пока туда не войдет и за «нет его процесс есс РО. Может оказаться так, что процесс Р1 уже на)«о: Гическом разд зделе в тот момент когда РО устанавливает свой флаг. 1 ~ае процесс РО будет заблокирован инструкцией иг.11е до тех пор, до «нет критическ ческий раздел. Аналогичные действия происходят при ра процесса Р1. М- Тем самым гарантируется взаимное исключение", однако третья ц9 зждает еще од ° дну проблему.
Если оба процесса установят значения «ыми свое до ог, того как один из них выполнит инструкцию иЬ11е, из процессов будет считать, что другой находится в критическом самым осуществится взаимоблокировка. Четвертая попытка В третьей попытке установка процессом флага состояния выполи та информации о состоянии другого процесса. Взаимоблокировка той причине, что каждый процесс мог добиваться своих прав на вхояг. еский раздел и отсутствовала возможность отступить назад из им ожения.
Можно попытаться исправить ситуацию, делая процес тупчивыми": каждый процесс, устанавливая свой флаг равным т.г««Е,':. т о своем желании войти в критический раздел, но готов отложить с упая другому процессу, как показано на рис. 5.1,г. Это уже совсем близко к корректному решению, хотя все еще илмоисключение гарантируется (в чем можно убедиться, применяя те." «дения, что и при третьей попытке), однако рассмотрим возможную ельность событий: устанавливает значение Е1аЧ (01 равным гг««е; устанавливает значение й1ад11) равным т.где,' проверяет ~1ад11.); проверяет Й1ад(О); устанавливает значение 11аа101 равным Га1эе; 'ф устанавливает значение й1ад (11 равным йа1эе; устанавливает значение 11ад10) равным ~где; устанавливает значение ~1ао(11 равным ггые.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
