Tuyıqlıqlar mashqalası

Resursların bólistiriw grafi
Kórip shıǵıwǵa v biyiklikler kompleksi hám E ayqulaqlar kompleksinen ibarat resursların bólistiriw grafini kiritemiz. v eki túrler degi - balanliklar-processler hám biyiklikler-resurslarǵa bólinedi. Basqasha aytqanda, v sistema daǵı barlıq processler J = {J₁, J₂, …, J_n} túrdegi biyiklikler kompleksi hám R = {R₁, R₂, …, R_m} túrdegi biyiklikler kompleksine bólinedi.
Ayqulaqlardıń tómendegi eki túrlerin kiritemiz:
 “soraw” túrdegi ayqulaq (request edge) - J_i → R_j túrdegi jóneltirilgen ayqulaq.
 “belgilew” túrdegi ayqulaq (assignment edge) - J_i ← R_j túrdegi jóneltirilgen ayqulaq.
Ayqulaqlardıń túrli baǵdarlarınıń mánisi tómendegishe. Eger process qanday resursqa dawagerlik qilsa, ol halda ayqulaq biyiklik-processdan bálentik-resursqa ótkeriledi.
Anıq resurs birligi qanday da processga ajratilsa, ol halda ayqulaq bul belgine tiyisli boladı hám biyiklik-resurstan processtiń bálentligine ótkeriledi. Kirgizetuǵın graf hám onıń grafining ayriqsha qásiyetlerin anıqlawtıramız.
Zamanagóy terminde bul túrdegi graf - rezervlangan graf (reserved graph) dep ataladı. Onıń biyiklik-procesi ápiwayı kóriniske iye boladı, R_j resursqa sáykes keletuǵın biyiklik-resurs bolsa Wj nimbalandliklardan dúziledi, olardan hár biri anıq bir resurs birligin belgileydi. Rezervlangan graflar teoriyasında bunday biyiklikler superbalandliklar (super-vertices) dep ataladı.
Sonday etip, soraw yoyi ulıwma biyiklik-processdan biyiklik-resursqa baradı, belgilew yoyi bolsa biyiklik-resursnng uyqas nimbalandligidan biyiklik-procesine baradı. Biyiklik-processga mısal 1-su’wretde keltirilgen.

1-súwret. Resursların bólistiriw grafidagi biyiklik-processga mısal
Tórtew nusqalı superbalandlik-resursqa mısal 2-su’wretde kelti-rilgan. Resurstıń hár bir nusqasına óz nimbalandligi sáykes keledi.
Resursların bólistiriw grafiga mısal 3-su’wretde keltirilgen.

2-súwret. Tórtew nusqalı superbalandlik-resursqa missal

3- súwret. Resursların bólistiriw grafiga mısal
Bul graf ush processler hám tórtew resursları túrlerine iye bolǵan sistemanı sáwlelendiredi: 1- hám 3- túrler degi resurslar birden nusqaǵa iye, 2- túrdegi resurs eki nusqaǵa iye, 4- túrdegi resurs ush nusqaǵa iye. 1- process 2- process menen bánt bolǵan 1- resursqa dawagerlik etedi. 2- process 3- process menen bánt bolǵan 3- resursqa dawagerlik etedi. 2- resurstıń eki birlikleri 1- hám 2- processlerge berilgen. 4- resurs bólistirilmegen (barlıq ush birlikler bos ).
Resursların bólistiriw grafi boyınsha tuyıqlıqlardı qıdırıw
Ekenin aytıw kerek, bunday grafdasikl tuyıqlıqtıń bar ekenin ańlatadı.

4- súwret. Tuyıqlikli resursların bólistiriw grafiga mısal
4- su’wretde tuyıqlikli resursların bólistiriw grafiga mısal keltirilgen. 1, 2 hám 3- processler arasındaǵı siklli kútiw jaǵdayı bar. 1- process, 2- process iye bolǵan resursqa dawagerlik etedi. 2- process, 3- process iye bolǵan resursqa dawagerlik etedi. 3- process bir birligi 1- processga, ekinshi birligi 2- processga berilgen resursqa dawagerlik etedi.
Lekin mudamı da resursların bólistiriw grafida siklning bolıwı tuyıqlıqtı bar ekenin bildirmeydi.
5 – su’wretde siklli, lekin tuyıqliksiz resursların bólistiriw grafiga mısal keltirilgen. Bul halda (5 - súwret) tórtew processler hám eki resurslar túrleri ámeldegi boladı. Siklda 1- hám 3- biyiklikler-processler qatnasadı. Lekin hár bir resursda ekinen birlikler bar ekenligi sebepli tuyıqlıqtıń aldın alıwǵa eriwiladi. 1- resurstı kutadigan 1- process onı bul resurstıń bir birligine iye bolǵan hám kútiw sikliga kirmaydigan 2- process (1- process emes) tawsılǵannan keyin alıwı múmkin. Soǵan uqsas, 2- resursqa dawagerlik etetuǵın 3- process onı 4- process (1- process emes) bosatganidan keyin alıwı múmkin.

5 - súwret. Siklli, lekin tuyıqliksiz resursların bólistiriw grafiga mısal
Sonday etip, tómendegi oy-pikirdi búydew múmkin. Eger resursların bólistiriw grafi cikllerge iye bolmasa, ol halda sistemada tuyıqlıqlar joq. Eger resursların bólistiriw grafi cikllerge iye bolsa, ol halda tómendegi eki hallar bolıwı múmkin:
1. Eger hár bir túrdegi resurslar tek birden bolsa, ol halda tuyıqlıq óz ornına iye boladı ;
2. Eger resurslar bir neshe nusqalarda bolsa, ol halda tuyıqlıq bolıwı múmkin.
Tuyıqlıqlarǵa qayta islew usılları
Teoriyalıq tárepten tómendegi tuyıqlıqlarǵa qayta islew usılları bolıwı múmkin:
 Sistema hesh qashan tuyıqlıq jaǵdayına kirmewine isenim bolıń ;
 Sistema tuyıqlıq jaǵdayına kiriwi múmkinligin alıw, lekin tuyıqlıqtan keyin qayta tikleniw múmkinshiligin ańlıw.
Ókiniw menen aytamız, ámelde kóplegen OTlarda (sonday-aq, UNIXda) tuyıqlıqlar menen gúresiwdin’ úshinshi “usılı” da isletiledi. Tuyıqlıqlar mashqalası biykar etiledi, lekin OT avtorları hesh bir tiykarlarsız sistemada tuyıqlıqlar múmkin emesligine dawa qılıwadı.
Tuyıqlıqlardıń aldın alıw
Tuyıqlıqlardıń aldın alıw qanday usıllarınıń múmkinligin analiz etemiz. Tiykarǵı ideya processler tárepinen resurslarǵa sorawlar usılların sheklew esaplanadı. Resurslarǵa ıyelewdi óz-ara biykar qılıw (tuyıqlıqtıń birinshi shárti) múmkinshiligin sheklew ushın ol barlıq resurslar ushın da talap etińmesligin atap ótiw zárúr.
Bólinetuǵın resurslar (mısalı, konstantlar, kodlar, faylları dızbekleri) ushın ol talap etińmeydi. Saqlaw hám kútiw múmkinshiligin sheklew (tuyıqlıqtıń ekinshi shárti) ushın qanday da resurstı so'raydign process basqa hesh qanday resurslarǵa iye bolmaslıǵın talap qılıw múmkin.
Alternativ variant barlıq processler olardıń haqıyqıy atqarılıwın baslanıwıǵa shekem barlıq zárúr resurslarǵa ıyelewi talabı esaplanadı. Ókiniw menen aytamız, hár eki talaplardıń atqarılıwı resurslardan paydalanıwdıń jetiwmasligi hám “ash qalıw”ga (starvation) alıp keledi.
Process resurstı hár bir kútiwinde resursların qayta bólistiriw algoritmı maqulroq esaplanadı. Eger process qanday da A resursqa iye bolsa hám oǵan tezlik penen ajratılıwı múmkin bolmaǵan basqa B resurstı so'rasa, ol halda process kútiwi kerek. Bunda process iyelegen A resurs tezlik penen bosatilishi kerek. A resurs process kutayotgan resurslar dizimine kirtiladi.
Process tek eger oǵan bir waqıtta ol iye bolǵan barlıq eski resurslar hám ol kutayotgan jańa resurslar ajratılıwı múmkin bolsa, qayta tikleniwi múmkin.
Ciklli kútiw jaǵdayınıń aldın alıw ushın eń ápiwayı sheshim barlıq resurslar túrleri nomerleri boyınsha tártiplashtirishni kirgiziw hám process resursların tek olardıń nomerlerin artıp barıwı tártibinde soranıwı talabın kirgiziw esaplanadı.
Ámelde bunday sheshimdi qollanıwı hám qolay bolıwı múmkinshiligı kem, sebebi tutınıw etiletuǵın hám talap etiletuǵın resurslar túrleriniń ayriqshalıǵı barlıq bolıwı múmkin nomerlashlarga hesh qanday baylanıslı emes hám qálegen cifrlı resursqa mútajlik zárúrshiligi boyınsha payda bolıwı múmkin.