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

Еще до статьи Лэмпорта, в 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 ридерами (мультирайтерных) из n безопасных 1-ридерных и n-райтерных (мультиридерных) переменных. Первая «проекция» является оптимальной, однако последняя может быть неоптимальной, поскольку она использует O(n) управляющих бит на одну операцию записи, в то время как была установлена только нижняя граница <math>\Omega(log \ n)</math>. Принимая вызов, построение в работе [6] претендует на достижение этой нижней границы.