Тупик в OperaСистема ting: що таке циклічне очікування (приклади)

Приклад тупика

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

Що таке циклічне очікування?

Один процес очікує на ресурс, який утримує другий процес, який також очікує на ресурс, який утримує третій процес тощо. Це триватиме, доки останній процес не чекатиме на ресурс, який утримує перший процес. Це створює круговий ланцюг.

Наприклад, процесу A виділяється ресурс B, оскільки він запитує ресурс A. Так само процесу B виділяється ресурс A, і він запитує ресурс B. Це створює круговий цикл очікування.

Приклад циклічного очікування

Наприклад, комп’ютер має три USB-накопичувачі та три процеси. Кожен із трьох процесів може містити один із USB-накопичувачів. Таким чином, коли кожен процес запитує інший диск, три процеси матимуть тупикову ситуацію, оскільки кожен процес чекатиме на звільнення USB-накопичувача, який зараз використовується. В результаті вийде круглий ланцюжок.

Виявлення взаємоблокувань в ОС

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

Запобігання взаємоблокуванням в ОС

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

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

Жодних попереджувальних дій

Без перехоплення – ресурс може бути звільнений тільки добровільно процесом, який його утримує, після того, як цей процес завершить своє завдання

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

Взаємне виключення

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

Спільні ресурси, такі як файли лише для читання, ніколи не призводять до тупикових блокувань, але ресурси, як-от принтери та стрічкові накопичувачі, потребують ексклюзивного доступу для одного процесу.

Тримай і чекай

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

Кругове очікування

Він накладає загальне впорядкування всіх типів ресурсів. Циркулярне очікування також вимагає, щоб кожен процес запитував ресурси в порядку зростання нумерації.

Уникнення тупикової ситуації Algorithms

Краще уникати тупикової ситуації, а не вживати заходів після її виникнення. Йому потрібна додаткова інформація, наприклад, як слід використовувати ресурси. Уникнення взаємоблокувань — це найпростіша та найкорисніша модель, у якій кожен процес оголошує максимальну кількість ресурсів кожного типу, які йому можуть знадобитися.

Уникнення Algorithms

Алгоритм уникнення взаємоблокувань допомагає динамічно оцінювати стан розподілу ресурсів, щоб ніколи не виникало циклічної ситуації очікування.

Один екземпляр типу ресурсу.

• Використовуйте графік розподілу ресурсів
• Необхідні цикли, достатні для Deadlock

Кілька екземплярів типу ресурсу.

• Цикли необхідні, але ніколи не достатні для Deadlock.
• Використовує Алгоритм банкіра

Різниця між голодуванням і глухим кутом

Ось кілька важливих відмінностей між тупиком і голодом:

Deadlock	Голодування
Тупикова ситуація виникає, коли один із процесів заблоковано.	Голод — це ситуація, коли всі процеси з низьким пріоритетом заблоковані, а процеси з високим пріоритетом виконуються.
Безвихідна ситуація – нескінченний процес.	Голодування - це довге очікування, але не безкінечний процес.
Кожен тупик завжди голодує.	Будь-яке голодування не обов’язково має глухий кут.
Взаємоблокування відбувається тоді Взаємне виключення, утримуйте та чекайте. Тут випередження та циклічне очікування не відбуваються одночасно.	Це відбувається через неконтрольоване управління пріоритетами та ресурсами.

Переваги Deadlock

Ось плюси/переваги використання методу Deadlock

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

Недоліки Deadlock

Ось мінуси/недоліки використання методу взаємоблокування

• Затримує початок процесу
• Процеси повинні знати майбутні потреби в ресурсах
• Випереджає частіше, ніж необхідно
• Забороняє додаткові запити ресурсів
• Власні втрати на випередження.

Підсумки

• Визначення безвиході: це ситуація, яка виникає в OS коли будь-який процес переходить у стан очікування, оскільки інший процес, що очікує, утримує потрібний ресурс
• Циркулярне очікування відбувається, коли один процес очікує на ресурс, який утримує другий процес, який також очікує на ресурс, який утримує третій процес тощо.
• Виникнення взаємоблокування може бути виявлено планувальником ресурсів.
• Важливо запобігти тупиковій ситуації до її виникнення.
• Ресурс може бути звільнений тільки добровільно процесом, який його утримує, після того, як цей процес завершить своє завдання.
• Взаємне виключення є повною формою Mutex. Це особливий тип двійкових файлів семафор який використовується для керування доступом до спільного ресурсу.
• Утримання та очікування — це умова, коли процеси повинні бути зупинені, щоб вони не утримували один або кілька ресурсів, одночасно очікуючи на один або більше інших.
• Уникнення взаємоблокувань — це найпростіша та найкорисніша модель, у якій кожен процес оголошує максимальну кількість ресурсів кожного типу, які йому можуть знадобитися.
• Алгоритм уникнення взаємоблокувань допомагає динамічно оцінювати стан розподілу ресурсів, щоб ніколи не виникало циклічної ситуації очікування.
• Тупик — нескінченний процес, тоді як голод — це довге очікування, але не нескінченний процес.