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

V ta tugun va ularni o’zaro bog’lovchi E yoydan tashkil topgan resurslarni taqsimlash grafini o’rganib chiqamiz. V tugunlar ikkita qism tugunlarga bo’linadi: jarayon-tuguni va resurs-tugun, ya’ni V tugunlar to’plami tizimdagi barcha jarayonlar P = {P1, P2, … ,Pn} va barcha resurslar R = {R1, R2, … ,Rm} qism to’plamlariga ajratiladi.
Ikki turdagi yoyni kiritib olamiz:
· «so’rov» turidagi yoy (request edge) – Pi -> Rj kabi yo’naltirilgan yoy.
· “ta’minlash” turidagi yoy (assignment edge) – Ri -> Pj kabi yo’naltirilgan yoy.
Yoylarning turli yo’naltirilganligi quyidagicha. Agar jarayon biror bir resursga talabgor bo’lsa, u holda yoy jarayon-tugundan resurs-tugunga o’tkazilgan (yo’naltirilgan) bo’ladi. Agar aniq bir birlikdagi resurs qaysidir aniq jarayonga ajratilgan bo’lsa, u holda yoy mansubligi bo’yicha resurs-tugundan jarayon-tugunga o’tkazilgan bo’ladi.
Kiritilayotgan graf va uning tugunlarining asosiy xususiyatlariga aniqlik kiritib olamiz. Zamonaviy atamashunoslikda bunday ko’rinishda tavsiflanadigan graflar reserved graph deb ataladi. Uning jarayon-tuguni oddiy ko’rinishga ega, resurs-tuguni esa, ya’ni Rj resursga mos keluvchi tugun har biri resursning aniq bir birligini anglatuvchi Wj qism tugunlardan tashkil topgan bo’ladi. Reserved graphs nazariyasida bunday tugunlar odatda supertugun (super-vertices) deb ataladi. Xuddi shunday, so’rov yoyi jarayon-tugundan resurs-tugunga o’tkazilgan yoy, ta’minlash yoyi esa resurs-tugunning qism-resursidan jarayon-tugunga o’tkaziladi.

1-rasm. Resurslarni taqsimlash grafining jarayon-tuguniga misol.
O’zining to’rtta nusxasiga ega bo’lgan (super) resurs-tugunga misol 2-rasmda keltirilgan: resursning har bir nusxasi o’zining qismtuguniga mos keladi.