Усі найважливіші поняття, що мають відношення до взаємо-виключень Дейкстра об’єднав у концепції семафорів.
Семафор – це захищена змінна, значення якої можна читати та змінювати тільки за допомогою операцій P та V, а також операції ініціалізації.
Двійкові семафори можуть приймати тільки значення 0 та 1. Рахункові семафори приймають невід’ємні цілі значення.
Операція P над семафором S записується як P(S) і виконується наступним чином:
якщо S > 0 то S := 0; інакше чекакати_S();
Операція V над семафором S записується як V(S) і виконується так:
якщо процеси_чекають_S() то дозволити_одному_них_роботу(); інакше S := S + 1;
Узагальнений зміст примітиву P(S) (P – Proberen - перевірити) полягає в перевірці біжучого значення семафору S, та якщо воно не менше 0, виконується перехід до наступної за примітивом операції. Інакше процес знімається на деякий час з виконання і переводиться у стан „пасивного очікування”. Знаходячись у списку заблокованих, процес, що очікує, не перевіряє семафор безперервно, як у випадку активного очікування. Замість нього на процесорі може виконуватися інший процес, який реально виконує корисну роботу.
Операція V(S) (V – Verhogen – збільшити) пов’язана зі збільшенням значення семафору S на одиницю та переведення одного або декількох процесів у стан готовності.
Операції P та V виконуються в ОС у відповідь на запит виданий деяким процесом та ім’я семафору як параметр.
Для роботи із семафорами необхідна ще операція ініціалізації самого семафору, тобто операцію присвоєння йому початкового значення.
Семафори можна використовувати для реалізації механізму синхронізації процесів шляхом блокування / деблокування:
- один процес блокує себе (виконуючи операцію P(S) з початковим значенням S = 0) для того щоб очікувати настання деякої події;
- інший процес виявляє, що очікувана подія відбулася та відновлює заблокований процес (за допомогою операції V(S)).
Рахункові семафори особливо корисні у випадках, коли деякий ресурс виділяється з множиною ідентичних ресурсів. Кожна P – операція показує, що ресурс виділяється деякому процесові, а V – операція, що ресурс повертається в загальну множину.
Операції над семафорами можна реалізувати з використанням режиму активного очікування, але це може привести до втрати ефективності. Щоб цього уникнути, потрібні операції реалізовуються в ядрі ОС.
Розглянуті засоби взаємо-виключення мають суттєві недоліки. Вони настільки елементарні, що не дозволяють ефективно описувати розв’язання порівняно складних проблем паралельних обчислень. Їх використання ускладнює доведення коректності програм паралельних обчислень. Неправильне використання таких примітивів може привести до порушення працездатності систем паралельної обробки.
Тому для реалізації взаємо-виключень треба було шукати механізми більш високого рівня, які б:
- спрощували опис розв’язку складних проблем паралельних обчислень;
- спрощували доведення коректності програм;
- було важко (якщо не неможливо) зіпсувати або неправильно використати.
Одним з рішень цієї проблеми є монітори.