Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно).pdf), страница 97

Согласно рассматриваемому алгоритму выполняется P( ∗). По теореме 10.10 имеет место соотношение ∗e , и поскольку переменная detect получила значение true после. В силу устойчивозавершения построения ∗ , имеет место соотношение eсти свойства P будет верно P( ).4. Наличие «мусора». В объектно-ориентированной среде программирования создается совокупность объектов, каждый из которых может содержатьссылку на другие объекты. Объект считается доступным, если можно отыскать путь, ведущий по ссылкам к данному объекту от некоторого предписанногообъекта; в противном случае объект объявляется «мусором». Ссылки могут появляться и исчезать, но ссылки, ведущие к «мусорным» объектам, никогда невозникают.

Поэтому, как только объект становится «мусором», он будет во векивечные оставаться таковым. (Проблеме сборки «мусора» посвящено изрядноеколичество работ, но в этой книге она не рассматривается. Читатель, интересующийся этой задачей, может обратиться к работе [189] и воспользоваться спискомлитературы из указанной работы.)Чтобы выполнить предписанные действия, как только предикат P стал истинным, его истинность нужно обнаружить посредством вспомогательного алгоритма, который следит за вычислением и запускает нужные действия, когдаобнаружит истинность предиката P.364366Гл. 10. Моментальные состояния системы=⇒ f( ) 6 f( ).зывается монотонной, если выполняется соотношениеЕсли вычислено моментальное состояние системы ∗ и проведена оценка f ∗ == f( ∗), то для всех последующих конфигураций будет выполняться неравенство f( ) > f∗ . Примером монотонной функции может служить глобальное виртуальное время (GVT) в распределенном дискретном симуляторе событий (см.,например, [187, гл.

4] или [49]).10.4. Приложения: обнаружение тупиковВ некоторых распределенных программах процессы могут время от временибыть заблокированы в ожидании сообщений от других процессов. Примерамимогут служить транзакции в базах данных, а также процессы, состязающиесяза право доступа к ресурсам. Тупиковые ситуации, если таковые случаются и неразрешаются должным образом, таят серьезную опасность для распределенныхсистем, понижая их производительность и сокращая область применения. Прежде всего, процессы, вовлеченные в тупиковую ситуацию, никогда не смогут завершить выполнение своей задачи, и, кроме того, ресурсы, занятые этими процессами, уже никогда не будут доступны другим процессам.

Понятно, что грамотнаяобработка тупиковых ситуаций чрезвычайно важна для реализации распределенных систем10.4.1. Модель базового вычисления и постановка задачиРассмотрим множество процессов P, выполняющих базовое вычисление ; мыне будем касаться здесь их предназначения и принципов функционирования.

Всякий процесс может быть вынужден приостановить свое локальное вычисление,если необходимо дождаться сообщений от других процессов; это моделируетсязаменой состояния active на состояние blocked.Когда процесс p становится заблокированным (действие B p в алгоритме 10.7),,он отправляет сообщение-запрос семейству процессов, которое мы будем обозначать символом Reqsp . Чтобы снова стать активным (действие Fp), процесс pдолжен получить разрешение от каких-либо процессов семейства Reqsp , но необязательно от всех сразу.

Подмножество семейства Reqs p , получения разрешения от которых достаточно, чтобы процесс p стал вновь активным, образуютвсе те процессы, которые удовлетворяют предикату Free p . Запросы, полученныепроцессом p (действие Rp), образуют множество Pendp , и процесс p откликнетсяна них, как только станет активным (действие G p). К каждому запросу и разрешению прикрепляется номер запроса, проставленный процессом p, которыйпозволяет отбросить разрешения, отправленные в ответ на устаревшие запросы(см. Fp).Мы покажем на нескольких примерах, как применяется условие Free p . Вопервых, если p требует отклика на все сообщения-запросы, то Freep будет истинно только на множестве Reqsp . Во-вторых, если процессу p достаточно одного-10.4. Приложения: обнаружение тупиковvar statepvpReqspGrantpPendpFreep::::::(active, blocked)integerset of processes ;set of processes ;set of requestspredicate ;init active ;init 0 ;(*(*(*init ∅ ;(*(*367Номер запроса *)Множество запросов *)Полученные разрешения *)Ожидаемые разрешения *)Ограничения освобождения *)Bp : { statep = active }begin определить Reqsp и Freep ; vp := vp + 1 ;forall q ∈ Reqsp do send hreq, vp i to q ;Grantp := ∅ ; statep := blockedendRp : { Сообщение hreq, vi доставлено от q }begin receive hreq, vi from q ; Pendp := Pendp ∪ { (q, v) } endGp : { statep = active ∧ (q, v) ∈ Pendp }begin send hgrant, vi to q ; Pendp := Pendp \ { (q, v) } endFp : { Сообщение hgrant, vi доставлено от q }begin receive hgrant, vi from q ;if statep = blocked and v = vp thenbegin Grantp := Grantp ∪ {q} ;if Freep (Grantp) then statep := activeendendАлгоритм 10.7.

Базовый алгоритмединственного разрешения, то Freep будет истинно на всяком непустом множестве. И, наконец, в-третьих, предположим, что процессу p необходимо 1000 мегабайт свободной памяти и он отправляет запрос дискам A (с 900 мегабайтамисвободной памяти), B (с 600 мегабайтами свободной памяти), C (с 300 мегабайтами свободной памяти) и D (с 100 мегабайтами свободной памяти). Если процессудоступен диск A, а также любой другой диск, то p может продолжить вычисление. Процесс p может продолжить вычисление и в том случае, когда доступныдиски B, C и D. Такой предикат Freep (S) можно выразить формулой(#S > 2 ∧ A ∈ S) ∨ (#S > 3).Один и тот же процесс p может использовать разные варианты предикатаFreep , освобождающие процесс от разных блокировок, но всякий раз при этомдолжны быть соблюдены следующие условия.D1.

Утверждение Freep (∅) всегда ложно, а Freep (Reqsp) всегда истинно.D2. Если выполняется утверждение Freep (A) и A ⊆ B, то выполняется и утверждение Freep (B).368Гл. 10. Моментальные состояния системы10.4. Приложения: обнаружение тупиковСогласно условию D1 процесс p не может стать активным, не получив никакого разрешения, и обязательно становится активным при получении разрешенияот всех процессов из множества Reqsp .

Согласно условию D2 процесс p имеетправо стать активным, если полученный им набор разрешений включает в себякакой-либо минимально необходимый набор разрешений.Пусть задан базовый алгоритм; тогда мы можем дать следующее определениетаким понятиям, как мертвый процесс и тупиковая конфигурация.Определение 10.13. Процесс p называется действующим в конфигурации , если существует такая конфигурация , достижимая из , в которой процесс p активен; процесс p считается мертвым, если он не является действующим.Конфигурацияназывается тупиковой конфигурацией, если она содержитмертвый процесс.Свойство конфигурации быть тупиковой — это устойчивое свойство; еслипроцесс p стал мертвым в конфигурации 1 и 12 , то он остается мертвыми в конфигурации 2 . Последовательность событий базового вычисления, в результате осуществления которой система переходит из конфигурации в конфигурацию , называется продолжением базового вычисления из в .Задача обнаружения тупиков состоит в разработке контрольного алгоритма,который можно было бы совместить с базовым вычислением так, чтобы при этомсоблюдались следующие три условия.1.

Невмешательство. Контрольный алгоритм не оказывает влияния на базовое вычисление.2. Полнота. Если образуется тупиковая ситуация, то она будет обнаруженаконтрольным алгоритмом.3. Корректность. Алгоритм обнаруживает тупиковую ситуацию только тогда, когда она действительно сложилась.По ходу работы контрольному алгоритму может понадобиться провести обмен дополнительными сообщениями— мы будем называть их контрольнымисообщениями,— которые могут быть отправлены как активными, так и заблокированными процессами. Помимо доклада о возникновении тупиковой ситуации,от контрольного алгоритма обычно требуется также указать один или несколькомертвых процессов, используя которые можно было бы устранить этот тупик.369Переменной alivep первоначально присвоено значение false, но, как толькопроцесс p обнаружит, что он является действующим в рассматриваемом моментальном состоянии, это значение будет изменено на true.

Это происходит в томслучае, когда p пребывает в активном состоянии в данном моментальном состоянии системы, а также если множество сообщений hgrant, v ∗p i и hAlivei, полученных к этому моменту, удовлетворяют предикату Free ∗p . Переменная GrRecp сохраняет множество разрешений (для текущего запроса), которые либо уже былиполучены, либо находятся на этапе пересылки в заданном моментальном состоянии системы, а также сообщения hAlivei, которые были получены процессом p.var alive : boolinit false ;GrRec : set of P init Grant∗p ∪ {q : hgrant, vp i ∈ sent∗qp \ rcvd∗qp } ;Mp :(* Начать разметку в активном процессе *){ ¬alivep ∧ (state∗p = active ∨ Free∗p (GrRecp)) }begin alivep := true ;forall q ∈ Pend∗p ∪ {q : hreq, vi ∈ (sent∗qp \ rcvd∗qp) }do send hAlivei to qendPp : (* Распространить разметку на освобожденные процессы *){ An hAlivei message arrives from q }begin receive hAlivei from q ; GrRecp := GrRecp ∪ {q} ;if not alivep and Free∗p (GrRecp) thenbegin alivep := true ;forall q ∈ Pend∗p ∪ {q : hreq, vi ∈ (sent∗qp \ rcvd∗qp) }do send hAlivei to qendendАлгоритм 10.8.