Апаратна підтримка взаємовиключень

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

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

Команда Test-and-Set (Перевірити та присвоїти 1)

Про виконання команди Test-and-Set, що здійснює перевірку значення логічної змінної з одночасною установкою її значення в 1, можна думати, як про виконання функції

int Test_and_Set (int *target)

int tmp = * target; *target = 1; return tmp;

З використанням цієї атомарної команди ми можемо модифікувати наш алгоритм для змінної-замку, так щоб він забезпечував взаємовиключення

shared int lock = 0;

while (some condition)

while(Test_and_Set(&lock));

Critical section

lock = 0;

Remainder section

Команда Swap (Обмінювати значення)

Виконання команди Swap, яка обмінює два значення, що знаходяться в пам'яті, можна проілюструвати наступною функцією

void Swap (int *a, int *b)

int tmp = * a; *a = *b; * b = tmp;

Застосовуючи атомарну команду Swap ми можемо реалізувати попередній алгоритм, ввівши додаткову логічну змінну keyлокальну для кожного процесу:

shared int lock = 0; int key;

while (some condition)

key = 1; do Swap(&lock,&key); while (key);

Critical section

lock = 0;

Remainder section

Глава 6. Механізми синхронізації

Розглянуті наприкінці попередньої глави алгоритми хоч і є коректними, але досить громіздкі і не мають елегантності. Більш того, процедура очікування входу в критичний ділянку включає досить тривале обертання процесу в порожньому циклі, вхолосту пожираючи дорогоцінний час процесора. Існують інші серйозні недоліки в алгоритмів, побудованих засобами звичайних мов програмування. Припустимо, що в обчислювальній системі знаходяться два взаємодіючі процеси: один з них -H - з високим пріоритетом, інший -L - з низьким пріоритетом. Нехай планувальник влаштований так, що процес із високим пріоритетом витісняє низькопріоритетний процес щоразу, коли він готовий до виконання, і займає процесор на весь час свого CPU burst (якщо не з'явиться процес із ще більшим пріоритетом). Тоді у разі, коли процесL знаходиться у своїй критичній секції, а процесH, отримавши процесор, підійшов до входу в критичну область, ми отримуємо тупикову ситуацію. ПроцесH не може увійти в критичну область, перебуваючи в циклі, а процесL не отримує управління, щоб залишити критичний ділянку.

Для того, щоб усунути виникнення подібних проблем, були розроблені різні механізми синхронізації вищого рівня: семафори, монітори та повідомлення, розгляду яких і присвячений цей розділ.

Семафори

Одним із перших механізмів, запропонованих для синхронізаціїповедінки процесів стали семафорами, концепцію яких описав Дейкстра (Dijkstra) в 1965 році.

Концепція семафорів

Семафор являє собою цілу змінну, що набуває невід'ємних значень, доступ будь-якого процесу до якої, за винятком моменту її ініціалізації, може здійснюватися тільки через дві атомарні операції:P (від датського слова proberen - перевіряти ) іV (від verhogen - збільшувати). Класичне визначення цих операцій виглядає так:

P(S):

поки S

---