Таненбаум Э. Распределенные системы. Принципы и парадигмы

Подождите немного. Документ загружается.

6.2. Модели непротиворечивости, ориентированные

на

данные 351

непротиворечивостью {eager release

consistency),

чтобы не путать ее с «ленивым»

собратом, при освобождении процесс, выполняющий освобождение, рассылает

все модифицированные данные всем процессам, которые уже имеют копии этих

данных и поэтому потенциально могут быть заинтересованными в их обновлен-

ной версии. Не существует способа указать, нужны они на самом деле или нет, и

для надежности обновленные данные получают все эти процессы.

Хотя разослать повсюду все данные несложно, обычно это неэффективно.

При ленивой свободной непротиворечивости в момент освобождения ничего ни-

куда не рассылается. Взамен этого в момент захвата процесс, пытающийся про-

извести захват, должен получить наиболее свежие данные из процесса или про-

цессов, в которых они хранятся. Для определения того, что эти элементы данных

действительно были переданы, используется протокол отметок времени.

Во многих программах критическая область располагается внутри цикла.

слу-

чае

энергичной свободной непротиворечивости освобождение происходит при каж-

дом проходе цикла, при этом все модифицированные данные рассылаются всем

процессам, поддерживающим их копии. Этот алгоритм поглощает пропускную

способность каналов и вызывает неизбежные задержки. В варианте ленивой сво-

бодной непротиворечивости в момент освобождения не происходит ничего. При

следующем захвате процесс определяет, что уже обладает всеми необходимыми

данными, а значит, ему не нужно генерировать никаких сообщений. В результате

при ленивой свободной непротиворечивости, до тех пор пока другой процесс не

произведет захват, сетевой трафик вообще не генерируется. Повторяющиеся пары

операций захвата—освобождения, происходящие в одном и том же процессе, в от-

сутствие попыток доступа к данным извне не вызывают никакой нагрузки на сеть.

6.2.7. Поэлементная непротиворечивость

Еще одна модель непротиворечивости, созданная для применения в критических

областях,

—

поэлементная непротиворечивость {entry

consistency)

[48]. Как и оба

варианта свободной непротиворечивости, она требует от программиста (или ком-

пилятора) вставки кода для захвата и освобождения в начале и конце крити-

ческой области. Однако в отличие от свободной непротиворечивости, поэле-

ментная непротиворечивость дополнительно требует, чтобы каждый отдельный

элемент совместно используемых данных был ассоциирован с переменной син-

хронизации

—

блокировкой или барьером. Если необходимо, чтобы к элементам

массива имелся независимый параллельный доступ, то различные элементы мас-

сива должны быть ассоциированы с различными блокировками. Когда происхо-

дит захват переменной синхронизации, непротиворечивыми становятся только

те данные, которые ассоциированы с этой переменной синхронизации. Поэле-

ментная непротиворечивость отличается от ленивой свободной непротиворечи-

вости тем, что в последней отсутствует связь между совместно используемыми

элементами данных и блокировками или барьерами, потому при захвате необхо-

димые переменные определяются эмпирически.

Связывая список совместно используемых элементов данных с переменными

синхронизации, мы снижаем накладные расходы на захват и освобождение пере-

352 Глава 6. Непротиворечивость

репликация

менных синхронизации до нескольких синхронизируемых элементов данных.

Это также позволяет нам, увеличивая степень параллелизма, иметь несколько

одновременно выполняемых критических областей, включающих в себя непере-

секающиеся группы совместно используемых элементов данных. Цена, которую

мы платим за это,

—

дополнительные усилия и сложность связывания всех раз-

деляемых элементов данных с переменными синхронизации. Программирование

в этом случае также сложнее и грозит ошибками.

Переменные синхронизации используются следующим образом. Каждая пе-

ременная синхронизации имеет текущего владельца

—

процесс, который захва-

тил ее последним. Владелец может многократно входить в критические области

и выходить из них, не посылая в сеть никаких сообщений. Процесс, не являю-

щийся в настоящее время владельцем переменной синхронизации, но желающий

захватить ее, должен послать текущему владельцу сообщение, запрашивая право

собственности и текущие значения данных, ассоциированных с переменной син-

хронизации. Кроме того, несколько процессов могут одновременно владеть пере-

менной синхронизации, но не в эксклюзивном режиме. Это означает, что они мо-

гут прочесть ассоциированные с переменной данные, но не записать их.

Формально хранилище данных обеспечивает поэлементную непротиворечи-

вость, если оно удовлетворяет трем условиям [50].

4- Захват процессом доступа к переменной синхронизации невозможен до

тех пор, пока не осуществлены все обновления отслеживаемых совместно

используемых данных этого процесса.

Пока один из процессов имеет эксклюзивный доступ к переменной син-

хронизации, никакой другой процесс не может захватить эту переменную

синхронизации, в том числе и не эксклюзивно.

> После эксклюзивного доступа к переменной синхронизации не эксклю-

зивный доступ любого другого процесса к этой переменной синхрониза-

ции запрещен, пока это не будет разрешено владельцем этой переменной.

Первое условие гласит, что если процесс производит захват, то захват не мо-

жет быть выполнен (то есть нельзя передать управление следующей инструк-

ции) до тех пор, пока все контролируемые общие данные не станут непротиво-

речивыми. Другими словами, при захвате должны быть визуализированы все

изменения, сделанные в этих данных удаленными процессами.

Второе условие говорит, что перед обновлением элемента совместно исполь-

зуемых данных процесс должен войти в критическую область в эксклюзивном

режиме, чтобы гарантировать, что никакой другой процесс в то же самое время

не изменяет эти данные.

Третье условие гласит, что если процесс хочет войти в критическую область

в не эксклюзивном режиме, он должен сначала проверить, что владелец перемен-

ной синхронизации, отслеживающей эту критическую область, получил самую

свежую копию отслеживаемых данных.

Пример поэлементной непротиворечивости иллюстрирует рис. 6.12. Вместо

того чтобы работать со всеми совместно используемыми данными, в этом приме-

ре мы ассоциируем блокировку с каждым элементом данных. Здесь процесс Р1

6.2. Модели непротиворечивости, ориентированные на данные 353

осуществляет захват

х,

изменяет

х,

после чего захватывает

у.

Процесс Р2 захва-

тывает

но

не у

после чего считывает из

значение для

а,

но для

может счи-

тать только нуль (NIL). Поскольку процесс РЗ сначала захватывает

у, он

может

прочитать значение

после того,

как

элемент

будет освобожден процесом

Р1.

Р1:

Acq(Lx)

W(x)a

Acq(Ly)

W(y)b

Rel(Lx) Rel(Ly)

P2:

Acq(Lx)

R(x)a

P3:

Acq(Ly)

R(y)NIL

R(y)b

Рис. 6.12. Допустимая последовательность событий

для поэлементной непротиворечивости

Одна

из

проблем программирования

для

поэлементной непротиворечивости

относится

правильному связыванию данных

переменными синхронизации.

Один

из

способов решения этой проблемы состоит

применении распределен-

ных совместно используемых объектов. Это делается следующим образом. Каж-

дый распределенный объект имеет ассоциированную

ним переменную синхро-

низации.

Эта

переменная предоставляется базовой распределенной системой

при создании распределенного объекта,

но тем не

менее полностью скрыта

от

клиента.

Когда клиент обращается

методу распределенного объекта, базовая система

сначала выполняет захват ассоциированной

объектом переменной синхрониза-

ции. В результате самые свежие значения состояния объекта, который можно ре-

плицировать

распределить

по

нескольким машинам, передаются клиентской

копии этого объекта.

этот момент, пока объект остается заблокированным

от

параллельных операций,

происходит обращение.

По

окончании обращения

следует внутренняя операция освобождения, деблокирующая объект

для

даль-

нейших операций.

В результате

все

обращения

распределенному, совместно используемому

объекту последовательно непротиворечивы.

счастью, клиент

не

должен зани-

маться переменными синхронизации, поскольку они полностью поддерживают-

ся базовой распределенной системой. В то же время каждый объект оказывается

автоматически защищенным

от

одновременного выполнения параллельных

об-

ращений.

Подобный подход реализован

языке программирования Огса [28, 30], кото-

рый мы обсудим

деталях

этой главе чуть позже. Сходный подход использован

в CRL

[219],

где объекты имеют вид неперекрывающихся областей распределен-

ной общей памяти. Каждая область получает ассоциированную

с ней

перемен-

ную синхронизации, предоставляемую базовой исполняющей системой.

За

син-

хронизацию доступа

этим областям также отвечает исполняющая система.

6.2.8.

Сравнение моделей непротиворечивости

Хотя мы еще будем рассматривать другие модели непротиворечивости, основные

(модели непротиворечивости данных)

мы

уже обсудили. Они отличаются огра-

ничениями, сложностью реализации, простотой программирования

произво-

354 Глава 6. Непротиворечивость и репликация

дительностью. Строгая непротиворечивость

—

наиболее ограниченный вариант,

но поскольку ее реализация в распределенных системах, в сущности, невозмож-

на, то она никогда в них не применяется.

Линеаризуемость

—

более слабая модель, основанная на идее синхронизиро-

ванных часов. В ней делать вывод о корректности параллельных программ про-

ще,

но все равно слишком сложно для того, чтобы ее можно было использовать

для построения реальных программ. С этой точки зрения лучшей моделью яв-

ляется последовательная непротиворечивость, которая применима, популярна

среди программистов и действительно широко используется. Однако у нее есть

проблема

—

низкая производительность. Единственный способ улучшить пока-

затели производительности

—

это ослабить модель непротиворечивости. Неко-

торые из возможностей иллюстрирует табл. 6.5. Модели перечислены в прибли-

зительном порядке снижения ограничений.

Таблица 6.5. Модели непротиворечивости, не требующие операций

синхронизации

Непротиворечивость Описание

Строгая Абсолютная упорядоченность во времени всех обращений

к совместно используемой памяти

Линеаризуемость Все процессы наблюдают все обращения к совместно

используемой памяти в одном и том же порядке. Обращения

упорядочены в соответствии с (неуникальными)

глобальными отметками времени

Последовательная Все процессы наблюдают все обращения к совместно

используемой памяти в одном и том же порядке.

Обращения не упорядочены по времени

Причинная Все процессы наблюдают все обращения, связанные

причинно-следственной связью, к совместно используемой

памяти в одном и том же порядке

FIFO Все процессы наблюдают операции записи любого процесса

в порядке их выполнения. Операции записи различных

процессов могут наблюдаться разными процессами

в разном порядке

Причинная непротиворечивость и непротиворечивость FIFO представляют

собой ослабленные модели, в которых отсутствует глобальный контроль над тем,

какие операции в каком порядке выполняются. Разным процессам последова-

тельность операций кажется разной. Эти две модели различаются в том, какие

последовательности считаются допустимыми, а какие нет.

Другой подход состоит во введении явных переменных синхронизации, как

сделано для слабой непротиворечивости, свободной непротиворечивости и по-

элементной непротиворечивости. Эти три модели приведены в табл. 6.6. Когда

процесс выполняет операцию с обычным элементом совместно используемых

данных, отсутствуют какие-либо гарантии по поводу того, когда его смогут уви-

деть другие процессы. Изменения распространятся только при явной синхрони-

зации. Эти три модели различаются способом синхронизации, но во всех случаях

процесс может производить множественные операции чтения и записи в крити-

6.3. Модели непротиворечивости, ориентированные на клиента 355

ческой области без реального переноса данных. После окончания критической

области результат передается другим процессам или хранится в готовом виде,

ожидая, пока другой процесс не потребует этих данных.

Таблица 6.6. Модели непротиворечивости, использующие операции

синхронизации

Непротиворечивость Описание

Слабая Совместно используемые данные могут считаться

непротиворечивыми только после синхронизации

Свободная Совместно используемые данные становятся непротиворечивыми

после выхода из критической области

Поэлементная Совместно используемые данные, относящиеся к данной

критической области, становятся непротиворечивыми при входе

в эту область

Говоря кратко, слабая, свободная и поэлементная непротиворечивости требу-

ют дополнительных программных конструкций, которые при правильном ис-

пользовании позволяют программистам представить дело так, будто хранилище

данных обладает последовательной непротиворечивостью. В принципе эти три

модели, использующие явную синхронизацию, можно задействовать для повы-

шения производительности, однако вполне вероятно, что для разных приложе-

ний успешность такого подхода будет разной.

6.3. Модели непротиворечивости,

ориентированные на клиента

Модели непротиворечивости, описанные в предыдущем разделе, ориентированы

на создание непротиворечивого представления хранилища данных. При этом

делалось важное предположение о том, что параллельные процессы одновремен-

но изменяют данные в хранилище и необходимо сохранить непротиворечивость

хранилища в условиях этой параллельности. Так, например, в случае поэлемент-

ной непротиворечивости на базе объектов хранилище данных гарантирует, что

при обращении к объекту процесс получит копию объекта, отражающую все про-

изошедшие с ним изменения, в том числе и сделанные другими процессами.

хо-

де обращения гарантируется также, что нам не помешает никакой другой объект,

то есть обратившемуся процессу будет предоставлен защищенный механизмом

взаимного исключения доступ.

Возможность осуществлять параллельные операции над совместно исполь-

зуемыми данными в условиях последовательной непротиворечивости является

базовой для распределенных систем. По причине невысокой производительно-

сти последовательная непротиворечивость может гарантироваться только в слу-

чае использования механизмов синхронизации

—

транзакций или блокировок.

В этом разделе мы рассмотрим специальный класс распределенных храни-

лищ данных, которые характеризуются отсутствием одновременных изменений

356 Глава 6. Непротиворечивость и репликация

или легкостью их разрешения в том случае, если они все-таки случатся. Большая

часть операций подразумевают чтение данных. Подобные хранилища данных со-

ответствуют очень слабой модели непротиворечивости, которая носит название

потенциальной непротиворечивости. После введения специальных моделей не-

противоречивости, ориентированных на клиента, оказывается, что множество

нарушений непротиворечивости можно относительно просто скрыть.

6.3.1.

Потенциальная непротиворечивость

Степень, в которой процессы действительно работают параллельно, и степень,

в которой действительно должна быть гарантирована непротиворечивость, могут

быть разными. Существует множество случаев, когда параллельность нужна лишь

в урезанном виде. Так, например, во многих системах управления базами данных

большинство процессов не производит изменения данных, ограничиваясь лишь

операциями чтения. Изменением данных занимается лишь один, в крайнем слу-

чае несколько процессов. Вопрос состоит в том, как быстро эти изменения могут

стать доступными процессам, занимающимся только чтением данных.

В качестве другого примера рассмотрим глобальную систему именования, та-

кую как DNS. Пространство имен DNS разделено на домены, каждый домен имеет

источник именования, который действует, как владелец этого домена. Только

этот источник может обновить свою часть пространства имен. Соответственно,

конфликт двух операций, которые хотели бы одновременно обновить одни и те

же данные (то есть конфликт двойной записи), невозможен. Единственная си-

туация, которую может потребоваться решать,

—

это конфликт чтения-записи.

том случае, когда он происходит, часто распространение изменений может про-

изводиться постепенно, в том смысле, что процессы чтения могут обнаружить

произошедшие изменения только через некоторое время после того, как они на

самом деле произойдут.

Еще один пример

—

World Wide Web. Фактически web-страницы всегда из-

меняются одним человеком

—

web-мастером или настоящим владельцем страницы.

В результате разрешать конфликты двойной записи обычно не требуется. С дру-

гой стороны, для повышения эффективности браузеры и прокси-серверы часто

конфигурируются так, чтобы сохранять загруженные страницы в локальном кэ-

ше и возвращать при следующем запросе именно их. Важный момент обоих ти-

пов систем web-кэширования состоит в том, что они могут возвращать устарев-

шие web-страницы. Другими словами, кэшированные страницы, возвращаемые в

ответ на запрос клиента, могут не соответствовать более новым версиям страниц,

хранящимся на web-сервере. Но даже при этом многие пользователи lyioryT счесть

такое несоответствие приемлемым.

Эти примеры могут рассматриваться как случаи распределенных и репли-

цируемых баз данных (крупных), нечувствительных к относительно высокой

степени нарушения непротиворечивости. Обычно в них длительное время не

происходит изменения данных, и все реплики постепенно становятся непротиво-

речивыми. Такая форма непротиворечивости называется

потенциальной

непро-

тиворечивостью

{eventual

consistency).

6.3. Модели непротиворечивости, ориентированные на клиента 357

Потенциально непротиворечивые хранилища данных имеют следующее свой-

ство:

отсутствие изменений все реплики постепенно становятся идентичными.

Как

мы

будем говорить позднее

этой главе, потенциальная непротиворечи-

вость,

сущности, требует только, чтобы изменения гарантированно расходи-

лись

по

всем репликам. Конфликты двойной записи часто относительно легко

разрешаются, если предположить, что вносить изменения может лишь неболь-

шая группа процессов. Поэтому реализация потенциальной непротиворечиво-

сти часто весьма дешева. Специфику реализации

мы

рассмотрим позже

этой

главе.

Потенциально непротиворечивые хранилища данных с успехом работают, если

клиент всегда осуществляет доступ

одной

той же реплике. Однако при рабо-

те с разными репликами возникают проблемы. Они прекрасно иллюстрируются

схемой доступа мобильного пользователя

распределенной базе данных, пред-

ставленной

на

рис. 6.13.

Клиент перемещается

в другое место

связывается

(прозрачно)

другой репликой

Портативный

компьютер

Распределенная

реплицированная

база данных

Операции чтения

записи

Рис. 6.13. Принцип доступа мобильного пользователя

разным репликам

распределенной базы данных

Мобильный пользователь работает

базой данных, прозрачно подсоединяясь

к одной

из ее

реплик. Другими словами, приложение, работающее

на

портатив-

ном компьютере пользователя, не знает,

какой именно репликой оно работает.

Допустим, пользователь произвел несколько операций изменения данных

и от-

соединился

от

базы. Позже

он

снова начал работать

базой данных, возможно,

после перемещения

другое место или

другого устройства доступа. В этот мо-

мент пользователь может подсоединиться

другой нежели раньше реплике,

что

и показано

на

рисунке. Однако если изменения, сделанные

базе данных рань-

ше,

еще

не

распространены

на

эту реплику, пользователь обнаружит противоре-

358 Глава 6. Непротиворечивость и репликация

чивость данных в базе данных. В частности, он будет ожидать увидеть сделанные

раньше изменения, а вместо этого обнаружит, что ничего не изменилось.

Этот пример типичен для потенциально непротиворечивых хранилищ данных

и вызван тем, что пользователь может иногда работать с различными репликами.

Острота проблемы снижается путем введения

пепротиворечивосши,

ориентиро-

ванной на клиента

{client-centric

consistency).

По существу, непротиворечивость,

ориентированная на клиента, предоставляет одному клиенту гарантии непроти-

воречивости при доступе к хранилищу данных. Относительно параллельного

доступа других клиентов никаких гарантий не предоставляется.

Моделям непротиворечивости, ориентированным на клиента, дала начало ра-

бота над Bayou [453, 454]

—

системой управления базами данных, разработан-

ной для мобильных вычислений. В этой системе предполагается, что сетевые

подключения ненадежны и имеют различные проблемы с производительностью.

В эту категорию попадают беспроводные сети и глобальные сети, такие как Ин-

тернет.

В системе Bayou различают четыре основных модели непротиворечивости.

Для рассмотрения этих моделей мы вновь обсудим хранилище данных, распре-

деленное по нескольким машинам. Когда процесс получает доступ к хранилищу

данных, он обычно связывается с локальной (или ближайшей) копией, хотя в

принципе подойдет любая копия. Все операции чтения и записи осуществляют-

ся с локальной копией. Изменения постепенно распространяются и на другие

копии. Для простоты примем, что элементы данных имеют ассоциированного с

ними владельца, которым является единственный процесс, имеющий право из-

менять их. Таким образом, мы избежим конфликтов двойного чтения.

Модели непротиворечивости, ориентированные на клиента, описываются с ис-

пользованием следующей нотации. Пусть

Xi[t]

означает версию элемента данных х

на локальной копии 1, в момент времени t. Версия

Xi[t\

—

результат серии опера-

ций записи, произведенных в i, после инициализации. Мы обозначим эту серию

как W5(Xj[^]). Если операции из серии ^^^(^/[^i]) были также произведены в ло-

кальной копии Lj в более позднее время

^2,

мы запишем это как W5(X,[^i];X/[^2])-

Если временная очередность операций будет ясна из контекста, мы будем опус-

кать индекс у символа времени.

6.3.2. Монотонное чтение

Первая из моделей непротиворечивости, ориентированная на клиента,

—

монотон-

ное чтение. Хранилище данных обеспечивает

непротиворечивость монотонного

чтения (monotonic-read

consistency)^

если удовлетворяет следующему условию:

если

процесс

читает значение

элемента

данных х, любая

последующая

операция

чтения х

всегда возвращает

то

же самое

или

более позднее

значение.

Другими словами, непротиворечивость монотонного чтения гарантирует, что

если процесс в момент времени t видит некое значение х, то позже он никогда не

увидит более старого значения х.

В качестве примера применения монотонного чтения рассмотрим распреде-

ленную базу данных электронной почты. В этой базе данных почтовый ящик каж-

6.3. Модели непротиворечивости, ориентированные на клиента 359

дого пользователя может быть распределен

по

нескольким машинам

репли-

цирован. Корреспонденция добавляется

почтовые ящики всех реплик. Однако

изменения распространяются медленно (по запросу). Данные пересылаются

ко-

пии базы только

том случае, когда эти данные нужны этой копии для поддер-

жания непротиворечивости. Представим себе, что пользователь читает свою поч-

ту

Сан-Франциско. Допустим,

что

чтение почты

не

оказывает воздействия

на

почтовый ящик,

то

есть сообщения не удаляются, не сохраняются во вложенных

каталогах, не помечаются как прочитанные

т. п. Когда пользователь после это-

го улетает

Нью-Йорк

снова открывает свой почтовый ящик, непротиворечи-

вость монотонного чтения гарантирует, что сообщения, которые

он

видел

сво-

ем почтовом ящике

Сан-Франциско,

он

увидит

своем почтовом ящике

и в

Нью-Йорке.

Если использовать нотацию, похожую на ту, которая применялась для описа-

ния непротиворечивости, ориентированной на данные, непротиворечивость моно-

тонного чтения может быть графически представлена так, как показано на

рис.

6.14.

Вдоль вертикальной оси располагаются две различных локальных копии храни-

лища данных,

Ы и

L2. Вдоль горизонтальной оси откладывается время.

L1:

WS(Xi)

R(x^) L1:

\NS(x,)

R{x,)

L2:

WS(x^;x2)

R(x^) L2:

WS(X2)

R(X2)

WS(x^;x2)

Рис. 6.14. Операции чтения, осуществляемые одиночным процессом Р над двумя различными

копиями одного хранилища данных. Хранилище

непротиворечивостью монотонного

чтения (а). Хранилище без непротиворечивости монотонного чтения

(б)

На рис. 6.14,

процесс

сначала выполняет операцию чтения

из копии

L1,

которая возвращает значение

(в

этот момент). Это значение является резуль-

татом операции записи WS(x\), производимой

копией

L1.

Позднее

выполняет

операцию чтения

из хранилища 12, обозначаемую как R(x2). Чтобы гарантиро-

вать непротиворечивость монотонного чтения, все операции, сделанные

WS(x\),

должны распространиться

на

до

момента второго чтения. Другими словами,

мы должны точно знать, что операция WS(Xi) является частью операции WS(x2)

и может быть выражена как WS(xuX2).

В противоположность этому, на рис. 6.14, б показана ситуация,

которой непро-

тиворечивость монотонного чтения

не

гарантируется. После того

как

процесс

считывает

Х\

из

Ы,

он производит операцию

R(x2)

из

L2.

Однако в L2 была выпол-

нена только операция записи

WS(x2)y

поэтому нет никаких гарантий, что в этом

наборе учтены также

операции, содержавшиеся

WS(xt).

6.3.3. Монотонная запись

Во многих ситуациях важно, чтобы

по

всем копиям хранилища данных

пра-

вильном порядке распространялись операции записи. Это можно осуществить при

условии

непротиворечивости монотонной записи {monotonic-xmite

consistency).

Если

хранилище обладает свойством непротиворечивости монотонной записи,

для

360 Глава 6. Непротиворечивость и репликация

него соблюдается следующее условие: операция записи

процесса

в элемент дан-

пых X завершается раньше любой

из

последующих операций записи этого процесса

элемент

х.

Здесь завершение операции записи означает, что копия, над которой выпол-

няется следующая операция, отражает эффект предыдущей операции записи,

произведенной тем же процессом, и при этом не имеет значения, где эта опера-

ция была инициирована. Другими словами, операция записи в копию элемента

данных

выполняется только в том случае, если эта копия соответствует резуль-

татам предыдущей операции записи, выполненных над другими копиями х.

Отметим, что непротиворечивость монотонной записи напоминает одну из

моделей непротиворечивости, ориентированной на данные, — непротиворечи-

вость FIFO. Сущность непротиворечивости FIFO состоит в том, что операции

записи одного процесса всегда выполняются в правильной очередности. Такое

же ограничение на очередность применяется и при монотонной записи, за ис-

ключением того, что здесь мы говорим об одном процессе, а не о наборе парал-

лельных процессов.

Актуализация копии х не обязательна, если каждая операция записи полно-

стью изменяет существующее значение х. Однако операции записи часто выпол-

няются только над частью элемента данных. Рассмотрим, например, библиотеку

подпрограмм. Во многих случаях обновление библиотеки заключается в замене

одной или нескольких функций, а результатом этого является новая версия. При

условии непротиворечивости монотонной записи даются гарантии того, что если

изменения вносятся в одну из копий библиотеки, сначала будут внесены все пред-

шествующие изменения. Получившаяся библиотека будет реально представлять

собой самую последнюю версию и содержать все обновления, имевшиеся в пре-

дыдущей версии этой библиотеки.

Непротиворечивость монотонной записи иллюстрирует рис. 6.15. Процесс Р осу-

ществляет операцию записи W(xi) элемента х

локальную копию

(см. рис.

6.15,

а).

Позднее Р выполняет еще одну операцию записи

W(x2),

на этот раз над L2, Для

непротиворечивости монотонной записи необходимо, чтобы предыдущая опера-

ция записи в L1 уже распространилась на L2, Это поясняет наличие операции

W(x\) в 12 и то, почему она помещена перед операцией W(x2).

L1:

W(x,) L1: W(x^)

L2:

W(Xi) W(X2) L2: W(X2)

Рис, 6.15. Операции записи, осуществляемые единичным процессом Р над двумя

различными копиями одного хранилища данных. Хранилище данных

с непротиворечивостью монотонной записи (а). Хранилище

без непротиворечивости монотонной записи (б)

В противоположность этому, на

рис.

6.15, б показана ситуация, в которой непро-

тиворечивость монотонной записи не гарантирована. По сравнению с рис. 6.15, а

распространение операции W(x\) на копию L2 отсутствует. Другими словами,

нет никаких гарантий того, что копия элемента

х,

над которой производится вто-