14-lekciya Operacion sistemada tupik (deadlock) túsinigi

14-lekciya
Operacion sistemada tupik (deadlock) túsinigi
Reje:

1. 
   Tupik máseleleri.
   
2. 
   Resursların bólistiriw grafi.
   
3. 
   Tupiklerdi qayta islew usılları.
   
4. 
   Tupiklerdiń aldın alıw.
   

Тupik (Deadlock) - bul OSda júzege keletuǵın jaǵday bolıp, hár qanday process kútiw jaǵdayına ótedi, sebebi basqa kútiw procesi talap etiletuǵın resurstı saqlaydı. Óz-ara tupiklew kóp qayta islewde keń tarqalǵan mashqala bolıp, bir neshe processler programmalıq támiynat blokirovkası yamasa programmalıq támiynat sıpatında belgili bolǵan óz-ara baylanıslı resurslarınıń arnawlı bir túrin almasǵanda.
Tupik máseleleri:

• 
  Haqıyqıy turmıstıń úlgisi tek bir baǵdarda ketetuǵın háreket bolıp tabıladı.
  
• 
  Bul jerde resurs kópir esaplanadı.
  
• 
  Sonday etip, tupik júzege kelip, rezerv nusqasın bir transport quralı ámelge asırǵan táǵdirde, onı ańsatǵana sheshiw múmkin (aldınan resurslar hám keyin basıp qaytıw).
  
• 
  Eger tupikli jaǵday júzege kelse, bir neshe avtomobildi rezervlewińiz kerek bolıwı múmkin.
  

13.1-súwret. Tupik máseleleri
Tupikti anıqlaw
Resurs rejelestiriwshisi blokirovkanıń payda bolıwın anıqlay aladı. Resurs rejelestiriwshisi OSda túrli processlerge ajıratılǵan barlıq resursların baqlawda járdem beredi. Sonday etip, blokirovka anıqlanǵanda, onı tómendegi usıllar menen sheshiw múmkin:

1. 
   Tupikli jaǵdaydıń aldın alıw - Tupik júzege keliwinen aldın onıń aldın alıw zárúrli bolıp tabıladı. Sistema tupik jaǵdaylarǵa alıp kelmewine isenim payda etiw ushın onı ámelge asırıwdan aldın hár bir operatsiyanı tekseredi.
   
2. 
   Hesh qanday xáreketler joq - Tólew joq - resurs tek onı uslap turıw procesi óz qálewi menen bul process óz wazıypasın orınlaǵannan keyin shıǵarıwı múmkin. Eger ayrım resurslardı uslap turatuǵın process tezlik penen oǵan ajratılmaytuǵın basqa resurstı talap qılsa, bul jaǵdayda barlıq resurslar azat etiledi. Ajıratılǵan resurslar kútip atırǵan process ushın resurslar dizimin talap etedi. Process aldınǵı resurstı hám ózi talap qılıp atırǵan jańasın tiklay alǵanda ǵana qayta baslanadı. Eger process bar bolǵanda basqa resurstı talap qilsa, ol soraw procesine ótkerildi. Eger ol basqa resurstı kútip atırǵan basqa process tárepinen ustap turılsa, biz onı azat etemiz hám soraw procesin ótkeremiz.
   
3. 
   Óz-ara esaptan tısqarı - bul Mutex tiń tolıq forması. Bul ulıwma resursqa kiriwdi basqarıw ushın isletiletuǵın ekilik semafornıń arnawlı túri. Ol keńeytirilgen ustuvor inversiya mashqalalarınan qashıw ushın ustuvor miyraslar mexanizmin óz ishine aladı. Bul bolsa, eń qısqa waqıt ishinde giltlengen jaǵdayda qalıw ushın joqarı ustuvor wazıypalardı orınlawǵa múmkinshilik beredi. Birgelikte isletiletuǵın resurslar, mısalı, tek oqıw faylları hesh qashan óz-ara giltlewge alıp kelmeydi, lekin printerler hám lenta drayverleri sıyaqlı resurslar bir process arqalı monopolistik kiriwge mútáj.
   
4. 
   Uslap turıń hám kútiń - bunday jaǵdayda, processler bir yamasa bir neshe resursların uspap turıwdan toqtatılıwı kerek, bir yamasa bir neshesin kútiw kerek.
   

Resurslardi’ bo’listiriw grafi.
V tepaliklar kompleksi hám E yoylar kompleksinen shólkemlesken resursların bólistiriw grafigini kórip shıǵamız. V tepaliklar eki túrge bólinedi: process tepasi hám derek tepasi. Basqasha etip aytqanda, V sistemadaǵı barlıq processler kompleksiniń P = {P1, P2, …, Pn} tepaliklariga hám R = {R1, R2, …, Rm} tip tepaliklarga bólinedi.
Eki túrdegi yoylarni tanıstıramız

• 
  Pi -> Rj tipindegi shetke jóneltirilgen yoyni soran’
  
• 
  Ri -> Pj tipidagi belgige jóneltirilgen yoy.
  

Yoylarnıń túrli baǵdarlarınıń mánisi tómendegishe. Eger process qandayda bir resursqa dawa qi’lsa, ol halda yoy túyininen resurs túyinine tartıladı. Eger málim bir resurs birligi qashannan berli belgili bir processke ajıratılǵan bolsa, ol jaǵdayda yoy, tiyisliliktiń belgisi si’pati’nda, resurs tepasidan process tepasiga tartıladı.
Zamanagóy terminologiyada bul túrdegi grafik rezerv etilgen grafik dep ataladı. Onıń túyin procesi ádetiy formaǵa iye hám Rj resursına sáykes keletuǵın túyin-resurs Wj kishi túyinlerinen ibarat bolıp, olardıń hár biri resurstıń málim birligin ańlatadı. Rezerv etilgen grafikalar teoriyasında bunday tepalikler geyde super vertikalar dep te ataladı. Sonday etip, soraw yoyi process túyininen ulıwma resurs túyinine, belgilew yoyi bolsa resurs túyininiń tiyisli tómengi resursınan process túyinine júrgizedi.

13. 2-súwret. Resurslardı bólistiriw grafikasındaǵı process túyinine mısal.
Tórt mısalı bolǵan (super) resurs tepasining úlgisi 13.3-súwret: Resurstıń hár bir nusqası óziniń tómengi qatlamına iye.

13.3-su’wret. Tórt nusqali resurs tepasiga mısal.
Resursların bólistiriw grafigining úlgisi 13.4-suwretde keltirilgen.

13.4-súwret. Resursların bólistiriw grafigine mısal.
Bul grafikda u’sh process hám tórt túrdegi resurslar bar sistema su’wretlengen: 1 hám 3 túrdegi resurslar hár biri bir nusqaǵa iye, 2 túrdegi resurslar eki mısalǵa, 4 túrdegi resurslar u'sh mısalǵa iye. 1-process 2-process iyelegen 1-resursqa dawa qılıp atır. 2-process 3-process iyelegen 3-resursqa dawa qılıp atır. Eki birlik resurs 2 1 hám 2-processlerge berilgen. Resurs 4 bólistirilmegen (úshew birlik de azat).
Resursların bólistiriw grafiginde tupiklerdi tabıw
Shubhasız, bunday grafiktegi cikl tupik noqattıń bar ekenligin ańlatıwı múmkin. 13.5-su’wrette tupik grafikanıń úlgisi. 1, 2 hám 3-processler ortasında cikllı kútiw jaǵdayı bar, 1-process 2-processke tiyisli resurs dep dawa qılıp atır. 2-processke tiyisli bolǵan resursqa 2-dawa. Resursqa 3 dawa, onıń birligi 1-processke, ekinshisi - 2-processke berilgen.

13.5-súwret. Tamamlanbag’an resursların bólistiriw grafigine mısal.
Biraq, resursların bólistiriw grafigida cikldıń bar ekenligi mudamı da tupik degeni emes. 13.6-su’wrette ciklı bolǵan, biraq tupik halda resursların bólistiriw grafigi úlgisi kórsetilgen.

13.6-su’wret. Resursların bólistiriw grafigine ciklı, biraq tiqilib qalmaǵan halda mısal keltirilgen.
Bunday halda (13.6-súwret) tórt process hám eki qıylı resurslar bar. Cikl 1 hám 3 tepaliklar-processlerdi óz ishine aladı. Biraq, hár bir resursda eki birlik bar ekenligi sebepli, tupikten quti’li’w múmkin: 1-process, 1-resurstı kútiw, onı 2-process (hám process emes) qabıllawı múmkin boladı bul resurstıń bir birligine iye hám kútiw dáwirine kiritilmegen. Tap sol tárzde, 2-resursqa dawa etken 3-process, onı 4-process (1 emes) azat etilgeninen keyin alıw múmkinshiligine iye boladı.
Sonday etip, tómendegi sózlerdi qáliplestiriw múmkin:

• 
  Eger resursların bólistiriw grafigi cikllerdi óz ishine almasa, ol halda sistemada tupik noqatlar joq;
  
• 
  Eger resursların bólistiriw grafasında cikl bolsa, ol jaǵdayda eki jaǵday bolıwı múmkin:
  
  1. 
     Eger hár bir túrdegi resurslarınıń birewden nusqası bolsa, ol halda tupik boladı;
     
  2. 
     Eger bir neshe resurslar bar bolsa, ol halda tupikke kirip qalıwı múmkin.