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

Bankir algoritmining qo‘llanilishiga misol
5 ta jarayonlar - P₀ dan P₄ gacha;
resurslarning 3 ta turi - A (10 nusxa), B (5 nusxa) va C (7 nusxa).
T₀ vaqtdagi (boshlang’ich) holat:

	Allocation	Max	Available
	A B C	A B C	A B C
P0	0 1 0	7 5 3	3 3 2
P1	2 0 0	3 2 2
P2	3 0 2	9 0 2
P3	2 1 1	2 2 2
P4	0 0 2	4 3 3

Matritsalar holati. Need quyidagicha aniqlanadi (Max – Allocation):

	Need
	A B C
P0	7 4 3
P1	1 2 2
P2	6 0 0
P3	0 1 1
P4	4 3 1

Tizim xavfsiz holatda, chunki < P₁, P₃, P₄, P₂, P₀> xavfsizlik mezonini qanoatlantiradi.
P₁ jarayon so‘rovi (talabi) (1,0,2)
Request £ Available ekanligini tekshirib ko‘ramiz, ya’ni (1,0,2) £ (3,3,2) Þ true.

	Allocation	Need	Available
	A B C	A B C	A B C
P0	0 1 0	7 4 3	2 3 0
P1	3 0 2	0 2 0
P2	3 0 1	6 0 0
P3	2 1 1	0 1 1
P4	0 0 2	4 3 1

Xavfsizlik algoritmining bajarilishi ₁, P₃, P₄, P₀, P₂> ketma-ketlikning xavfsizlik mezonini qanoatlantirishini ko‘rsatadi.
P₄ uchun (3,3,0) talab qanoatlantirishi mumkinmi?
P₀ uchun (0,2,0) talab qanoatlantirishi mumkinmi?
wait-for grafi
Resurslarni taqsimlash grafiga qo’shimcha ravishda tuzilishi bo’yicha oddiyroq bo’lgan wait-for grafini qo’shami: uning tugunlari jarayonlarga mos qo’yiladi, yoylari esa, agar P_i jarayon P_j jarayonni kutib turgan bo’lsa, P_i tugundan P_j tugunga o’tkaziladi. Agar tizimdagi har bir resurs bir nusxadan mavjud bo’lsa, u holda shubhasiz bu grafdagi tsikl tupik holatida ekanligini bildiradi. Tizim tupikni aniqlash uchun wait-for grafida tsikl bo’lmasligini davriy ravishda tekshirib turishi kerak. Bizga ma’lumki, grafda tsiklni aniqlash algoritmi O(n²)ta amalni talab qiladi, bu yerda n– grafdagi tugunlar soni.
8-rasmda tupikli tizim uchun resurslarni taqsimlash grafiga misol va unga mos wait-for grafi keltirilgan.

8-rasm. Resurslarni taqsimlash grafi va wait-for grafi.
Resurslar ko’p nusxada bo’lgan hol uchun tupiklarni aniqlash
Umumiy holda tupiklarni aniqlash algoritmini qurish va bankir algoritmi uchun quyidagi tuzilmalardan foydalaniladi:
Mavjud resurslar haqidagi ma’lumotlarni saqlovchi m uzunlikdagi Available vektori. Agar Avaliable[j] = k bo’lsa, u holda ayni vaqtda tizimda j turidagi resursning k ta birligi mavjud.
Tizimda aniq ajratilgan resurslar matritsasi Request_____A'>Allocation ( n * m ). Agar Allocation [i, j] = k bo’lsa, u holda ayni vaqtda tizimda i jarayonga j turidagi resursning k ta nusxasi ajratilgan bo’ladi.
P_i jarayon uchun so’rovlar vektor Requesti (m uzunlikda). Agar Requesti [j] = k bo’lsa, u holada P_i jarayon R_j resursning k ta nusxasini talab qilgan bo’ladi.
Tupikni aniqlash algoritmi
Xavfsizlikni aniqlash algoritmiga o’xshash, butun soni ushunligi m ga teng bo’lgan Work vektori va uzunligi n ga teng bo’lgan mantiqiy Finish vektorini kiritib olamiz. Work vektori sinov resurslarining ajratilishini tasvirlaydi. Finish vektori tizimning ushbu holatida jarayonlarning yakunlanuvchanligini ifodalaydi.
1-qadam. Boshlash
Work = Available
Agar i = 1, …, n lar uchun Allocation [i] != 0 bo’lsa, u holda finish[i] = false bo’ladi, aks holda finish [i] = true.
2-qadam. Shunday i topamizki:
Finish [i] = false
Request [i] <= Work
Agar bunday i mavjud bo’lmasa, 4-qadamga o’tish.
3-qadam.
Work = Work + Allocation [i]
Finish [i] = true
2-qadamga o’tish.
4-qadam. Agar ba’zi i = 1 dan n gacha bo’lganda Finish[i] = false bo’lsa, u holda tizim tupik holada bo’ladi.
Bundan tashqari, agar Finish[i] = false bo’lsa, u holda P_i –jarayon tupik holatida bo’ladi.
Bu algoritmning to’g’riligini isbotlashni talabalarga mustaqil ishlash uchun qoldiramiz. Bu algoritm tizim tupik holatini aniqlash uchun O(m * n²) ta opertsiyani talab qiladi.
Tupiklarni aniqlash algoritmiga misol
Faraz qilaylik 5 ta – P₀ , …, P₄ jarayonlar va 3 ta turdagi resurslar – A resurs (7 nusxa), B resurs (2 nusxa) va C resurs (6 gusxa) berilgan bo’lsin. Vaqtning T0 lahzasida tizim quyidagi holatda bo’lsin:

	Allocation			Request
	A	B	C	A	B	C
P0	0	1	0	0	0	0
P1	2	0	0	2	0	2
P2	3	0	3	0	0	0
P3	2	1	1	1	0	0
P4	0	0	2	0	0	2

Berilgan holatda tizimdagi jarayonlar ketma-ketligi 
₀, P₂, P₃, P₁, P ₄> bo’ladi va u xavfsiz (tekshirib ko’ring!).
Aytaylik P₂ jarayon C turidagi qo’shimcha resursni talab qilsin:

	Request
	A	B	C
P0	0	0	0
P1	2	0	1
P2	0	0	1
P3	1	0	0
P4	0	0	2

Bu holatda tizimda P₁, P₂, P₃, P₄ jarayonlar tupik holatda bo’ladi (bu holatni ham tekshirib ko’ring).
Tupiklarni aniqlash algoritmining qo’llanilishi
Tizim ko'rib chiqilayotgan tupikni aniqlash algoritmidan qanchalik tez-tez va qanday holatlarda foydalanishi kerakligi, bu tupik qanchalik tez-tez yuz berishi mumkinligiga va tupikdan chiqish uchun qancha jarayonni orqaga qaytarish kerakligiga bog'liq.
Agar tupikni aniqlash algoritmi o'zboshimchalik bilan chaqirilsa, u holda resurslarni taqsimlash grafi ko'plab sikllarga ega bo'ladi va ko'plab tupik jarayonlarning qaysi biri berilgan tupikga sabab bo'lganligini aniq aytish mumkin bo'lmaydi.
Tupikdan keyin tiklash
Tizim tupik holatidan chiqish uchun shubhasiz, barcha tupik holatidagi jarayonlarni to’xtatish va ular egallab turgan resurslarni bo’shatish zarur bo’ladi. Buning eng optimal varianti tizim har bir qadamda bitta jarayonni to’xtatib, tupik bartaraf etilganmi yoki yo’qligini tekshirib borishi kerak bo’ladi.
Muhim masalalardan biri – bu jarayonlarni qaysi tartibda to’xtatish kerakligida. Turli xil yondoshuvlar mavjud:
· Jarayonlarning ustivorligi.
· Jarayon qancha vaqt bajarilgan va tugashiga yana qancha vaqt qoldi.
· Jarayon bajarilishi davomida qancha ko‘p resurslar talab qilingan.
· Uning yakunlanishi uchun yana qancha resurs talab qilinadi.
· Qancha jarayonni tugatish kerak.
· Jarayon interaktiv yoki paketli hisoblanadimi?
Minimal xarajat bilan "jabrlanuvchi" jarayonini tanlagandan so'ng (yuqoridagi mezonlardan biriga muvofiq) tizim tanlangan jarayonni (jarayonlarni) tugatadi, ularning resurslarini chiqaradi va resurslarni qayta taqsimlaydi. Tizim avvalgi xavfsiz holatga qaytadi.
Tizimning bunday harakatlarini takroriy bajarish natijasida "ochlik" mumkin, chunki bir xil jarayon qurbon sifatida ko'p marta tanlanishi mumkin.
Tupiklarni qayta ishlashga aralash yondoshuv

• 
  Uchta tayanch yondoshuvning aralashmasi
  
• 
  Oldini olish
  
• 
  Qochish (yo‘l qo‘ymaslik)
  
• 
  aniqlash, bular tizim resurslarining har biri uchun maqbul (optimal) yondashuvdan foydalanishga imkon beradi.
  
• 
  Resurslarni ierarxik tartiblangan sinflarga ajratish.
  

Har bir sinf ichidagi (tarkibidagi) tupiklarni qayta ishlash uchun eng maqbul usulni qo‘llash.
Asosiy tushunchalar:
Reserved graph – oddiy tugunlardan tashqari super-tugunlarni ham o’zi ichiga olgan yo’naltirilgan graf; bunday graflarning yoylari oddiy tugunlardan super-tugunlarga o’tkazilgan yoki super-tugunlarning qism tugunlaridan oddiy tugunlarga o’tkazilgan bo’lishi mumkin.
Jarayon-tugun – resurslarni taqsimlash grafidagi jarayonlarni tasvirlovchi tugun.
Resurs-tugun – resurslarni taqsimlash grafidagi qandaydir turdagi resurslarning har bir birligini tasvirlovchi super-tugun.
O’zaro istisno – tupikning zaruriy shartlaridan biri: vaqtning har bir momentida faqat bitta jara1n resursga kirish imkonini olishi mumkin.
Resurslarni taqsimlash grafi – tugunlar to’plami (jarayon-tutugn va resurs-tugun turidagi) va yoylar to’plami (so’rov turidagi yoy va ta’minlash turidagi yoylar)dan tashkil topgan tizimda resurslarni taqsimlash holatini tavsiflovchi graf.
“so’rov” turidagi yoy (request edge) – jarayon-tugundan resurs-tugunga yo’naltirilgan yoy.
“ta’minlash” turidagi yoy (assignment edge) – aniq resurs birligini tasvirlovchi qism tugundan jarayon-tugunga yo’naltirilgan yoy.
So’rov (request) – jarayon o’ziga zarur bo’ladigan qaysidir turdagi resursni ajratish haqidagi OT ga qo’ygan talabi.
Foydalanish (use) – jarayonning OTdan talabi bo’yicha olgan qaysidir turdagi resursga egalik qilishi va uni iste’mol qilishi.
Bo’shatish (release) – jarayon qaysidir turdagi resurs birligini operatsion tizimdan olib foydalangan va boshqa talab qilinmaydigan resurs.
Uzilishning yo’qligi – tupiklarning zaruriy shartlaridan biri: jarayon resursni faqat o’z ishni yakunlagandan keyin bo’shatishi mumkin.
Jarayon pasporti – dastlabki OTda: jarayonning har bir turdagi resurslarga maksimal talabi ro’yxati – tezkor va tashqi xotira, bajarilish vaqti, chop etish sahifasi va boshq.
Super-tugun (reserved graph tarkibidagi) – yoy chiqarish mumkin bo’lgan bir yoki bir nechta qism tugunlardan tashkil topgan tarkibli tugun.
Tupik (deadlock) – har biri alohida resurslarni egallab, boshqa bir jarayon band qilgan resursning bo’shashini kutib turgan bloklangan jarayonlarning tsiklik ketma-ketliklari to’plami.
Ushlanib qolish va kutish – tupikning zaruriy shartlaridan biri: bitta resursni band qilib turgan holda, boshqa jarayonlar ishlatayotgan resursni kutib qolish holati.
Davriy kutish – tupikning zaruriy shartlaridan biri: mavjud {P0, P1, … P0} to’plamda P0 jarayon P1 ishlatayotgan resursni kutish holatida; P1 jarayon P2 ishlatayotgan resursni kutish holatida va x.k. Pn jarayon P0 ishlatayotgan resursni kutish holatida.
Bankir algoritmi (banker’s algorithm) – operatsion tizimlarda resurslarni taqsimlashda tupiklardan qochishni ta’minlovchi E.Deykstr algoritmi.
Jarayonlarning xavfsiz ketma-ketligi – bu 
₁, … P_n> ko’rinishdagi ketma-ketlik bo’lib, bu yerda resurs talab qiluvchi har bir P_i jarayon o’ziga zarur bo’lgan resursga P_j jarayon band qilib turgan resursni bo’shatgandan keyin egalik qiladi, bu yerda j < i.
Xavfsiz holat – tizimning tupik paydo bo’lmaydigan holati.
wait-for grafi – tugunlari jarayonlarga mos keluvchi, agar P_i jarayon P_j jarayonni kutish holatida bo’lsa, yoy P_i tugundan P_j tugunga o’tkazilgan yo’naltirilgan graf.
Talab yoyi (claim edge) – resurslarni taqsimlash grafining yoyi bo’lib, bu yoy jarayon tugundan resurs-tugunga o’tkaziladi, ya’ni, ushbu jarayon berilgan resursni talab qilayotgan bo’lsa nuqtali chiziq bilan belgilanadi.
 Xulosa
Tupik – bu jarayonlar o’zaro bir-birini bloklash holati bo’lib, jarayonlarning talablarida davriylik paydo bo’ladi, ya’ni birinchi jarayon ikkinchi jarayon ishlatayotgan resrusni, ..., n-jarayon birinchi jarayonni kutadi.
Tupikdan qochishning eng oddiy va foydali modeli bu, tizimga kirayotgan har bir jarayon tizimning har bir turdagi resursiga maksimal talabni ko’rsatishi lozim bo’lar ekan (jarayon pasporti shakllantirilishi zarur). Tupikdan qochish algoritmi tizim holatini va tizim xavfli vaziyatga (tupik holatlari nuqtai nazaridan) tushib qolmasligini tahlil qilishi shart. Tizimning holati mavjud va ajratilgan resurslar miqdori va jarayonlarning har birining maksimal ehtiyojlari sifatida tavsiflanadi.