|
"Tupik"larni bartaraf qilish algoritmi
| | bet | 7/7 | | Sana | 24.05.2024 | | Hajmi | 351,43 Kb. | | #252150 |
Bog'liq 7-m Operatsion tizimda tupik (deadlock) tushunchasi
(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 ?
- 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?
- “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
|
| |
