lamport-lock-fail

Ошибочный алгоритм Лампорта

В рамках данного задания вы проанализируете некорректную попытку реализации алгоритма Лампорта для взаимного исключения.

Вася Пупкин увидел второй вариант реализации алгоритма Лампорта (см. лекцию), очень порадовался его простоте и решил его оптимизировать. Он избавился от массива choosing и получил вот такой код, явно расписав процедуру выбора максимальной метки в отдельный цикл, используя значение 0 для обозначения отсутствия интереса потока к взятию блокировки:

threadlocal int id       // 0..N-1 -- идентификатор потока
shared      int label[N] // заполнено нулями по умолчанию

def lock:
  1: my = 1 // номер билета текущего потока
  2: for k in range(N): if k != id:
  3:     my = max(my, label[k] + 1) // должен быть больше, чем у других
  4: label[id] = my // публикуем свой номер билета для других потоков
  5: for k in range(N): if k != id:
  6:     while true: // пропускаем поток k до тех пока, пока номер его билета меньше
  7:         other = label[k] // читаем номер билета потока k
  8:         if other == 0 or (other, k) > (my, id): break@6 // если номер его билета меньше, перестаем ждать  

def unlock:
  9: label[id] = 0

Чтения и записи элементов разделяемого массива label происходят атомарно.

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

Задание

Продемонстрируйте исполнение данного алгоритма на двух потоках (N == 2), которое нарушает условие взаимного исключения.

Описание исполнения должно содержаться в файле solution.txt и содержать набор событий (одно событие = одна строка) в следующем формате:

<tid> <line> <action> <location> <value>

• <tid> - id потока, 0 или 1;
• <line> - номер строчки кода, которая исполняется; 3, 4 или 7;
• <action> - тип события, rd (чтение) или wr (запись)
• <location> - описание разделяемой переменной, к которой происходит обращение, label[<index>];
• <value> - значение, которое записано или прочитано; например, 10.

В первой строке файла впишите вашу фамилию и имя.

Для проверки корректности вашего примера, запустите ./gradlew build из корня репозитория.

Если у вас не получается найти решение силой мысли, то проанализируйте в черновике варианты одновременного исполнения двумя потоками операции lock методом чередования операций. Обратите внимание, что при анализе вас интересуют только те строки кода, которые обращаются к разделяемым переменным. В данном случае это обращения к элементам массива label (строки 3, 4, 7).

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