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

Tupiklardan qochish strategiyasi uchun resurslarni taqsimlash grafining yangilangan (o’zgartirilgan) varianti
Resurslarni taqsimlash grafi “Tupiklar (deadlocks), tupiklarni aniqlash va bartaraf etish metodlari” mavzusida qarab chiqilgan edi. Tupiklardan qochish strategiyasini tatbiq qilish uchun ushbu grafga nafaqat jarayonlar tomonidan egallab turilgan aniq resurslar, balki kelgusida talab qilinadigan resurslar haqidagi ma’lumotlarni ham qo’shish kerak bo’ladi. Buning uchun, so’rovlar va ta’minlash yoylaridan tashqari, Pi jarayon-tugundan Rj resurs tugunga olib boruvchi talab yoyi (claim edge)ni hisobga olib, ushbu yoyni nuqtali chiziq bilan belgilab olamiz. Bu Pi jarayon Rj resursni talab qilishi mumkinligini anglatadi.
Agar jarayon ushbu resursni aniq talab qilsa, u holda talab yoyi so’rov yoyiga almashtiriladi (nuqtali chiziq butun chiziqqa aylantiriladi).
Agar jarayon resursni bo’shatsa, ta’minlash yoyi talab yoyiga almashtiriladi.
Grafni bunday yangilashdan maqsad – jarayonlarning tizim resurslariga bo’lgan talablarni oldindan aniqlashdir.
Tupiklardan qochish strategiyasi uchun resurslarni taqsimlash grafiga misol 6-rasmda tasvirlangan.

6-rasm. Tupiklardan qochish strategiyasi uchun resurslarni taqsimlash grafiga misol.
Resurslarni taqsimlashning yangilangan grafida tizimning xavfli holatini tasvirlash osonligini ko’rish mumkin. Xavfli holatga misol 7-rasmda berilgan.

7-rasm. Resurslarni taqsimlash grafidagi xavfli holatga misol.
Bankir algoritmi printsiplari
Operatsion tizimning resurslarini xavfsiz taqsimlash uchun bankir algoritmi (tupiklardan qochish) E.Deykstr tomonidan taklif qilingan va birinchi marotoba 1960-yillarning oxirida THE oeratsion tizimida tatbiq qilingan. Algoritmning nomlanishi algoritmga yondoshuv bank operatsiyalarini bajarishda bankirning ehtiyotkorligini eslatadi. Bankir algoritmining printsiplari quyidagicha:
· Har bir jarayon o’zining resurslarga bo’lgan ehtiyojini maksimal darajada belgilab berishi shart.
· Jarayon resursni talab qilganda, u kutish holatida bo’lishi mumkin (so’rov bo’yicha hamma vaqt ham resurslar zudlik bilan ajratilmasligi mumkin).
· Jarayon talab qilgan resursini olgandan keyin, cheklangan vaqt davrida uni tizimga qaytarishi shart.