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

Алгоритм Петерсона – это программный алгоритм взаимного исключения потоков без запрещения прерываний. Он был предложен в 1981 году Гарри Петерсоном из университета Рочестер (США). В основу алгоритма Петерсона лег алгоритм Деккера. Изначально алгоритм был сформулирован для 2-поточного случая, но он может быть обобщен для произвольного количества потоков. Алгоритм не основан на использовании таких команд процессора, которые запрещают прерывания, блокировки шины памяти, в нём используются только общие переменные памяти и цикл ожидания входа в критическую секцию кода, поэтому условно алгоритм называют программным. Алгоритм Петерсона учитывает отсутствие атомарности в операциях чтения и записи переменных и может применяться без использования команд управления прерываниями.

Алгоритм работает следующим образом: у каждого процесса есть своя переменная flag[i] и общая переменная turn. Хранение всех переменных происходит в общей памяти. Факт захвата ресурса запоминается в переменной flag, в переменной turn – номер захватившего ресурс процесса.

Когда исполняется пролог критической секции, процесс Pi заявляет о готовности к выполнению критического участка и сразу предлагает другому процессу приступить к его выполнению. В случае, когда оба процесса подошли к прологу единовременно, они оба объявят о своей готовности и предложат друг другу выполняться. При этом каждое предложение следует друг за другом. Тем самым работу в критическом участке продолжит процесс, которому было сделано последнее предложение.

flag[0] = 0flag[1] = 0turn = 0 P0: flag[0] = 1 P1: flag[1] = 1turn = 1 turn = 0while(flag[1] && turn == 1); while(flag[0] && turn == 0);// ожидаем // ожидаем// начало критической секции // начало критической секции......... … // её конец // её конец flag[0] = 0 flag[1] = 0

Сначала процесс устанавливает флаг занятости, потом – номер процесса соседа. После этих действий каждый из процессов входит в цикл ожидания. Выход из цикла происходит, в случае, если флаг занятости установлен, и номер процесса соответствует номеру соседа.

Еще один вариант реализации алгоритма Петерсона:

void mut_excl(int me /* 0 or 1 */) { static int loser; static int interested[2] = {0, 0}; int other; /* локальная переменная */ other = 1 - me; interested[me] = 1; loser = me; while (loser == me && interested[other]); /* критическая секция*/ interested[me] = 0; }

Алгоритм Петерсона, разработанный в 1981 году, состоит из двух процедур, написанных на С.

#define FALSE 0

#define TRUE 1

#define N 2

int turn; int interested[N];

void enter_region(int process)

{

int other;

other=1-process;

interested[process]=TRUE;

turn=process;

while(turn==process && interested[other]==TRUE) { } // Пустой цикл

}

void leave_region(int process)

{

interested[process]=FALSE;

}

При попытке обратиться к критическому ресурсу процесс вызывает функцию enter_regian, передавая в неё свой номер. Если критический ресурс в это время уже занят, то функция войдёт в так называемый "тугой" цикл ожидания, пока ресурс не будет освобождён. Освобождение ресурса производится функцией leave_regian. Данный алгоритм основан на идее, так называемого, активного ожидания, т.е. на постоянном опросе состояние собственной переменной блокировки во время нахождения в "тугом" цикле. Неэффективность главного алгоритма заключается в том, что тратится много процессорного времени на режим активного ожидания во время занятости ресурса другими процессами.

Существуют приёмы синхронизации, позволяющие избежать "активного ожидания":

1. Блокировка. Этот механизм используется для управления параллельным доступом к ресурсам. Если какая-либо операция получает доступ к ресурсу, то механизм блокировки отклоняет попытку получения доступа к этому же ресурсу со стороны других процессов или других операций. Наиболее часто в качестве ресурсов в этом способе выступают данные, а сам механизм соответственно применяется при разработке СУБД.

2. Множественная блокировка. Данный механизм представляет собой использование сразу нескольких блокировок по отношению к одному ресурсу. При использовании данного механизма приходится учитывать возможность возникновения взаимной блокировки. Это тупиковая ситуация, которая может возникнуть, когда две транзакции находятся во взаимном ожидании освобождения блокировки, удерживаемой каждой из них.

Каждая система проводит собственную политику разрешения тупиковых ситуаций. Существует 3 основных подхода:

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

Автоматическое обнаружение тупиковых ситуаций. Данный метод допускает, что система может попасть в тупиковую ситуацию, и для разрешения такой ситуации в системе присутствует механизм, позволяющий вывести систему из тупика. Этот механизм состоит из двух основных частей. I часть отвечает за идентификацию тупиковой ситуации и, в развитых системах, за классификацию тупика. II часть применяет принудительную политику разрешения тупиковой ситуации. Плюсом такого подхода является экономия системных ресурсов на просчитывание тупиковых ситуаций. Минусом отсутствие всех видов тупиков в имеющемся механизме разрешения.

Разрешение тупиковых ситуаций при участии оператора. Метод основан на следующей точке зрения: система попадает в тупиковые ситуации достаточно редко, и предусматривать специальные механизмы их разрешения не нужно. В случае возникновения тупиковой ситуации у системы есть оператор, который поможет её разрешить (например, нажав кнопку reset). Плюсом такого подхода является упрощение и ускорение системы. Минусом является то, что программное обеспечение для таких систем должно предусматривать серьёзные механизмы защиты собственных данных на случай возникновения тупика, т.е. вся нагрузка ложится на разработчиков прикладного программного обеспечения (ППУ).

5. ЗАДАЧА «О СИНХРОНИЗАЦИИ СТРЕЛКОВ»

Дата добавления: 2014-12-16