Русская Википедия:Алгоритм Петерсона
Алгоритм Петерсона — алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в 1981 г. Хотя изначально был сформулирован для 2-поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Алгоритм условно называется программным, так как не основан на использовании специальных команд процессора для запрета прерываний, блокировки шины памяти и т. д., используются только общие переменные памяти и цикл для ожидания входа в критическую секцию исполняемого кода.
Принцип работы
Перед тем, как начать исполнение критической секции кода, поток должен вызвать специальную процедуру (назовем её lock()) со своим номером в качестве параметра. Она должна организовать ожидание потоком своей очереди входа в критическую секцию. После исполнения критической секции и выхода из неё поток вызывает другую процедуру (назовем её unlock()), после чего уже другие потоки смогут войти в критическую область. Посмотрим, как реализуется этот общий принцип алгоритмом Петерсона для двух потоков.
Код на языке C++
class PetersonMutex
{
public:
PetersonMutex()
{
want[0].store(false);
want[1].store(false);
waiting.store(0);
}
void lock(int threadId)
{
int other = 1 - threadId;
want[threadId].store(true); // индикатор интереса текущего потока
waiting.store(threadId); // говорим, что этот поток будет ждать, если понадобится
/* Цикл ожидания. Мы находимся в этом цикле, если второй процесс выполняет свою
критическую секцию. Когда второй процесс выйдет из критической секции, выполнится
процедура unlock(int threadId), флаг заинтересованности (want[other])
станет равен false, и цикл закончится. */
while (want[other].load() && waiting.load() == threadId) {
// wait
}
}
void unlock(int threadId) {
want[threadId].store(false);
}
private:
std::array<std::atomic<bool>, 2> want; // флаги заинтересованности потоков
std::atomic<int> waiting; // номер ждущего потока
};
Для наглядности рассмотрим два сценария исполнения параллельных потоков с номерами 0 и 1. Шаблон:Начало скрытого блока
| Время | Поток 0 | Поток 1 |
|---|---|---|
| t1 | int other = 1; | |
| t2 | want[0] = true; | |
| t3 | waiting = 0; | |
| t4 | while (waiting == 0 && want[1]); | |
| t5 | Критическая область кода |
int other = 0; |
| t6 | want[1] = true; | |
| t7 | waiting = 1; | |
| t8 | while (waiting == 1 && want[0]); | |
| t9 | while (waiting == 1 && want[0]); | |
| t10 | want[0] = false; | Критическая область кода |
| t11 | ||
| t12 | ||
| t13 | want[1] = false; |
Поток с номером 0 вызывает lock, задавая этим индикатор своей «заинтересованности», устанавливая флаг очереди так, чтобы уступить очередь исполнения потоку номер 1. Поскольку последний пока еще не «заинтересован» в попадании в критическую область, выполнение сразу же возвращается из lock, и поток 0 входит в неё. Теперь lock вызывается потоком 1, для которого также выполняются описанные выше действия. Но так как поток 0 все еще «заинтересован» (want[0] == true), выполнение остается в lock — поток 1 в ожидании (в таблице это выражено повторением инструкции для цикла 'while'). Как только поток 0 вызывает unlock и сбрасывает флаг своей «заинтересованности», поток 1 входит в критическую область и в конце сам вызывает unlock. Шаблон:Конец скрытого блока
| Время | Поток 0 | Поток 1 |
|---|---|---|
| t1 | int other = 1; | |
| t2 | int other = 0; | |
| t3 | want[1] = true; | |
| t4 | want[0] = true; | |
| t5 | waiting = 0; | |
| t6 | waiting = 1; | |
| t7 | while (waiting == 1 && want[0]); | |
| t8 | while (waiting == 1 && want[0]); | |
| t9 | while (waiting == 0 && want[1]); | |
| t10 | Критическая область кода |
while (waiting == 1 && want[0]); |
| t11 | while (waiting == 1 && want[0]); | |
| t12 | while (waiting == 1 && want[0]); | |
| t13 | want[0] = false; | Критическая область кода |
| t14 | ||
| t15 | ||
| t16 | want[1] = false; |
Потоки почти одновременно вызывают lock, устанавливая тем самым флаг своей «заинтересованности» и уступая очередь выполнения конкурирующему потоку посредством установки значения переменной waiting. Поскольку последним это делает поток 1, ему уже придется ждать в цикле, в то время как поток 0 беспрепятственно входит в критическую область кода. Ожидание потока 1, как и в предыдущей таблице, выражено повторением инструкции while для цикла ожидания. После того, как поток 0 выходит из критической области и сбрасывает флаг своей «заинтересованности», поток 1 продолжает своё исполнение и в конце сам сбрасывает соответствующий флаг вызовом unlock. Шаблон:Конец скрытого блока
Корректность алгоритма
Взаимное исключение
Потоки 0 и 1 никогда не могут попасть в критическую секцию в один момент времени: если 0 вошёл в секцию, он установил want[0] в true. Тогда либо want[1] == false (тогда поток 1 не в критической секции), либо waiting == 1 (тогда поток 1 пытается войти в критическую секцию и крутится в цикле), либо поток 1 пытается войти в критическую секцию после установки want[1] == true, но до установки waiting и цикла. Таким образом, если оба процесса находятся в критической секции, должно быть want[0] && want[1] && waiting == 0 && waiting == 1, но такого не может быть одновременно и мы пришли к противоречию.
Свобода от взаимной блокировки
Для того, чтобы оба процесса находились в ожидании, необходимы противоположные значения переменной waiting, что невозможно.
Свобода от голодания
Возможна ситуация, когда один процесс будет несколько раз подряд захватывать себе критическую секцию, а другой, изъявивший желание попасть туда, будет ждать. В алгоритме Петерсона процесс не будет ждать дольше, чем один вход в критическую секцию: после выполнения unlock и повторного захода в lock процесс установит себя как ждущего и попадёт в цикл, который не завершится, пока не отработает другой процесс.
См. также
Литература
