https://richardbarabe.wordpress.com/2014/02/21/java-deadlock-livelock-and-lock-starvation-examples/
https://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html
Disadvantages of locks? What is Deadlock? What is Starvation
Disadvantages of Locks: 1) adds overhead for each access, even when the chances for collision are very rare.
2) deadlock, where two threads each hold a lock on resources that the other needs before releasing its lock.
3) When a thread is waiting for a lock, it cannot do anything else. If a thread holding a lock is permanently blocked (due to an infinite loop, deadlock, livelock, or other liveness failure), any threads waiting for that lock will be blocked for ever, and can never make progress.
4) priority inversion: high priority threads cannot proceed if a low priority thread is holding the common lock, this effectively downgrades its priority to that of the lower-priority thread
Improvements:
Optimistic concurrency control:
We proceed with an update, hopeful that you can complete it without interference. This approach relies on collision detection to determine if there has been interference from other parties during the update, in which case the operation fails and can be retried (or not).
For example, in java, besides the heavyweight lock or synchronized, we can use atomic varibales such as AtomicInteger etc to improve concurrency.
Deadlock:
A deadlock occurs when two (or more) threads have created a situation where they are all blocking each other. Imagine that threads T1 and T2 need to acquire both resources A and B in order to do their work. If T1 acquires resource A, then T2 acquires resource B, T1 could then be waiting for resource B while T2 was waiting for resource A. In this case, both threads will wait indefinitely for the resource held by the other thread. These threads are said to be deadlocked.
"A deadlock cannot occur unless all of the following conditions are met:
Protected access to shared resources, which implies waiting.
No resource preemption, meaning that the system cannot forcibly take a resource from a thread holding it.
Multiple independent requests, meaning a thread can hold some resources while requesting others.
Circular dependency graph, meaning that Thread A is waiting for Thread B which is waiting for Thread C which is waiting for Thread D which is waiting for Thread A."
Starvation:
Reference: http://www.justanswer.com/computer/05887-major-differences-deadlock-starvation-race.html
Starvation occurs when a scheduler process (i.e. the operating system) refuses to give a particular thread any quantity of a particular resource (generally CPU).
If there are too many high-priority threads, a lower priority thread may be starved. This can have negative impacts, though, particularly when the lower-priority thread has a lock on some resource.
Race conditions
Race conditions occurs when two thread operate on same object without proper synchronization and there operation interleaves on each other.
Classical example of Race condition is incrementing. as increment is not an atomic operatio, if multipe threads try to incremet one variable at same time, race conditions occur
The situation where two threads compete for the same resource, where the sequence in which the resource is accessed is significant, is called race conditions. A code section that leads to race conditions is called a critical section.
References
http://www.careercup.com/question?id=15432682
http://codeidol.com/community/java/disadvantages-of-locking/13510/
Deadlock happens when a process wait for another one who is using some needed resource (ie: file or database table row) to finish with it, while the other process also wait for the first process to release some other resource.
static void transfer(BankAccount from, BankAccount to, double amount) { synchronized(from) { from.withdraw(amount); synchronized(to) { to.deposit(amount); } } } final BankAccount fooAccount = new BankAccount(1, 100d); final BankAccount barAccount = new BankAccount(2, 100d); new Thread() { public void run() { BankAccount.transfer(fooAccount, barAccount, 10d); } }.start(); new Thread() { public void run() { BankAccount.transfer(barAccount, fooAccount, 10d); } }.start(); static void transfer(BankAccount from, BankAccount to, double amount) { from.lock.lock(); from.withdraw(amount); to.lock.lock(); to.deposit(amount); to.lock.unlock(); from.lock.unlock(); }LiveLock
with the livelock, each process is waiting “actively”, trying to resolve the problem on its own (like reverting back its work and retry). A live lock occurs when the combination of these processes’s efforts to resolve the problem makes it impossible for them to ever terminate.
two threads tries to transfer money from one account to another one at the same time. But this time, instead of waiting for a lock to be released when a required account is locked, a thread will just revert its work if any, and retry the whole operation in loop until successful :
public class BankAccount { double balance; int id; Lock lock = new ReentrantLock(); BankAccount(int id, double balance) { this.id = id; this.balance = balance; } boolean withdraw(double amount) { if (this.lock.tryLock()) { // Wait to simulate io like database access ... try {Thread.sleep(10l);} catch (InterruptedException e) {} balance -= amount; return true; } return false; } boolean deposit(double amount) { if (this.lock.tryLock()) { // Wait to simulate io like database access ... try {Thread.sleep(10l);} catch (InterruptedException e) {} balance += amount; return true; } return false; } public boolean tryTransfer(BankAccount destinationAccount, double amount) { if (this.withdraw(amount)) { if (destinationAccount.deposit(amount)) { return true; } else { // destination account busy, refund source account. this.deposit(amount); } } return false; } public static void main(String[] args) { final BankAccount fooAccount = new BankAccount(1, 500d); final BankAccount barAccount = new BankAccount(2, 500d); new Thread(new Transaction(fooAccount, barAccount, 10d), "transaction-1").start(); new Thread(new Transaction(barAccount, fooAccount, 10d), "transaction-2").start(); }}class Transaction implements Runnable { private BankAccount sourceAccount, destinationAccount; private double amount; Transaction(BankAccount sourceAccount, BankAccount destinationAccount, double amount) { this.sourceAccount = sourceAccount; this.destinationAccount = destinationAccount; this.amount = amount; } public void run() { while (!sourceAccount.tryTransfer(destinationAccount, amount)) continue; System.out.printf("%s completed ", Thread.currentThread().getName()); }}Lock Starvation
Lock starvation is all about thread priority. It occurs when a thread, having lesser priority than other ones, is constantly waiting for a lock, never able to take it because other thread(s) with higher priority are constanly aquiring the lock. Suppose our bank account example. The bank adds a feature that constantly watch one’s account balance and send an email if that balance goes below zero (a monitor thread). But in this implementation, the monitor thread is of a higher priority than the transaction threads. Because of this, the transaction threads can take a very long time(say ever) to execute.
public static void main(String[] args) { final BankAccount fooAccount = new BankAccount(1, 500d); final BankAccount barAccount = new BankAccount(2, 500d); Thread balanceMonitorThread1 = new Thread(new BalanceMonitor(fooAccount), "BalanceMonitor"); Thread transactionThread1 = new Thread(new Transaction(fooAccount, barAccount, 250d), "Transaction-1"); Thread transactionThread2 = new Thread(new Transaction(fooAccount, barAccount, 250d), "Transaction-2"); balanceMonitorThread1.setPriority(Thread.MAX_PRIORITY); transactionThread1.setPriority(Thread.MIN_PRIORITY); transactionThread2.setPriority(Thread.MIN_PRIORITY); // Start the monitor balanceMonitorThread1.start(); // And later, transaction threads tries to execute. try {Thread.sleep(100l);} catch (InterruptedException e) {} transactionThread1.start(); transactionThread2.start(); }}class BalanceMonitor implements Runnable { private BankAccount account; BalanceMonitor(BankAccount account) { this.account = account;} boolean alreadyNotified = false; @Override public void run() { System.out.format("%s started execution%n", Thread.currentThread().getName()); while (true) { if(account.getBalance() <= 0) { // send email, or sms, clouds of smoke ... break; } } System.out.format("%s : account has gone too low, email sent, exiting.", Thread.currentThread().getName()); } }https://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html
Starvation
Starvation describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress. This happens when shared resources are made unavailable for long periods by "greedy" threads. For example, suppose an object provides a synchronized method that often takes a long time to return. If one thread invokes this method frequently, other threads that also need frequent synchronized access to the same object will often be blocked.
Livelock
A thread often acts in response to the action of another thread. If the other thread's action is also a response to the action of another thread, then livelock may result. As with deadlock, livelocked threads are unable to make further progress. However, the threads are not blocked — they are simply too busy responding to each other to resume work. This is comparable to two people attempting to pass each other in a corridor: Alphonse moves to his left to let Gaston pass, while Gaston moves to his right to let Alphonse pass. Seeing that they are still blocking each other, Alphone moves to his right, while Gaston moves to his left. They're still blocking each other, so...
Bloomberg LP Interview Question:Disadvantages of locks? What is Deadlock? What is Starvation
Disadvantages of Locks: 1) adds overhead for each access, even when the chances for collision are very rare.
2) deadlock, where two threads each hold a lock on resources that the other needs before releasing its lock.
3) When a thread is waiting for a lock, it cannot do anything else. If a thread holding a lock is permanently blocked (due to an infinite loop, deadlock, livelock, or other liveness failure), any threads waiting for that lock will be blocked for ever, and can never make progress.
4) priority inversion: high priority threads cannot proceed if a low priority thread is holding the common lock, this effectively downgrades its priority to that of the lower-priority thread
Improvements:
Optimistic concurrency control:
We proceed with an update, hopeful that you can complete it without interference. This approach relies on collision detection to determine if there has been interference from other parties during the update, in which case the operation fails and can be retried (or not).
For example, in java, besides the heavyweight lock or synchronized, we can use atomic varibales such as AtomicInteger etc to improve concurrency.
Deadlock:
A deadlock occurs when two (or more) threads have created a situation where they are all blocking each other. Imagine that threads T1 and T2 need to acquire both resources A and B in order to do their work. If T1 acquires resource A, then T2 acquires resource B, T1 could then be waiting for resource B while T2 was waiting for resource A. In this case, both threads will wait indefinitely for the resource held by the other thread. These threads are said to be deadlocked.
"A deadlock cannot occur unless all of the following conditions are met:
Protected access to shared resources, which implies waiting.
No resource preemption, meaning that the system cannot forcibly take a resource from a thread holding it.
Multiple independent requests, meaning a thread can hold some resources while requesting others.
Circular dependency graph, meaning that Thread A is waiting for Thread B which is waiting for Thread C which is waiting for Thread D which is waiting for Thread A."
Starvation:
Reference: http://www.justanswer.com/computer/05887-major-differences-deadlock-starvation-race.html
Starvation occurs when a scheduler process (i.e. the operating system) refuses to give a particular thread any quantity of a particular resource (generally CPU).
If there are too many high-priority threads, a lower priority thread may be starved. This can have negative impacts, though, particularly when the lower-priority thread has a lock on some resource.
Race conditions
Race conditions occurs when two thread operate on same object without proper synchronization and there operation interleaves on each other.
Classical example of Race condition is incrementing. as increment is not an atomic operatio, if multipe threads try to incremet one variable at same time, race conditions occur
The situation where two threads compete for the same resource, where the sequence in which the resource is accessed is significant, is called race conditions. A code section that leads to race conditions is called a critical section.
References
http://www.careercup.com/question?id=15432682
http://codeidol.com/community/java/disadvantages-of-locking/13510/
