logo search
СПЗ_лекції

4.Уникнення взаємоблокувань при наявності декількох ресурсів кожного типу.

Якщо в системі існує декілька екземплярів деяких з ресурсів, для виявлення взаємоблокувань необхідний інший метод. Розглянемо алгоритм, що базується на матрицях, який виявляє тупіки серед n процесів, від P1 до Pn. Нехай m – це число класів ресурсів, причому в системі E1 - ресурсів класу 1, E2 – ресурсів класу 2 і, в загальному, Ei –ресурсів класу i (де 1≤i≤m). E – вектор існуючих ресурсів. Він передає загальну кількість наявних екземплярів кожного ресурсу.

Далі потрібно два масиви: C – матриця поточного розподілу і R – матриця запитів. I-ий рядок в матриці C показує, скільки представників кожного класу ресурсів в даний момент використовує процес Pi. Таким чином, Cij – кількість екземплярів ресурсу j, яке займає процес i. Аналогічно Rij – кількість екземплярів ресурсу j, які хоче отримати процес Pi. Ці чотири структури показано на рис.5.3.

Рис.5.3. Чотири структури даних, необхідних для алгоритму виявлення тупіків

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

Алгоритм виявлення взаємоблокувань базується на порівнянні векторів. Визначимо, що для двох векторів A і B відношення A≤B означає, що кожен елемент вектору A менше або дорівнює відповідному елементу вектора B. Математично запис буде таким: A≤B тоді і тільки тоді, коли Ai≤Bi для 1≤i≤m.

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

Кроки алгоритму виявлення тупіків:

  1. Шукаємо немаркований процес Pi, для якого i-ий рядок матриці R менше вектора A або дорівнює йому.

  2. Якщо такий процес знайдено, добавляємо i-ий рядок матриці C до вектора A, маркуємо процес і повертаємося до кроку 1.

  3. Якщо таких процесів не існує, то робота алгоритму закінчується.

Завершення алгоритму означає, що всі немарковані процеси, якщо такі є, попали в тупік.

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

Розглянемо приклад (рис.5.4)

Рис.5.4. Приклад використання алгоритму виявлення тупіків.

Тут є три процеси і чотири класи ресурсів. Працюючи з алгоритмом виявлення взаємоблокувань, ми шукаємо процес, чий запит ресурсів може бути задоволений в даній системі. Тільки третій процес може отримати все потрібне, тому він працює, закінчується і повертає всі свої ресурси, даючи A=(2 2 2 0). З цього моменту може виконуватись процес 2, по завершенні повертаючи свої ресурси в систему. Ми отримаємо А=(4 2 2 1)

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

  1. Вихід із взаємоблокування.

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

- Відновлення за допомогою примусового вивантаження ресурсу

- Відновлення через відкат

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

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

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

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