Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 89
Текст из файла (страница 89)
Эта последовательность допустима для хранилища с причиннойнепротиворечивостью, но недопустима для хранилища со строгойили последовательной непротиворечивостьюРассмотрим теперь второй пример. На рис. 6.8, а мы видим, что W2{x)h потенциально зависит от W1{x)a, поскольку b может быть результатом вычислений, в которые входит значение, прочитанное операцией 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)aW(x)bR(x)bR(x)aR(x)aR(x)bP1: W(x)aP2:P3:P4:W(x)bR(x)bR(x)aR(x)aR(x)bРис. 6.8, Нарушение причинной непротиворечивости хранилища (а).
Правильнаяпоследовательность событий в хранилище с причинной непротиворечивостью (а)Реализация причинно-следственной непротиворечивости требует отслеживать,какие процессы какие записи видели. Это можно успешно проделать, создав иподдерживая граф зависимостей, на котором будет указана взаимная зависимостьопераций друг от друга. Один из способов сделать это — воспользоваться векторными отметками времени, которые мы обсуждали в предыдущей главе.
Позже мыеще вернемся к использованию векторных отметок времени для определенияпричинно-следственной связи.6.2.4. Непротиворечивость FIFOв случае причинно-следственной непротиворечивости допустимо, чтобы на различных машинах параллельные операции записи наблюдались в разном порядке,но операции записи, связанные причинно-следственной связью, должны иметьодинаковый порядок выполнения, с какой бы машины ни велось наблюдение.Следующим шагом в ослаблении непротиворечивости будет освобождение от последнего требования. Это приведет нас к непротиворечивости FIFO (FIFO consistency), которая подчиняется следующему условию: операции записи, осуществляемые единичным процессом, наблюдаются всеми остальными процессами в томпорядке, в котором они осуществляются, но операции записи, происходящие вразличных процессах, могут наблюдаться разными процессами в разном порядке.Непротршоречивость FIFO в случае распределенных систем с совместно используемой памятью называют также непротиворечивостью PRAM (PRAM consistency).
Она описана в [268]. Сокращение PRAM происходит от Pipelined RAM(конвейерная оперативная память), потому что запись, производимая одним процессом, может быть конвейеризована, в том смысле, что процесс не должен терять скорость, ожидая окончания одной операции записи, чтобы начать другую.Сравнение непротиворечивости FIFO с причинной непротиворечивостью иллюстрирует рис.
6.9. Приведенная последовательность событий допустима для хранилища данных с непротиворечивостью FIFO, но запрещена для любой болеестрогой модели из тех, которые мы рассматривали.Непротиворечивость FIFO интересна нам из-за простоты ее реализации. В действительности она не дает никаких гарантий того, в каком порядке операции записи будут наблюдаться в различных процессах, исключая порядок прохожде-6.2. Модели непротиворечивости, ориентированные на данные345ния двух или более операций записи, принадлежащих одному процессу.
Если изложить это другими словами, в этой модели все операции записи во всех процессах являются параллельными. Эта модель может быть реализована просто путемименования каждой операции парой (процесс, очередной помер) и осуществлением операций записи каждого из процессов в порядке их номеров.P1:W(x)aР2:РЗ:Р4:R(x)aW(x)bW(x)cR(x)bR(x)aR(x)a R(x)cR(x)b R(x)cРис. 6.9. Допустимая последовательность событий для непротиворечивости FIFOРассмотрим вновь три процесса из табл. 6.1, опираясь на этот раз на непротиворечивость FIFO вместо последовательной непротиворечивости. При условиинепротиворечивости FIFO различные процессы могут наблюдать выполнениеинструкций в различном порядке (табл. 6.3). Так, например, в варианте 1 показано, как выглядит последовательность событий с точки зрения процесса Р1,в варианте 2 — с точки зрения процесса Р2, а в варианте 3 — с точки зрения процесса РЗ (наблюдаемые результаты создают инструкции, выделенные жирнымшрифтом).
В условиях последовательной непротиворечивости три различныхпредставления были бы недопустимы.Таблица 6.3. Очередность выполнения инструкций с точки зрения трех процессов,представленных в табл. 6.1ВариантИнструкцииПечать123х=1:х=1:y=l;print(y,z):у=1:print(x.z):у=1:prlnt(x.z);z=l:prlnt(x.z);prlnt(y.z):printCx.y);z=l:z=l:x=l;prlnt(x.y):prlnt(x.y):prlnt(y.z):001001Если мы объединим результаты трех процессов, то получим итоговый результат 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Процесс Р 2х=1:if (у == 0) k1ll(P2):У=1:1f(x= =0)k1ll(Pl):6.2.5. Слабая непротиворечивостьХотя непротиворечивость FIFO и дает большую производительность, чем болеестрогие модели непротиворечивости, для многих приложений она остается излишне строгой, поскольку требует, чтобы операции записи одного процесса отовсюду наблюдались в одном и том же порядке.
Не все приложения нуждаются даже в том, чтобы наблюдать все операции записи, не говоря уже .об их порядке.Рассмотрим случай, когда процесс внутри критической области заносит записи вреплицируемую базу данных. Хотя другие процессы даже не предполагают работать с новыми записями до выхода этого процесса из критической области, система управления базой данных не имеет никаких средств, чтобы узнать, находитсяпроцесс в критической области или нет, и может распространить изменения навсе копии базы данных.Наилучшим решением в этом случае было бы позволить процессу покинутькритическую область и затем убедиться, что окончательные результаты разосланы туда, куда нужно, и не обращать внимания на то, разосланы всем копиям промежуточные результаты или нет.
Это можно сделать, введя так называемую переменную синхронизации {synchronization variable). Переменная синхронизации Sимеет только одну ассоциированную с ней операцию, synchronize(S), которая синхронизирует все локальные копии хранилища данных. Напомним, что процесс Росуществляет операции только с локальной копией хранилища. В ходе синхронизации хранилища данных все локальные операции записи процесса Р распространяются на остальные копии, а операции записи других процессов — на копию данных Р.Используя переменные синхронизации для частичного определения непротиворечивости, мы приходим к так называемой слабой непротиворечивости {weakconsistency) [130].
Модель слабой непротиворечивости имеет три свойства."¥ Доступ к переменным синхронизации, ассоциированным с хранилищем данных, производится на условиях последовательной непротиворечивости.6.2. Модели непротиворечивости, ориентированные на данные3474 С переменной синхронизации не может быть произведена ни одна операция до полного и повсеместного завершения предшествующих ей операций записи.4^ С элементами данных не может быть произведена ни одна операция дополного завершения всех операций с переменными синхронизации.Первый пункт гласит, что все процессы могут наблюдать за всеми операциями над переменными синхронизации, которые с точки зрения этих процессовпроисходят в одинаковом порядке. Другими словами, если процесс Р1 вызываетоперацию synchronlze(Sl) в то же самое время, когда процесс Р2 вызывает операцию synchron1ze(S2), результат будет точно таким же, как если бы операцияsynchronlze(Sl) была вызвана раньше операции synchronize(S2), или наоборот.Второй пункт указывает на то, что синхронизация очищает конвейер.
Она ускоряет выполнение всех операций чтения, которые в этот момент происходят,частично завершены или завершены в некоторых локальных копиях, и приводитих к повсеместному завершению. Когда синхронизация заканчивается, гарантировано заканчиваются все предшествовавшие ей операции записи. Производя синхронизацию после изменения совместно используемых данных, процесс переносит новые значения во все локальные копии хранилища.Третий пункт поясняет, что при доступе к элементам данных (как для записи,так и для чтения) все предшествующие синхронизации должны быть завершены.Производя перед чтением совместно используемых данных синхронизацию, процесс может быть уверен, что получит самые «свежие» значения.В отличие от предыдущих моделей непротиворечивости, слабая непротиворечивость реализует непротиворечивость групп операций, а не отдельных операций чтения и записи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
