Lukkiutuminen

Lukkiutuminen (engl. deadlock) on tilanne, jossa kaksi tai useampia prosessia ei pääse etenemään, koska ne odottavat toisiaan. Tilanne syntyy helposti ohjelmointivirheen tuloksena, kun yritetään ratkaista rinnakkaisuuden mukanaan tuomia ongelmia.

Lukkiutumisella on neljä välttämätöntä ja samalla riittävää ehtoa. Tämä tarkoittaa sitä, että lukkiutuminen on mahdotonta, elleivät kaikki ehdot ole tosia, ja toisaalta sitä, että lukkiutuminen ennen pitkää tapahtuu, jos kaikki ehdot ovat tosia. Ehdot ovat:

1. Poissulkemisehto. Tämä tarkoittaa sitä, että prosessi (tai säie) varaa jonkin resurssin vain omaan käyttöönsä. Resurssi voi olla esimerkiksi muistia, oheislaite tai tiedosto.
2. Irrottamattomuusehto. Tämä tarkoittaa sitä, että vain prosessi itse voi vapauttaa varaamansa resurssin.
3. Varaus-odotusehto. Tämä tarkoittaa sitä, että prosessi ei vapauta resurssejaan odottaessaan lisäresurssien vapautumista.
4. Silmukkaodotusehto. Tämä tarkoittaa sitä, että prosessit odottavat toisiaan silmukassa, eli prosessi A odottaa prosessin B varaamaa resurssia ja päinvastoin.

Koska yhdenkin ehdon rikkominen riittää estämään lukkiutumiset, ei kaikkia ehtoja tarvitse estää. Esimerkiksi virtuaalimuistijärjestelmä rikkoo irrottamattomuusehtoa: käyttöjärjestelmä voi vapauttaa keskusmuistia ilman prosessin myötävaikutusta. Näin keskusmuistin loppuminen kesken ei voi aiheuttaa järjestelmän lukkiutumista. Sovelluksissa on tyypillistä varata resurssit aina samassa järjestyksessä, jolloin silmukkaodotusehto ei voi toteutua. Varjopuolena on se, että osa varauksista joudutaan tällöin tekemään liian aikaisin.

Lukkiutumista muistuttavia ongelmia ovat nälkiintyminen (engl. starvation) ja livelock.

Katso myös

• Synkronointi (ohjelmointi)

Lähteet

• Ilkka Haikala ja Hannu-Matti Järvinen: Käyttöjärjestelmät (luku 3). Talentum 2003. ISBN 951-762-837-4