Линеаризуемость и последовательная непротиворечивость

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

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

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

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

В противоположность происходящему на схеме (б) последовательная непротиворечивость нарушается, поскольку не все процессы видят одинаковое чередование операций записи. В частности, для процесса РЗ дело выглядит так, что элемент данных сначала принимает значение b, а затем — а. С другой стороны, Р4 полагает, что итоговое значение элемента данных — b.

Хранилище данных называется линеаризуемым, если каждая операция имеет отметку време­ни и соблюдается следующее условие: результат всякого действия такой же, как если бы все операции (чтения и записи) всех процессов с хранилищем дан­ных выполнялись бы в некотором последовательном порядке, причем операции ка­ждого отдельного процесса выполнялись бы в этой последовательности в порядке, определенном в их программах, и, кроме того, если ts_OP1(x)< ts_OP2(x), то операция OP(x) в этой последовательности должна предшествовать операции ОР2(у).

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

Рассмотрим три параллельно выполняющихся процесса P1, P2 и РЗ, приведенные в таблице. Элементы данных в этом примере представлены тремя целыми переменными — х, у и z, которые хранятся в последовательно непротиворечивом хранилище данных, предназначенном для совместного доступа. Предположим, что каждая из перемен инициализирована нулем. В этом примере присвоение соответствует операции записи, а инструкция print — одновременным операциям чтения обоих аргументов. Все инструкции считаются неделимыми.

Процесс Р1	Процесс Р2	Процесс РЗ
x = 1;	y = 1;	z = 1;
print(у, z);	print(x, z):	print(x, y);

При выполнении возможны различные варианты чередования. Имея шесть независимых выражений, мы получаем 720 (6!) потенциально возможных после­довательностей выполнения, хотя некоторые из них нарушают порядок, задан­ный в программах. Рассмотрим 120 (5!) последовательностей, которые начи­наются с х=1. В половине из них инструкция print(x.z) выполняется раньше инструкции у=1, а потому нарушают порядок выполнения инструкций програм­мы. Еще у половины инструкция print(x.y) выполняется раньше инструкции z=l и также нарушают порядок выполнения инструкций программы. Только 1/4 из 120 последовательностей являются допустимыми (всего 30). Еще 30 допустимых последовательностей могут начинаться с инструкции у=1 и еще 30 — с инструк­ции 2=1, давая в сумме 90 допустимых последовательностей выполнения инст­рукций. Четыре из них приведены в таблице.

	Вариант
Инструкции «. Инструкции	x = 1;	x = 1;	y = 1;	y = 1;
	print(у, z);	y = 1;	z = 1;	x = 1;
	y = 1;	print(x, z):	print(x, y);	z = 1;
	print(x, z):	print(у, z);	print(x, z):	print(x, z):
	z = 1;	2-1;	x = 1;	print(у, z);
	print(x, y);	print(x, y);	print(у, z);	print(x, y);
Печать
Сигнатура

В варианте 1 три процесса запускаются в следующем порядке: P1, Р2, РЗ, В трех других вариантах демонстрируются различные, но допустимые чередования выражений во времени.

Если мы объединим результаты работы процессов Р1, Р2 и РЗ в таком порядке, мы получим строку из шести битов, характеризующую частичное чередование инструкций. Эта строка в таблице представлена в графе «Сигнатура», Ниже мы характеризуем каждый из вариантов по его сигнатуре, а не по результатам печати.

Не все из 64 сигнатур допустимы. Сигнатура 000000 не разрешена, поскольку означает, что инструкции печати выполнены раньше, чем инструкции присваивания, что нарушает требования о выполнении инструкций в порядке, предусмотренном программой. Более сложный пример — 001001. Пер­вые два бита, 00, означают, что переменные у и z в момент их печати были равны нулю. Такая ситуация может возникнуть только в том случае, если обе инструк­ции из процесса Р1 выполняются до начала выполнения процессов Р2 и РЗ. Сле­дующие два бита, 10, означают, что Р2 выполняется после начала выполнения Р1, но до начала выполнения РЗ. Последние два бита, 01, означают, что выполнение РЗ должно закончиться до начала выполнения Р1, но мы уже видели, что про­цесс Р1 должен выполняться первым. Таким образом, сигнатура 001001 недопу­стима.

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

Хотя последовательная непротиворечивость и дает удобную для программистов модель, она имеет серьезные проблемы с производительностью. Доказано, что при времени чтения r, времени записи w и минимальном времени передачи пакета между узлами t всегда выполняется условие г + w ≥ t. Другими словами, для всякого последовательно непротиворечивого хранилища изменение протокола для увеличения скорости чтения вызывает падение скорости записи, и наоборот.

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