Теорія операційної системи

:: Меню ::

Головна
Представлення даних в обчислювальних системах
Машинні мови
Завантаження програм
Управління оперативною пам'яттю
Сегментна і сторінкова віртуальна пам'ять
Комп'ютер і зовнішні події
Паралелізм з точки зору програміста
Реалізація багатозадачності на однопроцесорних комп'ютерах  
Зовнішні пристрої
Драйвери зовнішніх пристроїв
Файлові системи
Безпека
Огляд архітектури сучасних ОС

:: Друзі ::

Карта сайту
 

:: Статистика ::

 

 

 

 

 

Примітиви того, що взаємовиключає

У класичній роботі Г. М. Дейтела [Дейтел 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;

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

 

:: Реклама ::

Молозиво Колострум купить

 

:: Посилання ::


 

 

 


Copyright © Kivik, 2017