<<
>>

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

Алгоритм Петерсона дает нам решение задачи корректной организации взаимодействия двух процессов. Давайте рассмотрим теперь соответствующий алгоритм для п взаимодействующих процессов, который получил название алгоритм булочной, хотя применительно к нашим условиям его следовало бы скорее назвать алгоритм регистратуры в поликлинике.
Основная его идея выглядит так. Каждый вновь прибывающий клиент (он же процесс) получает талончик на обслуживание с номером. Клиенте наименьшим номером на талончике обслуживается следующим. К сожалению, из-за неатомарности операции вычисления следующего номера алгоритм булочной не гарантирует, что у всех процессов будут талончики с разными номерами. В случае равенства номеров на талончиках у двух или более клиентов первым обслуживается клиенте меньшим значением имени (имена можно сравнивать в лексикографическом порядке). Разделяемые структуры данных для алгоритма — это два массива:

shared enum {false, true} choosing[n]; shared int number[n] ;

Изначально элементы этих массивов инициируются значениями false и 0 соответственно. Введем следующие обозначения:

(а,b) < (c,d), если а < с или если а == с и b < d

max(aO, al, ...., an) - это число к такое, что

k >= ai для всех i = 0, ...,п

Структура процесса 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, выполните самостоятельно в качестве упражнения.

<< | >>
Источник: В.Е. Карпов К.А. Коньков. Основы операционных систем. 2005

Еще по теме Алгоритм булочной (Bakery algorithm):

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. АЛГОРИТМ
  3. АЛГОРИТМ УДАЧИ
  4. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. ЗАДАЧА: РЕШЕНИЕ
  13. Переживание
  14. Переживание
  15. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  16. Замечания по структуре материала
  17. Прием структуризации психологического портрета.