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

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

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

допустимые чередования выражений во времени. В каждом из этих трех процес-

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

принимать каждая из переменных,

—

это исходное значение (0) или присвоенное

значение (1), каждый процесс печатает строку из двух битов. Числа в графе «Пе-

чать»

—

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

Если мы объединим результаты работы процессов

РУ,

Р2 и РЗ в таком поряд-

ке,

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

ние инструкций. Эта строка в таблице представлена в графе «Сигнатура». Ниже

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

печати.

Не все из 64 сигнатур допустимы. Тривиальный пример: сигнатура 000000 не

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

инструкции присваивания, что нарушает требования о выполнении инструкций

в порядке, предусмотренном программой. Более сложный пример

—

001001.

Пер-

вые два бита, 00, означают, что переменные

и z в момент их печати были равны

нулю.

Такая ситуация может возникнуть только в том случае, если обе инструк-

ции из процесса Р1 выполняются до начала выполнения процессов Р2 и

РЗ.

Сле-

дуюш;ие два бита, 10, означают, что Р2 выполняется после начала выполнения Р1,

но до начала выполнения

РЗ.

Последние два бита, 01, означают, что выполнение

РЗ

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

цесс Р1 должен выполняться первым. Таким образом, сигнатура 001001 недопу-

стима.

Говоря коротко, 90 допустимых последовательностей выполнения инструк-

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

все-таки менее 64), допустимых по условиям последовательной непротиворечи-

вости. Соглашение между процессами и распределенным хранилищем данных,

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

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

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

зультаты в качестве правильных ответов и корректно работать в случае получе-

ния одного из них. Программа, которая работает с какими-то из этих результа-

тов,

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

данных и является неправильной.

Существуют различные способы формального выражения последовательной

непротиворечивости (и других моделей). Общий подход изложен в [5, 298]. Каж-

дый процесс Pi имеет ассоциированную с ним

реализацию

(execution)

Ei,

которая

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

значений из хранилища данных 5. Эта последовательность соответствует поряд-

ку, заданному в программе, ассоциированной с процессом Pi,

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

может быть задана следующим образом:

Е1:

W1(x)a

Е2:

W2{x)b

ЕЗ:

R3(x)b, R3(x)a

Е4:

R4(x)b, R4(x)a

342 Глава

Непротиворечивость

репликация

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

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

строку Я

так,

чтобы каждая из операций, входящих в

Ei,

входила и в Я. Строка Я

называется историей (history). Интуитивно понятно, что Я описывает очеред-

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

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

должен сохраняться такой же порядок выполнения, как и в программе;

должно сохраняться соотношение между данными.

Первое ограничение означает, что если операция записи или чтения 0Р1 в од-

ной из строк реализации Ei следует перед другой операцией 0Р2, то 0Р1 должна

следовать перед 0Р2 и в истории Я. Если это ограничение для всех пар операций

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

шающих порядок, заданный программой.

Второе ограничение, которое мы будем называть связностью данных (data

coherence),

означает, что чтение R(x) некоторого элемента данных х всегда долж-

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

писанное последней перед R(x) операцией W(x)v. Связность данных проверяет-

ся путем выделения каждого элемента данных и последовательности операций с

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

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

писи различных элементов данных и их порядок. Если мы рассматриваем совме-

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

элементы данных, такой случай связности данных называется

связностью

памя-

ти (memory

coherence).

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

мым значением истории Я для них может быть следующая строка:

Я = W1(x)b,R3(x)b,R4(x)b,W2(x)a,R3(x)a,R4(x)a.

С другой стороны, для исполнения четырех процессов, представленных на

рис.

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

но непротиворечивой системе невозможно сделать так, чтобы процесс РЗ снача-

ла выполнял операцию R3(x)b, а затем

—

операцию R3(x)a, в то время как про-

цесс R4 считывает значения аи b в обратном порядке.

Более сложным примером могут быть несколько допустимых значений Я.

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

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

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

мистов модель, она имеет серьезные проблемы с производительностью. В [268]

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

мени передачи пакета между узлами t всегда выполняется условие г

w>t. Дру-

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

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

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

еще более слабых моделей. В следующем пункте мы рассмотрим некоторые

из них.

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

6.2.3. Причинная непротиворечивость

Модель причинной

непротиворечивости

{causal

consistency)

[208]

представляет

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

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

но-следственной связью,

событиями, ею не обладающими. Мы уже говорили

причинно-следственной связи

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

отметки времени. Если событие В вызвано предшествующим событием А или на-

ходится

под его

влиянием,

то

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

все

окружающие наблюдали сначала событие Л,

затем

В.

Рассмотрим пример

памятью. Предположим,

что

процесс

Р1

записывает

значение переменной х. Таким образом, чтение

и запись

будут потенциально

связаны

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

ние

может зависеть от значения х, которое прочтет Р2 (то есть

от

значения,

за-

писанного процессом Р1).

другой стороны, если два процесса спонтанно

од-

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

они не

могут

иметь причинно-следственную связь. Когда

за

записью следует чтение,

эти два

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

вообще, чтение

связано

записью, которая предоставляет данные

для

этого чтения, причинно-

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

на-

зываются параллельными

{concurrent).

Для того чтобы хранилище данных поддерживало причинную непротиво-

речивость,

оно

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

которые

потенциально связаны

причинно-следственной

связью,

должны

наблю-

даться

всеми

процессами

одинаковом

порядке,

параллельные

операции записи

могут наблюдаться

на разных машинах в

разном

порядке.

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

ность событий, возможная

для

хранилища

причинной непротиворечивостью,

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

востью. Стоит отметить,

что

W2{x)b

W1{x)c

—

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

и по-

этому

их

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

не

важна.

Р1:

W(x)a

Р2:

РЗ:

Р4:

R(x)a

W(x)b

W(x)c

R(x)c

R(x)b

R(x)c

Рис. 6.7. Эта последовательность допустима для хранилища

причинной

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

но

недопустима для хранилища

со

строгой

или последовательной непротиворечивостью

Рассмотрим теперь второй пример.

На

рис. 6.8,

а мы

видим,

что

W2{x)h

по-

тенциально зависит

от

W1{x)a, поскольку

может быть результатом вычис-

лений,

которые входит значение, прочитанное операцией R2{x)a. Две операции

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

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

наблюдать

их в

одинаковом порядке. Таким образом,

рис. 6.8, а

некорректен.

другой стороны, на рис. 6.8, б операция чтения из процесса Р2 убрана,

теперь

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

W1(x)a и W2(x)b стали параллельными операциями записи. Хранилище с при-

чинное! непротиворечивостью не требует, чтобы параллельные операции записи

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

Р1:

W(x)a

Р2:

РЗ:

Р4:

R(x)a

W(x)b

R(x)b

R(x)a

R(x)b

P1:

W(x)a

P2:

P3:

P4:

W(x)b

R(x)b

R(x)a

R(x)b

Рис. 6.8, Нарушение причинной непротиворечивости хранилища (а). Правильная

последовательность событий

хранилище с причинной непротиворечивостью (а)

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

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

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

операций друг от друга. Один из способов сделать это

—

воспользоваться вектор-

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

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

причинно-следственной связи.

6.2.4. Непротиворечивость FIFO

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

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

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

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

Следующим шагом в ослаблении непротиворечивости будет освобождение от по-

следнего требования. Это приведет нас к

непротиворечивости FIFO (FIFO

consis-

tency),

которая подчиняется следующему условию: операции записи, осуществ-

ляемые

единичным

процессом,

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

том

порядке,

котором они

осуществляются,

но операции

записи,

происходящие

враз-

личных

процессах,

могут

наблюдаться

разными

процессами в

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

Непротршоречивость FIFO в случае распределенных систем с совместно ис-

пользуемой памятью называют также

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

PRAM (PRAM

con-

sistency).

Она описана в

[268].

Сокращение PRAM происходит от Pipelined RAM

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

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

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

Сравнение непротиворечивости FIFO с причинной непротиворечивостью иллю-

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

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

строгой модели из тех, которые мы рассматривали.

Непротиворечивость FIFO интересна нам из-за простоты ее реализации.

дей-

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

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

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

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

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

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

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

(процесс,

очередной помер)

осуществлени-

ем операций записи каждого

из

процессов

порядке

их

номеров.

P1:W(x)a

Р2:

РЗ:

Р4:

R(x)a

W(x)b

W(x)c

R(x)b

R(x)a

R(x)c

R(x)b

R(x)c

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

Рассмотрим вновь три процесса из табл. 6.1, опираясь на этот раз на непроти-

воречивость FIFO вместо последовательной непротиворечивости. При условии

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

инструкций

различном порядке (табл. 6.3). Так, например,

варианте 1 пока-

зано,

как

выглядит последовательность событий

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

Р1,

варианте 2

—

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

Р2,

в варианте

—

точки зрения про-

цесса РЗ (наблюдаемые результаты создают инструкции, выделенные жирным

шрифтом).

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

три

различных

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

Таблица 6.3. Очередность выполнения инструкций с точки зрения трех процессов,

представленных в табл. 6.1

Инструкции

Печать

Вариант

х=1:

print(y,z):

у=1:

prlnt(x.z);

z=l:

prlnt(x.y):

х=1:

у=1:

prlnt(x.z);

prlnt(y.z):

z=l:

prlnt(x.y):

y=l;

print(x.z):

z=l:

printCx.y);

x=l;

prlnt(y.z):

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

тат

001001,

что, как мы говорили раньше,

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

воречивости невозможно. Основное различие между последовательной непроти-

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

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

том, что

первом случае,

хотя порядок выполнения инструкций

не

регламентирован,

все

процессы,

по

крайней мере,

ним согласны. Во втором

же

случае

им нет

нужды

ни с

чем

со-

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

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

Иногда непротиворечивость FIFO может приводить

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

воречащим здравому смыслу.

примере, взятом

из

[174],

предполагается,

что

целые переменные

х и у

инициализируются нулями. Кажется,

что в

ситуации,

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

представленной в табл. 6.4, возможны три результата: будет прерван процесс Р1,

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

Р2,

ни один из процессов не будет прерван (если первыми

произойдут обе операции присваивания). Однако в случае непротиворечивости

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

если Р1 осуществит чтение R1(y)0 до обнаружения выполненной процессом Р2

записи W2(y)1j а Р2 осуществит чтение R2(x)0 до обнаружения выполненной

процессом Р1 записи W1(x)1. При последовательной непротиворечивости суще-

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

не ведет к прерыванию обоих процессов.

Таблица

6.4.

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

Процесс

Р1

х=1:

(у ==

k1ll(P2):

Процесс

Р2

У=1:

1f(x=

=0)k1ll(Pl):

6.2.5. Слабая непротиворечивость

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

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

лишне строгой, поскольку требует, чтобы операции записи одного процесса ото-

всюду наблюдались в одном и том же порядке. Не все приложения нуждаются да-

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

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

реплицируемую базу данных. Хотя другие процессы даже не предполагают рабо-

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

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

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

все копии базы данных.

Наилучшим решением в этом случае было бы позволить процессу покинуть

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

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

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

ременную синхронизации

{synchronization

variable).

Переменная синхронизации S

имеет только одну ассоциированную с ней операцию, synchronize(S), которая син-

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

осуществляет операции только с локальной копией хранилища. В ходе синхро-

низации хранилища данных все локальные операции записи процесса Р распро-

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

—

на ко-

пию данных Р.

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

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

{weak

consistency)

[130].

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

"¥ Доступ к переменным синхронизации, ассоциированным с хранилищем дан-

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

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

на

данные 347

4 С переменной синхронизации не может быть произведена ни одна опера-

ция до полного и повсеместного завершения предшествующих ей опера-

ций записи.

С элементами данных не может быть произведена ни одна операция до

полного завершения всех операций с переменными синхронизации.

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

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

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

операцию synchronlze(Sl) в то же самое время, когда процесс Р2 вызывает опера-

цию synchron1ze(S2), результат будет точно таким же, как если бы операция

synchronlze(Sl) была вызвана раньше операции synchronize(S2), или наоборот.

Второй пункт указывает на то, что синхронизация очищает конвейер. Она ус-

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

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

их к повсеместному завершению. Когда синхронизация заканчивается, гаранти-

ровано заканчиваются все предшествовавшие ей операции записи. Производя син-

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

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

Третий пункт поясняет, что при доступе к элементам данных (как для записи,

так и для чтения) все предшествующие синхронизации должны быть завершены.

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

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

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

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

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

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

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

гого времени).

Другое важное отличие от предыдущих моделей непротиворечивости заключа-

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

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

формой

непротиворечиво-

сти.

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

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

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

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

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

го нового. Множество компиляторов «плутуют» таким же образом. Для примера

рассмотрим фрагмент программы из листинга

6.1,

где все переменные инициали-

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

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

результат и не обновляя эти переменные в памяти. Только вызов функции f за-

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

скольку f должна ими пользоваться. Это типичный пример оптимизация компи-

лятора.

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

репликация

Листинг 6.1. Хранение в регистрах некоторых переменных

Inta.b.c.d.e.x.y:

переменные

int

'^р.

*q:

указатели

int f(int *р. int

*q);

прототип функции

= X *

х: //а хранится

регистре

= у *

у;

// b

тоже

a*a*a

b*b

a*b:

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

a*a*c:

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

&а;

// р

получает адрес

&Ь:

// q

получает адрес

f(p. q):

вызов функции

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

компилятор знает, что делает (а программу не волнует, что значения в памяти не

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

из памяти без ограничений, эта схема перестанет работать. Так, например, если в

ходе присвоения значения

второй процесс считает а,

и с, он получит противо-

речивые данные (старые значения а и b и новое значение с). Для предупрежде-

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

тор сначала должен считывать специальный бит (флаг), сигнализирующий, что

память не актуальна. Если доступ к а хочет получить другой процесс, ему при-

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

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

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

Обсудим теперь относительно менее отвлеченную ситуацию. На рис. 6.10, а

мы видим, что процесс Р1 осуществляет две записи значений элементов данных,

после чего синхронизируется (показано буквой S). Если Р2 и РЗ к этому моменту

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

того,

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

P1:W(x)a W(x)b S P1:W(x)a W(x)b S

P2:

R(x)a R(x)b S P2: S R(x)a

P3:

R(x)b R(x)a S

Рис. 6.10. Допустимая при слабой непротиворечивости последовательность событий (а).

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

Ситуация на рис. 6.10, б иная. Здесь процесс Р2 синхронизирован. Это озна-

чает актуальность его локальной копии хранилища данных. Когда он будет счи-

тывать значение х, он получит значение

Ь.

Получение а, как видно из рисунка,

при слабой непротиворечивости невозможно.

6.2.6. Свободная непротиворечивость

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

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

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

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

данных, то ли наоборот начал чтение данных. Соответственно, оно может пред-

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

шены (то есть распространены на все копии) все локально инициированные опе-

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

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

из нее, может потребоваться более эффективная реализация. Для предоставле-

ния этой информации необходимо два типа переменных или два типа операций

синхронизации, а не один.

Свободная непротиворечивость {release consistency)

предоставляет эти два ти-

па

[165].

Операция захвата {acquire) используется для сообщения хранилищу

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

освобождения {release)

гово-

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

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

специальными переменными; во-вторых, специальными операциями. В любом

случае программист отвечает за вставку в программу соответствующего допол-

нительного кода, реализующего, например, вызов библиотечных процедур acquire

и release или процедур enter_cr1tical_reg1on и leave_crit1cal_reg1on.

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

ских областей можно использовать барьеры. Барьер {barrier) — это механизм

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

под номером п+1 до того, как все процессы окончат фазу п. Когда процесс по-

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

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

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

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

—

по освобождению.

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

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

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

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

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

вость, называются

защищенными

{protected).

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

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

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

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

измененные защищенные данные будут распространены на другие локальные

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

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

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

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

довательность событий. Процесс Р1 производит захват, дважды изменяет эле-

мент данных, а затем производит освобождение. Процесс Р2 производит захват

считывает элемент данных. Он гарантировано получает значение, которое эле-

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

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

хват Р2 происходит раньше, чем захват Р1). Если захват произошел до того, как

процесс Р1 произвел освобождение, захват будет ожидать совершения освобож-

дения. Поскольку процесс РЗ не сможет осуществить захват до чтения совместно

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

значение х, и этому процессу будет возвращено значение а.

Р1:

Acq(L) W(x)a \

Р2:

РЗ:

Л/(х)Ь Rel(L)

Acq(L) R(x)b

Rel(L)

R(x)a

Рис.

6.11.

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

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

ее возможную реализацию (несложную) в контексте реплицируемой базы дан-

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

синхронизации, запрашивая захват отдельной блокировки. В отсутствии других

желающих запрос удовлетворяется и происходит захват. Затем следует произ-

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

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

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

пользуют эти данные. После того как каждая копия подтвердит получение этих

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

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

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

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

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

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

не единственный подход. Вообще говоря, распределенное хранилище данных яв-

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

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

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

стью закончены.

"¥ Перед выполнением освобождения все предыдущие операции чтения и за-

писи этого процесса должны быть полностью закончены.

> Доступ к синхронизируемым переменным должен обладать непротиворе-

чивостью FIFO (последовательная непротиворечивость не требуется).

Если все эти условия выполнены и процессы правильно (то есть попарно) ис-

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

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

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

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

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

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

сво-

бодная

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

{lazy

release consistency)

[231].

При обычной свобод-

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

энергичной свободной