Deadlock

Sissejuhatus

synchronized lahendab tõrkeolukordi, tagades, et korraga pääseb kriitilisse sektsiooni ainult üks lõim. Kuid sünkroniseerimine toob kaasa uue võimaliku vea: kaks lõime võivad kumbki hoida lukku, mida teine vajab, ning kumbki ei saa edasi liikuda. Programm ei jookse kokku, ei anna veateadet ega lõpeta tööd - see lihtsalt jääb lõputult ootama.

Sellist olukorda nimetatakse deadlock'iks. See on üks keerulisemaid konkurrentsusevigu, mida siluda, sest programm näib korras olevalt - see lihtsalt ei tee enam midagi.

Probleemist lähemalt

Toome näiteks kaks pangakontot, millest kumbki kaitstud oma lukuga. Raha ülekandmine nõuab mõlema luku samaaegset hoidmist: lähtekonto vähendamiseks ja sihtkonto suurendamiseks.

public class Account {
    private int balance;

    public void transferTo(Account other, int amount) {
        synchronized (this) {
            synchronized (other) {
                if (this.balance >= amount) {
                    this.balance -= amount;
                    other.balance += amount;
                }
            }
        }
    }
}

See toimib senikaua, kuniks transferTo-d kutsub korraga ainult üks lõim. Samaaegse kasutuse korral võib tekkida deadlock.

Oletame, et kaks lõime proovivad samal ajal teha ülekandeid samade kontode vahel vastassuundades:

Account a = new Account();
Account b = new Account();

new Thread(() -> a.transferTo(b, 10)).start();  // locks a, then wants b
new Thread(() -> b.transferTo(a, 10)).start();  // locks b, then wants a

Kui esimene lõim seab lukku objekti a ja samal ajal teine lõim lukustab objekti b, proovivad mõlemad seejärel omandada luku, mis on juba teise lõime käes. Kumbki ei saa oma lukku vabastada enne, kui saab teise, ning kumbki ei saa teist lukku enne, kui teine selle vabastab. Programm jääb kinni.

Selline muster - ringikujuline ootamine lõimede vahel - on deadlock'i peamine tunnus.

Deadlock'i esinemise tingimused

Deadlock tekib ainult siis, kui kõik järgmised neli tingimust kehtivad samaaegselt:

1. Vastastikune välistamine (mutual exclusion) - ressursse ei saa jagada - neid saab hoida vaid üks lõim korraga
2. Hoia ja oota (hold and wait) - lõim hoiab üht ressurssi ja ootab samal ajal teist
3. Eemaldamise puudumine (no preemption) - ressursse ei saa lõimelt sunniviisiliselt ära võtta
4. Ringikujuline ootus (circular wait) - eksisteerib tsükkel, kus lõim A ootab lõime B järgi, kes omakorda ootab lõime A järgi.

Kui eemaldada ükskõik milline neist tingimustest, ei saa ummikseisu tekkida. Esimesed kolm tulenevad tavaliselt probleemi olemusest ega ole kergesti muudetavad. Praktiline lahendus on lahendada ära neljas tingimus ehk vältida ringikujulist ootust.

Lukkude järjestamine

Tavapärane lahendus on määrata kõigile programmi lukkudele kindel järjestus ning nõuda, et iga lõim, mis omandab rohkem kui ühe luku, teeb seda alati samas järjekorras. Kui kõik lõimed järgivad sama järjekorda, ei saa tekkida ringikujulist ootejärjekorda.

Loomulik järjestus võib näiteks tulla unikaalse ID kujul:

public class Account {
    private final int id;
    private int balance;

    public void transferTo(Account other, int amount) {
        Account first  = this.id < other.id ? this : other;
        Account second = this.id < other.id ? other : this;

        synchronized (first) {
            synchronized (second) {
                if (this.balance >= amount) {
                    this.balance -= amount;
                    other.balance += amount;
                }
            }
        }
    }
}

Nüüd omandavad mõlemad lõimed kõigepealt väiksema ID-ga konto luku ja seejärel suurema ID-ga konto luku. Sellises olukorras ei saa tekkida stsenaariumi, kus üks lõim hoiab lukku, mida teine vajab, samal ajal oodates lukku, mida teine lõim hoiab.

Kui loomulik järjestus puudub

Teiste objektide puhul ei pruugi sellist järjestust olla. Levinud varulahendus on kasutada System.identityHashCode(obj) väärtust - see on arv, mis põhineb objekti identiteedil (tavaliselt seotud mäluaadressiga). Kuna kahel objektil võib teoreetiliselt olla sama räsi, tuleks käsitleda ka viigiolukorda:

Object tieBreaker = new Object();

int h1 = System.identityHashCode(a);
int h2 = System.identityHashCode(b);

if (h1 < h2) {
    synchronized (a) { synchronized (b) { /* work */ } }
} else if (h1 > h2) {
    synchronized (b) { synchronized (a) { /* work */ } }
} else {
    synchronized (tieBreaker) {
        synchronized (a) { synchronized (b) { /* work */ } }
    }
}

Viik lahendatakse ühe globaalse luku kaudu, mida kasutatakse ainult siis, kui kahel objektil on sama räsi.

Try-lock

Teine lähenemine on proovida lukk omandada ilma blokeerimata ning loobuda, kui see ei õnnestu. synchronized seda ei toeta, kuid ReentrantLock.tryLock() võimaldab:

public boolean transferTo(Account other, int amount) {
    if (this.lock.tryLock()) {
        try {
            if (other.lock.tryLock()) {
                try {
                    // perform the transfer
                    return true;
                } finally {
                    other.lock.unlock();
                }
            }
        } finally {
            this.lock.unlock();
        }
    }
    return false;  // could not acquire both locks - caller may retry
}

See väldib deadlock'i ennast, kuid võib tekitada livelock'i: kui mõlemad lõimed loobuvad ja proovivad lukku omistada täpselt samal ajal uuesti. Antud olukorras ei tee kumbki lõim edusamme ja töö jääb jällegi seisma. Selle vältimiseks lisatakse tavaliselt enne uut katset väike juhuslik viivitus, mis katkestab sümmeetria.

Kokkuvõtteks

• Kui lõim hoiab korraga kahte lukku, määra neile kindel järjestus ja omanda need alati samas järjekorras
• Kui järjestust ei saa määrata, kasuta tryLock-i ja taandu vajadusel
• Hoia lukke võimalikult lühikest aega - mida lühem kriitiline sektsioon, seda väiksem on deadlock'i tekkimise võimalus
• Väldi tundmatu koodi väljakutsumist lukku hoides; see kood võib proovida omandada teise luku ja tekitada ootamatu olukorra