Иллюстрированный самоучитель по теории операционных систем

Примитивы взаимоисключения

В классической работе Г. М. Дейтела [Дейтел 1987] предлагается несколько последовательных усовершенствований механизма взаимоисключений, основанного на флаговых переменных, и как завершающий этап этого анализа приводится алгоритм взаимоисключений Деккера (пример 7.2).

Пример 7.2. Алгоритм Деккера (цит. по [Дейтел 1987])

program АлгоритмДеккера;
var
избранный процесс: (первый, второй);
п1 хочет войти, п2 хочет войти: Boolean; procedure процесс один;
begin
while true do begin
п1 хочет войти: = True;
while п2 хочет войти do
if избранный процесс = второй then
begin
п1 хочет войти: = False;
while избранный процесс = второй do;
п1 хочет войти: = True;
end
критический участок 1;
избранный процесс: = второй;
п1 хочет войти: = False;
…
end
end
procedure процесс два;
begin
while true do
begin
п2 хочет войти: = True;
while п1 хочет войти do
if избранный процесс = первый then
begin
п2 хочет войти: = False;
while избранный процесс = первый do;
п2 хочет войти: = True;
end
критический участок 2;
избранный процесс: = первый;
п2 хочет войти: = False;
…
end
end D
begin
п1 хочет войти: = False;
п2 хочет войти: = False;
избранный процесс: = первый;
parbegin процессодин;
процесс два;
parend
end.

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

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