Livelock: Какво е, пример, разлика с Deadlock

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

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

🔁 Определение: Застой в реално време (Livelock) възниква, когато процесите постоянно променят състоянието си, за да се съобразят един с друг, но никога не напредват, за разлика от замразените процеси в безизходица (deadlock).
🚶 Пример: Двама души стъпватping един до друг в коридор, за да се пропускат един друг, илюстрирайки живо заключване, движение непрекъснато, но никога пресичане.
🧮 Причина: Многократното запитване и повторни опити за заключвания, ограничени от крайни слотове в таблицата с процеси, кара процесите да се заключват в режим на живо (livelock), без нито един от тях да блокира.
️ Сравнение: Безизходицата замразява процесите, гладуването отказва ресурси за неопределено време, а livelock държи процесите заети без напредък.
️ Предотвратяване: Рандомизираното отлагане, ограниченията за повторни опити и подреждането на приоритетите прекъсват симетричните повторни опити, които създават „livelock“.
🤖 Ъгъл на изкуствен интелект: Машинното обучение сигнализира за модели на процесора, които не показват напредък, а Copilot помага за писането на код за отсрочка и подреждане на заключения, който избягва заключването на живо.

Прочетете повече

Какво е Livelock?

A livelock е ситуация, при която заявка за ексклузивно заключване се отхвърля многократно, тъй като много от тях се припокриватping Споделените заключвания непрекъснато си пречат. Процесите непрекъснато променят статуса си, което им пречи да изпълнят задачата.

Примери за Livelock

Пример 1:

Най-лесният пример за „Ливлок“ са двама души, които се срещат лице в лице в коридор и двамата се отдръпват, за да пропуснат другия. Те продължават да се движат от едната страна на другата, без да напредват, защото се движат по един и същи начин едновременно. Тук те никога не се пресичат.

Пример 2:

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

Процес А държи ресурс Y
Процес B държи ресурс X
Процес А изисква ресурс X
Процес Б изисква ресурс Y

Да приемем, че процес А се изпълнява първо и придобива ресурс X, а след това процес B се изпълнява и придобива ресурс Y. Без значение кой процес се изпълнява пръв, нито един от тях не постига по-нататъшен напредък.

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

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

Какво води до Livelock?

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

Какво е Deadlock?

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

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

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

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

Какво е гладуване?

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

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

Пример за гладуване

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

Разлика между Deadlock, Starvation и Livelock

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

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

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

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

Често да. Блокираните процеси остават замразени, което е лесно за откриване, докато активно блокираните процеси остават активни и постоянно променят състоянието си. Откриването обикновено търси високо натоварване на процесора, комбинирано с нулев напредък с течение на времето.

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

Да. Нишките, които реагират многократно една на друга – например, едновременно освобождават и изискват повторно заключване в един и същи момент – могат да се заключват в режим „livelock“ (живо заключване), без изобщо да блокират. Това често се появява в логиката за повторен опит и отказ, на която липсва случайност.

Моделите за машинно обучение изучават процесора, планирането и моделите на използване на ресурси, за да сигнализират за процеси, които изгарят цикли, без да напредват. Това помага на операторите да открият „livelock“ по-рано от фиксирани прагове, особено при големи натоварвания в облака и центрове за данни с много взаимодействащи процеси.

Да. GitHub Copilot може да предложи рандомизирани модели за отсрочка, времеви ограничения и последователни модели за подреждане на заключванията, които намаляват риска както от livelock, така и от deadlock. Разработчиците все пак трябва внимателно да преглеждат генерираната логика за паралелизъм, тъй като е лесно да се пропуснат фините грешки във времето.

Понякога. Ако времето се измести — например чрез случайни интервали на повторен опит — процесите могат да нарушат модела и да продължат. Без такива промени, livelock може да продължи неопределено време, изразходвайки процесор, докато никой процес не завърши задачата си.