Регистры

Ключевые слова и синонимы

Разделяемая память (без ожидания); регистры без ожидания; общие переменные без ожидания; аппаратные средства асинхронной связи

Постановка задачи

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

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

1. Безопасная переменная – это переменная, для которой операция чтения, не перекрывающаяся с какой-либо операцией записи, возвращает последнее записанное значение. Операция чтения, перекрывающаяся с операцией записи, может вернуть любое значение из области изменения переменной.

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

3. Атомарная переменная – это обычная переменная, для которой операции чтения и записи ведут себя так, словно они выполняются в некотором общем порядке, который является расширением отношения предшествования.

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

Основные результаты

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

Система временных меток

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

Применение

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

Открытые вопросы

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

Экспериментальные результаты

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

См. также

• Невозможность асинхронного консенсуса
• Атомарная широковещательная передача
• Причинно-следственное упорядочение, логические часы, репликация конечного автомата
• Параллельное программирование, взаимное исключение
• Линеаризуемость
• Переименование
• Самостабилизация
• Моментальные снимки в совместно используемой памяти
• Синхронизаторы и остовы
• Топологический подход в распределенных вычислениях

Литература

1. Bloom, B.: Constructing two-writer atomic registers. IEEE Trans. Comput. 37(12), 1506-1514 (1988)

2. Burns, J.E., Peterson, G.L.: Constructing multi-reader atomic values from non-atomic values. In: Proc. 6th ACM Symp. Principles Distr. Comput., pp. 222-231. Vancouver, 10-12 August 1987

3. Dolev, D., Shavit, N.: Bounded concurrent time-stamp systems are constructible. SIAM J. Comput. 26(2),418-455 (1997)

4. Haldar, S., Vitanyi, P.: Bounded concurrent timestamp systems using vector clocks. J. Assoc. Comp. Mach. 49(1), 101-126 (2002)

5. Israeli, A., Li, M.: Bounded time-stamps. Distribut. Comput. 6, 205-209 (1993) (Preliminary, more extended, version in: Proc. 28th IEEE Symp. Found. Comput. Sci., pp. 371-382,1987.)

6. Israeli, A., Shaham, A.:Optimal multi-writer multireader atomic register. In: Proc. 11th ACM Symp. Principles Distr. Comput., pp. 71 -82. Vancouver, British Columbia, Canada, 10-12 August 1992

7. Kirousis, L.M., Kranakis, E., Vitanyi, P.M.B.: Atomic multireader register. In: Proc. Workshop Distributed Algorithms. Lect Notes Comput Sci, vol 312, pp. 278-296. Springer, Berlin (1987)

8. Lamport, L.: On interprocess communication—Part I: Basic formalism, Part II: Algorithms. Distrib. Comput. 1(2), 77-101 (1986)

9. Li, M., Tromp, J., Vitanyi, P.M.B.: How to share concurrent wait-free variables. J. ACM 43(4), 723-746 (1996) (Preliminary version: Li, M., Vitanyi, P.M.B. A very simple construction for atomic multiwriter register. Tech. Rept. TR-01-87, Computer Science Dept., Harvard University, Nov. 1987)

10. Peterson, G.L.: Concurrent reading while writing. ACM Trans. Program. Lang. Syst. 5(1), 56-65 (1983)

11. Peterson, G.L., Burns, J.E.: Concurrent reading while writing II: The multiwriter case. In: Proc. 28th IEEE Symp. Found. Comput. Sci., pp. 383-392. Los Angeles, 27-29 October 1987

12. Singh, A.K., Anderson, J.H., Gouda, M.G.: The elusive atomic register.J. ACM 41(2), 311-339 (1994) (Preliminary version in: Proc. 6th ACM Symp. Principles Distribt. Comput., 1987)

13. Tromp, J.: How to construct an atomic variable. In: Proc. Work shop Distrib. Algorithms. Lecture Notes in Computer Science, vol. 392, pp. 292-302. Springer, Berlin (1989)

14. Vitanyi, P.M.B., Awerbuch, B.: Atomic shared register access by asynchronous hardware. In: Proc. 27th IEEE Symp. Found. Comput. Sci. pp. 233-243. Los Angeles, 27-29 October 1987. Errata, Proc. 28th IEEE Symp. Found. Comput. Sci., pp. 487-487. Los Angeles, 27-29 October 1987