5-Ma'ruza: Kirish

Resurslarni taqsimlash grafi. Ko‘rib chiqishga V balandliklar to‘plami va E yoylar to‘plamidan iborat resurslarni taqsimlash grafini kiritamiz. V ikkita turlardagi – balandliklar-jarayonlar va balandliklar-resurslarga bo‘linadi. Boshqacha aytganda, V tizimdagi barcha jarayonlar J = {J₁, J₂, … , J_n} turdagi balandliklar to‘plami va R = {R₁, R₂, … , R_m} turdagi balandliklar to‘plamiga bo‘linadi.
Yoylarning quyidagi ikkita turlarini kiritamiz:

• 
  “so‘rov” turdagi yoy (request edge) – J_i → R_j turdagi yo‘naltirilgan yoy.
  
• 
  “tayinlash” turdagi yoy (assignment edge) – J_i ← R_j turdagi yo‘naltirilgan yoy.
  

Yoylarning turli yo‘nalishlarining ma’nosi quyidagicha. Agar jarayon qanday resursga da’vogarlik qilsa, u holda yoy balandlikjarayondan 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, R_j resursga mos keladigan balandlik-resurs esa W_j 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.

7.2- rasm. Resurslarni taqsimlash grafidagi balandlik-jarayonga misol
To‘rtta nusxali superbalandlik-resursga misol 7.3-rasmda keltirilgan. Resursning har bir nusxasiga o‘z nimbalandligi mos keladi. Resurslarni taqsimlash grafiga misol 7.4- rasmda keltirilgan.

7.3- rasm. To‘rtta nusxali superbalandlik-resursga misol

7.4- 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).