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

Слабая непротиворечивость имеет проблему следующего рода: когда осуществляется доступ к переменной синхронизации, хранилище данных не знает, происходит это потому, что процесс закончил запись совместно используемых данных, или наоборот начал чтение данных. Соответственно, оно может предпринять действия, необходимые в обоих случаях, например, убедиться, что завершены (т.е., распространены на все копии) все локально инициированные операции записи и что учтены все операции записи с других копий. Если хранилище должно распознавать разницу между входом в критическую область и выходом из нее, может потребоваться более эффективная реализация. Для предоставления этой информации необходимо два типа переменных или два типа операций синхронизации, а не один.

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

В случае свободной непротиворечивости, кроме того, независимо от критиче­ских областей можно использовать барьеры. Барьер — это механизм синхронизации, который предваряет любой процесс в начале фазы программы под номером n+1 до того, как все процессы окончат фазу n. Когда процесс по­дойдет к барьеру, он должен дождаться, пока к нему не «подтянутся» и все ос­тальные процессы. Когда последний из процессов подойдет к барьеру, все совме­стно используемые данные синхронизируются, и процессы продолжают свою работу. Отправление от барьера выполняется по захвату, а приход к барьеру — по освобождению.

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

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

На схеме показана допустимая последовательность событий. Процесс Р1 производит захват, дважды изменяет элемент данных, а затем производит освобождение. Процесс Р2 производит захват и считывает элемент данных. Он гарантировано получает значение, которое элемент данных имел в момент освобождения, а именно b (кроме случая, когда захват Р2 происходит раньше, чем захват Р1). Если захват произошел до того как процесс Р1 произвел освобождение, захват будет ожидать совершения освобождения. Поскольку процесс РЗ не сможет осуществить захват до чтения совместно используемых данных, хранилище данных не будет обязано выдать ему текущее значение х, и этому процессу будет возвращено значение а.

Р1: Acq(L) W(x)a W(x)b Rel(L) _

P2: Acq(L) R(x)b Rel(L) _

P3: R(x)a

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

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

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

Доступ к синхронизируемым переменным должен обладать непротиворечивостью FIFO (последовательная непротиворечивость не требуется).

Дата добавления: 2015-08-18