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

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

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

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

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

* [[Синхронизаторы и остовы