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


Bankir algoritmining qo‘llanilishiga misol



Download 169,23 Kb.
bet8/8
Sana12.06.2022
Hajmi169,23 Kb.
#657763
1   2   3   4   5   6   7   8
Bog'liq
13-14

Bankir algoritmining qo‘llanilishiga misol
ta jarayonlar - Pdan P4 gacha;
resurslarning ta turi - A (10 nusxa), B (5 nusxa) va C (7 nusxa).
Tvaqtdagi (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 < P1, P3, P4, P2, P0> xavfsizlik mezonini qanoatlantiradi.
P1 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 1, P3, P4, P0, P2> ketma-ketlikning xavfsizlik mezonini qanoatlantirishini ko‘rsatadi.
Puchun (3,3,0) talab qanoatlantirishi mumkinmi?
Puchun (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 Pi jarayon Pj jarayonni kutib turgan bo’lsa, Pi tugundan Pj 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(n2)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-rasmResurslarni 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 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.
Pi jarayon uchun so’rovlar vektor Requesti (m uzunlikda). Agar Requesti [j] = k bo’lsa, u holada Pi jarayon Rj 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 topamizki:
Finish [i] = false
Request [i] <= Work
Agar bunday 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 gacha bo’lganda Finish[i] = false bo’lsa, u holda tizim tupik holada bo’ladi.
Bundan tashqariagar Finish[i] = false bo’lsau holda Pi –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 * n2) ta opertsiyani talab qiladi.
Tupiklarni aniqlash algoritmiga misol
Faraz qilaylik 5 ta – P0 , …, P4 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 
0, P2, P3, P1, P 4> bo’ladi va u xavfsiz (tekshirib ko’ring!).
Aytaylik P2 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 P1, P2, P3, P4 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)

  • aniqlashbular 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; Pjarayon 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 
1, … Pnko’rinishdagi ketma-ketlik bo’lib, bu yerda resurs talab qiluvchi har bir Pi jarayon o’ziga zarur bo’lgan resursga Pj 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 Pi jarayon Pj jarayonni kutish holatida bo’lsa, yoy Pi tugundan Pj 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.
Download 169,23 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish