26. Starvation and Fairness and Livelock

1. Liveness.

1. A concurrent application's ability to execute in a timely manner is known as its liveness.
2. Some common kind of problems in liveness are
1. DeadLock
2. Starvation
3. LiveLock
3. Starvation and livelock are much less common a problem than deadlock, but are still problems that every designer of concurrent software is likely to encounter.

2. Starvation.

1. Starvation describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress.
2. This happens when shared resources are made unavailable for long periods by "greedy" threads.
3. For example, suppose an object provides a synchronized method that often takes a long time to return.
4. If one thread invokes this method frequently, other threads that also need frequent synchronized access to the same object will often be blocked.
5. If thread waits for long time then remaining threads called as Starvation.

3. Deadlock vs Starvation.

1. Long waiting of a thread where waiting taking never ends is called deadlock.
2. Where as long waiting of a thread where waiting ends at certain point is called starvation.
3. For example has to wait until completing all high priority threads this waiting it may be long waiting but ends at certain point which is nothing but starvation.

4. Causes of Starvation.

1. Threads with high priority swallow all CPU time from threads with lower priority.
2. Threads are blocked indefinitely waiting to enter a synchronized block, because other threads are constantly allowed access before it.
3. Threads waiting on an object (called wait() on it) remain waiting indefinitely because other threads are constantly awakened instead of it.

5. What is fairness.

1. Internally thread scheduler allocates execution for each thread based on priority.
2. Thread scheduler can follows any algorithm like Round Robin, FCFS, SJF ...etc.
3. Some times some low priority threads or waiting state threads will get chance on after long time.
4. So we can explicitly mention to Thread scheduler about execute FCFS threads.
5. Longest waiting threads can get the chance first is called fairness.
6. In normal synchronization concept we can’t set fairness.
7. But in external Locks concept we can set fairness.(Discuss in later sections)

6. What is LiveLock.

1. 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.
2. As with deadlock, livelock threads are unable to make further progress.
3. However, the threads are not blocked, they are simply too busy responding to each other to resume work.
4. A deadlock results in an infinite wait whereas a livelock results in wasting CPU cycles.
5. Livelock means processes are active but not able to progress due to interdependence.
6. It's like two people trying to cross a one man bridge, both backing off together and then both trying to move at the same time and doing this indefinitely.