Toshkent axborot texnologiyalari universiteti u. R. Xamdamov, dj. B. Sultanov, S. S. Parsiyev, U. M. Abdullayev operatsion tizimlar

Tizim modeli
Bunday vaziyatlarni tavsiflash va tadqiq qilish uchun tizimning rasman modelini umumiy ko‘rinishda kiritamiz. Model yordamida jarayonlarning resurslari so‘rovlar haqida, jarayonlarning resurslarga haqiqatda egaligi haqida va resurslarning bo‘shashi haqidagi ma’lumotlarni beramiz. Tizimda m turlardagi resurslar (masalan, protsessor, xotira, kiritish/chiqarish qurilmalari) bo‘lsin. Tizimda resurslar turlarini R₁, R₂, … R_m bilan belgilaymiz. Har bir R_i resurs turi W_i nusxalarga ega bo‘lsin. Har bir jarayon quyidagi usullardan biri orqali resursdan foydalanishi mumkin:

• 
  so‘rov (request);  foydalanish (use);
  
• 
  bo‘shatish (release).
  

Berklikagarquyidagito‘rttashartlarbirvaqtdabajarilsa, vujudgakelishimumkin:

1. 
   O‘zaro inkor qilish: har bir vaqt momentida faqat bitta jarayon resursga ulanishni olishi mumkin;
   

2. 
   Saqlash va kutish: bitta resursni saqlayotgan jarayon boshqa jarayonlar ega bo‘lgan boshqa resurslarni olishni kutadi;
   
3. 
   Uzilishlarning bo‘lmasligi: jarayon o‘zining ishlashini tugatganidan keyingina resursni bo‘shatishi mumkin.
   
4. 
   Siklli kutish: J₀ jarayon J₁ jarayon ega bo‘lgan resursni kutadigan, J₁ jarayon J₂ jarayon ega bo‘lgan resursni kutadigan...... J_n jarayon J₁ jarayon ega bo‘lgan resursni kutadigan {J₀, J₁, … J_n} to‘plam mavjud.
   

Resurslarni taqsimlash grafi
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 = {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.

2.25- rasm. Resurslarni taqsimlash grafidagi balandlik-jarayonga misol
To‘rtta nusxali superbalandlik-resursga misol 2.26-rasmda keltirilgan.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

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