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

Модель строгой непротиворечивости определяется следующим условием: всякое чтение элемента данных х возвращает значение, соответствующее результату последней записи х.

Это определение естественно и очевидно, хотя подразу­мевает существование абсолютного глобального времени, в котором определение «последней» однозначно. Однопроцессорные сис­темы традиционно соблюдают строгую непротиворечивость, и программисты таких систем склонны рассматривать такое поведение, как естественное. Рассмотрим следующую программу:

а = 1; а = 2; print(a);

Система, в которой эта программа напечатает 1 или любое другое значение, кроме 2, приведет к явному недовольству программистов.

Для системы, в которой данные разбросаны по нескольким машинам, а до­ступ к ним имеет несколько процессов, все сильно усложняется. Допустим, что х — элемент данных, хранящийся на машине В. Представим, что процесс, ра­ботающий на машине А, читает х в момент времени t₁, то есть посылает В сооб­щение с требованием возвратить х. Чуть позже, в момент времени t₂, процесс с машины В производит запись х. Если строгая непротиворечивость сохраняется, чтение должно всегда возвращать прежнее значение, которое не зависит от того, где находятся машины и насколько мал интервал между t₁ и t₂. Однако если t₂ - t₁ = 1 нс., а машины расположены в трех метрах друг от друга, то чтобы запрос на чтение от А к В дошел до машины раньше В с правления запроса на запись, он должен двигаться в 10 раз быстрее скорое света, а это противоречит теории относительности Эйнштейна.

Для детального изучения непротиворечивости будем использовать специальную нотацию, при помощи которой отобразим операции процессов на ось времени. Ось времени рисуется горизонтально, время увеличивается слева направо. Сим­волы W_i(x)a и R_i(x)b означают соответственно, что выполнены запись процес­сом Р в элемент данных х значения а и чтение из этого элемента процессом Р, возвратившее b. Мы полагаем, что каждый элемент данных первоначально был инициализирован нулем. Если с процессом доступа к данным не было никаких проблем, мы можем опустить индексы у символов W и R.

На схеме (а) процесс Р1 осуществляет запись в элемент данных х, изменяя его значение на а. Отметим, что в принципе эта операция, W₁(x)a, сначала производит копирование значения в локальное хранилище дан­ных Р1, а затем распространяет его и на другие локальные копии. В нашем примере Р2 позже читает значение х из его локальной копии в хранилище и обнаружи­вает там значение а. Такое поведение характерно для хранилища данных, сохра­няющего строгую непротиворечивость. В противоположность ему, на схеме (б) процесс Р2 производит чтение после записи (возможно, лишь на наносекунду позже, но позже) и получает нуль (NIL). Последующее чтение возвращает а. Такое поведение для хранилища данных, сохраняющего строгую непротиворечивость, некорректно.

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

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