Berkliklar muammosi
Berklik (deadlock) bu bloklangan jarayonlar to‘plami bo‘lib, ulardan har biri qandaydir resursga ega va bu to‘plamdan qandaydir boshqa jarayon ega bo‘lgan resursni kutadi.Berklikka oddiy misolni semaforalar yordamida modellashtirish oson.
Tizimda ikkita J1 va J2 jarayonlar murojaat qiladigan ikkita tashqi A va B qurilmalar bo‘lsin. Semafor sinxronlashtirish maqsadida tashqi qurilmalarning har biri bilan bog‘langan, ularni ham A va B bilan belgilaymiz. Semaforlar oldindan ochiq. Jarayonlardan har biriga har ikkala qurilmalar zarur bo‘lsin, lekin ular qurilmalarga qarama-qarshi tartibda murojaat qiladi:
J1: kutish (A); kutish (B) J2: kutish (B); kutish (A).
Bu holda berklik o‘z o‘rniga ega bo‘ladi. J1 jarayon A semaforni yopish va birinchi qurilmani bloklash bilan ikkinchi qurilma bilan bog‘langan B semaforni qachon ochilishini hech qachon mo‘ljallay olmaydi, chunki uni J2 jarayon yorishga ulgurgan. Shunga o‘xshash, J2 jarayon A semaforning ochilishini mo‘ljallay olmaydi.
Tizim modeli
Bunday vaziyatlarni tavsiflash va tadqiq qilish uchun tizimning rasman modelini umumiy ko‘rinishda kiritamiz. Model yordamida jarayonlarning resurslari so‘rovlar haqida, jarayonlarning resurslarga haqiqatda egaligi haqida va resurslarning bo‘shashi haqidagi ma’lumotlarni beramiz. Tizimda m turlardagi resurslar (masalan, protsessor, xotira, kiritish/chiqarish qurilmalari) bo‘lsin. Tizimda resurslar turlarini R1, R2, … Rm bilan belgilaymiz. Har bir Ri resurs turi Wi nusxalarga ega bo‘lsin. Har bir jarayon quyidagi usullardan biri orqali resursdan foydalanishi mumkin:
so‘rov (request);
foydalanish (use);
bo‘shatish (release). Berklikagarquyidagito‘rttashartlarbirvaqtdabajarilsa,
vujudgakelishimumkin:
O‘zaro inkor qilish: har bir vaqt momentida faqat bitta jarayon resursga ulanishni olishi mumkin;
Saqlash va kutish: bitta resursni saqlayotgan jarayon boshqa jarayonlar ega bo‘lgan boshqa resurslarni olishni kutadi;
Uzilishlarning bo‘lmasligi: jarayon o‘zining ishlashini tugatganidan keyingina resursni bo‘shatishi mumkin.
Siklli kutish: J0 jarayon J1 jarayon ega bo‘lgan resursni kutadigan, J1 jarayon J2 jarayon ega bo‘lgan resursni kutadigan Jn
jarayon J1 jarayon ega bo‘lgan resursni kutadigan {J0, J1, … Jn} to‘plam mavjud.
Resurslarni taqsimlash grafi
Ko‘rib chiqishga V balandliklar to‘plami va E yoylar to‘plamidan iborat resurslarni taqsimlash grafini kiritamiz. V ikkita turlardagi – balanliklar-jarayonlar va balandliklar-resurslarga bo‘linadi. Boshqacha aytganda, V tizimdagi barcha jarayonlar J = {J1, J2, … , Jn} turdagi balandliklar to‘plami va R = {R1, R2, … , Rm} turdagi balandliklar to‘plamiga bo‘linadi.
Yoylarning quyidagi ikkita turlarini kiritamiz:
“so‘rov” turdagi yoy (request edge) – Ji → Rj turdagi yo‘naltirilgan yoy.
“tayinlash” turdagi yoy (assignment edge) – Ji ← Rj turdagi yo‘naltirilgan yoy.
Yoylarning turli yo‘nalishlarining ma’nosi quyidagicha. Agar jarayon qanday resursga da’vogarlik qilsa, u holda yoy balandlik- jarayondan balandik-resursga o‘tkaziladi.
Aniq resurs birligi qandaydir jarayonga ajratilsa, u holda yoy bu belgiga tegishli bo‘ladi va balandlik-resursdan jarayonning balandligiga o‘tkaziladi. Kiritiladigan graf va uning grafining o‘ziga xos xususiyatlarini aniqlashtiramiz.
Zamonaviy atamada bu turdagi graf – zahiralangan graf (reserved graph) deyiladi. Uning balandlik-jarayoni oddiy ko‘rinishga ega bo‘ladi, Rj resursga mos keladigan balandlik-resurs esa Wj nimbalandliklardan tashkil topadi, ulardan har biri aniq bir resurs birligini belgilaydi. Zahiralangan graflar nazariyasida bunday balandliklar superbalandliklar (super-vertices) deyiladi.
Shunday qilib, so‘rov yoyi umuman balandlik-jarayondan balandlik-resursga boradi, tayinlash yoyi esa balandlik-resursnng mos nimbalandligidan balandlik-jarayonga boradi. Balandlik-jarayonga misol 2.25- rasmda keltirilgan.
2.25- rasm. Resurslarni taqsimlash grafidagi balandlik-jarayonga
misol
To‘rtta nusxali superbalandlik-resursga misol 2.26-rasmda kelti- rilgan.Resursning har bir nusxasiga o‘z nimbalandligi mos keladi.
Resurslarni taqsimlash grafiga misol 2.27- rasmda keltirilgan.
2.26- rasm. To‘rtta nusxali superbalandlik-resursga misol
R1 R3
R2
R4
2.27- rasm. Resurslarni taqsimlash grafiga misol
Bu graf uchta jarayonlar va to‘rtta resurslari turlariga ega bo‘lgan tizimni aks ettiradi: 1- va 3- turlardagi resurslar bittadan nusxaga ega, 2- turdagi resurs ikkita nusxaga ega, 4- turdagi resurs uchta nusxaga ega. 1- jarayon 2- jarayon bilan band bo‘lgan 1- resursga da’vogarlik qiladi. 2- jarayon 3- jarayon bilan band bo‘lgan 3- resursga da’vogarlik qiladi. 2- resursning ikkita birliklari 1- va 2-
jarayonlarga berilgan.4- resurs taqsimlanmagan (barcha uchta birliklar bo‘sh).
Resurslarni taqsimlash grafi bo‘yicha berkliklarni qidirish
Ma’lumki, bunday grafdasikl berklikning borligini bildiradi.
R1 R3
R4
2.28- rasm. Berklikli resurslarni taqsimlash grafiga misol
2.28- rasmda berklikli resurslarni taqsimlash grafiga misol keltirilgan. 1, 2 va 3- jarayonlar orasidagi siklli kutish vaziyati mavjud. 1- jarayon, 2- jarayon ega bo‘lgan resursga da’vogarlik qiladi. 2- jarayon, 3- jarayon ega bo‘lgan resursga da’vogarlik qiladi. 3- jarayon bitta birligi 1- jarayonga, ikkinchi birligi 2- jarayonga berilgan resursga da’vogarlik qiladi.
Lekin har doim ham resurslarni taqsimlash grafida siklning bo‘lishi berklikni borligini bildirmaydi.
2.29- rasmda siklli, lekin berkliksiz resurslarni taqsimlash grafiga misol keltirilgan. Bu holda (2.29- rasm) to‘rtta jarayonlar va ikkita resurslar turlari mavjud bo‘ladi. Siklda 1- va 3- balandliklar- jarayonlar qatnashadi. Lekin har bir resursda ikkitadan birliklar borligi tufayli berklikning oldini olishga erishiladi. 1- resursni kutadigan 1- jarayon uni bu resursning bitta birligiga ega bo‘lgan va kutish sikliga kirmaydigan 2- jarayon (1- jarayon emas) tugagandan keyin olishi mumkin. Shunga o‘xshash, 2- resursga da’vogarlik qiladigan 3-
jarayon uni 4- jarayon (1- jarayon emas) bo‘shatganidan keyin olishi mumkin.
2.29- rasm. Siklli, lekin berkliksiz resurslarni taqsimlash grafiga misol
Shunday qilib, quyidagi mulohazani aytish mumkin. Agar resurslarni taqsimlash grafi sikllarga ega bo‘lmasa, u holda tizimda berkliklar mavjud emas. Agar resurslarni taqsimlash grafi sikllarga ega bo‘lsa, u holda quyidagi ikkita hollar bo‘lishi mumkin:
Agar har bir turdagi resurslar faqat bittadan bo‘lsa, u holda berklik o‘z o‘rniga ega bo‘ladi;
Agar resurslar bir necha nusxalarda bo‘lsa, u holda berklik bo‘lishi mumkin.
Berkliklarga ishlov berish usullari
Nazariy jihatdan quyidagi berkliklarga ishlov berish usullari bo‘lishi mumkin:
Tizim hech qachon berklik holatiga kirmasligiga amin bo‘ling;
Tizim berklik holatiga kirishi mumkinligini olish, lekin berklikdan keyin qayta tiklanish imkoniyatini ko‘zda tutish.
Afsuski, amalda ko‘plab OTlarda (shu jumladan, UNIXda) berkliklar bilan kurashishning uchinchi “usuli” ham ishlatiladi. Berkliklar muammosi inkor qilinadi, lekin OT mualliflari hech bir asoslarsiz tizimda berkliklar mumkin emasligiga da’vo qilishadi.
Berkliklarning oldini olish
Berkliklarning oldini olish qanday usullarining mumkinligini tahlil qilamiz. Asosiy g‘oya jarayonlar tomonidan resurslarga so‘rovlar usullarini cheklash hisoblanadi. Resurslarga ega bo‘lishni o‘zaro inkor qilish (berklikning birinchi sharti) imkoniyatini cheklash uchun u barcha resurslar uchun ham talab qilinmasligini ta’kidlash zarur.
Bo‘linadigan resurslar (masalan, konstantlar, kodlar, fayllari massivlari) uchun u talab qilinmaydi. Saqlash va kutish imkoniyatini cheklash (berklikning ikkinchi sharti) uchun qandaydir resursni so‘raydign jarayon boshqa hech qanday resurslarga ega bo‘lmasligini talab qilish mumkin.
Muqobil variant barcha jarayonlar ularning haqiqiy bajarilishini boshlanishigacha barcha zarur resurslarga ega bo‘lishi talabi hisoblanadi. Afsuski, har ikkala talablarning bajarilishi resurslardan foydalanishning yetishmasligi va “och qolish”ga (starvation) olib keladi.
Jarayon resursni har bir kutishida resurslarni qayta taqsimlash algoritmi ma’qulroq hisoblanadi. Agar jarayon qandaydir A resursga ega bo‘lsa va unga darhol ajratilishi mumkin bo‘lmagan boshqa B resursni so‘rasa, u holda jarayon kutishi kerak. Bunda jarayon egallagan A resurs darhol bo‘shatilishi kerak. A resurs jarayon kutayotgan resurslar ro‘yxatiga kirtiladi.
Jarayon faqat agar unga bir vaqtda u ega bo‘lgan barcha eski resurslar va u kutayotgan yangi resurslar ajratilishi mumkin bo‘lsa, qayta tiklanishi mumkin.
Siklli kutish vaziyatining oldini olish uchun eng oddiy yechim barcha resurslar turlari raqamlari bo‘yicha tartiblashtirishni kiritish va jarayon resurslarni faqat ularning raqamlarini ortib borishi tartibida so‘rashi talabini kiritish hisoblanadi.
Amalda bunday yechimni qo‘llanishi va qulay bo‘lishi ehtimoli kam, chunki iste’mol qilinadigan va talab qilinadigan resurslar turlarining o‘ziga xosligi barcha bo‘lishi mumkin raqamlashlarga hech qanday bog‘liq emas va istalgan raqamli resursga ehtiyoj zarurati bo‘yicha vujudga kelishi mumkin.
Berkliklardan qochish
Berkliklardan qochish usullari tizim har bir jarayon tizimga kiritilishi momentidan boshlab jarayon va uning resurslarga ehtiyojlari haqidagi qo‘shimcha tekshirilmagan ma’lumotlarga ega bo‘lishini talab qiladi. Eng oddiy va foydali model har jarayon tizimga kiritilishida unga kerak bo‘ladigan har bir turdagi resurslarning maksimal hajmini ko‘rsatishini talab qiladi.
Bu yondashish hatto oldingi OTlarda ishlatilgan va topshiriqlar pasporti nomiga – jarayonning har bir turdagi resurslarga maksimal ehtiyojlari ro‘yxatiga – operativ va tashqi xotira, bajarilish vaqti, chop etish varaqlari va boshqalarga ega.
Berkliklardan qochish algoritmi siklli kutish vaziyati hech qachon yuz bermasligiga ishonch hosil qilish uchun resurslarni taqsimlanishi holatini tahlil qilishi kerak. Resurslarni taqsimlanishi holati mumkin resurslar hajmi, taqsimlangan resurslar hajmi va jarayonlarning maksimal talablari sifatidatavsiflanadi.
|
