302
правки
Изменения
→Алгоритм Петерсона для N потоков
===Алгоритм Петерсона для <tex>N</tex> потоков===
Обобщение Алгоритм Петерсона для <tex>N</tex> потоков. Гарантирует взаимное исключение, отсутствие блокировки и отсутствие голодания. Но алгоритм не очень честный. Невезучий поток может ждать пока другие потоки <tex>O(N^2)</tex> раз войдут в критическую секцию (квадратичное ожидание).
'''threadlocal int''' id <font color=green>// 0 to N-1</font>
'''shared int''' level[N]
'''shared int''' victim[N]
'''def''' lock: '''for''' j = 1..N-1: <font color=green>//Для входа в CS надо пройти на N-1 уровней</font> level[id] = j <font color=green>//Обобщаем want на уровень j: level[id] >= j</font> victim[j] = id <font color=green>//Своя жертва на каждом уровне</font> '''while''' '''exist''' k: k != id '''and''' <font color=green>//Для прохода на следующий уровень соревнуемся со всеми другими потоками</font>
level[k] >= j '''and'''
victim[j] == id:
