Multithreading concepts

Race Condition: 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.

 Mutex :  Mutual exclusion (often abbreviated to mutex) algorithms are used in concurrent programming to avoid the simultaneous use of un-shareable resources by pieces of computer code called critical sections.
 
Critical section : In concurrent programming a critical section is a piece of code that accesses a shared resource (data structure or device) that must not be concurrently accessed by more than one thread of execution.

Semaphore: Synchronization tool.
A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations : wait() and signal().


Definiation of wait():

wait(S){
    while S<=0;
    //no-op
    s--;
}

Definiation of signal():

signal(S){
    S++;
}
 
Mutual Exclusion Implementation by Semaphores:
 
do {

waiting(mutex);
      // critical section
signal(mutex);
     //remainder section
}
while(TRUE);

Semaphores can be counting and binary.
The value of a counting semaphore can range over an unrestricted domain.

The value of a binary semaphore can range only between 0 and 1.
Binary semaphores are also known as mutex locks, as they are locks that provide mutual exclusion

Producer-Consumer Problem:
In the Producer-consumer problem, one process (the producer) generates data items and another process (the consumer) receives and uses them. They communicate using a queue of maximum size N. Obviously the consumer has to wait for the producer to produce something if the queue is empty. Perhaps more subtly, the producer has to wait for the consumer to consume something if the buffer is full.


The problem is easily solved if we model the queue as a series of boxes which are either empty or full, and regard empty boxes as one type of resource and full boxes as another type of resource. The producer "removes" an empty box and then "creates" a full one, whilst the consumer does the reverse.
Given that emptyCount and fullCount are counting semaphores, and emptyCount is initially N whilst fullCount is initially 0, the producer does the following repeatedly:
produce:


P(emptyCount)
putItemIntoQueue(item)
V(fullCount)

The consumer does the following repeatedly:-
consume:

P(fullCount)
item ← getItemFromQueue()
V(emptyCount)

It is important to note that the order of operations is essential. For example, if the producer places the item in the queue after incrementing fullCount, the consumer may obtain the item before it has been written. If the producer places the item in the queue before decrementing emptyCount, the producer might exceed the size limit of the queue.


Monitor : A monitor is like a building that contains one special room that can be occupied by only one thread at a time. The room usually contains some data. From the time a thread enters this room to the time it leaves, it has exclusive access to any data in the room. Entering the monitor building is called "entering the monitor." Entering the special room inside the building is called "acquiring the monitor." Occupying the room is called "owning the monitor," and leaving the room is called "releasing the monitor." Leaving the entire building is called "exiting the monitor."

Java's monitor supports two kinds of thread synchronization: mutual exclusion and cooperation. Mutual exclusion, which is supported in the Java virtual machine via object locks, enables multiple threads to independently work on shared data without interfering with each other. Cooperation, which is supported in the Java virtual machine via the wait and notify methods of class Object, enables threads to work together towards a common goal.

The form of monitor used by the Java virtual machine is called a "Wait and Notify" monitor. (It is also sometimes called a "Signal and Continue" monitor.) In this kind of monitor, a thread that currently owns the monitor can suspend itself inside the monitor by executing a wait command. When a thread executes a wait, it releases the monitor and enters a wait set. The thread will stay suspended in the wait set until some time after another thread executes a notify command inside the monitor. When a thread executes a notify, it continues to own the monitor until it releases the monitor of its own accord, either by executing a wait or by completing the monitor region. After the notifying thread has released the monitor, the waiting thread will be resurrected and will reacquire the monitor.


The kind of monitor used in the Java virtual machine is sometimes called a Signal and Continue monitor because after a thread does a notify (the signal) it retains ownership of the monitor and continues executing the monitor region (the continue). At some later time, the notifying thread releases the monitor and a waiting thread is resurrected. Presumably, the waiting thread suspended itself because the data protected by the monitor wasn't in a state that would allow the thread to continue doing useful work. Also, the notifying thread presumably executed the notify command after it had placed the data protected by the monitor into the state desired by the waiting thread. But because the notifying thread continued, it may have altered the state after the notify such that the waiting thread still can't do useful work. Alternatively, a third thread may have acquired the monitor after the notifying thread released it but before the waiting thread acquired it, and the third thread may have changed the state of the protected data. As a result, a notify must often be considered by waiting threads merely as a hint that the desired state may exist. Each time a waiting thread is resurrected, it may need to check the state again to determine whether it can move forward and do useful work. If it finds the data still isn't in the desired state, the thread could execute another wait or give up and exit the monitor.



Blocking Queue: Suppose we have one producer thread and one or more consumer threads. The producer thread gets a data object and then it gets exclusive access to the queue. It then enqueues the data object and sleeps for 100 milliseconds. The consumer thread loops, getting exclusive access to the queue, and checking to see if there are any objects to dequeue. If there are, the objects are dequeued and processed. If there is not, the thread sleeps for 100 milliseconds and then tries again.


The down side to this is that if there is a lot of time between the enqueueing of objects, the consumer thread will spend a lot of CPU time just checking to see if there is anything to do. It would be more efficient if the consumer thread was blocked from executing until there was an object in the queue.

This is the purpose of a blocking queue. With this type of queue, the thread that calls the Dequeue method is blocked until there is an object in the queue.


Future: A Future represents the result of an asynchronous computation. Methods are provided to check if the computation is complete, to wait for its completion, and to retrieve the result of the computation.