5-Ma'ruza: Kirish

4. Berkliklar muammosi.
Berklik (deadlock) bu bloklangan jarayonlar to‘plami bo‘lib, ulardan har biri qandaydir resursga ega va bu to‘plamdan qandaydir boshqa jarayon ega bo‘lgan resursni kutadi. Berklikka oddiy misolni semaforalar yordamida modellashtirish oson.
Tizimda ikkita J1 va J2 jarayonlar murojaat qiladigan ikkita tashqi A va B qurilmalar bo‘lsin. Semafor sinxronlashtirish maqsadida tashqi qurilmalarning har biri bilan bog‘langan, ularni ham A va B bilan belgilaymiz. Semaforlar oldindan ochiq. Jarayonlardan har biriga har ikkala qurilmalar zarur bo‘lsin, lekin ular qurilmalarga qarama-qarshi tartibda murojaat qiladi:
J1: kutish (A); kutish (B)
J2: kutish (B); kutish (A).
Bu holda berklik o‘z o‘rniga ega bo‘ladi. J1 jarayon A semaforni yopish va birinchi qurilmani bloklash bilan ikkinchi qurilma bilan bog‘langan B semaforni qachon ochilishini hech qachon mo‘ljallay olmaydi, chunki uni J2 jarayon yorishga ulgurgan. Shunga o‘xshash, J2 jarayon A semaforning ochilishini mo‘ljallay olmaydi.
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).
  

Berklik agar quyidagi to‘rtta shartlar bir vaqtda bajarilsa, vujudga kelishi mumkin:

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.