рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Образование
- /
- Алгоритм Петерсона
Реферат Курсовая Конспект
Алгоритм Петерсона
Алгоритм Петерсона - раздел Образование, Понятие многослойности ядра Алгоритм Петерсона — Программный Алгоритм Взаимного Исключения Потоков Исполн...
Алгоритм Петерсона — программный алгоритм взаимного исключения потоков исполнения кода, разработанный Г. Петерсоном в 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.
– Конец работы –
Эта тема принадлежит разделу:
Понятие многослойности ядра
Повышение удобства и эффективности работы пользователя является целью другого способа мультипрограммирования разделения времени В системах... В системах разделения времени эта проблема решается за счет того что ОС... Системы разделения времени призваны исправить основной недостаток систем пакетной обработки изоляцию...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Алгоритм Петерсона
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.02 сек.
Новости и инфо для студентов