|
Примітиви того, що взаємовиключає
У класичній роботі Г. М. Дейтела [Дейтел 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.
Недоліки цього рішення очевидні. Перший з них — для доступу до однієї
і тієї ж критичної секції з третьої нитки ми повинні значно сложнить
код обох ниток.
На практиці, для вирішення проблеми роботи з прапорами і іншими ска-ярными
змінними в багатопроцесорних конфігураціях більшість овременных процесорів
надають апаратні примітиви того, що взаємовиключає: засоби,
що дозволяють процесору монопольно захопити шину : виконати
декілька операцій над пам'яттю. Реалізації цих примітивів різні біля
різних процесорів. Наприклад, біля х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;
В тому випадку, якщо однією з ниток є обробник переривання, можна
скористатися сервісом, який надають всі сучасні процесори:
заборонити переривання на час знаходження основної нитки програми в критичній
секції. Втім, вказаним способом необхідно користуватися з обережністю
— це наводить до збільшення часу обробки переривання, що не завжди
допустимо, особливо в завданнях реального часу.
|
