Центральный Дом Знаний - Алгоритм Петерсона

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2653

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Алгоритм Петерсона

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

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

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

bool interested[2];

int turn;

void EnterRegion(int threadId)

{

int other = 1 - threadId; // Идентификатор второго потока

interested[threadId] = true; // Индикатор интереса текущего потока

turn = other; // Флаг очереди исполнения

/* Цикл ожидания, мы находимся в этом цикле, если второй процесс выполняет свою

критическую секцию. Как второй процесс выйдет из критической секции, выполнится

процедура LeaveRegion(int threadId), флаг заинтересованности (interested[other])

станет равен false, и цикл закончится. */

while (turn == other && interested[other]);

}

void LeaveRegion(int threadId)

{

interested[threadId] = false;

}


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


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

Время

Поток 0

Поток 1

t1

int other = 1;


t2

interested[0] = true;


t3

turn = 1;


t4

while (turn == 1 && interested[1]);


t5

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

int other = 0;

t6

interested[1] = true;

t7

turn = 0;

t8

while (turn == 0 && interested[0]);

t9

while (turn == 0 && interested[0]);

t10

interested[0] = false;

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

t11


t12


t13


interested[1] = false;


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


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

Время

Поток 0

Поток 1

t1

int other = 1;


t2


int other = 0;

t3


interested[1] = true;

t4

interested[0] = true;


t5

turn = 1;


t6


turn = 0;

t7


while (turn == 0 && interested[0]);

t8


while (turn == 0 && interested[0]);

t9

while (turn == 1 && interested[1]);


t10

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

while (turn == 0 && interested[0]);

t11

while (turn == 0 && interested[0]);

t12

while (turn == 0 && interested[0]);

t13

interested[0] = false;

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

t14


t15


t16


interested[1] = false;


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

Лит.: Э. Таненбаум Современные операционные системы = Modern Operating Systems — «Питер», 2004. — С. 1040. — ISBN 5-318-00299-4.

Loading

Календарь

«  Июнь 2019  »
ПнВтСрЧтПтСбВс
     12
3456789
10111213141516
17181920212223
24252627282930

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24