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

3-qadam.
Work = Work + Allocation [i]
Finish [i] = true
2-qadamga o’tish.
4-qadam.
Agar barcha i = 1, …, n lar uchun Finish[i] = true bo’lsa, u holda tizim xavfsiz holatda.
Algoritmga zarur tushuntirishlar:
· Agar u mavjud bo’lsa, algoritm i jarayonlar raqamlarining xavfsiz ketma-ketligini yaratadi. Ketma-ketlikning navbatdagi elementi aniqlangandan keyingi har bir qadamda, algoritm i-jarayon yakunlangandan keyin undan resursni bo’shatishni modellashtiradi.
· 1-qadamda vektorlarni ta’minlash elementlar bo’yicha amalga oshiriladi.
· 2-qadamda talab matritsasi Need – (n * m) o’lchamga ega; Need[i] - i jarayonning talablarini tasvirlovchi matritsa satri (m-uzunlikda). Taqqoslashlar ham elementlar bo’yicha amalga oshiriladi va uning natijasi berilgan munosabat vektorning barcha elementlari uchun o’rinli bo’lsa, rost deb qabul qilinadi. Tekshiruvchi shartlar i jarayon talablari topilgan raqamda zudlik bilan qanoatlantirganda va jarayon resursdan foydalanib, yakunlanganligini anglatadi.
· 3-qadamda, Allocation [i] – Allocation matritsasining satri, joriy resurs i jarayonga ajratilganligini bildiradi. Work vektori yordamida i – jarayon o’z ishini yakunlaganlik belgisi qo’yilgandan keyin resursni bo’shatish modellashtiriladi.
Algoritm aniqligi va uning to’g’riligini isbotlash va baholashni mustaqil bajarishga qoldiramiz.
Bankir algoritmining asosiy qismi - Pi jarayonning resurslarga talab algoritmi
Asosiy algoritm uchun Requesti (m uzunlikda) – P_i jarayon uchun so’rovlar vektorini kiritib olamiz. Agar Requesti [j] = k, u holda P_i jarayon R_j resursning k ta nusxasini talab qilgan bo’ladi.
1. Agar Request_i £ Need_i bo‘lsa, 2-qadamga o‘tish. Aks holda istisno holati yaratiladi, chunki jarayon o‘zining maksimal ehtiyojidan oshib ketdi.
2. Agar Request_i £ Available bo‘lsa, 3-qadamga o‘ting. Aks holda P_i jarayon resurs yopiq (band) bo‘lganligi uchun kutishi shart bo‘ladi.
3. P_i jarayonga resurslarni ajratishni holatni quyidagi ko‘rinishda modifikatsiyalagan holatda rejalashtirish:
Available = Available - Request_i;
Allocation_i = Allocation_i + Request_i;
Need_i = Need_i – Request_i;;
• Agar holat xavfsiz bo‘lsa Þ resurs P_i ga ajratilgan.
• Agar holat xavfli bo‘lsa Þ P_i kutadi; resurslarni taqsimlashning oldingi holatini tiklanadi.