Wielowątkowość - żywotność

Problemy żywotności aplikacji wielowątkowych

• Deadlock
• Livelock
• Starvation

Deadlock - zakleszczenie

 

Najczęstrzą i najpoważniejszym problemem żywotności programów są zakleszczenia. Klasyczny problem zakleszczenia to wątek A posiadający blokadę M i czekający na N i wątek B posiadający blokadę N i czekający na M. Takie wątki nigdy nie wykonają postępu. Problem ten da się rozszerzyć na wiele wątków.
Oczekiwanie na blokadę można zilustrować jako graf oczekiwania na odblokowanie, jeśli graf ten posiada cykl to wystąpiło zakleszczenie.

Klasycznym przykładem tego problemu jest problem transferowania pieniędzy między kontami:

public class AccountTransfer {
    private static class Account {
        private String number;
        private Integer balance;
        public Account(String number, Integer balance) {
            this.number = number;
            this.balance = balance;
        }
        public void setNewBalance(Integer amount) {
            balance += amount;
        }
        public String getNumber() {
            return number;
        }
        public Integer getBalance() {
            return balance;
        }
    }
    private static class TransferTask implements Runnable {
        private Account from;
        private Account to;  
        public TransferTask(Account from, Account to) {
            this.from = from;
            this.to = to;
        }
        public void transfer(Account from, Account to, Integer amount) {
            synchronized (from) {
                synchronized (to) {
                    if (from.getBalance() > amount) {
                        from.setNewBalance(-1 * amount);
                        to.setNewBalance(amount);
                    }
                }
            }
        }
        @Override
        public void run() {
            Random r = new Random();
            while (true) {
                int nextInt = r.nextInt(100);
                System.out.println("Transfering " + nextInt);
                transfer(from, to, nextInt);
            }
        }
    }
    public static void main(String[] args) {
        Account account1 = new Account("1", 10000);
        Account account2 = new Account("2", 20000);
        new Thread(new TransferTask(account1, account2)).start();
        new Thread(new TransferTask(account2, account1)).start();
    }
}

Problemem przy korzystaniu z wielu blokad jest kolejność ich zakładania - ta musi być określona i jednakowa - do określienia kolejności można użyć kodu hash code, albo innego identyfikatora obiektu który jest unikalny. Czyli najpierw wykonujemy porówanie hash code obiektów i ten który ma mniejszy hascode ma zakładaną blokadę szybciej, w przypadku kolizji można użyć dodatkowej blokady.

Metoda transfer bez deadlocku (przy unikalności numerów):

public void transfer(Account from, Account to, Integer amount) {
            int compareTo = from.getNumber().compareTo(to.getNumber());
            if (compareTo > 0) {
                synchronized (from) {
                    synchronized (to) {
                        trasferInternal(from, to, amount);
                    }
                }
            } else {
                synchronized (to) {
                    synchronized (from) {
                        trasferInternal(from, to, amount);
                    }
                }
            }
        }
        private void trasferInternal(Account from, Account to, Integer amount) {
            if (from.getBalance() > amount) {
                from.setNewBalance(-1 * amount);
                to.setNewBalance(amount);
            }
        }


Największym problemem przy wykrywaniu/unikaniu zakleszczeń są obiekty które ze sobą kooperują, jeśli obiekt A w metodzie synchronizowanej (czyli trzymając blokadę) wywołuje metodę obiektu B to jest to tak zwana alien method - potencjalnie niebezpieczny kod - ponieważ metoda w obiekcie B jest enkapsulowana i nie wiadomo jakie blokady zakłada - czyli nie można zdeterminować ich kolejności.
W tym wypadku należy - o ile to możliwe ograniczyć blok synchroniczny do absolutnego minimum i wykonywać metodę z obiektu B poza nim - nazywa się to open call.

Zapobieganie zakleszczeniom

 

Najważniejszym przy zapobieganiu zakleszczeniom jest poprawne - jednakowe uszeregowanie blokad. Należy unikać wykonywaniu metod z obiektów obcych podczas trzymania blokady.
Można też użyć czasowych metod tryLock obiektu Lock - nie da się tego niestety zrobić z blokiem synchronized.
Pomocnym może być też analiza blokad za pomocą zrzutu wątków (thread dump).
Program jvisualvm wykrywa zakleszczenia i pokazuje komunikat. Można także użyć programu z konsoli: jstack [PID].

Przykładowy zrzut dla programu na wyżej:

Found one Java-level deadlock:
=============================
"Thread-1":
  waiting to lock monitor 0x00000000026356a0 (object 0x00000000d96a4938, a com.java.ro.concurency.chapter10.AccountTransfer$Account),
  which is held by "Thread-0"
"Thread-0":
  waiting to lock monitor 0x00000000026355f8 (object 0x00000000d96a4950, a com.java.ro.concurency.chapter10.AccountTransfer$Account),
  which is held by "Thread-1"

Java stack information for the threads listed above:
===================================================
"Thread-1":
    at com.java.ro.concurency.chapter10.AccountTransfer$TransferTask.transfer(AccountTransfer.java:40)
    - waiting to lock <0x00000000d96a4938> (a com.java.ro.concurency.chapter10.AccountTransfer$Account)
    - locked <0x00000000d96a4950> (a com.java.ro.concurency.chapter10.AccountTransfer$Account)
    at com.java.ro.concurency.chapter10.AccountTransfer$TransferTask.run(AccountTransfer.java:55)
    at java.lang.Thread.run(Thread.java:722)
"Thread-0":
    at com.java.ro.concurency.chapter10.AccountTransfer$TransferTask.transfer(AccountTransfer.java:40)
    - waiting to lock <0x00000000d96a4950> (a com.java.ro.concurency.chapter10.AccountTransfer$Account)
    - locked <0x00000000d96a4938> (a com.java.ro.concurency.chapter10.AccountTransfer$Account)
    at com.java.ro.concurency.chapter10.AccountTransfer$TransferTask.run(AccountTransfer.java:55)
    at java.lang.Thread.run(Thread.java:722)

Found 1 deadlock.

Livelock

 

Livelock występuje jeśli pomimo że wątek nie czeka na blokadzie nie może wykonać postępu ponieważ jego operacja jest wycofywana. Typowym przykładem livelocku jest przetwarzanie wiadomości z kolejki - jeśli wykonuje to jeden wątek i nie może sobie poradzić z wiadomością - np przez błąd programistyczny to wiadomość zostaje cofnięta na początek kolejki i znów jest pobierana i zwracana, itd.
Innym przykładem są dwa wątki które są zbyt "miłe" i wycofują swoją operacje ponieważ widzą że inny ją wykonuje. Jeśli czas do powtórzenia jest taki sam dla obu wątków to operacje będą wykonywane bez końca. Pomocnym może być tutaj randomizowanie czasu oczekiwania przed ponowieniem operacji.

Starvation - zagłodzenie

 

Zagłodzenie występuje wtedy kiedy wątek jest permanentnie pozbawiony zasobów których potrzebuje aby wykonać postęp. Zwykle tym zasobem jest procesor.
Jest to dość rzadki przypadek i może wystąpić jedynie wtedy gdy nada się priorytety wątkom inne niż normalne - nie jest to zalecane. Ogólnie nie powinno się tego robić bo wtedy program może się inaczej zachowywać na innych systemach operacyjnych - np tylko na jednym może wystąpić zagłodzenie.