Тема 4. Синхронізація процесів

1. Незалежні та взаємодіючі обчислювальні процеси.

2. Види задач синхронізації паралельних процесів.

3. Синхронізація за допомогою блокування пам’яті.

4. Алгоритм Деккера.

5. Команда “перевірка” та “встановлення”.

6. Використання семафорів для синхронізації та впорядкування паралельних процесів.

7. Монітороподібні засоби синхронізації паралельних процесів.

8. Поштові ящики.

9. Конвеєри.

10. Черги повідомлень.

1. Незалежні та взаємодіючі обчислювальні процеси.

Основною особливістю сучасних операційних систем як складової частини СПЗ є виконання декількох задач одночасно (паралельно в часі). При цьому під паралельними задачами (процесами) розуміють не тільки процеси які виконуються паралельно на різних процесорах чи пристроях вводу/виводу, але й ті послідовні процеси, які розділяють один центральний процесор і хоча б частково перекриваються в часі.

Паралельні процеси – це такі послідовні процеси, які знаходяться в активному стані одночасно. Такі процеси можуть бути незалежні та взаємодіючі.

Незалежні процеси – це процеси, змінні яких знаходяться в процесі не перекриваючись. Змінні в цьому випадку розуміють – файл даних, область оперативної пам’яті та набір проміжних змінних, які використовуються в обчисленні.

Взаємодіючі процеси – це процеси, які спільно використовують деякі загальні змінні, а також виконання одного процесу може вплинути на виконання іншого.

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

Конкуруючі – це процеси, які сумісно виконують спільну роботу і мають доступ до спільних змінних.

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

2. Види задач синхронізації паралельних процесів.

Задача “взаємного виключення”.

Дозволяє попередити некоректне виконання конкуруючих процесів через нерегламентований доступ до сумісно – використовуваних змінних. Ті частини коду програми, які здійснюють звертання до критичних ресурсів називаються критичною секцією програми.

Рішення задачі взаємного виключення полягає в організації такого доступу до критичного ресурсу, коли тільки одному процесу дозволено “зайти” в критичну секцію (почати виконання своєї критичної секції).

Для кожного критичного ресурсу можуть існувати окремі критичні секції процесу. До критичних секцій процесу існують наступні вимоги:

• в кожен момент часу тільки один процес може знаходитись в певній критичній секції;

• ні один процес не може знаходитись в критичній секції в необмежений відрізок часу;

• жоден процес не повинен чекати входження в критичну секцію в нескінченний проміжок часу;

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

Задача “виробник – споживач”.

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

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

• задача взаємного виключення повинна бути забезпечена по відношенню до спільної області пам’яті;

• повинен враховувати стан цієї пам’яті, що характеризує можливість або неможливість обміну повідомленнями.

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

Задача “читачів – письменників”.

Ця задача характерна для організації файлових систем. По відношенню до певної загальної області пам’яті, яка в більшості випадків організовується як файл на сумісно використовуваному диску.

Виділяють два паралельних процеси:

1. процеси “читачі” – вони зчитують одночасно інформацію зі спільного файлу, якщо це допускається при роботі з таким файлом;

2. процеси “письменники” – вони записують інформацію в цей спільний файл, при умові забезпечення задачі взаємного виключення як з процесами “читачами”, так з процесами “письменниками”. Це забезпечується двома шляхами:

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

• більший пріоритет .надається процесам письменникам. В цьому випадку при появі запиту від процесу письменника ресурс недоступний для всіх процесів читачів, які видадуть запит на використання цього ресурсу після процесу письменника.

Задача “синхронізації виконання гілок алгоритмів”.

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