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

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