• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

Begin

Parend

Parbegin

Begin

While правда do begin

Begin

П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 – операція, що ресурс повертається в загальну множину.

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

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

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

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

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

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

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

Монітор

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

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

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

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

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

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

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

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

Монітор:

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

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

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

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

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

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

end;

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

Переглядів: 799