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