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

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

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

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

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

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

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