Тупики: попередження, виявлення, розв'язка

Боротьба з тупиками включає три завдання:

• попередження тупиків - яку стратегію розподілу ресурсів вибрати, щоб безвихідь не виникала взагалі?
• виявлення тупиків - якщо не вдалося застосувати стратегію, застережливу тупик, то як виявити виниклу тупик?
• розв'язка тупиків - якщо тупик виявлена, то як від нього позбавитися?

Можливі стратегії розподілу ресурсів розташовуються між двома полюсами - від найліберальніших до найконсервативніших. Чим ліберальніше стратегія, тим більш "охоче" за ОС задовольняє запити на ресурси. Але за дуже ліберальну стратегію доводиться розплачуватися можливістю виникнення тупиків. Консервативні стратегії робить тупик неможливими в принципі, завдання виявлення і розв'язки при застосуванні таких стратегій не ставляться, але плата за це - часті відмови у виділенні ресурсів, отже, зниження рівня мультипрограмування, а отже, - і зниження пропускної спроможності. Нижче ми розглядатимемо стратегії запобігання, рухаючись від консервативного полюса до ліберального в такому порядку:

• послідовне виділення;
• залпове виділення;
• ієрархічне виділення;
• виділення по попередніх заявках.

Послідовне виділення.

Будь-якими ресурсами може одночасно користуватися тільки один процес. Якщо процес A з попереднього прикладу отримав ресурс-принтер, то процесу B буде відмовлено навіть у виділенні ресурсу-стрічки. Очевидно, що така стратегія робить тупик абсолютно неможливою. Очевидно також, що деякі процеси при цьому простоюватимуть абсолютно невиправдано. Так, наприклад, буде припинений якийсь процес C, якому принтер і не потрібний, а потрібна тільки стрічка. Оскільки до числа розподілюваних ресурсів входять пристрої введення-виводу, а працюють вони поволі (приклад - той же друк на принтері), простій може затягнутися. Ця стратегія невиправдано знижує рівень мультипрограмування і неефективно використовує ресурси (вони теж простоюють), і може застосовуватися тільки в таких ОС, в яких і розрахунковий рівень мультипрограмування невисокий.

Залпове виділення.

Процес винен запрашивать/освобождать всі використовувані ним ресурси відразу. Ця стратегія дозволяє паралельно виконуватися процесам, що використовують непересічні підмножини ресурсів. (Процес C працює із стрічкою, процес D - з принтером.) Тупик як і раніше неможлива, проте невиправдане утримування ресурсів продовжується. Так, якщо процесу в ході виконання потрібні ресурси R1 і R2, причому ресурс R1 він використовує весь час свого виконання t1, а ресурс R2 потрібний йому тільки на якийсь час t2<<t1, то процес вимушений утримувати за собою і ресурс R2 протягом всього часу t1.

В рамках залпової стратегії можливі два варіанти: виділяти всі ресурси при створенні процесу і звільняти при його завершенні або ж дозволити процесу запрашивать/освобождать ресурси кілька разів в ході свого виконання (але обов'язково все "залпом"). Очевидно, що другий варіант ліберальніший, оскільки він дозволяє зменшити інтервал часу утримування ресурсів і рознести використання різних ресурсів по різних "залпах". Цікаві відмінності в API для цих двох варіантів. У першому випадку вимоги на ресурси можуть бути взагалі винесені за межі програмного коду процесу і задаватися в зовнішніх описувачах процесу (наприклад, в мові управління завданнями). У другому випадку системний виклик getResource є обов'язковим, причому обов'язково повинні бути забезпечена можливість запиту в одному виклику ресурсів різних класів і виділення всіх запитаних ресурсів однією безперервною операцією.