У багатозадачних системах мертві блокування (deadlocks) виникають, коли процеси не можуть продовжити виконання, оскільки чекають на ресурси, які утримуються іншими процесами в замкнутому ланцюгу. Мертві блокування можуть серйозно вплинути на продуктивність системи та призвести до зависання додатків. Для запобігання або уникнення таких ситуацій однією з найвідоміших стратегій уникнення мертвих блокувань є Алгоритм банкіра (Banker's Algorithm). Цей алгоритм, розроблений Едсгером Дейкстрою, отримав свою назву завдяки тому, як банкір може розподіляти доступні ресурси, щоб уникнути банкрутства.
У цій статті ми детально розглянемо алгоритм банкіра, розберемо, як він працює на прикладах, та обговоримо кращі практики для запобігання мертвим блокуванням у багатозадачних системах.
Що таке мертве блокування?
Мертве блокування — це ситуація, коли кілька процесів чекають нескінченно на ресурси, що утримуються один одним. Мертве блокування зазвичай виникає, коли одночасно виконуються чотири умови:
- Взаємне виключення (Mutual Exclusion): Ресурс може бути утримуваний лише одним процесом одночасно.
- Утримання та очікування (Hold and Wait): Процеси утримують хоча б один ресурс і чекають на додаткові ресурси.
- Без примусового відбирання (No Preemption): Ресурси не можуть бути насильно відібрані в процеса.
- Циклічне очікування (Circular Wait): Існує циклічний ланцюг процесів, де кожен процес чекає на ресурс, який утримує наступний процес.
Приклад мертвого блокування
Розглянемо два процеси P1 і P2 та два ресурси R1 і R2:
- P1 отримує R1 і запитує R2.
- P2 отримує R2 і запитує R1.
- Обидва процеси чекають на ресурси, що утримуються іншими, що призводить до мертвого блокування.
Алгоритм банкіра: Огляд
Алгоритм банкіра — це алгоритм уникнення мертвих блокувань (deadlock avoidance), який гарантує, що система ніколи не потрапить у стан мертвого блокування. Він моделює запити на виділення ресурсів і визначає, чи приведе надання запиту до безпечного стану (safe state) системи, тобто стану, коли всі процеси можуть завершити виконання.
Алгоритм працює на основі трьох матриць:
- Максимум (Maximum): Максимальна кількість ресурсів, яку може потребувати кожен процес.
- Виділено (Allocated): Кількість ресурсів, яка вже виділена кожному процесу.
- Доступно (Available): Кількість вільних ресурсів, доступних на даний момент.
Алгоритм перевіряє, чи приведе надання запиту на ресурси до стану, в якому всі процеси можуть завершити виконання без мертвих блокувань.
Кроки алгоритму банкіра
- Перевірити, чи запит не перевищує максимальну потребу:
Запитувані ресурси не повинні перевищувати максимальну кількість, зазначену процесом. - Перевірити наявність ресурсів:
Якщо запитувані ресурси перевищують кількість доступних ресурсів, процес повинен чекати. - Тимчасово виділити ресурси:
Симулюємо надання запиту та оновлюємо матриці Available, Allocated і Need. - Перевірка на безпечний стан:
Визначаємо, чи нове виділення ресурсів призводить до безпечного стану, де всі процеси можуть завершити виконання. Якщо ні, скасовуємо тимчасове виділення.
Якщо система залишається в безпечному стані після надання запиту, ресурси виділяються; якщо ні — запит відхиляється.
Детальний приклад алгоритму банкіра
Конфігурація системи
- Загальна кількість ресурсів: 10 екземплярів певного ресурсу (наприклад, принтерів).
- Процеси: 3 процеси (P0, P1, P2).
- Початкові матриці:
Process Maximum Allocated Need
P0 7 1 6
P1 5 2 3
P2 8 3 5
Available Resources: 3
Крок 1: Процес P1 запитує 2 екземпляри
- Запит: P1 запитує ще 2 екземпляри.
- Оновлені доступні ресурси: 3-2 = 1.
- Оновлені матриці:
Process Maximum Allocated Need
P0 7 1 6
P1 5 4 1
P2 8 3 5
Available Resources: 1
Крок 2: Перевірка на безпечний стан
- Перевіряємо, чи може P1 завершити:
P1 потрібно ще 1 екземпляр, і 1 екземпляр доступний — отже, P1 може завершити.
Після завершення P1 система звільняє всі виділені ресурси, збільшуючи доступні ресурси до 5.
2.
Перевірка, чи може P0 завершити:
P0 потрібно 6 екземплярів, але зараз доступно лише 5, тому P0 мусить чекати. - Перевірка P2:
P2 потрібно 5 екземплярів, і 5 доступно — отже, P2 може завершити.
Після завершення P2, доступні ресурси = 8. - Нарешті, P0 може завершити, оскільки йому потрібно лише 6 екземплярів, а доступно 8.
Оскільки всі процеси можуть завершити виконання без мертвого блокування, система знаходиться в безпечному стані.
Як алгоритм уникає мертвих блокувань
Алгоритм банкіра уникає мертвих блокувань, надаючи ресурси тільки в тому випадку, якщо це зберігає систему в безпечному стані. Це гарантує, що кожен процес зрештою завершить виконання, тим самим запобігаючи виникненню умов циклічного очікування.
Переваги та недоліки алгоритму банкіра
Переваги:
- Запобігає мертвим блокуванням, симулюючи та перевіряючи безпечні стани перед наданням запитів.
- Ефективний для малих і середніх систем з передбачуваними потребами в ресурсах.
- Легко реалізувати в системах, де максимальні потреби в ресурсах відомі заздалегідь.
Недоліки:
- Алгоритм вимагає від процесів оголошувати свої максимальні потреби в ресурсах заздалегідь, що може бути неможливим для деяких застосунків.
- Може призвести до непотрібного відхилення запитів у системах з коливними вимогами до ресурсів.
- Алгоритм може стати неефективним для великих систем з великою кількістю одночасних процесів і типів ресурсів.
- Він передбачає, що кількість доступних ресурсів залишатиметься сталою, що не завжди відображає реальні умови.
Практичні поради для уникнення мертвих блокувань
Окрім використання алгоритму банкіра, ось кілька загальних практик для запобігання та уникнення мертвих блокувань:
- Розрив умови циклічного очікування:
Задайте порядок отримання ресурсів і переконайтеся, що процеси отримують ресурси в певному порядку. - Обмежте час утримання ресурсів:
Забезпечте, щоб процеси не утримували ресурси довше, ніж це необхідно. - Уникайте вкладених блокувань:
Мінімізуйте використання вкладених блокувань, коли процес утримує один блокувальник, запитуючи інший. - Встановіть тайм-аути:
Встановіть обмеження часу для запитів ресурсів. Якщо процес не може отримати ресурс протягом певного періоду, він звільняє свої поточні ресурси та повторює спробу пізніше. - Використовуйте примусове відбирання ресурсів:
Дозвольте примусове відбирання ресурсів у процесів за певних умов (хоча це може призвести до неконсистентних станів, якщо не робити це обережно). - Реалізуйте виявлення мертвих блокувань:
Використовуйте окремий потік для виявлення та відновлення від мертвих блокувань, припиняючи або скасовуючи процеси, які спричинили блокування.
Висновок
Алгоритм банкіра залишається одним із основних підходів до уникнення мертвих блокувань в операційних системах та багатозадачному програмуванні. Точно моделюючи виділення ресурсів і забезпечуючи, щоб система залишалася в безпечному стані, алгоритм запобігає виникненню мертвих блокувань. Однак він вимагає детального знання потреб кожного процесу в ресурсах і може не підходити для систем з високою динамікою.
Для систем з високою непередбачуваністю вимог до ресурсів альтернативні стратегії, такі як розрив циклічних очікувань, встановлення тайм-аутів або використання примусового відбирання ресурсів, можуть бути більш ефективними. Врешті-решт, вибір стратегії уникнення мертвих блокувань залежить від конкретних вимог та обмежень системи, яку ви розробляєте.
Перекладено з: Understanding Banker’s Algorithm and Deadlock Avoidance: A Comprehensive Guide