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

"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) Requesti  Work
• 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  i  n), 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