Семафори. While правда do begin

Parend

Parbegin

Begin

While правда do begin

Begin

While правда do begin

Begin

П1хочезайти:= правда;

while П2хочезайти do begin { зовнішній цикл очікування }

if вибранийпроцес = другий then begin

П1хочезайти:= неправда;

while вибранийпроцес = другий do

П1хочезайти:= правда; { внутрішній цикл очікування }

end;

end;

{ початок критичної ділянки П1}

вибранийпроцес:= другий;

П1хочезайти:= неправда;

... { оператори критичної ділянки П1}

{ кінець критичної ділянки П1}

end;

end;

procedure Процес2

П2хочезайти:= правда;

while П1хочезайти do begin { зовнішній цикл очікування }

if вибранийпроцес = другий then begin

П2хочезайти:= неправда;

while вибранийпроцес = перший do

П2хочезайти:= правда; { внутрішній цикл очікування }

end;

end;

{ початок критичної ділянки П2}

вибранийпроцес:= перший;

П2хочезайти:= неправда;

... { оператори критичної ділянки П2}

{ кінець критичної ділянки П2}

end;

end;

{ основна програма }

П1хочезайти:= неправда;

П2хочезайти:= неправда;

вибранийпроцес:= перший;

Процес1;

Процес2;

end;

1. Процес П1 повідомляє про бажання увійти в свою критичну ділянку. Встановлює свій прапорець.

2. Процес П1 переходить до циклу, в якому перевіряє чи процес П2 не хоче також увійти у свою критичну ділянку коду.

3. Якщо, прапорець процесу П2 не встановлений, то П1 пропускає тіло циклу очікування та заходить у свою критичну ділянку.

4. Допускаємо, що П1 при виконанні циклу перевірки виявив, що прапорець П2 встановлено. Це примушує П1 увійти в тіло циклу очікування.

5. Аналізується значення змінної „вибраний процес”, яка використовується для вирішення конфліктів, які виникають у випадку, коли два процеси хочуть одночасно увійти в свої критичні ділянки.

6. Якщо, „вибраний процес” – П1, то він повторно виконує тіло свого циклу очікування моменту коли П2 скине свій прапорець.

7. Якщо, процес П1 виявляє, що „вибраний процес” (має право переваги) – П2, то він заходить у тіло свого циклу та скидає власний прапорець, а потім блокується у циклі доти, поки „вибраним процесом” залишається П2. Скидаючи свій прапорець П1 дає можливість П2 зайти у свою критичну ділянку.

8. З часом П2 вийде із своєї критичної ділянки і виконає оператор „вихід із взаємо-виключення”. Цей оператор забезпечує повернення права переваги процесу П1 і скидання прапорця П2.

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

10. Якщо П2 одразу ж намагається знову увійти в критичну ділянку, то його прапорець буде встановлений і П1 знову необхідно буде увійти в тіло зовнішнього циклу.

11. Але у цьому випадку керування вже знаходиться в П1, оскільки зараз саме він є „вибраним процесом”. Зауважимо, що П1 виходячи зі своєї критичної ділянки присвоїв змінній „вибраний процес” значення 1. Тому, П1 тіло конструкції if та виконує зовнішній цикл перевірки, доки П2 не скине власний прапорець, дозволивши П1 зайти у свою критичну ділянку.

Розглянемо цікаву деталь. Коли, П1 виходить із внутрішнього циклу активного очікування, він може втратити центральний процесор, а П2 в той час пройде свій цикл і знову буде намагатися увійти в свою критичну ділянку. При цьому П2 першим встановить свій прапорець і знову увійде в свою критичну ділянку.

Коли, П1 знову отримає у своє розпорядження процесор, він встановить свій прапорець. Оскільки зараз буде черга процесу П1, то П2 (якщо він знову буде намагатися увійти в свою критичну ділянку) буде вимушений скинути свій прапорець і перейти на внутрішній цикл активного очікування. Так що, П1отримає можливість входу в свою критичну ділянку.

У такий спосіб вирішується проблема безмежного відкладення.

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-11