Язык программирования Java


"Tupik"larni bartaraf qilish algoritmi



Download 351,85 Kb.
bet7/7
Sana25.06.2022
Hajmi351,85 Kb.
#703070
1   2   3   4   5   6   7
Bog'liq
OT-07 deadlock

"Tupik"larni bartaraf qilish algoritmi


(C) I.M.Boynazarov

Mos ravishda Work va Finish lar m va n uzunlik vektorlari bo‘lsin.

  • 1. Boshlash:
    • (a) Work = Available
    • (b) For i = 1,2, …, n, if Allocationi  0, then Finish[i] = false; otherwise, Finish[i] = true.
  • 2. Shunday i indeksni topingki, quyidagilar o‘rinli bo‘lsin:
    • (a) Finish[i] == false
    • (b) RequestiWork
    • Agar bunday i bo‘lmasa, u holda 4-qadamga o‘ting.

Bartaraf qilish algoritmi (davomi)


(C) I.M.Boynazarov

  • 3. Work = Work + Allocationi Finish[i] = true 2-qadamga o‘ting.
  • 4. Agar ba’zi i lar uchun Finish[i] == false bo‘lsa (1  in), u holda tizim "tupik" holatida bo‘ladi.
  • Bundan tashqari, agar Finish[i] == false bo‘lsa, u holda Pi jarayon "tupik" holatda bo‘ladi.
  • Bu algoritm tizimning "tupik" holatda ekanligini aniqlash uchun O(m x n2) operatsiyani talab qiladi.

Bartaraf etish algoritmi: misol


(C) I.M.Boynazarov
  • P0 - P4 - 5 ta jarayon va uchta turdagi resurslar berilgan bo‘lsin: A (7 nusxa), B (2 nusxa) va C (6 nusxa).
  • Vaqtning T0 holatida:
  • Taqsimlash__So‘rov

  • <P0, P2, P3, P1, P4> ketma-ketlik yakunlanadi, barcha i lar uchun Finish[i] = true.

Bartaraf etish algoritmi: davomi


(C) I.M.Boynazarov
  • P2 jarayon qo‘shimcha C turidagi resursni talab qiladi.
  • Tizim holati ?
    • P0 jarayon egallaydigan resurs talab qilinishi mumkin, lekin boshqa jarayonlarni qanoatlantiradigan yetarli resurslar mavjud emas.
  • P1, P2, P3 va P4 jarayonlar joylashgan joyda "tupik" mavjud.

"Tupik"larni bartaraf qilish algoritmining qo‘llanilishi



Ushbu algoritmdan qachon va qanchalik tez-tez foydalanish quyidagilarga bog’liq:

  • "Tupik" holati tez-tez uchrashi ehtimoli mavjudmi?
  • Nechta jarayonni orqaga qaytarish zarur bo‘ladi?
    • Kesishmaydigan har bir tsikllar uchun bitta jarayon
    • Agar "tupik"ni aniqlash algoritmi o'zboshimchalik bilan chaqirilsa, u holda resurslarni taqsimlash grafi ko'p sikllarga ega bo'ladi va "tupik" hosil qilgan jarayonlarning qaysi biri bu "tupik"ka "sabab" bo'lganligini tasdiqlash mumkin bo'lmaydi.

"Tupik"dan keyin tiklash: jarayonni yakunlash



  • Barcha "tupik" jarayonlarni to‘xtatish.
  • "Tupik" bartaraf qilinmaguncha vaqtning har bir momentida faqat bitta jarayonni to‘xtating.
    • Jarayonlarni qanday tartibda to‘xtatish zarur?
    • 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?

"Tupik"dan keyin tiklash – resurslarni qayta taqsimlash



  • “Qurbon”ni tanlash – xarajatlarni minimallashtirish.
  • Orqaga qaytarish – xavfsiz holatga qaytish; jarayonni ushbu holatga qaytarish.
  • “Och qolish” – bitta va aynan shu jarayon hamma vaqt “qurbon” sifatida tanlanishi mumkin, chunki qayta tiklangan jarayonlar soni qiymatni aniqlaydigan omil hisoblanadi.

"Tupik"larni 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) "tupik"larni qayta ishlash uchun eng maqbul usulni qo‘llash.

Q & A

  • Savollar va muhokamalar

Download 351,85 Kb.

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




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