Самостабилизация: различия между версиями

Задача [3]. Первая формулировка задачи самостабилизации, предложенная Дейкстрой, представляет собой кольцо из n процессов с номерами от 0 до n - 1. Обозначим состояние процесса i как x[i]. Коммуникация в кольце однонаправленная с использованием ''модели совместно используемого состояния''. Атомарный шаг процесса i может быть выражен защищенным назначением вида <math>g(x[i \ominus 1], x[i]) \to x[i]: = f(x[i \ominus 1], x[i])</math>. Здесь <math>\ominus</math> - это вычитание по модулю n, так что <math>x[i \ominus 1]</math> представляет собой состояние предыдущего процесса в кольце по отношению к процессу i. Защищенное присваивание g – это булево выражение; если g(x[i © 1];x[i]) истинно, то процесс i считается привилегированным (или включенным). Таким образом, за один атомарный шаг привилегированный процесс i считывает состояние предыдущего процесса и вычисляет новое состояние. Планирование выполнения контролируется центральным демоном, который справедливым образом выбирает один из всех разрешенных процессов для выполнения следующего шага. Задача заключается в выводе g и f таким образом, чтобы независимо от начальных состояний x[i], 0 < i < n, в конечном итоге существовала одна привилегия, и каждый процесс пользовался привилегией бесконечно часто.