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

Bankir algoritmi uchun ma’lumotlar tuzilmasi
n = jarayonlar soni; m = resurs turlari soni berilgan bo‘lsin
Avaliable: m vektorning uzunligi. Agar available [j] = k bo‘lsa, shu vaqtgacha R_j turidagi resurslarning k ta nusxasi ochiq bo‘ladi.
Max: n*m matritsa. Agar Max [i,j] = k bo‘lsa, u holda P_i jarayon R_j turidagi resurslarning eng ko‘p k ta resursni talab qilishi mumkin.
Allocation: n*m matritsa. Agar Allocation[i,j] = k bo‘lsa, u holda shu vaqtda P_i jarayonga R_j turidagi resurslarning k ta nusxasi band qilingan bo‘ladi.
Need: n * m matritsa. Agar Need [i,j] = k bo‘lsa, u holda P_i jarayon o‘z ishini yakunlash uchun R_j turidagi resurslarning yana k ta nusxasini talab qilishi mumkin.
Matritsa elementlari o'rtasida quyidagi munosabatlar mavjud:
Need [i,j] = Max[i,j] – Allocation [i,j].
 
Tizim holatini xavfsizlikka tekshirish algoritmi
Yuqoridagi belgilashlardan kelib chiqqan holda tizim holatini xavfsizlikka tekshirish algoritmini ko’rib chiqamiz.
Butun sonli Work (m uzunlikdagi) vektor va Finish (n uzunlikdagi) mantiqiy vektorni kiritamiz. Work vektori resurslarni namunaviy ajratishni ifodalaydi. Finish vektori tizimning ushbu holatida jarayonlarning yakunlanishi haqidagi ma’lumotlarni taqdim etadi.
Xavfsizlik algoritmi.
1-qadam. Boshlash.
Work = Available
Finish [i] = false dlya i = 1, …, n.
Bu yerda va keyingi o’rinlarda vektorlar yoki matritsalar ishtirokidagi barcha ta’minash va taqqoslashlar elementlar bo’yicha bajariladi..
2-qadam.
Shunday i ni topish kerakki, quyidagilar o’rinli bo’lsin:
Finish [i] = false
Need [i] <= Work
Agar bunday i mavjud bo’lmasa 4-qadamga o’tish.