Семафори

Усі найважливіші поняття, що мають відношення до взаємо-виключень Дейкстра об’єднав у концепції семафорів.

Семафор – це захищена змінна, значення якої можна читати та змінювати тільки за допомогою операцій 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 – операція, що ресурс повертається в загальну множину.

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

Розглянуті засоби взаємо-виключення мають суттєві недоліки. Вони настільки елементарні, що не дозволяють ефективно описувати розв’язання порівняно складних проблем паралельних обчислень. Їх використання ускладнює доведення коректності програм паралельних обчислень. Неправильне використання таких примітивів може привести до порушення працездатності систем паралельної обробки.

Тому для реалізації взаємо-виключень треба було шукати механізми більш високого рівня, які б:

- спрощували опис розв’язку складних проблем паралельних обчислень;

- спрощували доведення коректності програм;

- було важко (якщо не неможливо) зіпсувати або неправильно використати.

Одним з рішень цієї проблеми є монітори.

Монітор

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

Потреба увійти в монітор у різні моменти часу може виникати у багатьох процесів. Але вхід у монітор знаходиться під жорстким контролем – тут виконується взаємо-виключення процесів, так що в кожен момент часу тільки одному процесові дозволяється увійти в монітор. Процеси, що хочуть увійти в монітор коли він вже зайнятий, будуть очікувати його звільнення. Режимом очікування автоматично керує сам монітор. Механізм монітору гарантує взаємо-виключення.

Внутрішні дані монітору можуть бути або глобальними (відносяться до усіх процедур монітору) або локальними (відносяться тільки до однієї певної процедури). До всіх цих даних є доступ тільки зсередини монітору. Процеси, що знаходяться поза монітором не можуть отримати доступ до даних монітору.

Якщо процес звертається до деякої процедури монітору і виявляється, що відповідний ресурс вже зайнято, то ця процедура видає команду очікування Wait. Процес міг би залишатися у середині монітору, але це привело б до порушення принципу взаємо-виключення (завадило б іншому процесові увійти в монітор). Тому процес, який переводиться в режим очікування, повинен чекати настання події (звільнення ресурсу) поза монітором.

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

Фактично у процесів може виникнути необхідність очікувати звільнення ресурсу поза монітором з багатьох причин. Тому вводиться поняття змінна-умова. Для кожної з причин, за якою процес переводиться в стан очікування, призначається своя умова. У зв’язку з цим команди Wait та Signal модифікуються на Wait(ім’я_умови) та Signal(ім’я_умови).

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

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

Монітор:

monitor Розподілу_ресурсів;

var ресурс_зайнято : логічний;

ресурс_звільнено : логічний; {умова}

procedure Захопити_ресурс;

begin

if ресурс_зайнято then

wait(ресурс_звільнено);

ресурс_звільнено := правда;

end;

procedure Звільнити_ресурс;

begin

ресурс_зайнято := неправда;

signal(ресурс_звільнено);

end;

begin

ресурс_зайнято := неправда;

end;

Перевага такого монітору в тому, що він може працювати за аналогією до двійкового семафору:

„захопити ресурс” = P – оператор;

„звільнити ресурс” = V – оператор.

Тому монітори, як мінімум, мають таку ж логічну потужність, як і семафори.

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

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