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.

25. DeadLock

1. What is deadlock

1. If 2 threads are waiting for each other forever, such type of infinite waiting is called deadlock.
2. Synchronized keyword is one of the reason for deadlock situation, hence while using synchronized keyword we, we have to take special care.
3. There is no resolution technique for deadlock, but several prevention techniques.
4. Example thread t1 locks obj1, thread t2 locks obj2 , 2 threads entered into their own synchronized areas but after entered, t1 need to call synchronized method of obj2, and t2 need to call synchronized method of obj1, so 1 waits obj2 lock and t2 needs obj1 lock.It is the example of dead lock.
   
5. If join method calls itself for waiting also comes under deadlock.If t1 thread executes t1.join().
6. More complicated deadlocks are like.
1. Thread 1  locks A, waits for B
2. Thread 2  locks B, waits for C
3. Thread 3  locks C, waits for D
4. Thread 4  locks D, waits for A

2. How to prevent  deadlock

1. In some situations it is possible to prevent deadlocks.
1. Locks order
2. Locks timeout
2. Deadlock occurs when multiple threads need the same locks but obtain them in different order.
3. If you make sure that all locks are always taken in the same order by any thread, deadlocks cannot occur.
4. Another deadlock prevention mechanism is to put a timeout on lock attempts meaning a thread trying to obtain a lock will only try for so long before giving up.

24. Volatile keyword

1. What is Volatile keyword?

1. The Java volatile keyword is used to mark a Java variable as "being stored in main memory".
2. More precisely that means, that every read of a volatile variable will be read from the computer's main memory, and not from the CPU cache, and that every write to a volatile variable will be written to main memory, and not just to the CPU cache.
3. Actually, since Java 5 the volatile keyword guarantees more than just that volatile variables are written to and read from main memory.
4. In a multithreaded application where the threads operate on non-volatile variables, each thread may copy variables from main memory into a CPU cache while working on them, for performance reasons.
5. If your computer contains more than one CPU, each thread may run on a different CPU. That means, that each thread may copy the variables into the CPU cache of different CPUs.
   
6. With non-volatile variables there are no guarantees about when the Java Virtual Machine (JVM) reads data from main memory into CPU caches, or writes data from CPU caches to main memory. This can cause several problems
7. Imagine too, that only Thread 1 increments the counter variable, but both Thread 1 and Thread 2 may read the counter variable from time to time.
   

public class SharedObject {    public int counter = 0; }

8. If the counter variable is not declared volatile there is no guarantee about when the value of the counter variable is written from the CPU cache back to main memory. This means, that the countervariable value in the CPU cache may not be the same as in main memory.
   
9. The problem with threads not seeing the latest value of a variable because it has not yet been written back to main memory by another thread, is called a "visibility" problem. The updates of one thread are not visible to other threads.
10. By declaring the counter variable volatile all writes to the counter variable will be written back to main memory immediately. Also, all reads of the counter variable will be read directly from main memory. Here is how the volatile declaration of the counter variable looks:
    

public class SharedObject {    Public volatile int counter = 0; }

11. Declaring a variable volatile thus guarantees the visibility for other threads of writes to that variable.

2. What is Happens before relationship?

1. A happens-before relationship between two program statements is sort a guarantee which ensures that any memory writes by one statement are visible to another statement.
2. Since Java 5 the volatile keyword guarantees more than just the reading from and writing to main memory of variables.
3. Actually, the volatile keyword guarantees this:
1. If Thread A writes to a volatile variable and Thread B subsequently reads the same volatile variable, then all variables visible to Thread A before writing the volatile variable, will also be visible to Thread B after it has read the volatile variable.
2. The reading and writing instructions of volatile variables cannot be reordered by the JVM (the JVM may reorder instructions for performance reasons as long as the JVM detects no change in program behaviour from the reordering).
3. Instructions before and after can be reordered, but the volatile read or write cannot be mixed with these instructions. Whatever instructions follow a read or write of a volatile variable are guaranteed to happen after the read or write.

3. Synchronization supports Happens before relationship?

1. Yes, Synchronization also supports Happens before relationship.
2. If thread entered into synchronized area it will read the data from main memory to cpu caches of present thread.
3. If thread leaving the synchronized area it will write the data to main memory from cpu cache of present thread.

23. Critical section and Race conditions

1. What is race condition?

1. If multiple threads are operating simultaneously on same java object then there may be a chance of data consistency problem, this is called race condition.
2. We can overcome this problem by using synchronized keyword.
   

2. What is critical section?

1. A critical section is a section of code that is executed by multiple threads and where the sequence of execution for the threads makes a difference in the result of the concurrent execution of the critical section.
2. The section of code gives a problem called race condition.
   

3. Example of race condition?

4. How to avoid race condition?

1. We can overcome this problem by using synchronized keyword.
   

22. Methods of Thread class

21. Producer consumer problem using wait() and notify

1. Producer consumer problem.

1. In computing, the producer–consumer problem (also known as the bounded-buffer problem) is a classic example of a multi-process synchronization problem.
2. The problem describes two processes, the producer and the consumer, which share a common, fixed-size buffer used as a queue.

• The producer’s job is to generate data, put it into the buffer, and start again.
• At the same time, the consumer is consuming the data (i.e. removing it from the buffer), one piece at a time.

20. Missed signals and Spurious Wakeups

1. Is that give any effect if we call notify() or notifyAll() before calling of wait()

1. No, before wait() if we call notify() or notifyAll() call is wasted.
2. If we call notify() or notifyAll() it will check any thread is in waiting state respective to corresponding object lock.
3. If no thread is available in waiting state on specified lock, then call is wasted.
4. After the notify calls if we call wait() then the thread will go to waiting state by releasing the lock.
5. It will be in waiting state up to again call notify() or notifyAll() or any below case.
1. After call notify(), notifyAll() calling on same object, and completion of notify() executed thread completes or releases lock of that object.
2. If specified time completes.
3. Any interruption on that thread.
4. Any spurious wakeup

2. What is missed signal in thread communication.

1. From above concept we understand if we call notify methods before calling wait() then there is no effect on notify methods.
2. So calling notify methods are giving signals to waiting threads.
3. Sometimes there may be a chance of missing signals like below case.
1. In my application 2 threads are there for communication.
2. 1st thread need to go wait state and 2nd thread give the signal to 1st thread by calling notify methods.
3. But my 2nd thread executed first before my 1st thread, then the thread is calling notify methods before wait() by mistake.
4. Now 1st thread is executing wait()
4. In this case 1st thread will be in waiting state forever.
5. So this type of cases are called as missing signals.

3. How to avoid missed signal in thread communication.

1. We need to maintain some logic like if signal is not available then only my thread need to go wait state.
2. Else my thread need to skip wait state.
         
3. So we need to maintain flag or boolean variable to is signal is fired or not.
   

4. What is  spurious wakeups or spin lock in thread communication.

1. For inexplicable reasons it is possible for threads to wake up even if notify() and notifyAll() has not been called.
2. This is known as spurious wakeups. Wakeups without any reason.
3. If a spurious wakeup occurs in the Display class's wish() method the waiting thread may continue processing without having received a proper signal to do so! This could cause serious problems in your application.
   
4. To guard against spurious wakeups the signal member variable is checked inside a while loop instead of inside an if-statement.
5. Such a while loop is also called a spin lock. The thread awakened spins around until the condition in the spin lock (while loop) becomes false.

5. Why spurious wakeups are occurred in java.

1. It is a very rare scenario to occur spurious wakeups in java application.
2. In java 1.5 they introduced one daemon thread which runs on background of our application its priority of the thread is very less, so it will get less number of chances to execute.
3. The daemon thread is ‘malicious alarm clock’ introduced in jdk 1.5
   
4. The thread will get random object and calls notifyAll() , so some times only it will give spurious wakeups.

6. How locks will be released from thread in reentrance synchronization.

Locks in synchronization

1. If thread entered into synchronized area, then thread will acquire object lock.
2. After completion of the synchronized area only thread will releases the lock.
3. In middle of synchronized area if we write calling wait() on thread acquired object.
4. Thread will releases the lock and go to waiting state and waiting for notification on that object.
5. Some other thread will acquire the lock and executes its synchronized areas of that object.

Locks in reentrance synchronization

1. If thread entered into same object lock related synchronized area again and again then thread will hold same object lock multiple times.
2. In middle of synchronized area if we write calling wait() on thread acquired object.
3. Thread will releases the all the locks of same object and go to waiting state and waiting for notification on that object.