Алгоритм Деккера

Алгоритм Деккера является первым известным точным решением взаимного исключения без запрещения прерываний. Название алгоритма связано с голландским математиком Теодором Деккером, который разработал решение данной проблемы. Алгоритм позволяет двум потокам совместно использовать одноразовый ресурс без конфликтов, используя для связи лишь общую память.

Алгоритм Деккера имеет следующие ограничения:

1. Алгоритм рассчитан строго на 2 процесса;

2. При ожидании ресурса, процессы впустую тратят процессорное время, так как не снимаются с очереди на обслуживание;

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

4. При нахождении одного из процессов в критической секции, другой процесс будет находиться в ожидании.

Нужно отметить, что использование таких алгоритмов в операционной системе Реального Времени нежелательно, из-за того, что заблокированный процесс не снимается с обслуживания и напрасно расходует процессорное время.

Алгоритм Деккера основан на использовании 3-х переменных: ПР1 (процесс 1), ПР2 (процесс 2) и ОЧЕРЕДЬ.

1. Если первый процесс хочет войти в свой критический интервал, то переменная ПР2 принимает значение TRUE, т.е. значение переменной ОЧЕРЕДЬ показывает чьё именно сейчас право войти в критический интервал.

2. Если ПР1= TRUE, а ПР2=FALSE, то независимо от значения переменной ОЧЕРЕДЬ исполняется ПР1.

3. Если ПР1= TRUE и ПР2= TRUE, то дальше исполняется процесс, который определяется значением переменной ОЧЕРЕДЬ.

Завершив своё исполнение этот процесс сбрасывает флаг своего исполнения в FALSE и меняет значение переменной ОЧЕРЕДЬ на противоположное. Диапазон значений переменной ОЧЕРЕДЬ обычно колеблется в пределах [0;1] или [1;2]. Значение переменной ОЧЕРЕДЬ по сути тоже является флагом.

Begin integer C1,C2, очередь;

C1:=0; C2:=0; очередь=1;

begin

ПРОЦЕСС_1: begin C1:=1;

do while (C2=C1)

if (очередь=2) then

begin

C1:=0;

do while (очередь=2);

end;

end;

/* Критический участок ПРОЦЕССА_1 */

C1=0;

очередь=2;

/* Оставшаяся часть процесса */

end;

ПРОЦЕСС_2: begin C2:=C1;

do while (C1=1);

if (очередь=1) then

begin

C2:=0;

do while (очередь=1);

end;

C2=1;

end;

end;

/* Критический участок ПРОЦЕССА_2 */

C2=0;

очередь=1;

/* Оставшаяся часть процесса */

end;

end;

end.

Алгоритм Деккера обеспечивает взаимное исключение, невозможность возникновения deadlock или starvation. (Deadlock – это ситуация, при которой несколько процессов находятся в состоянии бесконечного ожидания ресурсов, занятых самими этими процессами; starvation – это зависание процессов).

Одним из преимуществ данного алгоритма является то, что он не требует специальных Test-and-set инструкций (атомарная операция чтения, модификации и записи), следовательно, он легко переносим на разные языки программирования и архитектуры компьютеров. Недостатками можно назвать его применимость к случаю только с двумя процессами и использование Busy waiting вместо приостановки процесса (использование busy waiting предполагает, что процессы должны проводить минимальное количество времени внутри критической секции).

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

Многие современные микропроцессоры исполняют инструкции не по порядку. Алгоритм не будет работать на SMP-машинах (Symmetric Multi Processing – симметричная мультипроцессорная обработка), оборудованных такими CPU (central processing unit - центральное обрабатывающее устройство), если не использовать барьеры памяти.

Таким образом, алгоритм Деккера удобен в случаях, если используется ограниченное количество процессов, с увеличением количества процессов будет пропорционально расти количество используемых элементов (Пр1,..., Прn), а также количество фрагментов кода, разрешения войти в критический участок для каждого из процессов.

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

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