Operacion sistemada tupik (deadlock) túsinigi Reje

Resursların bólistiriw grafi
Kórip shıǵıwǵa v biyiklikler kompleksi hám E doǵalar kompleksinen ibarat resursların bólistiriw grafigin kiritemiz. v eki túrlerdegi - biyiklikler-procesler hám biyiklikler-resurslarǵa bólinedi. Basqasha aytqanda, v sistemadaǵı barlıq procesler J = {J₁, J₂, …, J_n} túrdegi biyiklikler kompleksi hám R = {R₁, R₂, …, R_m} túrdegi biyiklikler kompleksine bólinedi.
Doǵalardıń tómendegi eki túrlerin kiritemiz:
 “soraw” túrdegi doǵa (request edge) - J_i → R_j túrdegi jóneltirilgen doǵa.
 “belgilew” túrdegi doǵa (assignment edge) - J_i ← R_j túrdegi jóneltirilgen doǵa.
Doǵalardıń túrli baǵdarlarınıń mánisi tómendegishe. Eger process qanday resursqa dawagerlik qilsa, ol halda ayqulaq biyiklik-procesten biyiklik-resursqa ótkeriledi.
Anıq resurs birligi qanday da proceske ajratılsa, ol halda doǵa bul belgige tiyisli boladı hám biyiklik-resurstan procestiń biyikligine ótkeriledi. Kiritiletuǵın graf hám onıń grafının’ ayrıqsha qásiyetlerin anıqlaymız.
Zamanagóy terminde bul túrdegi graf - rezervlengen 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. Rezervlengen graflar teoriyasında bunday biyiklikler superbiyiklikler (super-vertices) dep ataladı.
Sonday etip, soraw doǵai ulıwma biyiklik-procesten biyiklik-resursqa baradı, belgilew doǵai bolsa biyiklik-resurstın’ uyqas nimbalandligidan biyiklik-procesine baradı. Biyiklik-proceske mısal 1-súwretde keltirilgen.

1-súwret. Resursların bólistiriw grafidagi biyiklik-processga mısal

Tórt nusqalı superbiyiklik-resursqa mısal 2-súwrette keltirilgen. Resurstıń hár bir nusqasına óz nimbalandligi sáykes keledi.

2-súwret. Tórtew nusqalı superbiyiklik-resursqa mısal

Resursların bólistiriw grafina mısal 3-súwrette keltirilgen.

3- súwret. Resursların bólistiriw grafiga mısal

Bul graf úsh procesler hám tórt resursları túrlerine iye bolǵan sistemanı sáwlelendiredi: 1- hám 3- túrlerdegi resurslar birden nusqaǵa iye, 2- túrdegi resurs eki nusqaǵa iye, 4- túrdegi resurs úsh 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- proceslerge berilgen. 4- resurs bólistirilmegen (barlıq úsh birlikler bos).

Resursların bólistiriw grafı boyınsha tupiklerdi qıdırıw
Bunday grafda cikl tupiktiń bar ekenin ańlatadı.

4- súwret. Tupikli resursların bólistiriw grafına mısal

4- súwrette tupikli resursların bólistiriw grafına mısal keltirilgen. 1, 2 hám 3- procesler arasındaǵı ciklli 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- proceske, ekinshi birligi 2- proceske berilgen resursqa dawagerlik etedi.

Lekin mudamı da resursların bólistiriw grafında cikldin’ bolıwı tupiktin’ bar ekenin bildirmeydi.
5 – súwrette ciklli, lekin tupiksiz resursların bólistiriw grafına mısal keltirilgen. Bul halda (5 - súwret) tórt procesler hám eki resurslar túrleri bar boladı. Ciklda 1- hám 3- biyiklikler-procesler qatnasadı. Lekin hár bir resursta bar ekenligi sebepli tupiktiń aldın alıwǵa erisiledi. 1- resurstı kútetuǵın 1- process onı bul resurstıń birligine iye bolǵan hám kútiw cikline kirmeytuǵın 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) bosatqanınan keyin alıwı múmkin.

5 - súwret. Ciklli, lekin tupiksiz resursların bólistiriw grafına mısal

Sonday etip, tómendegi oy-pikirdi aytıw múmkin. Eger resursların bólistiriw grafi cikllerge iye bolmasa, ol jaǵdayda sistemada tupikler joq. Eger resursların bólistiriw grafi cikllerge iye bolsa, ol jaǵdayda tómendegi eki jaǵdaylar bolıwı múmkin:

1. Eger hár bir túrdegi resurslar tek birden bolsa, ol jaǵdayda tupik óz ornına iye boladı;
2. Eger resurslar bir neshe nusqalarda bolsa, ol halda tupik bolıwı múmkin.
Tupiklerge qayta islew usılları
Teoriyalıq tárepten tómendegi tupiklerge qayta islew usılları bolıwı múmkin:
 Sistema hesh qashan tupik jaǵdayına kirmewine isenim bolıń;
 Sistema tupik jaǵdayına kiriwi múmkinligin alıw, lekin tupikten keyin qayta tikleniw múmkinshiligin ańlıw.
Ámelde kóplegen OSlarda (sonday-aq, UNIXda) tupikler menen gúresiwdin’ úshinshi “usılı” da isletiledi. Tupikler mashqalası biykar etiledi, lekin OS avtorları hesh bir tiykarlarsız sistemada tupikler múmkin emesligine dawa qıladı.
Tupiklerdiń aldın alıw
Tupiklerdiń aldın alıw qanday usıllarınıń múmkinligin analiz etemiz. Tiykarǵı ideya procesler tárepinen resurslarǵa sorawlar usılların sheklew esaplanadı. Resurslarǵa iye bolıwdı óz-ara biykar qılıw (tupiktiń birinshi shárti) múmkinshiligin sheklew ushın ol barlıq resurslar ushın da talap etilmesligin atap ótiw zárúr.
Bólinetuǵın resurslar (mısalı, konstantlar, kodlar, faylları dızbekleri) ushın ol talap etilmeydi. Saqlaw hám kútiw múmkinshiligin sheklew (tupiktiń ekinshi shárti) ushın qanday da resurstı soraytuǵın process basqa hesh qanday resurslarǵa iye bolmaslıǵın talap qılıw múmkin.
Alternativ variant barlıq procesler olardıń haqıyqıy orınlanıwın baslanıwına shekem barlıq zárúr resurslarǵa iye bolıw talabı esaplanadı. Hár eki talaplardıń orınlanıwı resurslardan paydalanıwdıń jetispewshiligi hám “ash qalıw”ǵa (starvation) alıp keledi.
Process resurstı hár bir kútiwinde resursların qayta bólistiriw algoritmin esaplaydı. Eger process qanday da A resursqa iye bolsa hám oǵan tezlik penen ajratılıwı múmkin bolmaǵan basqa B resurstı sorasa, ol hjaǵdayda process kútiwi kerek. Bunda process iyelegen A resurs tezlik penen bosatılıwı kerek. A resurs process kútip atırǵan resurslar dizimine kiritiledi.
Process tek eger oǵan bir waqıtta ol iye bolǵan barlıq eski resurslar hám ol kútip atırǵan 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ártiplestiriwdi kiritiw hám process resursların tek olardıń nomerlerinin’ artıp barıwı tártibinde soranıwı talabın kiritiw 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ń ayrıqshalıǵı barlıq bolıwı múmkin nomerlewlerge hesh qanday baylanıslı emes hám qálegen cifrlı resursqa múta’jlik zárúrshiligi boyınsha payda bolıwı múmkin.