Безизходица в Operating система: какво е, кръгово изчакване (примери)

по: Натаниел Брукс Натаниел Брукс
Hours Обновено

⚡ Умно обобщение

Безизходица в операционна система възниква, когато набор от процеси са блокирани, защото всеки държи ресурс и чака друг, който друг процес държи, създавайки кръгова верига, в която никой процес не може да продължи.

  • 🔒 Определение: Безизходицата замразява процесите, всеки от които държи ресурс, докато чакат един друг.
  • 🧩 Четири условия: Взаимното изключване, задържането и чакането, липсата на превантивни мерки и кръговото чакане трябва да се спазват заедно.
  • 🔁 Кръгово чакане: Процесите образуват затворена верига, като всеки чака ресурс, задържан от следващия.
  • ️ Предотвратяване: Нарушаването на което и да е от четирите условия предотвратява образуването на безизходица.
  • 🏦 Избягването: Алгоритъмът на банкера проверява заявките за ресурси, за да поддържа системата в безопасно състояние.
  • 🤖 Ъгъл на изкуствен интелект: Машинното обучение открива модели на безизходица, а Copilot помага за писането и прегледа на код за заключване.
Прочетете повече

Безизходица в Operaтинг система

Какво е Deadlock?

застой е ситуация, която се случва в операционната система когато даден процес влезе в състояние на изчакване, защото друг чакащ процес държи искания ресурс. Безизходицата е често срещан проблем при многопроцесорна обработка, където няколко процеса споделят специфичен тип взаимно изключващ се ресурс, известен като меко заключване или софтуерно заключване.

Когато възникне безизходица, никой от участващите процеси не може да продължи, така че засегнатата работа спира, докато операционната система не се намеси.

Пример за безизходица

  • Пример от реалния свят би бил трафикът, който се движи само в една посока.
  • Тук един мост се счита за ресурс.
  • Така че, когато възникне безизходица, тя може да бъде разрешена, ако едната кола направи заден ход (използва ресурсите и се върне назад).
  • Може да се наложи няколко автомобила да бъдат резервни, ако възникне ситуация на безизходица.
  • Така че, гладуването е възможно.

Пример за безизходица

Пример за безизходица

Какво е кръгово изчакване?

Един процес чака ресурс, който се държи от втори процес, който също чака ресурс, държан от трети процес и така нататък. Това продължава, докато последният процес не чака ресурс, държан от първия процес. Това създава кръгова верига.

Например, на Процес А се разпределя Ресурс Б, докато той заявява Ресурс А. По същия начин, на Процес Б се разпределя Ресурс А, докато той заявява Ресурс Б. Това създава цикличен цикъл на изчакване.

Пример за кръгово изчакване

Например, един компютър има три USB устройства и три процеса. Всеки от трите процеса държи по едно от USB устройствата. Така че, когато всеки процес поиска друго устройство, трите процеса достигат до ситуация на безизходица, тъй като всеки от тях чака освобождаването на USB устройство, докато все още се използва. Това води до кръгова верига.

Пример за кръгово изчакване

Пример за кръгово изчакване

Deadlock Detection в OS

Възникване на безизходица може да бъде открито от планировчика на ресурси. Планировчикът на ресурси помага на операционната система да поддържа track от всички ресурси, разпределени на различни процеси. След като бъде открита безизходица, тя може да бъде разрешена чрез изпреварване на ресурси, връщане назад на процес или прекратяване на един или повече от безизходиците.

СВЪРЗАНИ СТАТИИ

Предотвратяване на блокиране в OS

Важно е да се предотврати безизходица, преди тя да възникне. Системата проверява всяка транзакция, преди да бъде изпълнена, за да се увери, че тя не води до безизходица. Дори малка операция, която би могла да причини безизходица в бъдеще, никога не се допуска да бъде изпълнена.

Предотвратяването на безизходица е набор от методи, които гарантират, че поне едно от четирите необходими условия не може да бъде изпълнено.

Без предимство

Ресурс може да бъде освободен само доброволно от процеса, който го държи, след като този процес е завършил задачата си.

  • Ако процес, който държи някакви ресурси, поиска друг ресурс, който не може да му бъде незабавно разпределен, тогава всички негови ресурси се освобождават.
  • Предварително заетите ресурси се добавят към списъка с ресурси, за които процесът чака.
  • Процесът се рестартира само когато може да си възвърне старите ресурси, както и новите, които изисква.

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

Взаимното изключване е пълната форма на Mutex. Това е специален вид двоичен файл. семафор който се използва за контролиране на достъпа до споделен ресурс. Той включва механизъм за наследяване на приоритети, за да се избегнат продължителни проблеми с инверсията на приоритети и да се блокират задачите с по-висок приоритет за възможно най-кратко време.

Споделените ресурси, като например файлове само за четене, никога не водят до безизходици, но ресурси като принтери и лентови устройства се нуждаят от ексклузивен достъп от един процес.

Задръжте и изчакайте

В това състояние, процесите трябва да бъдат спрени от задържането на един или повече ресурси, докато едновременно чакат един или повече други.

Циркулярно изчакване

Този метод налага тотално подреждане на всички типове ресурси. Предотвратяването на циклично чакане изисква също така всеки процес да изисква ресурси във възходящ ред на изброяване.

Избягване на задънена улица Algorithms

По-добре е да се избегне безизходица, вместо да се предприемат действия след като тя е възникнала. Избягването изисква допълнителна информация, като например как ще се използват ресурсите. Избягването на безизходица е полезен модел, при който всеки процес декларира максималния брой ресурси от всеки тип, от които може да се нуждае.

Избягване Algorithms

Алгоритъмът за избягване на безизходици динамично оценява състоянието на разпределение на ресурсите, така че никога да не възникне ситуация на циклично чакане.

За единичен екземпляр от тип ресурс:

  • Използвайте графика за разпределение на ресурсите.
  • Цикъл в графа е необходим и достатъчен за безизходица.

За множество екземпляри от даден тип ресурс:

Разлика между гладуване и безизходица

Ето някои важни разлики между безизходицата и гладуването:

застой глад
Ситуацията на безизходица възниква, когато един от процесите бъде блокиран. Гладът е ситуация, при която всички процеси с нисък приоритет се блокират, докато процесите с висок приоритет се изпълняват.
Безизходицата е безкраен процес. Гладът е дълго чакане, но не е безкраен процес.
Всяка безизходица винаги е свързана с глад. Всяко гладуване не е задължително да има задънена улица.
Безизходицата възниква поради взаимно изключване, задържане и изчакване, липса на превантивно действие и циклично изчакване, възникващи едновременно. Това се случва поради неконтролирано приоритизиране и лошо управление на ресурсите.

Предимства на Deadlock

Ето са предимствата на използването на метода за обработка на безизходици:

  • Тази ситуация работи добре за процеси, които извършват единичен импулс от активност.
  • Не е необходима превантивна мярка за безизходица.
  • Това е удобен метод, когато се прилага към ресурси, чието състояние може лесно да се запази и възстанови.
  • Възможно е да се приложи чрез проверки по време на компилация.
  • Не е необходимо изчисление по време на изпълнение, тъй като проблемът е решен в проектирането на системата.

Недостатъци на Deadlock

Ето недостатъците на използването на метода за обработка на безизходица:

  • Това забавя стартирането на процеса.
  • Процесите трябва предварително да знаят бъдещите си нужди от ресурси.
  • То предотвратява по-често от необходимото.
  • Това забранява нарастващите заявки за ресурси.
  • Това има присъщи загуби от превантивно действие.

Въпроси и Отговори

За да се постигне едновременно безизходица, е необходимо едновременно да са изпълнени четири условия на Кофман: взаимно изключване, задържане и изчакване, липса на превантивно действие и циклично изчакване. Премахването на което и да е от тези условия предотвратява образуването на безизходица.

Предотвратяването премахва едно от четирите условия предварително, така че никога да не може да се образува безизходица. Избягването позволява условията, но използва проверки по време на изпълнение, като например Алгоритъмът на банкера, за да се поддържа системата в безопасно състояние.

В безизходица блокираните процеси спират напълно и никога не променят състоянието си. livelock, процесите продължават да променят състоянието си и използват процесора, но все още не постигат напредък. Livelock е специален случай на гладуване на ресурси.

Повечето системи с общо предназначение, включително Windows и Linux, използвайте алгоритъма на щрауса и просто игнорирайте редките заключвания, защото предотвратяването е скъпо. Базите данни и системите в реално време вместо това изпълняват активни процедури за откриване и възстановяване.

Графът за разпределение на ресурси изобразява процесите и ресурсите като възли, свързани чрез ръбове на заявки и присвоявания. Цикъл в графа сигнализира за възможна патова блокировка; при ресурси с единична инстанция цикълът винаги означава, че съществува патова блокировка.

Не. Истинският безизход е постоянен, защото блокираните процеси никога не освобождават ресурсите си сами. Операционната система трябва да го прекъсне, като изпревари ресурс, отмени или прекрати един от процесите.

Моделите за машинно обучение изучават модели на заявки за ресурси, за да предвиждат и сигнализират за блокиране, преди да възникне. Планировчиците с изкуствен интелект могат да пренареждат заявките или да настройват политиките за заключване, което е полезно в бази данни, облачни платформи и разпределени системи.

Да. GitHub Copilot може да засече рисково подреждане на заключванията, да предложи последователно получаване на заключвания и да генерира тестове, които разкриват безизходици. Третирайте резултата му като първо преминаване и все пак проверете логиката на паралелността с подходящи инструменти за анализ.

Обобщете тази публикация с: