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

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

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