Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 87
Текст из файла (страница 87)
Соответственно, мы вынуждены учитывать возможность наличия в одном интервале нескольких операций. Аналогично ситуации параллельного выполнения распределенных транзакций, две операции в одном и том же интервале приводят к конфликту, если производятся над однимии теми же данными, и одна из них — операция чтения. Важный момент для определения модели непротиворечивости — точно выяснить, какой тип поведенияприменим при наличии конфликтующих операций.Для детального изучения непротиворечивости мы можем привести несколькопримеров. Чтобы сделать эти примеры точнее, мы нуждаемся в специальной нотации, при помощи которой отобразим операции процессов на ось времени.
Осьвремени всегда рисуется горизонтально, время увеличивается слева направо. Символы Wi(x)a и Ri(x)b означают соответственно, что выполнены запись процессом Р в элемент данных х значения а и чтение из этого элемента процессом Р,возвратившее Ь. Мы полагаем, что каждый элемент данных первоначально былинициализирован нулем. Если с процессом доступа к данным не было никакихпроблем, мы можем опустить индексы у символов Wn R.В качестве примера на рис. 6.5, а процесс Р1 осуществляет запись в элементданных Ху изменяя его значение на а. Отметим, что в принципе эта операция,W1(x)aj сначала производит копирование значения в локальное хранилище данных Р1, а затем распространяет его и на другие локальные копии. В нашем примереР2 позже читает значение х из его локальной копии в хранилище и обнаруживает там значение а.
Такое поведение характерно для хранилища данных, сохраняющего строгую непротиворечивость. В противоположность ему, на рис. 6.5, бпроцесс Р2 производит чтение после записи (возможно, лишь на наносекундупозже, но позже) и получает нуль (NIL). Последующее чтение возвращает а. Такоеповедение для хранилища данных, сохраняющего строгую непротиворечивость,некорректно.Р1:Р2:W(x)aR(x)aР1:Р2:W(x)aR(x)NILR(x)aРис. 6.5. Поведение двух процессов, работающих с одним и тем же элементом данных.Горизонтальная ось — время. Хранилище со строгой непротиворечивостью (а).Хранилище без строгой непротиворечивости (б)Итак, когда хранилище данных строго непротиворечиво, все операции записимгновенно замечаются всеми процессами.
Выдерживается абсолютный глобальный порядок по времени. Если элемент данных изменяется, все последующиеоперации чтения, совершаемые с данными, возвращают новое значение, при этомневажно, как скоро после изменения производится чтение, и не имеет значения,какой процесс производит чтение и где он расположен. Соответственно, если производится чтение, оно возвращает это текущее значение, и неважно, как быстропосле этого производится следующая запись.338Глава 6. Непротиворечивость и репликацияВ следующем пункте мы ослабим требования этой модели, заменив абсолютное время временными интервалами, и точно определим приемлемое поведениедля конфликтующих операций.6.2.2.
Линеаризуемость и последовательнаянепротиворечивостьХотя строгая непротиворечивость и представляет собой идеальную модель непротиворечивости, реализовать ее в распределенных системах невозможно. Крометого, опыт показал, что программисты часто могут значительно лучше управлятьне столь строгими моделями. Так, например, все книги по операционным системам содержат обсуждение проблем критических областей и взаимных исключений. При этом, как правило, имеется предупреждение о том, что правильно написанные параллельные программы (такие, как программа «производитель—потребитель») не должны делать никаких предположений об относительных скоростяхпроцессов или об очередности выполнения инструкций. Обработка двух событийв одном процессе происходит так быстро, что другой процесс не в состоянии сделать что-нибудь, если между ними обнаружит проблему.
Вместо этого читателяучат программировать так, чтобы точный порядок выполнения инструкций (насамом деле, ссылок на память) не имел никакого значения. Если важна очередность событий, следует использовать семафоры или другие операции синхронизации. Принятие этого аргумента означает согласие на модель слабой непротиворечивости.Последовательная непротиворечивость {sequential consistency) — это менее строгая модель непротиворечивости. Впервые она была определена в [250] в контексте совместно используемой памяти мультипроцессорных систем. В общем, хранилище данных считается последовательно непротиворечивым, если оно удовлетворяет следующему условию: результат любого действия такой же^ как если быоперации {чтения и записи) всех процессов в хранилище данных выполнялись бы внекотором последовательном порядке у причем операции каждого отдельного процесса выполнялись бы в порядке, определяемом его программой.Это определение означает, что когда процессы выполняются параллельно наразличных (возможно) машинах, любое правильное чередование операций чтения и записи является допустимым, но все процессы видят одно и то же чередование операций.
Отметим, что о времени никто не вспоминает, то есть никто нессылается на «самую последнюю» операцию записи объекта. Отметим, что в данном контексте процесс «видит» записи всех процессов, но только свои собственные чтения.Итак, время роли не играет, что мы и видим на рис. 6.6. Рассмотрим работучетырех процессов с одним элементом данных х. На рис. 6.6, а сначала процессР1 осуществляет запись W{x)a в элемент х. Позднее (по абсолютному времени)процесс Р2 также осуществляет запись, устанавливая значение хвЬ.
Однако обапроцесса, РЗ и Р4, сначала читают значение b и лишь затем — значение а. Другими словами, операция записи процесса Р2 представляется им происходящейраньше записи процесса Р1.6.2. Модели непротиворечивости, ориентированные на данныеР1 W(x)aР2W(x)bРЗР4R(x)bR(x)aR(x)b R(x)a339P1 W(x)aP2W(x)bR(x)bR(x)aP3P4R(x)a R(x)bРис. 6.6. Хранилище данных с последовательной непротиворечивостью (а).Хранилище данных без последовательной непротиворечивости (б)В противоположность происходящему на рис.
6.6, а, на рис. 6.6, б последовательная непротиворечивость нарушается, поскольку не все процессы видят одинаковое чередование операций записи. В частности, для процесса РЗ дело выглядит так, что элемент данных сначала принимает значение Ь, а затем — а. С другойстороны, Р4 полагает, что итоговое значение элемента данных — Ь.Модель непротиворечивости, более слабая, чем строгая непротиворечивость,но более сильная, чем последовательная — это линеаризуемость {linearizability).Согласно этой модели операции получают отметку времени, используя глобальные часы, имеющие конечную точность.
Такие часы могут быть реализованы в распределенной системе из предположения, что у процессов имеются слабо синхронизированные часы, которые обсуждались в предыдущей главе. Пусть tsop{x) —это отметка времени, назначенная операции ОР, которая работает с элементомданных X, причем ОР — это операция чтения {К) или записи (W). Хранилищеданных называется линеаризуемым, если каждая операция имеет отметку времени и соблюдается следующее условие [199]: результат всякого действия такойже у как если бы все операции {чтения и записи) всех процессов с хранилищем данных выполнялись бы в некотором последовательном порядке, причем операции каждого отдельного процесса выполнялись бы в этой последовательности в порядкеопределенном в их программах, и, кроме того, если tsopi(x) < tSoP2{x), то операция0Р1(х) в этой последовательности должна предшествовать операции 0Р2(у).Отметим, что линеаризуемое хранилище данных обладает еще и последовательной непротиворечивостью.
Разница между ними состоит в том, что при учете упорядоченности во внимание принимаются также установки синхронизированных часов. На практике линеаризуемость используется в первую очередь длясодействия в формальном подтверждении параллельных алгоритмов [199]. Дополнительные ограничения, такие как сохранение упорядоченности в соответствии с отметками времени, делает затраты на реализацию линеаризации выше,чем на реализацию последовательной непротиворечивости, как показано в [20].Последовательная непротиворечивость напоминает сериализуемость в транзакциях, о которой мы говорили в предыдущей главе.
Напомним, что набор параллельно выполняющихся транзакций считается сериализуемым, если итоговыйрезультат может быть получен путем выполнения этих транзакций последовательно с определенной очередностью. Основная разница заключается в степенидетализации: последовательная непротиворечивость определяется в понятиях операций записи и чтения, а сериализуемость — в понятиях транзакций, которыеобъединяют эти операции в одно целое.340Глава 6. Непротиворечивость и репликацияЧтобы получить более конкретное представление о последовательной непротиворечивости, рассмотрим три параллельно выполняюш.ихся процесса, Р1, Р2иРЗ, приведенные в табл.
6.1 [130]. Элементы данных в этом примере представлены тремя целыми переменными — х, у и z, которые хранятся в последовательно непротиворечивом хранилище данных (возможно, распределенном), предназначенном для совместного доступа. Предположим, что каждая из переменныхинициализирована нулем. В этом примере присвоение соответствует операциизаписи, а инструкция print — одновременным операциям чтения обоих аргументов.
Все инструкции считаются неделимыми.Таблица 6 . 1 . Три параллельно выполняющихся процессаПроцесс Р1х=1;prlnt(y.z):Процесс Р2Процесс РЗz=l:prlnt(x.y):у=1:print(x.z):При выполнении возможны различные варианты чередования. Имея шестьнезависимых выражений, мы получаем 720 (6!) потенциально возможных последовательностей выполнения, хотя некоторые из них нарушают порядок, заданный в программах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
