Я имел в виду примечания к алгоритму этого фильтра: http://cs.nyu.edu/wies/teaching/ppc-14/material/lecture02.pdf
В нем говорится, что это обеспечивает слабую справедливость, и некоторые потоки могут быть перехвачены произвольное количество раз. (слайд 98)
Я не могу понять эту часть, так как последний, кто запишет значение жертвы, должен ждать, а уже ожидающий поток переходит на следующий уровень, так как же здесь можно обогнать один поток?
Рассмотрим 4 потока (t0, t1, t2 и t3), использующих блокировку фильтра для получения взаимного исключения.
Мы предполагаем, что t0 застревает на уровне 0, t1 — на уровне 1 и так далее. Следовательно, t3 входит в свою критическую секцию и впоследствии открывает замок. Примечание. От t0 до t2 застряли в while((∃k != i) level[k] >= L) && victim[L] == i) {};, что на самом деле представляет собой несколько строк кода (см. Алгоритм блокировки фильтра). С этого момента я буду называть этот фрагмент кода (C1). Далее идет t2 с входом в критическую секцию и разблокировкой, а затем t1. Это означает, что t0 может покинуть уровень 0 (C1)... Однако это не означает, что его нельзя обогнать! Вполне вероятно, что к этому моменту t3, t2 и t1 снова захотят получить блокировку. Следовательно, один из трех потоков отфильтровывается и застревает на уровне 0 (C1), потому что один поток является «жертвой», скажем, t1. Хотя t0 выполняет все требования для выхода из (C1), он все еще может находиться в цикле for (C1), поскольку он может «работать медленнее» из-за различных архитектурных причин. Это позволяет t2 и t3 обогнать t0.
