Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 91
Текст из файла (страница 91)
В результате блокировка операций над совместно используемыми даннымибудет атомарной благодаря примитивам захвата и освобождения, которые будутпрепятствовать чередованию.У свободной непротиворечивости имеется такая реализация, как ленивая свободная непротиворечивость {lazy release consistency) [231]. При обычной свободной непротиворечивости, которую мы далее будем называть энергичной свободной6.2.
Модели непротиворечивости, ориентированные на данные351непротиворечивостью {eager release consistency), чтобы не путать ее с «ленивым»собратом, при освобождении процесс, выполняющий освобождение, рассылаетвсе модифицированные данные всем процессам, которые уже имеют копии этихданных и поэтому потенциально могут быть заинтересованными в их обновленной версии. Не существует способа указать, нужны они на самом деле или нет, идля надежности обновленные данные получают все эти процессы.Хотя разослать повсюду все данные несложно, обычно это неэффективно.При ленивой свободной непротиворечивости в момент освобождения ничего никуда не рассылается.
Взамен этого в момент захвата процесс, пытающийся произвести захват, должен получить наиболее свежие данные из процесса или процессов, в которых они хранятся. Для определения того, что эти элементы данныхдействительно были переданы, используется протокол отметок времени.Во многих программах критическая область располагается внутри цикла. В случае энергичной свободной непротиворечивости освобождение происходит при каждом проходе цикла, при этом все модифицированные данные рассылаются всемпроцессам, поддерживающим их копии. Этот алгоритм поглощает пропускнуюспособность каналов и вызывает неизбежные задержки. В варианте ленивой свободной непротиворечивости в момент освобождения не происходит ничего.
Приследующем захвате процесс определяет, что уже обладает всеми необходимымиданными, а значит, ему не нужно генерировать никаких сообщений. В результатепри ленивой свободной непротиворечивости, до тех пор пока другой процесс непроизведет захват, сетевой трафик вообще не генерируется. Повторяющиеся парыопераций захвата—освобождения, происходящие в одном и том же процессе, в отсутствие попыток доступа к данным извне не вызывают никакой нагрузки на сеть.6.2.7. Поэлементная непротиворечивостьЕще одна модель непротиворечивости, созданная для применения в критическихобластях, — поэлементная непротиворечивость {entry consistency) [48]. Как и обаварианта свободной непротиворечивости, она требует от программиста (или компилятора) вставки кода для захвата и освобождения в начале и конце критической области. Однако в отличие от свободной непротиворечивости, поэлементная непротиворечивость дополнительно требует, чтобы каждый отдельныйэлемент совместно используемых данных был ассоциирован с переменной синхронизации — блокировкой или барьером.
Если необходимо, чтобы к элементаммассива имелся независимый параллельный доступ, то различные элементы массива должны быть ассоциированы с различными блокировками. Когда происходит захват переменной синхронизации, непротиворечивыми становятся толькоте данные, которые ассоциированы с этой переменной синхронизации. Поэлементная непротиворечивость отличается от ленивой свободной непротиворечивости тем, что в последней отсутствует связь между совместно используемымиэлементами данных и блокировками или барьерами, потому при захвате необходимые переменные определяются эмпирически.Связывая список совместно используемых элементов данных с переменнымисинхронизации, мы снижаем накладные расходы на захват и освобождение пере-352Глава 6. Непротиворечивость и репликацияменных синхронизации до нескольких синхронизируемых элементов данных.Это также позволяет нам, увеличивая степень параллелизма, иметь несколькоодновременно выполняемых критических областей, включающих в себя непересекающиеся группы совместно используемых элементов данных.
Цена, которуюмы платим за это, — дополнительные усилия и сложность связывания всех разделяемых элементов данных с переменными синхронизации. Программированиев этом случае также сложнее и грозит ошибками.Переменные синхронизации используются следующим образом. Каждая переменная синхронизации имеет текущего владельца — процесс, который захватил ее последним. Владелец может многократно входить в критические областии выходить из них, не посылая в сеть никаких сообщений.
Процесс, не являющийся в настоящее время владельцем переменной синхронизации, но желающийзахватить ее, должен послать текущему владельцу сообщение, запрашивая правособственности и текущие значения данных, ассоциированных с переменной синхронизации. Кроме того, несколько процессов могут одновременно владеть переменной синхронизации, но не в эксклюзивном режиме. Это означает, что они могут прочесть ассоциированные с переменной данные, но не записать их.Формально хранилище данных обеспечивает поэлементную непротиворечивость, если оно удовлетворяет трем условиям [50].4- Захват процессом доступа к переменной синхронизации невозможен дотех пор, пока не осуществлены все обновления отслеживаемых совместноиспользуемых данных этого процесса.4^ Пока один из процессов имеет эксклюзивный доступ к переменной синхронизации, никакой другой процесс не может захватить эту переменнуюсинхронизации, в том числе и не эксклюзивно.> После эксклюзивного доступа к переменной синхронизации не эксклюзивный доступ любого другого процесса к этой переменной синхронизации запрещен, пока это не будет разрешено владельцем этой переменной.Первое условие гласит, что если процесс производит захват, то захват не может быть выполнен (то есть нельзя передать управление следующей инструкции) до тех пор, пока все контролируемые общие данные не станут непротиворечивыми.
Другими словами, при захвате должны быть визуализированы всеизменения, сделанные в этих данных удаленными процессами.Второе условие говорит, что перед обновлением элемента совместно используемых данных процесс должен войти в критическую область в эксклюзивномрежиме, чтобы гарантировать, что никакой другой процесс в то же самое времяне изменяет эти данные.Третье условие гласит, что если процесс хочет войти в критическую областьв не эксклюзивном режиме, он должен сначала проверить, что владелец переменной синхронизации, отслеживающей эту критическую область, получил самуюсвежую копию отслеживаемых данных.Пример поэлементной непротиворечивости иллюстрирует рис. 6.12. Вместотого чтобы работать со всеми совместно используемыми данными, в этом примере мы ассоциируем блокировку с каждым элементом данных.
Здесь процесс Р16.2. Модели непротиворечивости, ориентированные на данные353осуществляет захват х, изменяет х, после чего захватывает у. Процесс Р2 захватывает X, но не у у после чего считывает из х значение для а, но для у может считать только нуль (NIL). Поскольку процесс РЗ сначала захватывает у, он можетпрочитать значение b после того, как элемент у будет освобожден процесом Р1.Р1: Acq(Lx) W(x)a Acq(Ly) W(y)b Rel(Lx) Rel(Ly)P2:Acq(Lx) R(x)aP3:Acq(Ly)R(y)NILR(y)bРис. 6.12. Допустимая последовательность событийдля поэлементной непротиворечивостиОдна из проблем программирования для поэлементной непротиворечивостиотносится к правильному связыванию данных с переменными синхронизации.Один из способов решения этой проблемы состоит в применении распределенных совместно используемых объектов.
Это делается следующим образом. Каждый распределенный объект имеет ассоциированную с ним переменную синхронизации. Эта переменная предоставляется базовой распределенной системойпри создании распределенного объекта, но тем не менее полностью скрыта отклиента.Когда клиент обращается к методу распределенного объекта, базовая системасначала выполняет захват ассоциированной с объектом переменной синхронизации. В результате самые свежие значения состояния объекта, который можно реплицировать и распределить по нескольким машинам, передаются клиентскойкопии этого объекта. В этот момент, пока объект остается заблокированным отпараллельных операций, и происходит обращение. По окончании обращенияследует внутренняя операция освобождения, деблокирующая объект для дальнейших операций.В результате все обращения к распределенному, совместно используемомуобъекту последовательно непротиворечивы.
К счастью, клиент не должен заниматься переменными синхронизации, поскольку они полностью поддерживаются базовой распределенной системой. В то же время каждый объект оказываетсяавтоматически защищенным от одновременного выполнения параллельных обращений.Подобный подход реализован в языке программирования Огса [28, 30], который мы обсудим в деталях в этой главе чуть позже. Сходный подход использованв CRL [219], где объекты имеют вид неперекрывающихся областей распределенной общей памяти. Каждая область получает ассоциированную с ней переменную синхронизации, предоставляемую базовой исполняющей системой. За синхронизацию доступа к этим областям также отвечает исполняющая система.6.2.8. Сравнение моделей непротиворечивостиХотя мы еще будем рассматривать другие модели непротиворечивости, основные(модели непротиворечивости данных) мы уже обсудили.
Они отличаются ограничениями, сложностью реализации, простотой программирования и произво-354Глава 6. Непротиворечивость и репликациядительностью. Строгая непротиворечивость — наиболее ограниченный вариант,но поскольку ее реализация в распределенных системах, в сущности, невозможна, то она никогда в них не применяется.Линеаризуемость — более слабая модель, основанная на идее синхронизированных часов. В ней делать вывод о корректности параллельных программ проще, но все равно слишком сложно для того, чтобы ее можно было использоватьдля построения реальных программ. С этой точки зрения лучшей моделью является последовательная непротиворечивость, которая применима, популярнасреди программистов и действительно широко используется.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
