Семафори - Life-Prog

Тепер ми повернемося до механізмів операційних систем та мов програмування, які забезпечують паралельні обчислення. Цей розділ ми розпочнемо з розгляду семафорів; Наступні розділи будуть присвячені моніторам та передачі повідомлень.

Першою великою роботою, присвяченою питанням паралельних обчислень, стала монографія Дейкстри [DIJK65], який розглядав розробку операційної системи як побудову безлічі послідовних процесів, що співпрацюють, і створення ефективних і надійних механізмів підтримки цієї співпраці. Ці ж механізми легко застосовуються і процесами користувача — якщо процесор і операційна система роблять їх загальнодоступними. Фундаментальний принцип полягає в тому, що два або більше процесів можуть співпрацювати за допомогою простих сигналів, так що в певному місці процес може призупинити роботу доти, доки не дочекається відповідного сигналу. Вимоги кооперації будь-якого ступеня складності можуть бути задоволені структурою сигналів. Для сигналізації використовуються спеціальні змінні, які називаються семафорами. Для передачі сигналу через семафор s процес виконує примітив signal (s), а для отримання сигналу примітив wait (s). В останньому випадку процес зупиняється до тих пір, поки не здійсниться передача відповідного сигналу.

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

  • Семафор може бути ініціалізований невід'ємним значенням.
  • Операція wait зменшує значення семафору. Якщо це значення стає негативним, процес, який виконує операцію wait, блокується.
  • Операція сигналу збільшує значення семафора. Якщо це значенняне позитивно, що заблокований операцією wait процес деблокується.

Немає жодних інших способів отримання інформації про значення семафора або зміни його значення, крім перерахованих.

У лістингу 5.5 наведено формальне визначення примітивів семафорів. Передбачається, що примітиви wait і signal атомарні, тобто. вони не можуть бути перервані, і кожна підпрограм може розглядатися як єдиний крок. Більш обмежена версія семафору, відома як бінарний семафор, представлена ​​у лістингу 5.6. Бінарний семафор може набувати лише значення 0 або 1. У принципі реалізація бінарного семафору має бути більш простим завданням; можна також показати, що всі завдання, які вирішуються із застосуванням звичайних семафорів, можуть бути вирішені і з використанням лише бінарних семафорів (див. задачу 5.13).

Лістинг 5.5. Визначення семафорних примітивів

struct semaphore int count; queueType queue; > void wait(semaphore s) s.count-; if (s. count 0: значення s.count визначає кількість процесів, які можуть виконати wait(s) без припинення процесу (маю на увазі, що проміжні виклики signal(s) відсутні).

Повернутись до змісту: Операційні системи