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

2-rasm. To’rtta nusxasi bo’lgan resurs-tugunga misol.

3-rasm. Resurslarni taqsimlash grafiga misol.
Ushbu graf uchta jarayon va resurslarning to’rtta ko’rinishidan iborat tizimni tasvirlaydi: 1 va 2 ko’rinishdagi resurslar bitta nusxaga ega, 2-resurs ikkita nusxaga, 4-ko’rinishdagi resurs esa uch nusxada mavjud. 1-jarayon 2-jarayon band qilib turgan 1-resursga talabgor. 2-jarayon 3-jarayon band qilib turgan 3-resursga talabgor. 2-resursning ikkita birligi (nusxasi) 1- va 2-jarayonlarga berilgan. 4-resurs hozircha taqsimlanmagan (uning uchta nusxasi ham bo’sh).
Resurslarni taqsimlash grafi bo’yicha tupiklarni qidirish
Shubhasiz, yuqoridagi taqsimlash grafidagi tsikl, tupik holati mavjudligini anglatadi. 4-rasmda tupikli graf tasvirlangan. 1, 2, 3-jarayonlar o’rtasida tsiklik kutish holati mavjud. 1-jarayon 2-jarayon egallab turgan resursga talabgor. 2-jarayon 3-jarayon egallab turgan resursga talabgor. 3-jarayon 1 jarayonga berilgan resursning bitta nusxasiga talabgor va 2-jarayon esa ikkinchi nusxasiga talabgorlik qiladi.

4-rasm. Resurslarni tupikli taqsimlash grafiga misol.
Biroq, resurslarni taqsimlash grafida tsiklning borligi hamma vaqt ham tupik holati bor degani emas. 5-rasmda resurslarni tupiksiz taqsimlashning tsiklli grafi tasvirlangan.

5-rasm. Resurslarni tsiklli taqsimlashning tupiksiz holatiga misol.
Ushbu holatda (5-rasm) 4 ta jarayon va ikki turdagi resurs tasvirlangan. Grafdagi tsiklda 1 va 3 jarayon-tugunlar ishtirok etadi. Biroq, har bir resurs 2 tadan birlikdagi nusxalarga ega bo’lganligi uchun, tupik holatidan chiqib ketiladi: 1-resursni kutib turuvchi 1-jarayon Odnako, blagodarya tomu, chto kajdogo resursa imeetsya po dve yedinitsы, tupika udaetsya izbejat’: 1-resursni kutayotgan 1-jarayon, ushbu resursning bitta birligiga ega bo'lgan va kutish davriga kiritilmagan 2-jarayon (1-jarayon emas) tugagandan so'ng uni qabul qilishi mumkin. Xuddi shunday, 2-resursga talabgor bo’lgan 3-jarayon, uni 4-jarayon (1-jaran emas) bo’shatgandan keyin olishi mumkin.
Shunday qilib, quyidagi tasdiqlarni keltirish mumkin:
· Agar resurslarni taqsimlash grafida tsikl bo’lmasa, u holda tizimda tupik holati bo’lmaydi;
· Agar resurslarni taqsitmlash grafida tsikl mavjud bo’lsa, u holda ikkita holat bo’lishi mumkin:
· Har bir turdagi resurslar faqat bir nusxaga ega bo’lsa, u holda tupik holati bo’ladi;
· Agar resurslar bir nechta nusxada bo’lsa, u holda tupikning oldini olish mumkin.
Tupiklarni qayta ishlash metodlari
Nazariy jihatdan tupiklarni qayta ishlashning quyidagi metodlari mavjud:
• Tizim hech qachon tupik holatiga tushmasligiga ishonch hosil qiling;
• Tizimning tupik holatiga kirishiga ruxsat bering, ammo tupik holatdan chiqish imkoniyatini ta'minlang.
Afsuski, amalda ko'plab operatsion tizimlar (shu jumladan UNIX) tupiklar bilan ishlashning uchinchi "usuli"dan foydalanadi: tupik muammosi e'tiborga olinmaydi (istisno qilinadi), ammo OT mualliflari tizimda tupiklarni bartaraf qilish mumkin emasligini ta'kidlaydilar.
Tupiklar oldini olish (bartaraf qilish)
Qanday qilib tupik holatining oldini olish usullarini tahlil qilamiz. Asosiy g'oya - bu jarayon tomonidan resurslarni talab qilish usullarini cheklash.
Resursga egalik huquqini o'zaro istisno qilish imkoniyatini cheklash uchun (birinchi tupik sharti), shuni ta'kidlash kerakki, hamma resurslar uchun ham bu talab qilinmaydi. Bo’linuvchi resurslar uchun (masalan, konstantalar massivi, kodlar, fayllar) bu talab qilinmaydi.
Ushlanib qolish va kutish imkoniyatlarini cheklash uchun (ikkinchi tupik sharti), ba’zi resurslarni talab qiluvchi jarayondan boshqa birorta ham resursga egalik qilmaslik talabini qo’yish mumkin. Talab qo’yishning muqobil varianti barcha jarayonlarga ular bajarilishi boshlanishidan oldin ularga hamma zarur resurslarni egallashini oldindan tayinlash kerak. Afsuski, ushbu ikkala talabni amalga oshirish resurslardan yetarli darajada foydalanmaslik va “ochlik” (starvation) ehtimolini keltirib chiqaradi.
Jarayon resursni kutib turganda har safar resurslarni qayta taqsimlash yanada oqilona strategiya bo'lib tuyuladi.
Agar jarayon qaysidir A resursga egalik qilib turgan bo’lsa va tezkorlik bilan ajratib berish imkoni bo’lmagan boshqa B resursni talab qilsa, u holda jarayon kutib turishi shart. Buning uchun jara1n bilan band bo’lgan A resurs, tezkorlik bilan bo’shatilishi shart. A resurs jarayonlar kutib turgan resurslar ro’yxatiga kiritiladi. Agar jarayon o’zi egallab turgan eski resurslarni va kutib turgan barcha yangi resurslarni bir vaqtda taqsimlab olish mumkin bo’lsa, u qayta tiklanadi.
Davriy (tsiklik) kutish holatining oldini olish uchun eng oddiy yechim - barcha turdagi resurslarni raqam bo'yicha tartiblashni joriy qilish va jarayondan resurslarni faqat ularning raqami o'sish tartibida so’rashni talab qilishdir. Amalda bunday yechim deyarli tatbiq etilmaydi va qulay emas, chunki iste'mol qilinadigan va talab qilinadigan resurs turlarining o'ziga xosligi hech qanday tarzda mumkin bo'lgan raqamlashlarga bog'liq emas va zarur bo'lganda har qanday raqamga ega bo'lgan resursga ehtiyoj paydo bo'lishi mumkin.
Tupiklardan qochish
Tupikning oldini olish usullari tizimdan har bir jarayon tizimga kirgan paytdan boshlab jarayon va uning resurslariga bo'lgan talablari to'g'risida qo'shimcha ravishda muhim ma'lumotlarga ega bo'lishni talab qiladi.
Eng oddiy va foydali model har bir jarayon tizimga kirishda uni qanoatlantiradigan maksimal hajmda har bir turdagi resursni talab qiladi. Ushbu yondashuv hatto dastlabki operatsion tizimlarda ham amalga oshirilgan va jarayon pasporti, ya’ni jarayon talab qiladigan har bir turdagi – tezkor va tashqi xotira, ishlash vaqti, chop qilish sahifalari va boshqa resurslarning ro’yxati deb nomlanishigi olib kelgan.
Masalan, BESM-6 kompyuteri uchun ishlab chiqilgan DISPAK operatsion tizimi (1960-yy) uchun jarayon pasporti quyidagi ko’rinishda bo’lishi mumkin:
LIST 0-37^TRAK 50^VRЕM 240^ATSPU 10^
yoki
LIST 0-37^TRAK 50^TIME 240^ADC 10^
Bu yerda LIST – asosiy xotiraning sahifalari diapazoni, TRAK – tashqi xotiradan talab qilingan hajm, VRЕM – bajarilishning maksimal vaqti (2 minut 40 sekund, bu eng tez bajariladigan jarayonlar sinfiga mos keladi), ATSPU – chop qilish qurilmasiga berilgan varaqlardagi maksimal hajm.
Belgilagan cheklovlardan hech bo’lmagan bittasini oshirib yuborishga urinish foydalanuvchi uchun tashxis xabariga mos ravishda operatsion tizim jarayonni hisobdan o’chirib qo’yadi.
Tupik holatidan qochish algoritmi resurslarning taqsimlanganlik holatini hech qachon davriy kutish holatiga tushib qolmasligini tahlil qilishi shart.
Resurslarni taqsimlash holati mavjud resurslar miqdori, ajratilgan resurslar miqdori va jarayonlarning maksimal talablari sifatida tavsiflanadi.