Введение в распределённые алгоритмы. Ж. Тель (2009) (1185665), страница 96
Текст из файла (страница 96)
Во всяком выполнении вычисленное моментальное состояние системы располагается между тойконфигурацией, в которой началась запись состояния, и той, в которой эта записьзавершилась, о чем свидетельствует следующая теорема.10.3. Применение алгоритмов построения моментальных состояний363Теорема 10.10. П р е д п о л о ж и м , ч т о и м е е т с я в ы п о л н е н и е Е , о с у щ е с т в и м о е м о м ен т а льн о е со ст о ян и е сист ем ы S*, за п е ч а т л е н н о е по х о д у эт о гов ы п о л н е н и я , и с о о т в е т с т в у ю щ а я е м у к о н ф и г у р а ц и я с и с т е м ы у*.
П у с т ьуs — э т о к о н ф и г у р а ц и я , в к о т о р о й п е р в ы й п р о ц е с с з а п и с а л с в о е с о с т о я ние, а у е — эт о к о н ф и гур а ц и я , в к о т о р о й послед н и й процесс за п и са л своес о с т о я н и е . Т о гд а с п р а в е д л и в о с о о т н о ш е н и еуе.ysу*Д о к а з а т е л ь с т в о .
Усилим аргументацию, используемую при доказательстве теоремы 10.5. Построим последовательность событий /, сперва перечислив предмоментальные события выполнения Е в порядке их осуществления в Е ,а затем занумеруем все постмоментальные события выполнения Е в порядке ихосуществления в Е . Такая нумерация не противоречит причинно-следственномупорядку в £ и поэтому определяет некоторое выполнение Е.Выполнение Е содержит конфигурации ys, у*, и уе в указанном порядке, и отсюда следует утверждение теоремы. Выполнение Е содержит ys, поскольку всесобытия из Е , предшествующие уs, являются предмоментальными событиями, и,следовательно, / начинается именно с этих событий и именно в том же порядке.Выполнение Е содержит уе, поскольку совокупность событий, предшествующихYe в выполнении Е , содержит все предмоментальные события.
Значит, / начинается именно этими событиями (хотя, возможно, они следуют в другом порядке),и Е содержит уе на основании теоремы 2.21.□10.3.3. Обнаружение устойчивых свойствРассмотрим устойчивое свойство Р конфигураций; как только выполнениедостигает конфигурации, для которой выполняется Р , это свойство будет продолжать выполняться и для каждой последующей конфигурации.
К устойчивымотносятся следующие свойства:1. З а в е р ш е н и е в ы ч и с л е н и я . Если у — это заключительная конфигурацияи у ~ » 8 , т о у = 8 , и поэтому конфигурация 8 также является заключительной.Следовательно, задача обнаружения завершения (гл. 8 ) может быть решена засчет вычисления моментального состояния системы и анализа активных процессов и базовых сообщений в этом моментальном состоянии. Однако специальныерешения, предложенные в гл.
8 обычно более эффективны.2. Н а л и ч и е т у п и к о в . Если в конфигурации у некоторое множество процессов S оказывается заблокированными, из-за того что все процессы из S пребывают в ожидании 3> других процессов из S , то такая же ситуация повторитсяи в последующих конфигурациях, хотя процессы вне множества S могут изменятьсвои состояния.
Задача обнаружения тупиков рассматривается в § 10.4.3. П о т е р я м а р к е р о в . Рассмотрим алгоритм, в котором маркеры циркулируют между процессами, а сами процессы могут поглощать маркеры. Свойствовида «Имеется не более k маркеров» является устойчивым, так как маркерымогут поглощаться, но не могут порождаться.^поступления сообщений от — Прим, перев.Гл.
10. Моментальные состояния системы3644.Н а л и ч и е « м у с о р а » . В объектно-ориентированной среде программирования создается совокупность объектов, каждый из которых может содержатьс с ы л к у на другие объекты. Объект считается д о с т у п н ы м , если можно отыскать путь, ведущий по ссылкам к данному объекту от некоторого предписанногообъекта; в противном случае объект объявляется « м у с о р о м » .
Ссылки могут появляться и исчезать, но ссылки, ведущие к «мусорным» объектам, никогда невозникают. Поэтому, как только объект становится «мусором», он будет во векивечные оставаться таковым. (Проблеме сборки «мусора» посвящено изрядноеколичество работ, но в этой книге она не рассматривается. Читатель, интересующийся этой задачей, может обратиться к работе [189] и воспользоваться спискомлитературы из указанной работы.)Чтобы выполнить предписанные действия, как только предикат Р стал истинным, его истинность нужно обнаружить посредством вспомогательного алгоритма, который следит за вычислением и запускает нужные действия, когдаобнаружит истинность предиката Р.var detect: boolwhile notPholds dobegin вычислитьinit false ;глобальное моментальное состояние у* ;вычислить Pholds '.= Р(у*)end;detect := trueАлгоритм 10.6.
Алгоритм обнаруженияустойчивого свойстваВесьма общий механизм обнаружения представлен в алгоритме 10.6. В этомалгоритме требуется проводить проверку выполнимости свойства Р для конфигурации, соответствующей моментальному состоянию системы, но обычно этоосуществляется при помощи сравнительно простой распределенной процедуры.В то время как задача алгоритма обнаружения состоит в том, чтобы отслеживать динамику поведения распределенного вычисления, такая процедура всеголишь анализирует статические данные (которые представлены в конфигурации).Вычисление процедуры P h o l d s можно провести либо централизованно, либо распределение.
При централизованном вычислении каждый процесс отправляет своемоментальное состояние выделенному процессу, который восстанавливает полную конфигурацию и вычисляет P h o l d s . При распределенном вычислении всепроцессы участвуют в таком вычислении.Алгоритм 10.6 обладает свойствами корректности и полноты, о чем свидетельствуют следующие две теоремы; это как раз те свойства, которые требуютсяот всякого алгоритма обнаружения. Предположим, что алгоритм 10.6 следит занекоторым распределенным алгоритмом, который порождает выполнение Е .Теорема 10.11 (Корректности). Е с л и а л г о р и т м 10.6 п р и с в а и в а е т з н а ч е н и е t r u e п е р е м е н н о й d e t e c t , к о г д а с и с т е м а п р е б ы в а е т в к о н ф и г у р а ц и и Ь,т о в ы п о л н я е т с я Р(8 ).10.3.
Применение алгоритмов построения моментальных состояний365Д о к а з а т е л ь с т в о . Пусть у* — это последнее из вычисленных моментальных состояний системы, а уе — конфигурация выполнения Е , в которой былозапечатлено последнее локальное состояние конфигурации у*. Согласно рассматриваемому алгоритму выполняется Р(у*). По теореме 10.10 имеет место соотношение у*уе, и поскольку переменная d e t e c t получила значение t r u e послезавершения построения у*, имеет место соотношение уе 8. В силу устойчивости свойства Р будет верно Р(Ь).□Теорема 10.12 (Полноты). Е с л и в ы п о л н е н и е Е д о с т и г л о к о н ф и г у р а ц и и ,в кот о р о й свойст во Р вы полняет ся, т о спуст я ко н ечн ы й пром еж ут окв р е м е н и а л г о р и т м 10.6 п р и с в о и т п е р е м е н н о й d e t e c t з н а ч е н и е tr u e .Д о к а з а т е л ь с т в о .
Предположим, что 8 — это первая конфигурация выполнения Е , которая обладает свойством Р. Рассмотрим конфигурацию ys, следующую за 8 (или совпадающую с 8 ), в которой впервые после прохождения8 предпринято вычисление моментального состояния системы алгоритмом 1 0 .6 .Пусть у* — это моментальное состояние системы, вычисление которого началосьв конфигурации ys. Так как имеет место соотношение 8ysу*, верно Р(у*),и алгоритм обнаружения завершает работу после этого тура.□Алгоритм 10.6 можно использовать для решения всех задач по обнаружению устойчивых свойств, но при этом следует принять во внимание следующиезамечания.1.
Для некоторых свойств Р (распределенное) вычисление значения Р(у*)может потребовать применения достаточно сложных алгоритмов. Такое случается для некоторых модельных вариантов задачи обнаружения тупиков (один изалгоритмов обнаружения тупиков в заданной конфигурации приведен в § 10.4).2. В некоторых случаях этим методом нельзя воспользоваться ввиду ограничений по объему памяти. Такое возможно в случае задачи по сбору «мусора»;сохранение в памяти всех ссылок и сообщений моментального состояния системы более чем вдвое увеличивает объем запрашиваемой памяти, и это можетоказаться слишком высокой ценой.Ранние алгоритмы по сбору «мусора» приостанавливали базовое вычисление при проведении оценки значения предиката, служащего индикатором наличия«мусора»; это решение представляется весьма простым, но обычно оно отвергается, поскольку приостановка базового вычисления представляется недопустимой.
Сравнительно недавно были разработаны алгоритмы, работающие «на лету»; вместо того чтобы заниматься отдельной конфигурацией, они взаимодействуют с базовым вычислением и не относятся к категории алгоритмов, применяющихвычисление моментального состояния системы (см. [187, глава 5] и [189]).3. Даже в тех случаях, когда решения, основанные на применении алгоритма 1 0 .6 , просты и эффективны, они могут оказаться не самыми простыми и ненаиболее эффективными.
Это касается, например, задачи обнаружения завершения вычислений, для которой в гл. 8 были приведены совершенно простыерешения.Моментальные состояния системы можно использовать для вычисления м о н о т о н н ы х ф у н к ц и й , определенных на конфигурациях системы; функция / на366Гл. 10.
Моментальные состояния системызывается монотонной, если выполняется соотношениеу§=*>/(у )< /(8).Если вычислено моментальное состояние системы у* и проведена оценка /* == /(У*)» т 0 для всех последующих конфигураций 8 будет выполняться неравенство /( 8 ) > /*. Примером монотонной функции может служить глобальное виртуальное время (GVT) в распределенном дискретном симуляторе событий (см.,например, [187, гл. 4] или [49]).10.4.
Приложения: обнаружение тупиковВ некоторых распределенных программах процессы могут время от временибыть заблокированы в ожидании сообщений от других процессов. Примерамимогут служить транзакции в базах данных, а также процессы, состязающиесяза право доступа к ресурсам. Тупиковые ситуации, если таковые случаются и неразрешаются должным образом, таят серьезную опасность для распределенныхсистем, понижая их производительность и сокращая область применения. Прежде всего, процессы, вовлеченные в тупиковую ситуацию, никогда не смогут завершить выполнение своей задачи, и, кроме того, ресурсы, занятые этими процессами, уже никогда не будут доступны другим процессам. Понятно, что грамотнаяобработка тупиковых ситуаций чрезвычайно важна для реализации распределенных систем10.4.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
