Kiritilayotgan graf va uning tugunlarining asosiy xususiyatlariga aniqlik kiritib olamiz. Zamonaviy atamashunoslikda bunday ko’rinishda tavsiflanadigan graflar reserved graph deb ataladi. Uning jarayon-tuguni oddiy ko’rinishga ega, resurs-tuguni esa, ya’ni Rj resursga mos keluvchi tugun har biri resursning aniq bir birligini anglatuvchi Wj qism tugunlardan tashkil topgan bo’ladi. - Kiritilayotgan graf va uning tugunlarining asosiy xususiyatlariga aniqlik kiritib olamiz. Zamonaviy atamashunoslikda bunday ko’rinishda tavsiflanadigan graflar reserved graph deb ataladi. Uning jarayon-tuguni oddiy ko’rinishga ega, resurs-tuguni esa, ya’ni Rj resursga mos keluvchi tugun har biri resursning aniq bir birligini anglatuvchi Wj qism tugunlardan tashkil topgan bo’ladi.
- Reserved graphs nazariyasida bunday tugunlar odatda supertugun (super-vertices) deb ataladi. Xuddi shunday, so’rov yoyi jarayon-tugundan resurs-tugunga o’tkazilgan yoy, ta’minlash yoyi esa resurs-tugunning qism-resursidan jarayon-tugunga o’tkaziladi.
- Resurslarni taqsimlash grafining jarayon-tuguniga misol
- To’rtta nusxasi bo’lgan resurs-tugunga misol
Resurslarni taqsimlash grafini qurish algoritmi - Jarayonnning talab yoyi (claim edge) - Pi Rj – Pj jarayonning Rj resursga bo‘lgan talabini anglatadi; rasmda punktir chiziq bilan tasvirlangan.
- Jarayon resursni talab qilganda talab yoyi so‘rovlar yoyiga (request edge) akslanadi.
- Resurs jarayonlardan bo‘shaganda topshiriq (bog’lash) yoyi (assignment edge) teskarisiga talab yoyiga aylanadi.
- Resurslarga talablar tizimga ma’lum bo‘lishi shart.
Xavfsiz holatlar - Jarayon mumkin bo‘lgan resursni talab qilganda, tizim tezkorlik bilan ushbu ajartiladigan resursni xavfsiz holatda ekanligini aniqlashi shart.
- Tizim xavfsiz xolatda bo‘ladi, agar barcha jarayonlardan tuzilgan xavfsiz ketma-ketlik mavjud bo‘lsa.
- <P1, P2, …, Pn> ketma-ketlik har bir Pi resurs uchun xavfsiz bo‘ladi, agar u talab qiladigan mumkin bo‘lgan resurs + Pj jarayon band qilib turgan resurs manbasi xavfsiz bo‘lsa (bu yerda, j) .
- Agar resurslar Pi jarayonning talabini qanoatlantira olmasa, u holda Pi jarayon Pj jarayon tugallanmaguncha kutib turishi mumkin.
- Pj jarayon tugallangandan keyin, Pi talab qilgan resursini olishi, bajarilishi, band qilib turgan resurslarini qaytarishi va tugallanishi mumkin.
- Pi ishi yakunlangandan keyin Pi+1 jarayon talab qilgan resurslarni olishi mumkin va h.k.
Do'stlaringiz bilan baham: |