Регистры: различия между версиями

Задача состоит в конструировании общих переменных, для которых выполняются следующие два свойства. (1) Выполнение операций не обязательно атомарно, то есть они не являются неделимыми, а состоят из атомарных подопераций; (2) каждая операция завершает свое выполнение за ограниченное число собственных шагов, независимо от наличия других операций и их относительной скорости. Таким образом, выполнение операций ''не требует ожидания''. Эти два свойства дают основание для классификации общих переменных в зависимости от их выходных характеристик. Лэмпорт [8] выделяет три категории общих переменных с одним райтером, используя отношение предшествования для выполнения операций, определяемое следующим образом: при выполнении операций A и B операция A ''предшествует'' B (обозначается <math> A \to B</math>), если A завершается до начала B; A и В ''перекрываются', если ни A не предшествует B, ни B не предшествует A. Среди переменных с одним райтером все операции записи полностью упорядочены согласно отношению "<math>\to</math>". Лэмпорт следующим образом определяет три категории общих переменных с одним райтером:

В серии статей, начиная с 1974 года (подробнее см. в [4]), Лэмпорт исследовал различные понятия одновременного чтения и записи общих переменных; кульминацией этих статей стала основополагающая работа 1986 года [8]. В ней сформулировано понятие не требующей ожидания реализации атомарной многозначной общей переменной – записываемой одним райтером и считываемой (другим) одним ридером – из безопасных двузначных общих переменных с одним райтером и одним ридером, являющихся математическими версиями физических ''триггеров', позднее оптимизированных в работе [13]. Лэмпорт не рассматривал конструирование общих переменных с более чем одним райтером или ридером.

Еще до статьи Лэмпорта, в 1983 году, Петерсон [10] опубликовал изобретательный способ конструирования без ожидания атомарной m-значной общей переменной с одним райтером и n ридерами из n + 2 безопасных m-значных регистров с одним райтером и n ридерами, 2n 2-значных атомарных общих переменных с одним райтером и 1 ридером и двух 2-значных атомарных общих переменных с одним райтером и n ридерами. Он также представил надлежащее понятие самого свойства «без ожидания». В своей работе Петерсон не говорил о том, как построить n-ридерные булевы атомарные переменные из триггеров, а Лэмпорт упомянул об этом как о нерешенной проблеме; впрочем, он использует версию построения Петерсона для преодоления алгоритмически сложного шага от атомарных общих битов к атомарным общим многозначным переменным. На основе этой работы Н. Линч, заинтересованная параллельным управлением многопользовательскими базами данных, около 1985 года поставила вопрос о том, как конструировать не требующие ожидания атомарные переменные с несколькими райтерами из атомарных переменных с одним райтером и несколькими ридерами. Ее ученик Блум [1] в 1985 году нашел элегантный способ построения для случая с двумя райтерами, который, однако, не поддавалася обобщению на сиуацию с несколькими райтерами. Витаньи и Авербух [14] в 1986 году первыми определили и исследовали сложное понятие не требующего ожидания построения атомарных переменных общего вида с несколькими райтерами. Они представили метод доказательства в виде неограниченного решения построения из атомарных переменных с 1 райтером и 1 ридером и ограниченного решения построения из атомарных переменных с 1 райтером и n ридерами. Оказалось, что ограниченное решение не является атомарным, а лишь достигает регулярности (см. раздел «Исправления» в работе [14]). В статье были введены важные понятия и методы в этой области, такие как (ограниченные) векторные часы, и определены открытые вопросы, такие как построение атомарных ограниченных мультиридерных общих переменных без ожидания из триггеров, а также построение атомарных ограниченных мультирайтерных общих переменных без ожидания из мультиридерных переменных. Петерсон, работавший над проблемой мультирайтерных переменных в течение десятилетия, в 1987 году вместе с Бернсом попытался устранить ошибку в построении неограниченных переменных из [14], сохранив идею векторных часов, но заменив технику отслеживания устаревшей информации на повторное сканирование, как в работе [10]. Результат [11] был признан ошибочным в техническом отчете (R. Schaffer, On the correctness of atomic multiwriter registers, Report MIT/LCS/TM-364, 1988). Ни исправление в техническом отчете Шаффера, ни заявленная авторами [11] коррекция не появились в печати.  Также в 1987 году появилось не менее пяти предполагаемых решений для реализации построения атомарной общей переменной с одним райтером и n ридерами из переменных с одним райтером и одним ридером: [2, 7, 12] (остальные см. [4]), из которых одно [2] было объявлено неверным (S. Haldar, K. Vidyasankar, ACM Oper. Syst. Rev, 26:1(1992), 87-88), и только работа [12] появилась в журнальной версии. Статья [9], первоначально опубликованная в 1987 году в Гарвардском техническом отчете, одним махом разрешила все многопользовательские построения: она конструирует ограниченную атомарную переменную с n райтерами и n ридерами (мультирайтерную) из <math>O(n^2)</math> безопасных 1-ридерных и 1-райтерных бит, что является оптимальным, и <math>O(n^2)</math> обращений к битам на операцию чтения/записи, что также оптимально. Она работает за счет того, что делает неограниченное решение [14] ограниченным с помощью новой техники, что позволяет получить надежное доказательство корректности. «Проекции» этого построения дают специализированные построения для реализации атомарных переменных с 1 райтером и n ридерами (мультиридерных) из <math>O(n^2)</math> 1-ридерных и 1-райтерных  переменных с использованием O(n) обращений к битам на операцию чтения/записи, а также для реализации атомарных переменных с n райтерами и n ридерами (мультирайтерных) из <math>O(n^2)</math> безопасных 1-ридерных и n-райтерных (мультиридерных) переменных. Первая «проекция» является оптимальной, однако последняя может быть неоптимальной, поскольку она использует O(n) управляющих бит на одну операцию записи, в то время как была установлена только нижняя граница <math>\Theta(log \ n)</math>. Принимая вызов, построение в работе [6] претендует на достижение этой нижней границы.

Для мультирайтерной общей переменной необходимо только, чтобы каждый процесс отслеживал, какой процесс последним произвел в нее запись. В связи с этим возникает общий вопрос: может ли каждый процесс отслеживать порядок последних записей всех процессов? Израэли и Ли начали исследование этой темы в работе [14], после чего в важной статье [5] они подняли и решили вопрос о более общем и универсально применимом понятии ограниченной системы временных меток для отслеживания порядка событий в параллельной системе. В системе временных меток каждый процесс владеет ''объектом'' – абстракцией набора общих переменных. Одним из требований к системе является определение временного порядка, в котором записываются объекты. Для этого каждому объекту присваивается ''метка'' (также называемая ''временной меткой''), в которой записывается последнее (относительное) время, когда в него процессом-владельцем производилась запись. Процессы присваивают метки своим соответствующим объектам таким образом, чтобы эти метки отражали порядок операций записи в реальном времени. Такие системы должны поддерживать две операции, а именно ''маркировку'' (присваивание меток) и ''сканирование''. Выполнение операции маркировки (Labeling) присваивает объекту новую метку, а выполнение операции сканирования (Scan) позволяет процессу определить порядок, в котором записаны все объекты, то есть возвращает набор помеченных объектов, упорядоченных по времени. Проблемы возникают в системах, в которых операции могут выполняться ''параллельно'', перекрываясь друг с другом. Более того, выполнение операций должно производиться ''без ожидания'', то есть каждая операция будет выполнять ограниченное количество своих шагов (количество обращений к общему пространству), независимо от наличия других операций и их относительных скоростей. Израэли и Ли [5] построили битово-оптимальную систему ограниченных временных меток для ''последовательного'' выполнения операций. Предложенная ими система последовательных временных меток была опубликована в упомянутом журнале, однако предварительное представление системы параллельных временных меток в материалах конференции, более подробная версия которой была распространена в виде рукописи, не было опубликовано в окончательном виде. Первое общепризнанное решение ''параллельного'' случая системы ограниченных временных меток было получено в работе Долева и Шавита [3]. Их построение относится к типу, представленному в [5], и использует общие переменные размера O(n), где n – количество процессов в системе. Каждая маркировка требует O(n) шагов, каждое сканирование – <math>O(n^2 \; log \; n)</math> шагов. (Под «шагом» понимается обращение к битовой переменной размером O(n)). В работе [4] неограниченное построение из [14] было исправлено и расширено для получения эффективной версии более общего понятия ограниченной параллельной системы временных меток.

Регистры без ожидания, наряду с системами передачи сообщений, являются основным механизмом взаимодействия между процессами в теории распределенных вычислений. Они лежат в основе всех построений и протоколов, как можно увидеть в учебниках. Не требующие ожидания построения параллельных систем временных меток (сокращенно CTS) оказались мощным инструментом для решения задач управления параллелизмом, таких как различные типы взаимного исключения, мультирайтерные и мультиридерные общим переменные [14] и вероятностный консенсус, в результате синтеза «часов без ожидания» для определения последовательности действий в параллельной системе. Более подробное изложение см. в работе [4].

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

* [[Атомарная широковещательная передача]]