Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 97
Текст из файла (страница 97)
Модель базового вычисления и постановка задачиРассмотрим множество процессов Р, выполняющих б а з о в о е в ы ч и с л е н и е ; мыне будем касаться здесь их предназначения и принципов функционирования. Всякий процесс может быть вынужден приостановить свое локальное вычисление,если необходимо дождаться сообщений от других процессов; это моделируетсязаменой состояния a c t i v e на состояние b lo c k e d .Когда процесс р становится заблокированным (действие Вр в алгоритме 10.7)„он отправляет сообщение-запрос семейству процессов, которое мы будем обозначать символом R eq S p .
Чтобы снова стать активным (действие Fp), процесс рдолжен получить разрешение от каких-либо процессов семейства R e q s p , но необязательно от всех сразу. Подмножество семейства R e q s p , получения разрешения от которых достаточно, чтобы процесс р стал вновь активным, образуютвсе те процессы, которые удовлетворяют предикату F reep .
Запросы, полученныепроцессом р (действие Rp), образуют множество P e n d p , и процесс р откликнетсяна них, как только станет активным (действие Gp). К каждому запросу и разрешению прикрепляется номер запроса, проставленный процессом р , которыйпозволяет отбросить разрешения, отправленные в ответ на устаревшие запросы(см. Fp).Мы покажем на нескольких примерах, как применяется условие F reep . Вопервых, если р требует отклика на все сообщения-запросы, то F reep будет истинно только на множестве R e q s p . Во-вторых, если процессу р достаточно одного-10.4. Приложения: обнаружение тупиковvar s t a t e pVp: (a c t i v e , b lo c k e d ): integerR eqspG rantpP endpFreep: set of processes ;: set of processes ;: set of requests: predicate ;367init a c t i v e ;init 0 ;(* Номер запроса *)init0;(*(*(*(*Множество запросов *)Полученные разрешения *)Ожидаемые разрешения *)Ограничения освобождения *)Вp.
{ s t a t e p = a c t i v e }begin определить R e q s p и Freep ; vp := vp + 1 ;forall q € R e q s p do send (req, v p) to q ;G r a n t p := 0 ; s t a t e P := b l o c k e dendR,,,: { Сообщение (req, v) доставлено от q }begin receive (req, v) from q ; P e n d p :=O p:PendpU {{q, v ) } end{ s t a t e p = a c t i v e Л (q, v) € P e n d p }v) to q ; P e n d p := P e n d p \ {{q, ti)} endbegin send (grant,F^: { Сообщение (grant, v) доставлено от q }begin receive (grant, v) from q ;if s t a t e p = b l o c k e d and v = vp thenbegin G r a n t p := G r a n tp U { q } ;if Freep ( G r a n t p ) then s t a t e p := a c t i v eendendАлгоритм 10.7.
Базовый алгоритмединственного разрешения, то Freep будет истинно на всяком непустом множестве. И, наконец, в-третьих, предположим, что процессу р необходимо 1000 мегабайт свободной памяти и он отправляет запрос дискам А (с 900 мегабайтамисвободной памяти), В (с 600 мегабайтами свободной памяти), С (с 300 мегабайтами свободной памяти) и D (с 100 мегабайтами свободной памяти). Если процессудоступен диск А, а также любой другой диск, то р может продолжить вычисление.
Процесс р может продолжить вычисление и в том случае, когда доступныдиски В, С и D. Такой предикат Freep(S) можно выразить формулой(#S>2AH eS)V(#S^3).Один и тот же процесс р может использовать разные варианты предикатаFreep, освобождающие процесс от разных блокировок, но всякий раз при этомдолжны быть соблюдены следующие условия.D1. Утверждение Freep(0) всегда ложно, a Freep(Reqsp) всегда истинно.D2. Если выполняется утверждение Freep(A) и А СВ, то выполняется и утверждение Freep(B).368Гл. 10.
Моментальные состояния системыСогласно условию D 1 процесс р не может стать активным, не получив никакого разрешения, и обязательно становится активным при получении разрешенияот всех процессов из множества R e q s p . Согласно условию D2 процесс р имеетправо стать активным, если полученный им набор разрешений включает в себякакой-либо минимально необходимый набор разрешений.Пусть задан базовый алгоритм; тогда мы можем дать следующее определениетаким понятиям, как мертвый процесс и тупиковая конфигурация.Определение 10.13. Процесс р называется д е й с т в у ю щ и м в конфигурации у, если существует такая конфигурация 8 , достижимая из у, в которой процесс р активен; процесс р считается м е р т в ы м , если он не является действующим.Конфигурация у называется т у п и к о в о й к о н ф и г у р а ц и е й , если она содержитмертвый процесс.Свойство конфигурации быть тупиковой — это у с т о й ч и в о е свойство; еслипроцесс р стал мертвым в конфигурации yi и yiуг, то он остается мертвыми в конфигурации уг.
Последовательность событий базового вычисления, в результате осуществления которой система переходит из конфигурации у в конфигурацию 8 , называется п р о д о л ж е н и е м базового вычисления из у в 8 .Задача обнаружения тупиков состоит в разработке контрольного алгоритма,который можно было бы совместить с базовым вычислением так, чтобы при этомсоблюдались следующие три условия.1. Н е в м е ш а т е л ь с т в о . Контрольный алгоритм не оказывает влияния на базовое вычисление.2.
П о л н о т а . Если образуется тупиковая ситуация, то она будет обнаруженаконтрольным алгоритмом.3. К о р р е к т н о с т ь . Алгоритм обнаруживает тупиковую ситуацию только тогда, когда она действительно сложилась.По ходу работы контрольному алгоритму может понадобиться провести обмен дополнительными сообщениями— мы будем называть их к о н т р о л ь н ы м ис о о б щ е н и я м и , — которые могут быть отправлены как активными, так и заблокированными процессами. Помимо доклада о возникновении тупиковой ситуации,от контрольного алгоритма обычно требуется также указать один или несколькомертвых процессов, используя которые можно было бы устранить этот тупик.10.4.2. Алгоритм глобальной разметкиВ этом параграфе мы предлагаем алгоритм, который называется а л г о р и т для обнаружения тупиков и выявления всех мертвыхпроцессов.
Этот алгоритм постоянно вычисляет моментальные состояния системы и применяет к соответствующим им конфигурациям процедуру 10.8. В этойпроцедуре значения s t a t e * , v* , R e q s * , G r a n t* , P e n d * , Free* и (s e n t* p \ rcud*qp)считаются заданными константами (они вычисляются алгоритмом построения моментального состояния). В алгоритме 10.8 для выявления действующих процессов моделируется обмен разрешениями и освобождения процессов в продолжении вычисления из конфигурации у*.мом глобальной р а зм ет ки ,36910.4. Приложения: обнаружение тупиковПеременной a l i v e p первоначально присвоено значение f a l s e , но, как толькопроцесс р обнаружит, что он является действующим в рассматриваемом моментальном состоянии, это значение будет изменено на tr u e .
Это происходит в томслучае, когда р пребывает в активном состоянии в данном моментальном состоянии системы, а также если множество сообщений (grant, v* ) и (Alive), полученных к этому моменту, удовлетворяют предикату Free*p . Переменная G rR e c p сохраняет множество разрешений (для текущего запроса), которые либо уже былиполучены, либо находятся на этапе пересылки в заданном моментальном состоянии системы, а также сообщения (Alive), которые были получены процессом р .var alive: boolinit false ;GrRec : set of P init Grantf U {q : (grant,v p) e sent*qp \ rcvd*qp};M pi* Начать разметку в активном процессе *){ - 1alivep Л (statef=active Vbegin alivep := true ;forall q € Pendf, U {q : (req,do send (Alive) to qendFree*p (G rRecp)) }v) e (s e n t qp \rcvdqp)}Pp:(* Распространить разметку на освобожденные процессы *){ Ап (Alive) message arrives from q }begin receive (Alive) from q ; GrRecp := GrRecp U {q} ;if not alivep and Free*p(GrRecp) thenbegin alivep := true ;forall q € Pendf, U {q : (req, v) € (sentqp \ rcvdqp)}do send (Alive) to qendendАлгоритм 10.8.
Алгоритм глобальной разметкиТеорема 10.14. А л г о р и т м г л о б а л ь н о й р а з м е т к и в с е г д а з а в е р ш а е т с в о юр а б о т у , и п о с л е з а в е р ш е н и я п е р е м е н н а я a l i v e p и м е е т з н а ч е н и е tr u e в т о ми т олько т ом случае, ко гд а процесс р я вля ет ся дейст вую щ им в к о н ф и гу р а ц и и у*.Д о к а з а т е л ь с т в о . Процесс р присваивает значение tr u e переменной(и отправляет сопутствующие этому сообщения (Alive)) не более одногораза, и поэтому проводится обмен лишь конечным числом сообщений.Алгоритм разметки моделирует возможные продолжения вычислений базового алгоритма, начинающиеся из конфигурации у*, причем активными становятсялишь те процессы, у которых переменной a liv e присваивается значение tr u e ,а сообщениями-разрешениями служат сообщения (Alive).
В моделируемом продолжении вычисления всякий процесс немедленно отправляет разрешение всемотложенным запросам, как только становится активным. Процесс р , выполняюa liv e p370Гл. 10. Моментальные состояния системыщий действие м р, является активным в конфигурации у*. Этот процесс можеттакже стать активным в результате получения одного из тех сообщений, которыев конфигурации у* пребывают на этапе пересылки, и поэтому в этих случаях онсчитается действующим в у*. Процесс р, присвоивший переменной aliveр значение true в результате выполнения действия Рр, также становится активнымв моделируемом продолжении вычисления, так как он получил разрешающее сообщение, которое было отправлено в этом продолжении; и это также означает,что процесс является действующим в у*.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
