5.Семафори та їх використання.

В 1965 році Дейкстра запропонував цілу зміну для підрахунку сигналів запуску, збережених на майбутнє. Ним був запропонований новий тип змінних (семафори), значення яких може бути нулем (у випадку відсутності збережених сигналів активізації) або деяким додатнім числом, яке відповідає кількості відкладених активізуючих сигналів.

Операція down порівнює значення семафора з нулем. Якщо значення семафора більше нуля, то операція down зменшує його (тобто використовує один із збережених сигналів активації) і просто повертає керування. Якщо значення семафора дорівнює нулеві, то процедура down не повертає керування процесу, а процес переводиться в стан очікування. Цим гарантується, що після початку операції жоден процес не отримає доступу до семафору, до закінчення або блокування операції. Елементарність операції надзвичайно важлива для вирішення проблеми синхронізації і уникнення стану змагань.

Операція up збільшує значення семафору. Якщо з цим семафором пов’язані один або декілька очікуючих процесів, які не можуть завершити більшу ранню операцію down, один з них вибирається системою (наприклад, випадковим чином) і йому дозволяється завершити свою операцію down. Операція збільшення значення семафора і активізації процесу теж неподільна. Жоден процес не може бути блокований під час виконання операції up, як і жоден процес не може блокуватись під час виконання операції wakeup в попередній моделі.

В оригіналі Декстра використав замість down і up позначення Р і V відповідно. Вперше позначення down і up з’явились в мові Algol 68.

Стандартним способом є реалізація операцій down і up в вигляді системних запитів, із забороною операційній системі всіх переривань на період перевірки семафора, зміни його значення і можливого переведення процесу в стан очікування.

Якщо використовуються декілька процесорів, то кожен семафор потрібно запустити з змінною блокування з використанням команди TSL, щоб гарантувати одночасне звертання до семафору тільки одного процесора.