Алгоритм взаимного исключения, использующий только атомарные операции чтения и записи для неизвестного количества процессов и устойчивый к прерыванию процесса

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

Помимо взаимного исключения и отсутствия взаимоблокировок, он должен выполнять следующие свойства:

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

Я придумал способ, который, как мне кажется, может работать, но я хотел проверить его на вас, ребята, чтобы посмотреть, не допустил ли я где-то ошибку или есть более элегантное решение.

Идея состоит в том, чтобы объединить модифицированную версию трехбитного линейного ожидания Шиманского. Алгоритм (рис. 1 на стр. 4 документа «Возвращение к взаимному исключению») со схемой именования процессов, в общих чертах основанной на Моир и Андерсон "Алгоритмы без ожидания для быстрого и долговременного переименования" (M&A).

В качестве первого шага я определяю "заказ" для входящих процессов, назначая им идентификатор, например M&A:

Слияния и поглощения используют следующий примитив мьютекса (см. рис. 2 на стр. 5):
Mutex Primitive
где из n процессы, входящие в блок, не более 1 остановятся там, не более n-1 будут двигаться вправо и не более n -1 будет перемещаться вниз.

Эти примитивы можно связать вместе в сетку, где я решил пронумеровать ящики иначе, чем M&A, чтобы можно было рассчитать номер ящика, не зная общего количества ящиков:
Сетка
Номер ящика можно рассчитать с помощью box = (m*(m-1))/2 + r, где m — общее количество сделанных ходов (включая ход в верхний левый ящик, т. е. >m1), а r — количество ходов вправо (r0).

Каждому новому процессу первоначально будет назначен большой глобально уникальный идентификатор (например, отметка времени + огромное случайное число), который он будет использовать в качестве значения для p в алгоритме примитивов мьютекса, описанном выше. Затем он начнет пересекать сетку, следуя правилам примитива, начиная с верхнего левого угла, пока не остановится в каком-то поле. Номер ящика, в котором он остановился, теперь будет его новым идентификатором процесса.

Чтобы количество идентификаторов процессов было меньше (процессы могут исчезнуть; а также: ящики могут быть заблокированы навсегда без использования, если все входящие процессы перемещаются вправо или вниз и ни один из них не останавливается на достигнутом), я заменю логическую переменную Y< /strong> в примитиве выше с отметкой времени.

Затем строка Y := true будет заменена на Y := now, где сейчас — текущее время. Аналогично, условие if Y then ... будет заменено на if (now - Y < timeout) then ..., где время ожидания — это время, по истечении которого ящик будет возвращен в доступный пул.

Пока процесс все еще выполняется, ему необходимо постоянно устанавливать для Y-значения своего поля значение сейчас, чтобы его идентификатор никогда не истекал. Хотя меньшие значения timeout приведут к меньшим идентификаторам и меньшему использованию памяти, теоретически его можно выбрать произвольно большим, и, таким образом, всегда можно найти значение для timeout, которое гарантирует, что процессы никогда не потеряют свой идентификатор, если только они не завершат свою работу или не погибнут. Значения минут, часов или даже дней должны помочь.

Теперь мы можем использовать этот технологический порядок для реализации алгоритма Шиманского:

communication variables:: a, w, s: boolean = false
private variables:: j: 0..n

p1      ai=true;
p2      for(j=0;j<n;j++)
            while(sj);
p3      wi=true;
        ai=false;
p4      while(!si) {
p5          for (j=0;j<n & !aj;j++);
p6          if (j==n) {
                si=true;
p6.1            for (j=0;j<n & !aj;j++);
p6.2            if (j<n)
                    si=false;
p6.3            else {
                    wi=false;
p6.4                for(j=0;j<n;j++)
                        while(wj);
                }
            }
p7          if (j<n)
                for (j=0;j<n & (wj | !sj);j++);
p8          if (j!=i & j<n) {
p8.1            si=true;
                wi=false;
            }
        }
p9      for(j=0;j<i;j++)
            while(wj | sj);

Critical Section

e1      si=false;

Идея, лежащая в основе этого алгоритма, немного запутана, и для краткости (если это еще не безнадежное дело на данный момент) я не буду пытаться перефразировать ее здесь снова (В Википедии также обсуждается вариант этого алгоритма).

Чтобы этот алгоритм работал должным образом (т. е. при прерывании процесса и неизвестном общем количестве процессов), можно внести следующие изменения:

Как и Y выше, логические значения ai, wi и < strong>si будут заменены временными метками. За исключением того, что на этот раз тайм-ауты должны быть достаточно короткими, чтобы по-прежнему можно было входить в критическую секцию так часто, как это необходимо, в моем случае каждые несколько секунд, поэтому тайм-аут 5 с может работать. В то же время тайм-аут должен быть достаточно длинным, чтобы он никогда не истекал, если процесс не умирает, т. е. он должен быть больше, чем наихудшее время, которое требуется процессам для обновления временных меток для флагов, которые должны оставаться установленными.

Циклы по процессам (например, for(j=0;j<n;j++)) будут преобразованы в обходы сетки идентификаторов процессов сверху в порядке номеров ящиков. У каждого ящика может быть 3 состояния: никем не посещаемый, в нем остановлен процесс или все процессы перешли, а ящик в данный момент заблокирован. Нет необходимости делать различие между двумя последними, так как заблокированный ящик будет просто соответствовать процессу, который в данный момент не пытается войти в критическую секцию (т. е. ai, wi и si являются false /истекший). Цикл начинается с ящика 0. Если он сталкивается с ящиком, который был посещен (т. е. имеет установленное значение X), он добавляет соседние ящики в свой «контрольный список» (т. е. если ящик 8 был виден, в список будут добавлены ящики 12 и 13). Цикл завершается, когда «to-check-list» полностью обработан (если, конечно, не существует другого условия остановки, которое срабатывает первым (например, j < i или & !aj)).

Теперь мои вопросы:

  1. Похоже, что это будет работать надежно?
    Я никогда не делал формального подтверждения такой платформы. Моя интуиция (и напряженные размышления) подсказывает мне, что она должна быть твердой, но я не возражал бы против чего-то более строгого, чем это. Меня больше всего беспокоят последствия смерти процесса между p3 и e1 алгоритма Шиманского и случайного истечения срока действия флагов, когда другие процессы находятся в этой части кода.
  2. Есть ли лучшее решение (более простое/меньшее использование ресурсов)?
    Одной точкой атаки для оптимизации может быть тот факт, что мне не нужны все процессы чтобы в конечном итоге добраться до критической секции, мне нужен только один (и мне все равно, какой именно).

Извините за длину этого поста и спасибо за то, что вы терпеливо читали его! Предложения по сокращению приветствуются... :)

PS: я также разместил этот вопрос на обмен стеком CS.


algorithm mutual-exclusion
person Markus A.    schedule 19.10.2015    source источник
comment
Прочитал только первую часть, но вижу затруднение (это будет рассмотрено позже?): если процесс может умереть в любой точке, то он может умереть, удерживая мьютекс. Как это отличить от процесса, который просто удерживает мьютекс в течение неопределенно долгого времени?   -  person j_random_hacker    schedule 20.10.2015
comment
@j_random_hacker Эта проблема как бы решается позже, требуя, чтобы код, который проводит много времени в критической секции, отправлял повторные эхо-запросы с определенным максимальным интервалом. Но я просмотрел случай, когда пинги задерживаются, хотя процесс не мертв... (Максимальный интервал должен быть выбран таким, чтобы этот случай не возник)   -  person Markus A.    schedule 20.10.2015

Ответы (1)


arrow_upward
1
arrow_downward

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

Я нашел довольно красивую альтернативу: алгоритм Бернса и Линча:

program Process_i;
    type flag = (down, up);
    shared var F : array [1..N] of flag;
    var j : 1..N;
begin
    while true do begin
        1: F[i] := down;
        2: remainder;     (* remainder region *)
        3: F[i] := down;
        4: for j := 1 to i-1 do
               if F[j] = up then goto 3;
        5: F[i] := up;
        6: for j := 1 to i-1 do
               if F[j] = up then goto 3;
        7: for j := i+1 to N do
               if F[j] = up then goto 7;
        8: critical;      (* critical region *)
    end
end.

Вы можете найти его на странице 4 (836) их документа "Взаимное исключение Использование неделимых операций чтения и записи".

У него есть пара основных преимуществ:

  • Это намного проще
  • Он использует меньше памяти (на самом деле они заявляют, что их алгоритм оптимален в этом отношении)
  • У всей общей памяти есть только один писатель (но, конечно, несколько читателей)
  • Легко превратить занятые ожидания в отложенные повторные попытки (см. -мог-там">здесь)

Кроме того, идею этого алгоритма можно представить следующим образом:

Я процесс и стою где-то в ряду с другими людьми (все остальные процессы).
Когда я хочу войти в критическую секцию, я делаю следующее:

  • 3/4: я смотрю налево и держу руку опущенной до тех пор, пока вижу кого-то с поднятой рукой.
  • 5: Если никто слева от меня не поднял руку, я поднимаю свою.
  • 6: Я снова проверяю, поднял ли руку кто-нибудь слева от меня. Если да, то я кладу свою обратно и начинаю заново. В противном случае я держу руку вверх.
  • 7: Все, кто справа от меня, ходят первыми, поэтому я смотрю направо и жду, пока не перестану поднимать руки.
  • 8: Когда все руки справа от меня опущены, я могу войти в критическую секцию.
  • 1: Закончив, я опускаю руку.

Я реализовал всю идею выше (включая слияния и поглощения) с помощью этого алгоритма и в настоящее время тестирую его, и пока он кажется очень стабильным.

Реализация очень проста. На самом деле было только два дополнительных предостережения, которые я должен был учитывать (если, конечно, я что-то не упустил (указатели приветствуются)):

  • Если процесс доходит до строки 7 в алгоритме, он может в конечном итоге попасть в goto, и в этом случае в моей реализации (см. алгоритм исключения-by-burns-and-lynch-in-java-could-there">здесь), вход в критическую секцию отклоняется, и процесс повторяет попытку позже. Когда происходит повторная попытка (возможно, с большой задержкой), мне нужно обновить флаг процесса таким образом, чтобы у него не было даже малейшего момента, в течение которого флаг истек, или, если он был, мне нужно обнаружить это и вернуться к строке 3 в алгоритме вместо продолжения в строке 7.
  • Я добавил проверку, нужно ли вообще входить в критическую секцию (т.е. оператор, который ограничивает скорость входа в критическую секцию). Наиболее эффективно выполнять эту проверку прямо перед тем, как процесс даже попытается войти в критическую секцию. Чтобы быть на 100% уверенным, что ни один поток никогда не превысит предел скорости, необходимо будет выполнить вторую проверку, когда процесс успешно войдет в критическую секцию.

Из-за общих структур данных, которые использует мой код, в настоящее время он не совсем в том состоянии, чтобы публиковать его здесь, но немного поработав, я мог бы собрать автономную версию. Если кому интересно, пишите в комментариях, я так и сделаю.

person Markus A.    schedule 22.10.2015