|
Resurslarni taqsimlash grafi
|
| bet | 49/222 | | Sana | 15.05.2024 | | Hajmi | 5,84 Mb. | | #236377 |
Ko‘rib chiqishga V balandliklar to‘plami va E yoylar to‘plamidan iborat resurslarni taqsimlash grafini kiritamiz. V ikkita turlardagi – balanliklar-jarayonlar va balandliklar-resurslarga bo‘linadi. Boshqacha aytganda, V tizimdagi barcha jarayonlar J = {J1, J2, … , Jn} turdagi balandliklar to‘plami va R = {R1, R2, … , Rm} turdagi balandliklar to‘plamiga bo‘linadi.
Yoylarning quyidagi ikkita turlarini kiritamiz:
“so‘rov” turdagi yoy (request edge) – Ji → Rj turdagi yo‘naltirilgan yoy.
“tayinlash” turdagi yoy (assignment edge) – Ji ← Rj turdagi yo‘naltirilgan yoy.
Yoylarning turli yo‘nalishlarining ma’nosi quyidagicha. Agar jarayon qanday resursga da’vogarlik qilsa, u holda yoy balandlik- jarayondan balandik-resursga o‘tkaziladi.
Aniq resurs birligi qandaydir jarayonga ajratilsa, u holda yoy bu belgiga tegishli bo‘ladi va balandlik-resursdan jarayonning balandligiga o‘tkaziladi. Kiritiladigan graf va uning grafining o‘ziga xos xususiyatlarini aniqlashtiramiz.
Zamonaviy atamada bu turdagi graf – zahiralangan graf (reserved graph) deyiladi. Uning balandlik-jarayoni oddiy ko‘rinishga ega bo‘ladi, Rj resursga mos keladigan balandlik-resurs esa Wj nimbalandliklardan tashkil topadi, ulardan har biri aniq bir resurs birligini belgilaydi. Zahiralangan graflar nazariyasida bunday balandliklar superbalandliklar (super-vertices) deyiladi.
Shunday qilib, so‘rov yoyi umuman balandlik-jarayondan balandlik-resursga boradi, tayinlash yoyi esa balandlik-resursnng mos nimbalandligidan balandlik-jarayonga boradi. Balandlik-jarayonga misol 2.25- rasmda keltirilgan.
2.25- rasm. Resurslarni taqsimlash grafidagi balandlik-jarayonga misol
To‘rtta nusxali superbalandlik-resursga misol 2.26-rasmda kelti- rilgan.Resursning har bir nusxasiga o‘z nimbalandligi mos keladi.
Resurslarni taqsimlash grafiga misol 2.27- rasmda keltirilgan.
2.26- rasm. To‘rtta nusxali superbalandlik-resursga misol
R1 R3
R2
R4
2.27- rasm. Resurslarni taqsimlash grafiga misol
Bu graf uchta jarayonlar va to‘rtta resurslari turlariga ega bo‘lgan tizimni aks ettiradi: 1- va 3- turlardagi resurslar bittadan nusxaga ega, 2- turdagi resurs ikkita nusxaga ega, 4- turdagi resurs uchta nusxaga ega. 1- jarayon 2- jarayon bilan band bo‘lgan 1- resursga da’vogarlik qiladi. 2- jarayon 3- jarayon bilan band bo‘lgan 3- resursga da’vogarlik qiladi. 2- resursning ikkita birliklari 1- va 2-
jarayonlarga berilgan.4- resurs taqsimlanmagan (barcha uchta birliklar bo‘sh).
|
| |
