Э. Таненбаум, М. ван Стеен - Распределённые системы (принципы и парадигмы) (1162619), страница 90
Текст из файла (страница 90)
Эта модель наиболее широко используется, если отдельныепроцедуры доступа к общим данным редки, а большая часть операций доступа собрана в группы (много операций за короткий срок, а потом ничего в течение долгого времени).Другое важное отличие от предыдущих моделей непротиворечивости заключается в том, что теперь мы ограничены только временем поддержания непротиворечивости, в то время как ранее мы были ограничены формой непротиворечивости. На самом деле мы можем сказать, что в случае слабой непротиворечивостисоблюдается последовательная непротиворечивость между группами операций,а не между отдельными операциями. Для выделения этих групп используютсяпеременные синхронизации.В идее о допустимости существования в памяти неверных значений нет ничего нового. Множество компиляторов «плутуют» таким же образом.
Для примерарассмотрим фрагмент программы из листинга 6.1, где все переменные инициализируются соответствующими значениями. Оптимизирующий компилятор можетпроизводить вычисление переменных а и b в регистрах, временно сохраняя тамрезультат и не обновляя эти переменные в памяти. Только вызов функции f заставляет компилятор поместить текущие значения а и b обратно в память, поскольку f должна ими пользоваться. Это типичный пример оптимизация компилятора.348Глава 6. Непротиворечивость и репликацияЛистинг 6 .
1 . Хранение в регистрах некоторых переменныхInta.b.c.d.e.x.y:int '^р. *q:int f(int *р. int *q);// переменные// указатели// прототип функцииаbcdрqе//а хранится в регистре// b тоже// будет использовано позднее// будет использовано позднее// р получает адрес а// q получает адрес b// вызов функции= X * х:= у * у;= a * a * a + b * b + a*b:=a*a*c:= &а;= &Ь:= f(p. q):В данном случае неправильные значения в памяти допустимы, потому чтокомпилятор знает, что делает (а программу не волнует, что значения в памяти неактуальны). Ясно, что если будет создан второй процесс, который может читатьиз памяти без ограничений, эта схема перестанет работать.
Так, например, если входе присвоения значения d второй процесс считает а, b и с, он получит противоречивые данные (старые значения а и b и новое значение с). Для предупреждения хаоса можно представить себе специальную защиту, при которой компилятор сначала должен считывать специальный бит (флаг), сигнализирующий, чтопамять не актуальна. Если доступ к а хочет получить другой процесс, ему придется ожидать установки флага. Таким образом, мы получим почти абсолютнуюнепротиворечивость, обеспечиваемую программной синхронизацией и тем, чтовсе стороны выполняют правила.Обсудим теперь относительно менее отвлеченную ситуацию. На рис.
6.10, амы видим, что процесс Р1 осуществляет две записи значений элементов данных,после чего синхронизируется (показано буквой S). Если Р2 и РЗ к этому моментуеще не были синхронизированы, мы не можем дать никаких гарантий по поводутого, что они увидят. Таким образом, эта последовательность событий допустима.P1:W(x)aP2:P3:W(x)bSR(x)aR(x)bR(x)bR(x)aSSP1:W(x)aP2:W(x)bSS R(x)aРис. 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 \Л/(х)Ь Rel(L)Acq(L) R(x)bР2:РЗ:Rel(L)R(x)aРис. 6.11. Допустимая последовательность событий при свободной непротиворечивостиЧтобы прояснить свободную непротиворечивость, давайте кратко определимее возможную реализацию (несложную) в контексте реплицируемой базы данных. Производя захват, процесс посылает сообщение центральному менеджерусинхронизации, запрашивая захват отдельной блокировки.
В отсутствии другихжелающих запрос удовлетворяется и происходит захват. Затем следует произвольная последовательность локальных операций чтения и записи. Ни одна изэтих операций не распространяется на другие копии базы. В процессе освобождения модифицированные данные рассылаются другим копиям, которые используют эти данные. После того как каждая копия подтвердит получение этихданных, центральный менеджер синхронизации уведомляется о произошедшемосвобождении.
Таким образом, произвольное число операций чтения и записисовместно используемых данных сопровождается фиксированными дополнительными затратами. Захваты и освобождения при разных блокировках происходят независимо друг от друга.Хотя описанный централизованный алгоритм и решает проблему, это отнюдьне единственный подход. Вообще говоря, распределенное хранилище данных является свободно непротиворечивым при условии выполнения им трех правил.> Перед выполнением операций чтения или записи совместно используемых данных все предыдущие захваты этого процесса должны быть полностью закончены."¥ Перед выполнением освобождения все предыдущие операции чтения и записи этого процесса должны быть полностью закончены.> Доступ к синхронизируемым переменным должен обладать непротиворечивостью FIFO (последовательная непротиворечивость не требуется).Если все эти условия выполнены и процессы правильно (то есть попарно) используют захваты и освобождения, результат любого выполнения не будет отличаться от порядка, характерного для последовательно непротиворечивых хранилищ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
