Анотація: Для підвищення продуктивності обчислювальних систем і полегшення завдання програмістів існують спеціальні механізми синхронізації. Опис деяких з них - семафорів Дейкстри, моніторів Хору, черг повідомлень - наводиться в цій лекції.
Розглянуті в кінці попередньої лекції алгоритми хоча і є коректними, але досить громіздкі і не володіють елегантністю. Більш того, процедура очікування входу в критичний ділянку передбачає досить тривалий обертання процесу в порожньому циклі, тобто марне витрачання дорогоцінного часу процесора. Існують і інші серйозні недоліки у алгоритмів, побудованих засобами звичайних мов програмування. Припустимо, що в обчислювальній системі знаходяться два взаємодіючих процесу: один з них - H - з високим пріоритетом, інший - L - з низьким пріоритетом. Нехай планувальник влаштований так, що процес з високим пріоритетом витісняє фоновий процес щоразу, коли він готовий до виконання, і займає процесор на весь час свого CPU burst (якщо не з'явиться процес з ще більшим пріоритетом). Тоді в разі, якщо процес L знаходиться в своїй критичній секції, а процес H. отримавши процесор. підійшов до входу в критичну область, ми отримуємо тупикову ситуацію. Процес H не може увійти в критичну область, перебуваючи в циклі, а процес L не отримує управління, щоб залишити критичний ділянку.
Для того щоб не допустити виникнення подібних проблем, були розроблені різні механізми синхронізації більш високого рівня. Опису ряду з них - семафорів. моніторів і повідомлень - і присвячена дана лекція.
Одним з перших механізмів. запропонованих для синхронізації поведінки процесів, стали семафори. концепцію яких описав Дейкстра (Dijkstra) в 1965 році.
концепція семафорів
Семафор являє собою цілу змінну, що приймає невід'ємні значення, доступ будь-якого процесу до якої, за винятком моменту її ініціалізації, може здійснюватися тільки через дві атомарні операції: P (від датського слова proberen - перевіряти) і V (від verhogen - збільшувати). Класичне визначення цих операцій виглядає наступним чином:
Цей запис означає наступне: при виконанні операції P над семафором S спочатку перевіряється його значення. Якщо воно більше 0. то з S віднімається 1. Якщо воно менше або дорівнює 0. то процес блокується до тих пір, поки S не стане більше 0. після чого з S віднімається 1. При виконанні операції V над семафором S до його значенням просто додається 1. В момент створення семафор може бути инициализирован будь-яким невід'ємним значенням.
Рішення проблеми producer-consumer за допомогою семафорів
Однією з типових задач, що вимагають організації взаємодії процесів, є завдання producer-consumer (виробник-споживач). Нехай два процеси обмінюються інформацією через буфер обмеженого розміру. Виробник закладає інформацію в буфер, а споживач отримує її звідти. На цьому рівні діяльність споживача і виробника можна описати таким чином.
Якщо буфер заповнений, то виробник повинен чекати, поки в ньому з'явиться місце, щоб покласти туди нову порцію інформації. Якщо буфер порожній, то споживач повинен чекати нового повідомлення. Як можна реалізувати ці умови за допомогою семафорів. Візьмемо три семафора. empty. full і mutex. Семафор full будемо використовувати для гарантії того, що споживач буде чекати, поки в буфері з'явиться інформація. Семафор empty будемо використовувати для організації очікування виробника при заповненому буфері, а семафор mutex - для організації взаємовиключення на критичних ділянках, якими є дії put_item і get_item (операції "покласти інформацію" та "взяти інформацію" не можуть перетинатися, так як в цьому випадку виникне небезпека спотворення інформації). Тоді рішення задачі на C-подібному мовою виглядає так:
Легко переконатися, що це дійсно коректне рішення поставленого завдання. Попутно зауважимо, що семафори використовувалися тут для досягнення двох цілей: організації взаємовиключення на критичній ділянці і взаімосінхронізаціі швидкості роботи процесів.