13,14 – ma’ruza. Operatsion tizimlarda tupik (deadlock) tushunchasi

7.5. O'zaro berk hodisalarni modellashtirish
Xolt (Xolt, 1972) yo'naltirilgan graflar yordamida ushbu to'rt shartni qanday modellashtirish mumkinligini isbotlab berdi. Graflarda ikki xil tugun mavjud: doiralar bilan ko'rsatilgan jarayonlar va kvadratlar bilan ko'rsatilgan resurslar. Resurs tugunidan (kvadratidan) jarayon tuguniga (doirasiga) qarab yo'naltirilgan qirra, ushbu resurs oldindan so'ralganligini, qabul qilinganligini va hozirda ushbu jarayon tomonidan ushlab turilishini anglatadi. R resurs hozirda A jarayoniga ajratilgan (1-rasm, a).
Jarayondan resursga o'tuvchi yo'naltirilgan qirra, bu jarayon hozirda ushbu resurs chiqarilishini kutib, bloklanganligini anglatadi. 1-rasm, b da, B jarayon S resurs chiqarilishini kutmoqda.1-rasm, c da biz o`zaro berk holatni ko'rib turibmiz: C jarayoni hozirda D jarayoni ushlab turgan T manbasini kutmoqda, D jarayoni T manbasini chiqarmoqchi emas, chunki u ushlab turgan U resursini chiqishini kutmoqda. C jarayoni bilan ushlab turilgan. Ikkala jarayon ham abadiy kutish holatida. Grafikning dumaloq tuzilishi shuni anglatadiki, biz tsikldagi jarayonlar va resurslarni o'z ichiga olgan o`zaro blikorovka bilan ish olib borayapmiz (tizimda har bir turdagi bitta resurs mavjud deb taxmin qilinadi). Ushbu misolda quyidagi tsikl chiqdi: C - T - D - U - C)

a b c
1 rasm. Resurslarni taqsimlash grafi: a – resurs band; b – resurs so’rovi;
d – bloklanish
7.6. O'zaro berk hodisadan chiqish
Bizning o'zaro berk hodisalarni aniqlash algoritmi muvaffaqiyatli ishlagan va bunday qulfni topdi. Keyingi nima? Bizga chiqib ketishning ba'zi usullari kerak bo’ladi, tizimning ish faoliyatini tiklashga imkon beradigan. Ushbu bo'limda o'zaro berk hodisadan chiqishning turli usullari ko'rib chiqiladi. Lekin ularning hech biri o'ziga xos e'tirozga ega emas.)
7.7. Tupiklarni qayta ishlash usullari
7.7.1. Resurslarni ustivor o'zlashtirish hisobiga tiklash
Ba'zan siz vaqtincha uning hozirgi egasidan resursni olib tashlash va boshqa jarayonga o'tkazishingiz mumkin. Ko'pgina hollarda, bu, ayniqsa, universal mashinalarda ishlaydigan ommaviy ishlov berish operatsion tizimlarida operatorning aralashuvini talab qilishi mumkin.
Misol uchun, lazer printerni egasidan olish uchun operator allaqachon chop etilgan barcha varaqlarni to`plamga qo'yishi mumkin. Keyinchalik, jarayon to'xtatilishi mumkin (ishlamaydigan deb belgilanadi). Shundan so'ng, printer boshqa jarayonga ajratilishi mumkin. Ushbu jarayon o'z ishini tugatgandan so'ng, bosilgan qog'oz varaqlarining to'plami printerning qabul qilish tepsisi ichiga joylashtirilishi va asl jarayonning ishlashi qayta tiklanishi mumkin.
Jarayondan resursni olib tashlash, uni boshqa jarayonga foydalanishga ruxsat berish va keyin jarayonni ogohlantirmasdan qaytarish qobiliyati asosan ushbu resursning tabiatiga bog'liq. Ushbu usul bilan tiklash ko'pincha qiyin yoki umuman mumkin emas. To'xtatib turish uchun jarayonni tanlash jarayoni qaysi manbaga ega ekanligi bilan bog'liq bo'lib, uni osongina olish mumkin.