Smrtni objem

Do smrtnega objema pride, ko se več procesov zaustavi in vsak od njih čaka na vir sistema, do katerega lahko dostopa samo s pomočjo drugega, zaustavljenega procesa. Da bi lažje razumeli nastanek smrtnih objemov si poglejmo primer iz vsakdanjega življenja: prijatelja sta se sprla in vsak pričakuje od drugega, da se bo prvi opravičil.

Pogosto uporabljeni viri kot so pomnilnik, medpomnilnik, prostor na disku...: Dokler takšni viri obstajajo le v omejenih količina bo moral en proces čakati na drugega, da sprosti sistemski vir, ki ga trenutno uporablja.
Primer: pet ljudi sedi za okroglo mizo na kateri so štiri vilice. Ob istem času vsak od njih z levo roko prime vilico, ki se nahaja na njegovi levi strani. Vilice so "serially reusable".
Potrošni viri, kot so sporočila in signali.: Proces čaka na sporočilo od drugega procesa. Rekli bomo, da pošiljajoč proces ustvarja vir in sprejema proces, ki ga uporablja.
Primer: Prvi proces čaka na sporočilo drugega in obratno. Noben od dveh ne more prekiniti smrtnega objema s pošiljanjem sporočila.

Poznamo štiri načine za obravnavanje smrtnih objemov.

Narediti nič (angl.do nothing): Več operacijskih sistemov se na smrtne objeme ne odzove.
Preprečitev: Možno je zgraditi sisteme, pri katerih ne prihaja do smrtnih objemov. To lahko storimo samo če preprečimo client server interactions.
Izogib: Pogosto imamo tudi možnost, da že vnaprej zaznamo nevarno stanje sistema, ko bi lahko prišlo do smrtnega objema. Metoda deluje samo pri nekaterih pogosteje uporabljenih sistemskih virih.
Zaznavanje: Sistem ne poizkuša preprečiti smrtnih objemov, ampak jih zazna in jih prekine.

Situacije, ki lahko vodijo do smrtnih objemov so pogosto predstavljene z grafom za dodeljevanje virov (angl. resource-allocation graph), čigar vozlišča (angl. nodes) so lahko procesi ali viri.

Pogoji za smrtni objem

Poznamo štiri pogoje, ki morajo biti izpolnjeni hkrati, da lahko pride do smrtnega objema.

Medsebojno izključevanje (angl. Mutal exclusion): Vsaj en vir v sistemu ni deljiv, torej ga zasede en proces, drugi pa morajo čakati nanj.
Zadrži in čakaj (angl. Hold and wait condition): Procesi lahko zadržujejo vire, ki so jim bili že dodeljeni medtem ko čakajo še na ostale vire.
Neprekinjevalni način (angl. No Preemption): Ko je nek vir dodeljen procesu, mu ne sme biti odvzet, dokler ga ne odrabi. Zasedba vira se torej ne da prekiniti.
Krožno čakanje (angl. Circular Wait): Potrebna je krožna veriga procesov tako, da si vsak proces v verigi pridržuje nekaj virov, ki jih zahteva naslednji proces v verigi.

Preprečevanje smrtnih objemov

Ker so za smrtni objem potrebni vsi zgoraj navedeni pogoji, ga lahko preprečimo s tem, ko preprečimo vsakega od štirih pogojev posebej.

Največji problem je, da je večina virov lahko dostopna samo enemu procesu na enkrat. Če določen proces piše v datoteko, noben od ostalih procesov nima dostopa do te datoteke.
Da preprečimo drugi pogoj moramo omogočiti procesu, da nek vir pridobi preden ga bo uporabil. Pri tem pride do dveh težav:
- Viri bodo zasedeni preden jih bodo procesi sploh uporabljali.
- Metoda ni uporabna na porabljive vire kot so sporočila (angl. messages), ker bi bilo potrebno, da bi vsak proces najprej sprejel vsa sporočila od drugega procesa in šele nato bi jih začel obdelovati
Dovoliti procesu, da ukrade ali si sposodi vir od drugega procesa je lahko rešitev, vendar moramo najprej prekiniti proces od katerega smo pobrali vir, kar bi se izkazalo kot izgubljeno delo, ali pa tudi izguba podatkov.
Vsem tipom virov lahko določimo skupen ukaz, ki bo prisilil vse procese, da sledijo ukazu, ko si prilastijo nove vire. Če nek procse potrebuje več kot eno enoto vira določenega tipa, si mora prilastiti vse ali nobenega.

"The dream of building large deadlock-free systems is just a dream." Neznacec

Izogibanje

Z opazovanjem dodeljevanja virov ne dovolimo sistemu, da pride do stanja ko nebi bil zmožen zadovoljiti največje zahteve procesa po virih.

Zaznavanje smrtnih objemov:

Najlažji način preprečevanja smrtnih objemov je uporaba časovnih prekinitev. Do smrtnega objema ponavadi pride, ko več procesov ne uspe napredovati v določenem časovnem obdobju.
Bolj splošna metoda je izdelava grafov za dodeljevanje virov (resource allocation graph) in iskanje ciklov; vsak cikel pomeni smrtni objem.

Windows XP

Razvrščanje – algoritem prioritete z možnostjo prekinjanja – 32 razredov prioritet in 6 relativnih znotraj vsakega razreda prioritet
Razvrščanje opravlja dispatcher
Proces(nit) se izvršuje dokler:
ga ne prekine nit z višjo prioriteto,
se ne konča,
ne izvede sistemskega klica,
se ne konča njegov quantum.
Realtime procesi imajo prednost pred ostalimi

Linux

Realtime procesi se razvrščajo po FIFO in RR
Razvrščajo in prekinjajo se samo procesi v uporabniškem načinu delovanja
Prioriteta - prekinjevalni algoritem
Kredit=kredit/2 + prioriteta
Ob vsakem časovni prekinitvi se izvajanemu procesu kredit zmanjša
Če imajo vsi procesi kredit=0, potem se opravi ponovno kreditiranje