Интернет магазин китайских планшетных компьютеров



Компьютеры - Алгоритм Петерсона

23 января 2011





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

Принцип работы

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

Код EnterRegion и LeaveRegion на языке C++

bool interested;
int turn;
 
void EnterRegion
{
    int other = 1 - threadId;                    // Идентификатор второго потока
    interested = true;                 // Индикатор интереса текущего потока
    turn = other;                                // Флаг очереди исполнения
 
    /* Цикл ожидания, мы находимся в этом цикле, если второй процесс выполняет свою 
       критическую секцию. Как второй процесс выйдет из критической секции, выполнится
       процедура LeaveRegion, флаг заинтересованности 
       станет равен false, и цикл закончится. */
    while ;
}
 
void LeaveRegion
{
    interested = false;
}


Для наглядности рассмотрим два сценария исполнения параллельных потоков с номерами 0 и 1.


1) Потоки вызывают EnterRegion последовательно

Время Поток 0 Поток 1
t1 int other = 1;
t2 interested = true;
t3 turn = 1;
t4 while;
t5

Критическая область кода

int other = 0;
t6 interested = true;
t7 turn = 0;
t8 while;
t9 while;
t10 interested = false;

Критическая область кода

t11
t12
t13 interested = false;


Поток с номером 0 вызывает EnterRegion, задавая этим индикатор своей «заинтересованности», устанавливая флаг очереди так, чтобы уступить очередь исполнения потоку номер 1. Поскольку последний пока еще не «заинтересован» в попадании в критическую область, выполнение сразу же возвращается из EnterRegion, и поток 0 входит в нее. Теперь EnterRegion вызывается потоком 1, для которого также выполняются описанные выше действия. Но так как поток 0 все еще «заинтересован», выполнение остается в EnterRegion — поток 1 в ожидании. Как только поток 0 вызывает LeaveRegion и сбрасывает флаг своей «заинтересованности», поток 1 входит в критическую область и в конце сам вызывает LeaveRegion.


2) Потоки вызывают EnterRegion почти одновременно

Время Поток 0 Поток 1
t1 int other = 1;
t2 int other = 0;
t3 interested = true;
t4 interested = true;
t5 turn = 1;
t6 turn = 0;
t7 while;
t8 while;
t9 while;
t10

Критическая область кода

while;
t11 while;
t12 while;
t13 interested = false;

Критическая область кода

t14
t15
t16 interested = false;


Потоки почти одновременно вызывают EnterRegion, устанавливая тем самым флаг своей «заинтересованности» и уступая очередь выполнения конкурирующему потоку посредством установки значения переменной turn. Поскольку последним это делает поток 1, ему уже придется ждать в цикле, в то время как поток 0 беспрепятственно входит в критическую область кода. Ожидание потока 1, как и в предыдущей таблице, выражено повторением инструкции while для цикла ожидания. После того, как поток 0 выходит из критической области и сбрасывает флаг своей «заинтересованности», поток 1 продолжает свое исполнение и в конце сам сбрасывает соответствующий флаг вызовом LeaveRegion.



Просмотров: 1297


<<< Алгоритм Деккера
Атомарные операции >>>