Тупик в OperaСистема ting: що таке циклічне очікування (приклади)
Натаніель Брукс
⚡ Розумний підсумок
Взаємоблокування в операційній системі виникає, коли набір процесів блокується, оскільки кожен з них утримує ресурс і очікує на інший, який утримує інший процес, створюючи циклічний ланцюг, де жоден процес не може продовжуватися.
Що таке Deadlock?
Deadlock це ситуація, яка виникає в операційна система коли процес переходить у стан очікування, оскільки інший процес, що очікує, утримує запитуваний ресурс. Взаємоблокування є поширеною проблемою в багатопроцесорній обробці, де кілька процесів спільно використовують певний тип взаємовиключного ресурсу, відомий як м'яке блокування або програмне блокування.
Коли виникає глухий кут, жоден із задіяних процесів не може продовжуватися, тому робота, що уражається, зупиняється, доки не втрутиться операційна система.
Приклад тупика
- Реальним прикладом може бути рух транспорту, який рухається лише в одному напрямку.
- Тут міст вважається ресурсом.
- Отже, коли виникає глухий кут, його можна вирішити, якщо один автомобіль зробить задній рух (використає ресурси та відкат).
- У разі виникнення тупикової ситуації може знадобитися резервне копіювання кількох автомобілів.
- Отже, голодування можливе.
Приклад тупикової ситуації
Що таке циклічне очікування?
Один процес очікує на ресурс, який займає другий процес, який також очікує на ресурс, що займає третій процес, і так далі. Це продовжується доти, доки останній процес не чекатиме на ресурс, що займає перший процес. Це створює циклічний ланцюжок.
Наприклад, процесу A виділяється ресурс B, поки він запитує ресурс A. Так само, процесу B виділяється ресурс A, поки він запитує ресурс B. Це створює циклічний цикл очікування.
Приклад циклічного очікування
Наприклад, комп'ютер має три USB-накопичувачі та три процеси. Кожен із трьох процесів містить один із USB-накопичувачів. Тому, коли кожен процес запитує інший диск, ці три процеси потрапляють у глухий кут, оскільки кожен з них очікує звільнення USB-накопичувача, поки він ще використовується. Це призводить до утворення циклічного ланцюжка.
Приклад циклічного очікування
Виявлення взаємоблокувань в ОС
Виникнення взаємоблокування може бути виявлено планувальником ресурсів. Планувальник ресурсів допомагає ОС підтримувати track усіх ресурсів, виділених різним процесам. Після виявлення глухого кута його можна вирішити, витіснивши ресурси, відкотивши процес або завершивши один або кілька глухих процесів.
Запобігання взаємоблокуванням в ОС
Важливо запобігти глухому куту до того, як він може виникнути. Система перевіряє кожну транзакцію перед її виконанням, щоб переконатися, що вона не призведе до глухого кута. Навіть невелика операція, яка може спричинити глухий кут у майбутньому, ніколи не буде виконана.
Запобігання глухим блокуванням – це набір методів, що гарантують, що принаймні одна з чотирьох необхідних умов не може виконуватися.
Без попередження
Ресурс може бути вивільнений лише добровільно процесом, який його зберігає, після того, як цей процес завершив своє завдання.
- Якщо процес, який утримує певні ресурси, запитує інший ресурс, який не може бути негайно виділений йому, то всі його ресурси звільняються.
- Використані ресурси додаються до списку ресурсів, на які очікує процес.
- Процес перезапускається лише тоді, коли він може відновити свої старі ресурси, а також нові, які запитує.
Взаємне виключення
Взаємне виключення – це повна форма Mutex. Це особливий тип бінарного файлу. семафор який використовується для контролю доступу до спільного ресурсу. Він включає механізм успадкування пріоритетів, щоб уникнути тривалих проблем інверсії пріоритетів, і блокує завдання з вищим пріоритетом на найкоротший можливий час.
Спільні ресурси, такі як файли лише для читання, ніколи не призводять до взаємоблокувань, але ресурси, такі як принтери та стрічкові накопичувачі, потребують ексклюзивного доступу для одного процесу.
Тримай і чекай
У цьому випадку процеси повинні бути зупинені від утримання одного або кількох ресурсів, одночасно очікуючи на один або кілька інших.
Кругове очікування
Цей метод нав'язує повне впорядкування всіх типів ресурсів. Запобігання циклічному очікуванню також вимагає, щоб кожен процес запитував ресурси у порядку зростання переліку.
Уникнення тупикової ситуації Algorithms
Краще уникнути глухого кута, ніж вживати заходів після його виникнення. Для уникнення потрібна додаткова інформація, наприклад, як будуть використовуватися ресурси. Уникнення глухого кута — це корисна модель, в якій кожен процес оголошує максимальну кількість ресурсів кожного типу, які йому можуть знадобитися.
Уникнення Algorithms
Алгоритм уникнення глухих блокувань динамічно оцінює стан розподілу ресурсів, щоб ситуація циклічного очікування ніколи не виникала.
Для одного екземпляра типу ресурсу:
- Використайте графік розподілу ресурсів.
- Цикл у графі є необхідним і достатнім для виникнення глухого кута.
Для кількох екземплярів одного типу ресурсу:
- Цикл необхідний, але недостатній для утворення глухого кута.
- Ввімкніть кнопку Алгоритм банкіра.
Різниця між голодуванням і глухим кутом
Ось деякі важливі відмінності між глухим кутом та голодуванням:
| Deadlock | Голодування |
|---|---|
| Ситуація тупика виникає, коли один із процесів блокується. | Голодування — це ситуація, коли всі процеси з низьким пріоритетом блокуються, поки виконуються процеси з високим пріоритетом. |
| Безвихідна ситуація – нескінченний процес. | Голодування — це довге очікування, але не нескінченний процес. |
| У кожному глухому куті завжди є голод. | Кожне голодування не обов'язково має глухий кут. |
| Взаємне блокування виникає через взаємне виключення, утримання та очікування, відсутність випередження та циклічне очікування, що виникають одночасно. | Це трапляється через неконтрольований пріоритет та погане управління ресурсами. |
Переваги Deadlock
Ось переваги використання методу обробки тупикових ситуацій:
- Ця ситуація добре працює для процесів, які виконують одиничний імпульс активності.
- Для утворення глухого кута не потрібне випередження.
- Це зручний метод, якщо його застосовувати до ресурсів, стан яких можна легко зберегти та відновити.
- Це можливо забезпечити за допомогою перевірок під час компіляції.
- Це не потребує обчислень під час виконання, оскільки проблема вирішується в проекті системи.
Недоліки Deadlock
Ось недоліки використання методу обробки глухих блокувань:
- Це затримує початок процесу.
- Процеси повинні заздалегідь знати свої майбутні потреби в ресурсах.
- Воно випереджає частіше, ніж потрібно.
- Це забороняє додаткові запити на ресурси.
- Це має невід'ємні втрати від превенції.
