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

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

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

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

while избранныйпроцесс=второй do;
п!хочетвойти := True;
end
критическийучасток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.

Недостатки этого решения очевидны. Первый из них — для доступа к одной и той же критической секции из третьей нити мы должны значительно сложнить код обеих нитей.
Нa практике, для решения проблемы работы с флаговыми и другими ска-ярными переменными в многопроцессорных конфигурациях большинство овременных процессоров предоставляют аппаратные примитивы взаимоисключения: средства, позволяющие процессору монопольно захватить шину : выполнить несколько операций над памятью. Реализации этих примитивов различны у разных процессоров. Например, у х86 это специальный код операции, префикс захвата шины, который сам по себе не совершает никаких действий, но зато исполняет следующую за ним операцию в монопольном режиме.
Благодаря этому мы можем одновременно получить старое значение флаговой переменной и установить новое командой xchg (eXCHanGe, обменять — операнды обмениваются значениями между собой — пример 7.3)- Если память модифицируется только одним процессором, исполняющим программу, префикс блокировки шины не нужен — зато, если процессоров (или других задатчиков шины) в системе несколько, префикс гарантирует взаимоисключение и для модификаций флага с их стороны.

Пример 7.3. Реализация примитива testandset через блокировку шины

.globl flag
; 0 = False, I = True
flag: .db 0
proc process1
tryagain:
move eax, 1
lock xchg eax, flag
tst eax
bnz tryagain
критическая секция
; в данном случае о взаимоисключении можно не заботиться
xor eax, eax
move flag, eax
ret
endp

Другие процессоры, например VAX, предоставляют отдельные команды, исполняющиеся в режиме монопольного захвата шины. В частности, Именно так этот процессор исполняет команды вставки в очередь и исключения из нее.
Имея возможность произвести атомарно исполняющуюся операцию над скалярной переменной, мы можем реализовать более сложные схемы взаимоисключения, используя эту переменную в качестве флаговой, при помощи относительно простого кода (пример 7.4). В отличие от алгоритма Деккера этот код легко распространяется на случай более чем двух нитей.

Пример 7.4. Реализация взаимоисключения при помощи атомарной операции testandset (ЦИТ. ПО [Дейтел 1987])

progam npimeptestandset
var активный: Boolean;
procedure процессодин;
var первомувходитьнельзя: Boolean;
begin
while true do
begin
первомувходитьнельзя := True;
while первомувходитьнельзя do
testandset(первомувходитьнельзя, активный);
критический участокодин;
активный := False;
....
end
end;
procedure процессдва;
var второмувходитьнельзя: Boolean; begin
while true do
begin
второмувходитьнельзя := True;
while второмувходитьнельзя do
testandset(второмувходитьнельзя, активный);
критический участокдва;
активный := False;
.....
end
end;

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

Содержание раздела

---

---