Елементарні прийоми синхронізації на верхньому рівні.

1. Поштові скриньки.

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

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

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

Аналогічно Р2 може одержувати повідомлення доти, поки є заповнені гнізда.

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

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

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

В одному з варіантів реалізації, у кожного із процесів може бути вступнийй вивідний порти. Поштові скриньки створюються й знищуються процесами. Коли процес створює поштову скриньку, його зв'язують із якимось портом за допомогою команди “зв'язати”. Щоб скасувати зв'язок її заміняють зв'язком між фіктивним портом і поштовою скринькою відповідно. Власник поштової скриньки може його знищити. Пам'ять, що він займав, повертається процесу, що його надав.

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

Монітор можна уявити собі як кімнату, від якої є тільки один ключ.

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

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

Розглянемо, наприклад, ресурс, котрий розподіляє деяка програма - планувальник.

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

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

Варто підкреслити, що монітор – це пасивний об'єкт, як кімната. Це не процес. Монітор оживає тільки тоді, коли який-небудь процес вирішує скористатися його послугами. Особливість програми-монітора полягає в тому, що в будь-який момент її може виконати  тільки один процес.

Використання монітора ілюструє Приклад 1, на якому зображена реалізація операцій P й V над семафором S. Вираження виду ІМ'Я УМОВИ.ЧЕКАТИ й ІМ'Я УМОВИ.СИГНАЛ ставляться до операцій “чекати” й ”сигнал”, пов'язаним з умовою ІМ'Я УМОВИ.

Приклад 1.

ДВІЙКОВИЙ_СЕМАФОР : monitor;

S: integer;

Begin

 condition СЕМАФОР ПОЗИТИВНИЙ;

 Procedure P;

Begin

if S<1 then СЕМАФОР ПОЗИТИВНИЙ.ЧЕКАТИ;

S:=S-1;

end;

 Procedure V;

Begin

S:=S+1;

if S=1 then СЕМАФОР ПОЗИТИВНИЙ.СИГНАЛ;

end;

end.

Звертання до операцій P й V записуються як ДВІЙКОВИЙ СЕМАФОР.Р і ДВІЙКОВИЙ СЕМАФОР.V. Умова СЕМАФОР ПОЗИТИВНИЙ указує, коли заблокований процес може безпечно продовжувати роботу. На прикладі два процеси взаємно виключаються із критичної ділянки за допомогою двійкового семафора, реалізованого в моніторі.

Begin

 parbegin

P1: begin do while (True);

                    call ДВІЙКОВИЙ СЕМАФОР.P;

                    Критична ділянка P1;

                    call ДВІЙКОВИЙ СЕМАФОР.V;

                    частина, Що Залишилася, P1;

                   end;

           end;

P2: begin do while (True);

                    call ДВІЙКОВИЙ СЕМАФОР.P;

                    Критична ділянка P2;

                    call ДВІЙКОВИЙ СЕМАФОР.V;

                    частина, Що Залишилася, P2;

                   end;

         end;

 parend;

end.

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

У порівнянні із семафорами монітори мають переваги в тім, що

· Монітори - дуже гнучкий інструмент. Наприклад, можна реалізувати з його допомогою поштову скриньку

· Здійснюється локалізація всіх поділюваних змінних усередині тіла монітора, що дозволяє позбутися від малоприємних конструкцій в синхронизуємих процесах.

Тупики.

Ситуація, коли процеси чекають один одного невиразно довго, називається тупиком або дедлоком (deadlock).

Існує три основних напрямки політики запобігання тупиків:

· запобігання тупиків;

· автоматичне виявлення;

· виявлення при участі оператора.

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

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