Deadlock

Deadlock — ikki yoki undan ko‘p bajarilish oqimi bir-biridan resurs kutib, hech biri davom eta olmaydigan holat.

Deadlock thread, process, database transaction, distributed service va operatsion tizim resurslarida yuz berishi mumkin.

Tizim crash qilmasligi mumkin, lekin ish to‘xtaydi va requestlar cheksiz kutadi.

Klassik misol

Ikki mutex mavjud: M1 va M2.

Thread A:
  M1ni oladi
  M2ni kutadi

Thread B:
  M2ni oladi
  M1ni kutadi

Har biri boshqasidagi resursni kutadi.

Hech kim o‘z lockini bo‘shatmaydi.

Coffman shartlari

Deadlock uchun to‘rtta shart bir vaqtda mavjud bo‘lishi kerak.

Mutual exclusion

Resursni bir vaqtda faqat bitta oqim ishlata oladi.

Hold and wait

Oqim bir resursni ushlab, boshqasini kutadi.

No preemption

Resurs ownerdan majburan xavfsiz olib qo‘yilmaydi.

Circular wait

Oqimlar aylana shaklida bir-birining resursini kutadi.

Shartlardan bittasi buzilsa, klassik deadlock oldi olinadi.

Lock order

Deadlockning eng keng tarqalgan oldini olish usuli — barcha locklarni bir xil tartibda olish.

Masalan:

Har doim M1 → M2 → M3

Hech bir kod M2dan keyin M1ni olmasligi kerak.

Lock hierarchy hujjatlashtiriladi.

Barcha lockni birga olish

Runtime bir nechta mutexni deadlockdan qochadigan algoritm bilan birga olishi mumkin.

Agar hammasi olinmasa, olinganlari bo‘shatiladi va qayta uriniladi.

Bu livelock ehtimolini hisobga oladi.

Timeout

Resursni cheksiz kutish o‘rniga timeout belgilanadi.

Timeout deadlockni to‘liq oldini olmaydi, ammo tizimni abadiy qotishdan chiqaradi.

Timeoutdan keyin:

• transaction rollback;
• request xato;
• retry;
• connection reset;
• alert

bajarilishi mumkin.

Try lock

Thread lockni ololmasa, ushlab turgan lockini bo‘shatib, keyin qayta urinadi.

Random backoff ikki threadning bir vaqtda qayta urinishini kamaytiradi.

Noto‘g‘ri algoritm livelock yaratishi mumkin.

Livelock

Oqimlar bloklanmagan, doim harakat qiladi, lekin foydali natija yo‘q.

Masalan, ikki thread bir-biriga yo‘l berib, doim lockni bo‘shatadi va yana to‘qnashadi.

Deadlockda harakat yo‘q, livelockda harakat bor, progress yo‘q.

Starvation

Bir thread resursga hech qachon navbat ololmasa starvation yuz beradi.

Boshqa threadlar ishlashda davom etadi.

Fair queue va priority siyosati starvationni kamaytiradi.

Database deadlock

Ikki transaction turli rowlarni teskari tartibda lock qilishi mumkin.

Database deadlock graphni aniqlab, transactionlardan birini victim sifatida rollback qiladi.

Ilova deadlock xatosini olib, transactionni boshidan retry qiladi.

Transaction misoli

Transaction A:
  account 1ni lock
  account 2ni kut

Transaction B:
  account 2ni lock
  account 1ni kut

Accountlarni doim ID tartibida lock qilish deadlockni kamaytiradi.

Distributed deadlock

Resurslar turli service yoki node’da bo‘lsa, global wait graphni ko‘rish qiyin.

Misol:

• Service A Bdan javob kutadi;
• B Cdan kutadi;
• C Aga synchronous request yuboradi.

Har service worker pooli to‘lib qolishi mumkin.

Timeout va asynchronous architecture muhim.

Thread pool deadlock

Barcha worker parent tasklarni bajaradi va har biri shu poolga yuborilgan child task natijasini kutadi.

Child task uchun bo‘sh worker qolmaydi.

Yechimlar:

• kutmaslik;
• alohida pool;
• pool hajmi;
• inline execution;
• structured concurrency.

File lock

Process fayl lockini olib, boshqa processdan javob kutishi mumkin. Qarshi process shu fayl lockini kutsa deadlock yuz beradi.

Process crashida advisory lock odatda OS tomonidan bo‘shatiladi, ammo lock file qolishi mumkin.

Signal va callback

Mutex ushlab turgan kod callback chaqirsa, callback yana shu mutexni olishga urinishi mumkin.

Reentrant bo‘lmagan mutexda o‘z-o‘zini deadlock qiladi.

Lock ichida noma’lum tashqi kod chaqirilmaydi.

Detection

Deadlock aniqlash vositalari:

• thread dump;
• wait-for graph;
• lock profiler;
• database deadlock log;
• watchdog;
• timeout;
• core dump;
• distributed tracing.

Har thread qaysi resursni ushlab, qaysini kutayotgani yoziladi.

Wait-for graph

Node thread yoki transaction, edge esa kutish munosabati.

Graphda cycle bo‘lsa deadlock mavjud.

Database engine cycle’ni avtomatik aniqlashi mumkin.

Recovery

Deadlock yuz berganda:

• bitta processni tugatish;
• transaction rollback;
• lockni recovery qilish;
• service restart;
• request timeout;
• cluster leadershipni o‘zgartirish

ishlatilishi mumkin.

Resursni majburan bo‘shatish shared state’ni buzishi mumkin.

Oldini olish

Amaliy qoidalar:

• global lock order;
• kichik critical section;
• lock ichida network I/O qilmaslik;
• timeout;
• transactionni qisqa saqlash;
• bir xil row order;
• callbackni lock tashqarisida chaqirish;
• monitoring;
• retryda backoff.

Diagnostika

Deadlock gumonida:

• threadlar CPU ishlatyaptimi;
• qaysi lock;
• owner;
• wait time;
• database transaction;
• worker pool;
• request chain;
• timeout;
• log timestamp

tekshiriladi.

Faqat service restart qilish sababni yo‘q qilmaydi.

Dining philosophers modeli

Deadlock tushuntirishda dining philosophers modeli ishlatiladi. Har ishtirokchi ikki yonidagi resursni olmasa ishini bajara olmaydi. Barchasi avval chap resursni olsa, har biri o‘ngdagisini kutadi.

Yechimlar:

• resurslarni tartib bilan olish;
• bir vaqtda kiruvchilar sonini cheklash;
• ikkala resursni atomik olish;
• markaziy arbiter.

Model real lock va transaction dizayniga mos keladi.

Deadlockdan keyingi ma’lumot

Service restart qilinishidan oldin thread dump, database lock graph va active requestlar saqlanadi. Restart dalilni yo‘qotishi mumkin.

Bog‘liq tushunchalar

Mutex, Semaphore, Lock, Circular wait, Livelock, Starvation, Transaction, Thread pool, Wait-for graph