Mavzu: Tupik muammolari. Resurslarni taqsimlash grafi. Tupiklarni qayta ishlash usullari. Tupiklarni oldini olish. Bankir algoritmi Annotatsiya

13-14-Mavzu: Tupik muammolari. Resurslarni taqsimlash grafi. Tupiklarni qayta ishlash usullari. Tupiklarni oldini olish. Bankir algoritmi 


Annotatsiya: Ma’ruzada, tupik (deadlock) tushunchasi, tizim modeli, resurslarni taqsimlash grafi, wait-for (kutish) grafi, tupiklarni qayta ishlash va barataraf qilish, tizimning xavfsizlik holati, bankir algoritmi, tupiklarni aniqlash algoritmlari tushunchalari bayon qilingan.
Kirish
Operatsion tizimlarning muhim vazifalaridan biri – kompyuter resurslarini jarayonlar o’rtasida taqimslash hisoblanadi. Ushbu vazifa bilan chambarchas bog’liq bo’lgan tupik (deadlock) tushunchasi mavjud. Ushbu ma’ruzada rusrularni taqsimlash va tupiklarni aniqlashga doir tayanch tushunchalar bayon qilingan. “Tupiklarni aniqlash va ulardan qochish metodalari” mavzusida o’rganilgan bilimlarni kengaytirish, - operatsion tizimda resurslarni taqsimlashda tupiklar bilan kurashish metodlari va algoritmlari bayon qilinadi. Quyidagi asosiy tushunchalar qarab chiqilgan:
· Tizim modeli Resurslarni taqsimlash grafi · Tupiklar tavsifi · Tupiklarni qayta ishlash · Tupiklarning oldini olish · Tizimning xavfsiz holatini aniqlash · Resurslarni taqsimlash grafini qurish algoritmi
· Resurslarni xavfsiz taqsimlash uchun bankir algoritmi (tupikdan qochish misolida) · Tupiklarni aniqlash printsiplari · wait-for grafi · Tupiklarni aniqlash algoritmi va uning qo’llanilishi · Tupikdan keyin tiklash · Tupiklarni qayta ishlashga kombinatsiyalashgan yondoshuvlar.
Tupik masalasi
Tupik (deadlock) – bloklangan (to’silgan) jarayonlar to’plami bo’lib, ularning har biri bir nechta resursga egalik qiladi va ushbu to'plamdan boshqa biron bir jarayonga tegishli resursni kutish holati.
Tupikning oddiy misolini semaforalar yordamida modellashirish mumkin . Misol uchun, tizimda ikkita P1 va P2 jarayon murojaat qiladigan ikkita A va B tashqi qurilmalar berilgan bo’lsin. Tashqi qurilmalarning har biri sinxronlash maqsadida semaforlar bilan bog’langan va ular ham A va B bilan belgilangan bo’lsin. Semaforlar boshlang’ich holatda ochiq. Jarayonlarning har biriga ikkala qurilma ham kerak bo’lsin, lekin ular qurilmalarga teskari tartibda murojaat qilsin, ya’ni:
P1: wait(A); wait (B)
P2: wait(B); wait (A).
Bunday holda tupik joyiga ega bo’lamiz: P1 jarayon, A semaforani band qilib, birinchi qurilmani qulflab (bloklab) qo'yganligi, shuningdek, P2 jarayon allaqachon yopilganligi sababli, ikkinchi qurilma bilan bog’liq bo’lgan B semaforaning ochilishini hech qachon kutmaydi. Xuddi shunday, P2 jarayoni hech qachon A semaforaning ochilishini kutmaydi.
Tizim modeli
Bunday vaziyatlarni tavsiflash va o'rganish uchun tizimning formal (rasmiy) modelining umumiy ko’rinishini kiritamiz. Modeldan foydalanib, jarayonlarning resurslarga bo'lgan talabi (so’rovlari), jarayonlarning resurslarga haqiqiy egaligi va resurslarning bo’shatirilishi to'g'risida ma'lumot taqdim etish mumkin.
Faraz qilaylik, tizimda m ta turdagi resurslar berilgan bo’lsin (masalan, protsessor, xotira, kiritish-chiqarish qurilmalari). Tizimdagi resurslar turini R1, R2, …, Rm bilan belgilab olamiz. Aytalik, har bir Ri turdagi resurslarning Wi nusxalari mavjud bo’lsin.
Har bir jarayon quyidagi usullardan biri yordamida resurslardan foydalanishi mumkin:
· so’rov (talab - request)
· foydalanish (use)
· bo’shatish (release).
Bir vaqtning o’zida quyidagi to’rtta shart bajarilganda tupik holati bo’lishi mumkin:
1. o’zaro istisno: vaqtning har bir lahzasida faqat bitta jarayon resursga kira oladi;
2. ushlanib qolish va kutish: bitta resursni band qilib turgan jarayon, boshqa jarayonlar egalik qilib turgan boshqa resursdan foydalanishni kutib turadi;
3. uzilishning bo’lmasligi: jarayon faqatgina o’z ishini yakunlagandan keyingina resursni bo’shatishi mumkin;
4. tsiklik kutish: {P0, P1, … Pn} to’plam mavjud bo’lib, bu yerda P0 jarayon P1 jarayon egallab turgan resursni kutadi; P1 jarayon, P2 jarayon egallab turgan resursni kutadi va h.k. Pn jarayon P0 jarayon egallab turgan resursni kutadi.
 Resurslarni taqsimlash grafi