Алгоритм булочной (Bakery algorithm)
Алгоритм Петерсона дает нам решение задачи корректной организации взаимодействия двух процессов. Давайте рассмотрим теперь соответствующий алгоритм для n взаимодействующих процессов, который получил название алгоритм булочной, хотя применительно к нашим условиям его следовало бы скорее назвать алгоритм регистратуры в поликлинике. Основная его идея выглядит так. Каждый вновь прибывающий клиент (он же процесс) получает талончик на обслуживание с номером. Клиент с наименьшим номером на талончике обслуживается следующим. К сожалению, из-за неатомарности операции вычисления следующего номера алгоритм булочной не гарантирует, что у всех процессов будут талончики с разными номерами. В случае равенства номеров на талончиках у двух или более клиентов первым обслуживается клиент с меньшим значением имени (имена можно сравнивать в лексикографическом порядке). Разделяемые структуры данных для алгоритма – это два массива
shared enum {false, true} choosing[n]; shared int number[n];
Изначально элементы этих массивов инициируются значениями false и 0 соответственно. Введем следующие обозначения
(a,b) < (c,d), если a < c или если a == c и b < d max(a0, a1, ...., an) – это число k такое, что k >= ai для всех i = 0, ...,n
Структура процесса Pi для алгоритма булочной приведена ниже
while (some condition) { choosing[i] = true; number[i] = max(number[0], ..., number[n-1]) + 1; choosing[i] = false; for(j = 0; j < n; j++){ while(choosing[j]); while(number[j] != 0 && (number[j],j) < (number[i],i)); } critical section number[i] = 0; remainder section }
Доказательство того, что этот алгоритм удовлетворяет условиям 1 – 5, выполните самостоятельно в качестве упражнения.
