Алгоритм решения проблемы критической секции

Синхронизация процессов по критическим секциям

Рассмотрим проанализированную проблему в общем виде. Пусть имеются n параллельных процессов, каждый из которых может обратиться к общим для них данным. Назовем критической секцией фрагмент кода каждого процесса, в котором происходин обращение к общим данным. Проблема синхронизации процессов по критическим секциям заключается в том, чтобы обеспечить следующий режим выполнения: если один процесс вошел в свою критическую секцию, то до ее завершения никакой другой процесс не смог бы одновременно войти в свою критическую секцию.

Можно показать, что для решения проблемы критической секции необходимо и достаточно выполнение следующих трех условий:

1. Взаимное исключение. Если некоторый процесс исполняет свою критическую секцию, то никакой другой процесс не должен в этот момент исполнять свою.

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

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

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

Пусть для простоты имеется только два процесса – P0 и P1. Общая структура i - го процесса должна иметь вид:

do {

вход в критическую секцию

критическая секция

выход из критической секции

остальная часть кода

} while (1)

Процессы могут использовать общие переменные для синхронизации своих действий.

Алгоритм 1. Предпримем первую попытку решения проблемы. Введем целую переменную turn (очередь), значение которой turn == i будет обозначать, что наступила очередь процесса номер i войти в свою критическую секцию. Первоначально turn == 0.

Алгоритм процесса Pi имеет вид:

do {

while (turn!= i);

критическая секция

turn = j; /* j!= i: если i == 0, j == 1; если i == 1, j == 0 */

остальная часть кода

} while (1)

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

Алгоритм 2. Будем хранить не номер процесса, допущенного к критической секции, а массов булевских флагов flag [2], такой, что flag[i] == true, если i -й процесс готов войти в свою критическую секцию. Алгоритм процесса Pi примет вид:

do {

flag[i] = true;

while (flag[j]); /* j!=i: если i==0, j==1; если i == 1, j == 0 */

критическая секция

flag[i] = false;

остальная часть кода

} while (1)

Данный вариант алгоритма также удовлетворяет принципу взаимного исключения, так как перед входом в критическую секцию процесс ждет, пока не останется других процессов, желающих войти в свои критические секции.

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

Алгоритм 3. Модифицируем алгоритм, используя в нем одновременно и переменную turn, и массив флагов flag. Алгоритм процесса примет вид:

do {

flag[i] = true;

turn = j;

while (flag[j] and turn == j);

критическая секция

flag[i] = false;

остальная часть кода

} while (1)

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

Алгоритм булочной (bakery algorithm)

Автор данного алгоритма – Л. Лампорт (L. Lamport). Рассмотрим другой алгоритм, решующий проблему синхронизации по критическим секциям. Происхождение названия следующее: алгоритм как бы воспроизводит стратегию автомата в (американской) булочной, где каждому клиенту присваивается его номер в очереди. В нашей российской реальности, данный алгоритм более уместно было бы назвать по этой же причине "алгоритм Сбербанка".

В алгоритме для n процессов используется булевский массив choosing[n]: значение choosing[i] == true будет означать, что в данный момент система определяет номер в очереди i-го процесса. Используется также целочисленный массив number[n]: number[i] будет обозначать вычисленный порядковый номер в очереди (приоритет) i-го процесса.

Алгоритм булочной (для i-го процесса) имеет вид:

do {

choosing[i] = true;

number [i] = max (number[0], number[1], …, number[n-1]) + 1;

while (flag[j] and turn == j);

choosing[i] = false;

for (j = 0; j < n; j++) {

while choosing[j];

while ((number[j]!= 0) && (number[j] < number[j]));

}

критическая секция

number [i] = 0;

остальная часть кода

} while (1)

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

Дата добавления: 2014-01-20