НОУ ІНТУІТ, Лекція, Механізми синхронізації
Примітиви send та receive вже мають прихований від наших очей механізм взаємовиключення. Більше того, у більшості систем вони вже мають і прихований механізм блокування при читанні з порожнього буфера і запису в повністю заповнений буфер . Реалізація рішення задачі producer-consumer для таких примітивів стає непристойно очевидною. Слід зазначити, що, незважаючи на простоту використання, передача повідомлень у межах одного комп'ютера відбувається значно повільніше, ніж робота з семафорами та моніторами.
Еквівалентність семафорів, моніторів та повідомлень
Ми розглянули три високорівневі механізми, що використовуються для організації взаємодії процесів. Можна показати, що в рамках однієї обчислювальної системи, коли процеси мають можливість використовувати пам'ять, що розділяється, всі вони еквівалентні. Це означає, що будь-які з запропонованих механізмів можуть бути реалізовані на базі третього, що залишився механізму.
Реалізація моніторів та передачі повідомлень за допомогою семафорів
Розглянемо спочатку, як реалізувати монітори за допомогою семафорів. Для цього нам потрібно вміти реалізовувати взаємовиключення при вході в монітор та умовні змінні. Візьмемо семафор mutex з початковим значенням 1 для реалізації взаємовиключення при вході в монітор та по одному семафору ci для кожної умовної змінної. Крім того, для кожної умовної змінної заведемо лічильник fi для індикації наявності процесів, що очікують. Коли процес входить у монітор, компілятор генеруватиме виклик функції monitor_enter, яка виконує операцію P над семафором mutex для даного монітора. При нормальному виході з монітора (тобто при виході без виклику операції signal для умовної змінної) компілятор генеруватиме викликфункції monitor_exit, яка виконує операцію V над цим семафором.
Для виконання операції wait над умовною змінною компілятор генеруватиме виклик функції wait , яка виконує операцію V для семафору mutex , дозволяючи іншим процесам входити в монітор , і виконує операцію P над відповідним семафором ci , блокуючи процес, що викликав. Для виконання операції signal над умовною змінною компілятор генеруватиме виклик функції signal_exit , яка виконує операцію V над асоційованим семафором ci (якщо є процеси, що очікують відповідної події), і вихід з монітора , минаючи функцію monitor_exit .
Зауважимо, що при виконанні функції signal_exit , якщо хтось очікував цієї події, процес залишає монітор без збільшення значення семафора mutex , не дозволяючи цим всім процесам, крім збудженого, увійти в монітор . Це збільшення здійснить збуджений процес, коли монітор залишить звичайним способом або коли виконає нову операцію wait над будь-якої умовної змінної .
Розглянемо тепер, як реалізувати надсилання повідомлень, використовуючи семафори . Для простоти опишемо реалізацію лише однієї черги повідомлень. Виділимо в пам'яті, що розділяється, досить велику область під зберігання повідомлень, там же будемо записувати, скільки порожніх і заповнених осередків знаходиться в буфері, зберігати посилання на списки процесів, що чекають читання і пам'яті. Взаємовиключення при роботі з пам'яттю будемо забезпечувати семафором mutex . Також заведемо по одному семафору ci на взаємодіючий процес, щоб забезпечувати блокування процесу при спробі читання з порожнього буфера або при спробі запису в переповнений буфер. Подивимося, як такий механізм працюватиме. Почнемо з процесу, який бажає отримати повідомлення.
Процес-одержувач з номером i насамперед виконує операцію P( mutex ) , отримуючи в монопольне володіння пам'ять, що розділяється. Після цього він перевіряє, чи є в буфері повідомлення. Якщо ні, то він заносить себе в список процесів, що очікують повідомлення, виконує V(mutex) і P(ci). Якщо повідомлення в буфері є, він читає його, змінює лічильники буфера і перевіряє, чи є процеси у списку процесів, які прагнуть записи. Якщо таких процесів немає, то виконується V( mutex ) і процес-одержувач виходить з критичної області. Якщо такий процес є (з номером j), то він видаляється з цього списку, виконується V для його семафору cj, і ми виходимо з критичного району. Процес, що прокинувся, починає виконуватися в критичному районі, так як mutex у нас має значення 0 і ніхто більше не може потрапити в критичний район. При виході з критичного району саме збуджений процес здійснить виклик V(mutex).
Як будується робота процесу-відправника з номером i? Процес, що посилає повідомлення, теж чекає, поки він не зможе мати монополію на використання пам'яті, що розділяється, виконавши операцію P( mutex ) . Далі він перевіряє, чи є місце в буфері, і якщо так, то поміщає повідомлення в буфер, змінює лічильники і дивиться, чи є процеси, що очікують повідомлення. Якщо ні, виконує V( mutex ) і виходить з критичної області, якщо є, "будить" один з них (з номером j ), викликаючи V(cj) , з одночасним видаленням цього процесу зі списку процесів, що очікують на повідомлення, і виходить з критичного регіону без виклику V( mutex ) , надаючи цим можливість збудженого процесу прочитати повідомлення. Якщо місця в буфері немає, то процес-відправник заносить себе в чергу процесів, що очікують можливості запису, і викликає V(mutex) і P(ci).
Реалізаціясемафорів та передачі повідомлень за допомогою моніторів
Нам достатньо показати, що за допомогою моніторів можна реалізувати семафори, тому що отримувати з семафорів повідомлення ми вже вміємо.
Найпростіший спосіб такої реалізації виглядає так. Заведемо всередині монітора змінну-лічильник, пов'язаний з семафором, що емулює, список блокованих процесів і по одній умовній змінній на кожен процес. При виконанні операції P над семафором процес, що викликає, перевіряє значення лічильника. Якщо воно більше за нуль, зменшує його на 1 і виходить з монітора . Якщо воно дорівнює 0, процес додає себе в чергу процесів, що чекають на події, і виконує операцію wait над своєю умовною змінною. При виконанні операції V над семафором процес збільшує значення лічильника, перевіряє, чи є процеси, що очікують цієї події, і якщо є, видаляє один з них зі списку і виконує signal операцію для умовної змінної , відповідної процесу.
Реалізація семафорів та моніторів за допомогою черг повідомлень
Покажемо, нарешті, як реалізувати семафори за допомогою черг повідомлень. Для цього скористаємося хитрішою конструкцією, ввівши новий синхронізуючий процес. Цей процес має лічильник і чергу для процесів, що очікують включення семафору. Для того щоб виконати операції P і V процеси посилають синхронізуючого процесу повідомлення, в яких вказують свої потреби, після чого очікують отримання підтвердження від синхронізуючого процесу.
Після отримання повідомлення процес синхронізації перевіряє значення лічильника, щоб з'ясувати, чи можна здійснити необхідну операцію. Операція V завжди може бути виконана, тоді як операція P може вимагати блокування процесу. Якщо операцію можна здійснити, вонавиконується, і процес, що синхронізує, посилає підтверджує повідомлення. Якщо процес має бути блокований, його ідентифікатор заноситься в чергу блокованих процесів, і підтвердження не посилається. Пізніше, коли будь-який з інших процесів виконає операцію V, один із блокованих процесів видаляється з черги очікування і отримує відповідне підтвердження.
Оскільки ми показали раніше, як з семафорів побудувати монітори, ми довели еквівалентність моніторів, семафорів та повідомлень.
Висновок
Для організації синхронізації процесів можуть застосовуватися спеціальні механізми високого рівня, які блокують процес, що очікує входу в критичну секцію або настання своєї черги для використання спільного ресурсу. До таких механізмів належать, наприклад, семафори, монітори та повідомлення. Всі ці конструкції є еквівалентними, тобто, використовуючи будь-яку з них, можна реалізувати дві, що залишилися.