P1: wait(A); wait (B) P2: wait(B); wait (A)

P1: wait(A); wait (B)

P2: wait(B); wait (A).

Tizim modeli

• 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).

Tizim modeli

• Bir vaqtning o’zida quyidagi to’rtta shart bajarilganda tupik holati bo’lishi mumkin:
• o’zaro istisno: vaqtning har bir lahzasida faqat bitta jarayon resursga kira oladi;
• ushlanib qolish va kutish: bitta resursni band qilib turgan jarayon, boshqa jarayonlar egalik qilib turgan boshqa resursdan foydalanishni kutib turadi;
• uzilishning bo’lmasligi: jarayon faqatgina o’z ishini yakunlagandan keyingina resursni bo’shatishi mumkin;
• siklik 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 grafini qurish algoritmi

• 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.