Problem smrtnega objema

Iz E-študij, proste zakladnice študentskega znanja

Skoči na: navigacija, iskanje

Vsebina

Smrtni objem (Deadlock)

Definicija

Nabor procesov je v smrtnem objemu, če vsak med njimi čaka na dogodek, ki ga lahko sproži le nek drugi proces iz istega nabora.

Pogosto naletimo na definicije v povezavi z alokacijo virov:

  • "A deadlock is a situation in which two computer programs sharing the same resource are effectively preventing each other from accessing the resource, resulting in both programs ceasing to function."
  • "A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set."

Dokler so v smrtnem objemu, nobeden od njih ne more:

  • izvajati
  • sprostiti vira
  • biti prebujen
Primeri
  • Shared resources

4 tape drives in system, and 2 processes. Each process holds 2 tape drives BUT needs 3 to progress

  • Spooling

Multiple processes spooling print files to disk Printer waits for files to be closed before printing Run out of disk space File cannot be completed (closed) until something is printed to free some space - nothing can be printed until a file is completed !! Start printing one file - or start killing processes to free space

  • DL primer procesi.png
Viri

Prosojnice predavanj profesorjev drugih univerz:

Zapiski:

Poskenirani zapiski:

Pogoji za nastop

Za nastop smrtnega objema so potrebni štirje pogoji:

  1. medsebojno izključevanje (mutual exclusion)
    Vsak vir je na voljo le enemu procesu.
  2. držanje in čakanje (hold and wait)
    Proces, ki že zaseda nek vir, lahko zahteva dodatne vire.
  3. brez odvzemanja virov (no preemprion)
    Če je bil procesu nek vir dodeljen, mi ne more biti na silo odvzet.
  4. krožno čakanje (circular wait)
    Obstajati mora zaporedje dveh ali več procesov, kjer vsak čaka na vir, ki ga zaseda naslednji proces v zaporedju.


Graf alokacije virov (Resource-allocation graph)

V = {P, R}, kjer je P = {P1, P2, ..., Pn} množica vseh procesov v sistemu, R = {R1, R2, ..., Rm} množica vseh virov v sistemu.

Povezave:

  • eij = Pi \rightarrow Rj (Request edge)

Proces Pi zahteva vir Rj.

  • eji = Rj \rightarrow Pi (Assignment Edge)

Proces Pi zaseda vir Rj.

Grafično se graf alokacije virov predstavlja s kvadratki in krogci in usmerjenimi povezavami:

  • oznaka za proces DL rag proces.png
  • oznaka za vir DL rag resurs.png, število pikic pomeni, število istovrstnih virov.
  • proces Pi zaseda resurs Rj DL rag 1.png
  • proces Pi zahteva resurs Rj DL rag 2.png

Ugotavljanje smrtnega objema z uporabo grafa alokacije virov:

  • Če v grafu NI ciklov, NI smrtnega objema.
  • V grafu je cikel:
    • vir v enem primerku ⇒ smrtni objem;
    • vir v več primerkih ⇒ možen je smrtni objem.


Primera:
Smrtni objem Ni smrtnega objema
DL rag primer 1.png DL rag primer 2.png


Viri


Načini soočanja s problemom smrtnega objema

Ignoriranje (The Ostrich Algorithm)

DL ostrich.png Ignoriranje problema v celoti. Delamo tako, kot da do smrtnega objema ne more priti. To je pristop, ki ga uporablja večina operacijskih sistemov (Unix, Windows,...). Tak pristop je primeren dokler do smrtnega objema pride razmeroma redko ali pa je cena vpeljave kakega algoritma za preprečitev previsoka.

Izogibanje smrtnim objemom

Dopustimo, da se trije od štirih pogojev za nastop smrtnega objema izpolnjeni, vendar ne dopustimo, da pride do smrtnega objema. Tak pristop omogoča večjo stopnjo paralelnosti, kot preprečevanje smrtnega objema. Uporabimo lahko dva osnovna pristopa:

  1. "ne zaženi procesa", če lahko njegove zahteve pripeljejo v smrtni objem (process initiation denial)
  2. "ne dovoli zahtev po dodatnih virih", če bi to lahko pripeljalo do smrtnega objema (baker)


Diagram trajektorije virov

DL trajektorije.png
Z diagramom trajektorije virov lahko prikažemo, kako sistem zaide v smrtni objem. Dvodimenzionalni diagram lahko narišemo na primeru dveh procesov in ob poenostavitvi izvajanja (ni skokov, zank,...). Stanje takega sistema ponazarja točka (x,y) na grafu, kjer je x stanje prvega procesa, y pa stanje drugega procesa.
Vstop v osenčeno območje pomeni neizogiben nastop smrtnega objema.


Varno stanje/sekvenca

Ko proces zahteva nek prosti resurs, mora sistem odločiti ali njegovo takojšnje zasedenje pusti sistem v varnem stanju. Sistem je v varnem stanju, če obstaja varna sekvenca izvajanja procesov. Sekvenca <P1,P2,...,Pn> je varna, če vsak proces Pi lahko zaseže vire, ki jih zahteva, iz množice še ne zasedenih virov in množice virov, ki jih zaseda Pj, kjer je j < i.

  • če zahtevam procesa Pi ne more biti takoj ugojeno, potem lahko Pi čaka dokler niso končani vsi procesi Pj
  • ko se Pj končajo, lahko Pi zasede potrebne resurse, se izvede in zaključi
  • ko se Pi zaključi, lahko Pi+1 zaseže potrebne resurse, ....

Varno stanje in smrtni objem

  • Če je sistem v varnem stanju, ne more priti do smrtnega objema.
  • Če sistem ni v varnem stanju, obstaja možnost smrtnega objema.

Izogibanje tako pomeni zagotavljanje, da se sistem vedno nahaja v varnem stanju.
DL safe unsafe.png


Primer
  • 3 procesi P0, P1, P2
  • 1 tip resursa, 12 primerkov
Stanje sistema v času t0
maksimalne potrebe trenutno zaseženo
P0 10 5
P1 4 2
P2 9 2
  • zaporedje izvajanja <P1, P0, P2> je varno
  • če bi proces P2 v času t1 zahteval 1 resurs več, sistem ne bi bil več v varnem stanju.


Process Initiation Denial

  • Vire razdelimo glede na tip. V vsakem sistemu obstaja določeno število resursov nekega tipa. Z E(i) označimo skupno število resursov tipa i v sistemu.
  • Z C(k,i) označimo zahteve procesa k po resursih tipa i (claimed).
  • Vsak proces mora vnaprej določiti C(k,i) za vse tipe virov i, to je potem tudi maksimalno število resursov tipa i, ki jih proces k lahko zasede.
  • Z A(i) označimo skupno število prostih resursov tipa i (available).
    • Velja: A(i) = E(i) - \sum_{k}^{} C(k,i)
  • Proces n lahko vstopi v sistem, samo če C(n,i) \le U(i) za vse i.

Ta pristop zagotavlja, da se izognemu smrtnemu objemu, saj je procesu dovoljen vstop v sistem, samo če je lahko zadoščeno njegovim zahtevam po virih. Strategija ni optimalna, saj je potrebno predpostaviti, da vsi procesi hkrati zahtevajo vse resurse.

Bankirjev algoritem (Banker's algorithm)

Obravnava več primerkov nekega tipa vira.
Namesto, da apriori odstranimo enega od pogojev za nastop smrtnega objema, raje pustimo, da se zahteve strežejo, dokler ne zaznamo možnosti nastopa problema. Bankirjev algoritem nikoli ne dovoli zaseganja, če ta pripelje sistem v nevarno stanje.

Pospošeni Bankirjev algoritem 

Na začetku so vsi Pi neoznačeni
1) poišči tak neoznačen Pi, da za vrstico Ri velja Ri - Ci <= A 
2)    če take vrstice ni -> nevarno stanje
      če taka vrstica obstaja: predpostavimo da Pi zasede vse željene vire in konča
          A <- A + Ri
          označi Pi
3) ponavljaj 1 in 2 dokler niso vsi Pi označeni ali ne nastopi nevarno stanje

V bolj razdelani obliki, je bankirjev algoritem sestavljen iz dveh delov:

  • safety algorithm: iz podanih podatkov ugotovi ali je stanje sistema varno
  • resorce-request algorithm: navidezno zaseže od procesa željene vire požene safety algorithm. Če ta ugotovi, da je stanje sistema po zaseganju še vedno varno, resurce-request algorithm dejansko zaseže željene vire.

Dobre strani:

  • preprečuje smrtni objem hkrati pa ni toliko restriktiven kot preprečevanje smrtnega objema

Slabosti algoritma:

  • procesi morajo predhodno napovedati maksimalne potrebe po resursih
  • število procesov v sistemu ni stalno
  • slabša odzivnost sistema
  • nepotrebna čakanja, ko se izogibamo nevarnim stanje, ki sicer ne vodijo v smrtni objem


Viri


Preprečitev smrtnega objema

Če hočemo, da do smrtnega objema ne pride, je potrebno odpraviti enega od štirih pogojev. Torej lahko tu pristopimo na 4 načine:

  • medsebojno izključevanje (mutual exclusion)
  1. Zahteve po virih se vpisujejo v čakalno vrsto in po potrebi obravnavajo po prioritetnem sistemu.
  • držanje in čakanje (hold and wait)
    Proces, ki že zaseda nek vir, lahko zahteva dodatne vire.
  1. Zagotovljeno mora biti, da proces, ki zahteva nek vir, ne zaseda nobenega drugega vira:
  2. procesi morajo zahtevati in alocirati VSE vire, preden začnejo izvajanje.
  • brez odvzemanja virov (no preemprion)
  1. Če proces, ki že zaseda nekaj virov, zahteva še en drug vir, ki mu ne more biti takoj alociran, potem mora sprostiti vse vire, ki jih zaseda;
  2. Odvzeti resursi se dodajo na seznam resursov, na katere proces čaka;
  3. Proces bo nadaljeval izvajanje šele, ko bo ponovno zasegel vse stare resurse in tiste, ki jih je na novo zahteval.
  • krožno čakanje (circular wait)
    • Uvedemo neki totalno urejenost vse tipov virov. Od procesov zahtevamo, da zasedajo vire po naraščajočem vrstnem redu.

R = {R1, R2, ..., Rm} množica virov v sistemu. Definiramo funkcijo F: R \rightarrow N Proces lahko zahteva Ri in Rj zaporedoma samo, če F(Ri) < Rj.

    • Dokaz s protislovjem:

Naj bo {P1, P2, ..., Pn} zaporedje procesov, ki so zašli v krožno čakanje, kjer proces Pi čaka na resurs Ri, tega pa je zaseda Pi+1 (Ri je zaseden od P0). Ker Pi+1 drži Ri in hkrati zahteva Ri+1, mora veljati F(Ri) < Ri+1. To pa hkrati pomeni da velja: F(R0) < R1 < ... < F(Rn) < R0. Ker pa F(R0) < R0 ne velja, smo z protislovjem dokazali, da do krožnega čakanja ne more priti.


Razlika med izogibanjem in preprečitvijo

  1. Preprečitev:
    1. omejuje načine zaseganja virov (design sistema);
    2. cilj je, da vsaj eden od štirih pogojev za smrtni objem, ni nikoli izpolnjen.
  1. Izogibanje:
    1. sistem dinamično pretehta vsako zahtevo in odloči, ali ji je v danem trenutku varno ustreči;
    2. sistem predhodno potrebuje dodatno informacijo o potrebah nekega procesa po resursih;
    3. mogoča večjo stopnjo paralelnosti.


Viri

Detekcija smrtnega objema in oživitev

Detekcija

1. En primerek posameznega vira

  1. Za vsak proce beležimo zasedene in zahtevane vire.
  2. Iz podatkov sestavimo graf alokacije virov.
  3. V grafu alokacije virov poiščemo cikle:

To lahko storimo z enem od algoritmov za iskanje v grafih (npr. iskanje v globino v vsakem vozlišču grafa) 

For each node N in the graph {
    Set L = empty listunmark all arcs
    Traverse (N,L)
}
If no deadlock reported by now, there isn’t any

define Traverse (C,L) {
   If C in L, report deadlock!
   Add C to L
   For each unmarked arc from C {
       Mark the arc
       Set A = arc destination
       /* L is local variable */
       Traverse (A,L)
   }
}

2. Viri v več primerkih

  • Imamo m tipov virov in n procesov
  • Vpeljemo naslednje oznake:
    • E_i (0 \le i \le m) - število razpoložljivih virov nekega tipa
    • E = (E1,E2,...,Em) - vektor vseh virov (existent)
    • A = (A1,A2,...,Am) - vektor razpoložljivih virov (available)
    • C = [c_{ij}], 0 \le i \le n, 0 \le j \le m - matrika trenutno alociranih virov (current allocation)
    • R = [r_{ij}], 0 \le i \le n, 0 \le j \le m - matrika zahtevanih virov (requests), katere vire potrebuje proces Pi
  • Velja: \sum_{k=1}^n c_{ij} + A_j = E_j
  • Pomožna definicija (operator \le za vektorje): A \le B, če velja \forall i: A_i \le B_i
  • Algoritem:

'Na začetku so vsi procesi Pi neoznačeni, med izvajanje algoritma se procesi označujejo, na koncu so vsi neoznačeni procesi v smrtnem objemu.'
Oznake: Ri i-ta vrstica matrike R, Ci i-ta vrstica matrike C 

1) Poišči tak neoznačen Pi, da je Ri <= A
2)   če tak Pi obstaja, prištej Ci k A in označi proces Pi
3)   če takega Pi ni, zaključi. 
Preostali procesi so v smrtnem objemu.


Oživitev

  • Z odvzemanjem (preemption)

Nekemu drugemu procesu odvzamemo konfliktni resurs. Ta način oživitve je odvisen od narave resursa in procesa (npr. Odvzemanje tiskalnik medtem kot ta tiska,...).

  • Prevrtenje nazaj (rollback)

Med izvajanje procesa periodično delamo kontrolne točke. če proces zaide v smrtni objem ga lahko povrnemo nazaj na stanje, v katerem je bil v eni od kontrolnih točk. Hraniti je potrebno vse relevantne podatke. Tak pristop predstavlja problem, če proces veliko dela z "zunanjim svetom".

  • Usmrtitev (kill)

Najenostavnejši vendar tudi najbolj grob način za rešitev iz smrtnega objema. Enega od procesov prekinemo. Tudi tu se pojavi vprašanje izbire primernega procesa: izberemo lahko takega, ki se ga da pognati nazaj od začetka, ne da bi se poznalo na delovanju, izberemo lahko takega, ki se je tekel najmanj časa,...

Viri


Kombiniran pristop

V prejšnjih poglavjih obdelani pristopi so najbolj primerni, ko imamo opravka z enakimi vrstami virov. Če pa je možno resurse razdeliti na različne razrede , lahko za vsakega od njih uporabimo zanj najbolj primerno metodo.


Dodatno branje


Methods and systems for analyzing multi-threaded programs are provided. The predisposed execution of multi-threaded programs is modified to cause and detect latent deadlocks. When a thread attempts to acquire a synchronization object, it is determined if the synchronization object was previously held by a thread that subsequently acquired another synchronization object while still holding the first. If this occurred, the thread is suspended and may be awakened by a thread that has acquired the synchronization object. The newly awakened thread may then attempt to acquire a synchronization object that is held by the second thread thereby increasing the likelihood that a latent deadlock will be caused and detected.


A deterministic, non-deadlocking technique to achieving distributed consensus in a multithreaded multiprocessing computing environment is provided. A communicator is established across multiple processes in the multithreaded computer environment notwithstanding that multiple groups of threads may be simultaneously trying to establish communicators. The technique includes communicating across the multiple processes to establish a candidate identifier for the communicator for a group of participating threads of the multiple processes; and communicating across the multiple processes to check at each participating thread of the multiple processes whether the candidate identifier can be claimed at its process, and if so, claiming the candidate identifier as the new identifier thereby establishing the communicator. As one example, the technique can be implemented via a subroutine call within a message passing interface (MPI) library.

Vzpostavljeno iz »http://www.e-studij.si/Problem_smrtnega_objema«
Osebna orodja
Imenski prostori
Različice
Dejanja
navigacija

Tiskanje/izvoz
orodja