Reentrant lock & field in interface

I looked back to my last week's unsolved problem in this blog:

Given the interface below, implement a task scheduler.

interface Task {
    void Run();
    Set<Task> GetDependencies();
}

Additionally, the task scheduler should follow two rules.
1. Each task may only be executed once.
2. The dependencies of a task should be executed before the task itself.

Reentrant lock
So the question is, what if we run it in parallel. Naturally I thought about concurrency. However, when I tried to write a synchronized method for the problem, I realized that there is a recursion in my method. So I wondered: will it cause a deadlock?

The answer is no.

Recall that a thread cannot acquire a lock owned by another thread. But a thread can acquire a lock that it already owns. Allowing a thread to acquire the same lock more than once enables reentrant synchronization. This describes a situation where synchronized code, directly or indirectly, invokes a method that also contains synchronized code, and both sets of code use the same lock. Without reentrant synchronization, synchronized code would have to take many additional precautions to avoid having a thread cause itself to block.

In short, if I have a synchronized recursion method, when the method invokes itself again, it will transfer the lock to the recursive method, executing that first, then the lock is returned to the current method. Java does provide an explicit ReentrantLock class, if you are interested, take a look at the source code.

The fields in an interface
Since I need to implement the Task interface provided by the problem statement for test, I wrote a Trsk class. When I tried to print the label I defined in the Trsk class of a instance of the Task interface,  I got an error. So I thought, ok, maybe I should add the field label into the Task. However, for an interface, all fields are automatically public, static and final, and all methods are public.
There are two solutions to solve the problem:
1. Declare a Trsk object in my TaskSechduler class;
2. Cast Task to Trsk object when I need to access the Trsk fields and methods.

I choose the second one.

Back to the problem
Here is the simple dependency graph of my test code. a -> b indicates a is dependent on b.

So this problem, I wrote a synchronized method, and another class ExecuteTask and created two Threads to run. And here is the result:

Yep, Thread 1 never gets a chance to executing any Tasks. Since in my random test graph, everyone is sort of dependent on everyone, Task 6 (which doesn't depend on anyone) is executed first. And since it is in Thread 2, which leads Thread 2 always acquires the lock and executes tasks, until all tasks are executed. And when it comes to Thread 1's turn, it realizes that there is nothing left (Thanks Thread 2 for being very hard working!).

In order to let Thread 1 to get some job, I removed "synchronized" keyword:

First run

Second run

Third run

Now it's all about who is more aggressive. However, do notice that this will cause some order problems since we have no idea who is accessing the recourse.

The intuition here is that when you need to run parallel, be careful if you have some rules on the order.

The code

public class TaskSchedulerParallel {
 Set executed;
 Set inProcess;
 public TaskSchedulerParallel(){
  executed = new HashSet();
  //executed = Collections.synchronizedSet(new HashSet());
  inProcess = new HashSet();
  //inProcess = Collections.synchronizedSet(new HashSet());
 }
 public void schedule(Task t){
 //public synchronized void schedule(Task t) {
  inProcess.add(t);
  /*for(Task ta : executed)
   System.out.print(((Trsk)ta).label + " ");
  System.out.println();*/
  for(Task dep : t.GetDependencies()){
   if(!executed.contains(dep) && !inProcess.contains(dep))
    schedule(dep);
  }
  if(executed.add(t)){
   t.Run();
   inProcess.remove(t);
  }
 }
}
public class ExecuteTask implements Runnable{
 private TaskSchedulerParallel tsp;
 private Set toExecute;
 private int label;
 public ExecuteTask(int label, TaskSchedulerParallel tsp, Set tasks){
  this.tsp = tsp;
  toExecute = tasks;
  this.label = label;
 }
 @Override
 public void run() {
  System.out.println("Thread: " + label);
  for(Task t : toExecute){
   tsp.schedule(t);
  }
  System.out.println("Thread " + label + " finishes!");
 }
}
public class Trsk implements Task{
 int label;
 Set dependencies = new HashSet();
 public Trsk(int label){
  this.label = label;
 }
 @Override
 public void Run() {
  System.out.println(label + " is running!");
 }
 public boolean addDependency(Task t){
  return dependencies.add(t);
 }
 @Override
 public Set GetDependencies() {
  return dependencies;
 }
 

}
public class TaskTester {

 public static void main(String[] args) {
  TaskSchedulerParallel tsp = new TaskSchedulerParallel();
  Task t1 = new Trsk(1);
  Task t2 = new Trsk(2);
  Task t3 = new Trsk(3);
  Task t4 = new Trsk(4);
  Task t5 = new Trsk(5);
  Task t6 = new Trsk(6);
  t1.addDependency(t2);
  t1.addDependency(t4);
  t2.addDependency(t3);
  t3.addDependency(t4);
  t3.addDependency(t5);
  t4.addDependency(t6);
  t5.addDependency(t1);
  Set s1 = new HashSet();
  s1.add(t1);
  s1.add(t2);
  s1.add(t3);
  Set s2 = new HashSet();
  s2.add(t4);
  s2.add(t5);
  s2.add(t6);
  (new Thread(new ExecuteTask(1, tsp, s1))).start();
  (new Thread(new ExecuteTask(2, tsp, s2))).start();

 }

}

Task Scheduler

Given the interface below, implement a task scheduler.

interface Task {
    void Run();
    Set<Task> GetDependencies();
}

Additionally, the task scheduler should follow two rules.
1. Each task may only be executed once.
2. The dependencies of a task should be executed before the task itself.

This one is quite straightforward. Given a set of task, using a DFS approach.

public class TaskScheduler {
 Set executed;
 Set allTasks;
 Set inProcess;
 public TaskScheduler(Set tasks){
  allTasks = tasks;
  executed = new HashSet();
  inProcess = new HashSet();
 }
 public void schedule(Set allTasks){
  for(Task t : allTasks){
   if(executed.contains(t))
    continue;
   if(!inProcess.isEmpty() && inProcess.contains(t)){
    t.Run();
    inProcess.remove(t);
    executed.add(t);
    continue;
   }
   inProcess.add(t);
   schedule(t.GetDependencies());
   t.Run();
   inProcess.remove(t);
   executed.add(t);
  }
 }
}

Now comes the second one:

implement the same task scheduler with parallel task execution.

So I am thinking, maybe it needs a concurrency approach. So I go back to my old posts and tried to come up an approach. Since all dependencies should be executed first, I use a stack to schedule all tasks. The scheduler will first add all its dependencies to the stack. Then I use a releaseCount to track the available resources. If releaseCount == 0 or if the current Task is not on top of the stack, it should wait for its turn. Pop the task out and execute it, while executing, the task has acquired the resource, so releaseCount should decrement by one, after executing, the task should release the resource, so releaseCount increment by one.

However, I am not sure if my approach is correct, so I have an open question on Stackoverflow.

public class TaskSchedulerParallel {
 Set executed;
 Stack scheduler;
 int releaseCount;
 //number of parallel nodes
 public TaskSchedulerParallel(int N){
  executed = new HashSet();
  scheduler = new Stack();
  releaseCount = N;
 }
 public synchronized void schedule(Task t) throws InterruptedException {
  scheduler.push(t);
  for(Task dep : t.GetDependencies()){
   if(!executed.contains(dep) && !scheduler.contains(dep))
    schedule(dep);
  }
  if(releaseCount == 0 || (!scheduler.isEmpty() && scheduler.peek() != t))
   t.wait();
  releaseCount--;
  scheduler.pop();
  t.Run();
  executed.add(t);
  releaseCount++;
 }
 

}

Mutex and spinlocks

Mutex:
Short for mutual exclusion object. Mutex is kind of a key to use any resources in the system. If you have mutex, you can use the resource. Any thread that needs the resource must lock the mutex from other threads while it is using the resource. The mutex is set to unlock when the data is no longer needed or the routine is finished.

In java, this can be implemented by simply using a "synchronized" key word.

Java Class Semaphore
A semaphore maintains a set of permits. Each acquire() blocks if necessary until a permit is available, and then takes it. Each release() adds a permit, Semaphore just keeps a count of the number available and acts accordingly.
A semaphore initialized to one, and which is used such that it only has at most one permit available, can serve as a mutual exclusion lock. It is also known as a binary semaphore, because it only has two states: one permit available, zero not, or vice versa. When used in this way, the binary semaphore has the property that the "lock" can be released by a thread other than the owner.


Spinlock:
Spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available.

In Java, this can be implemented by using a guarded block.

public synchronized String take(){
  //wait for the producer
  //to send the message
  while(empty){
   try{
    System.out.println("Waiting for producer to send the message...");
    wait();
   }catch(InterruptedException e){};
  }
  empty = true;
  //Notify producer that
  //status has changed
  notifyAll();
  return message;
 }

In the above example, while another thread is using the resource, the boolean empty = true, the current thread will wait until the empty is set to false. Then it will reset the empty to true and notify all other threads that it is using the resource after acquiring the resource.
The "synchronized" keyword in the above example allows multiple threads to share the same resource (object), however, if one thread is executing the take() method, all other threads must wait until the current thread finishes executing.

FIFOMutex
The following snippet is hacked from Java doc, which uses a queue to perform a FIFO order for each thread to access the resource. Basically, if you are not on top of the queue, wait for your turn. :)

public class FIFOMutex {
 private final AtomicBoolean locked = new AtomicBoolean(false);
 //The head of the queue is that element that has been on the queue the longest time. 
 //The tail of the queue is that element that has been on the queue the shortest time
 private final Queue waiters = new ConcurrentLinkedQueue();
 
 public void lock(){
  boolean wasInterrupted = false;
  //currentThread(): 
  //Returns a reference to the currently executing thread object.
  Thread current = Thread.currentThread();
  waiters.add(current);
  //if already locked or it is not the first thread in the queue
  while(waiters.peek() != current || !locked.compareAndSet(false, true)){
   //Disables the current thread for 
   //thread scheduling purposes unless the permit is available
   LockSupport.park(this);
   if(Thread.interrupted())//ignore interrupts while waiting
    wasInterrupted = true;
  }
  //remove head, inherent from AbstractQueue
  //throw an exception if queue is empty
  //poll() will return null if empty
  waiters.remove();
  //interrupt the thread that was supposed to be interrupted while waiting
  if(wasInterrupted)
   current.interrupt();
 }
 public void unlock(){
  locked.set(false);
  //Makes available the permit for the given thread, 
  //if it was not already available.
  LockSupport.unpark(waiters.peek());
 }

}

Here is another method stolen from here. I personally don't like this version, since its not as clear as the first one.

/**
 * the following code uses a ReentrantLock to queue up the threads, 
 * the fairness policy is applied so as to implement the FIFO nature
 * If releaseCount is zero, that means all threads on the queue is 
 * waiting for the lock
 * when release() is invoked, increase the releaseCount to release the number 
 * of threads
 * @author shirleyyoung
 *
 */

public class ResourceWaitQueue {
 //if using fairness policy
 //when set true, the lock favors granting access to the longest-waiting thread. 
 //Otherwise this lock does not guarantee any particular access order
 //use fair locks may cause the program to be slower, 
 //often much slower than those using the default setting, 
 //but have smaller variances in times to obtain locks and guarantee lack of starvation
 private final ReentrantLock lock = new ReentrantLock(true);
 //Returns a Condition instance for use with this Lock instance.
 private final Condition goodToGo = lock.newCondition();
 private int releaseCount = 0;
 
 public final void await() throws InterruptedException{
  lock.lock();
  try{
   while(releaseCount == 0)
    //Causes the current thread to wait 
    //until it is signaled or interrupted.
    goodToGo.await();
   if(--releaseCount > 0)
    //Wakes up one waiting thread.
    //If any threads are waiting on this condition 
    //then one is selected for waking up. 
    //That thread must then re-acquire the 
    //lock before returning from await.
    goodToGo.signal();
  } finally {
   lock.unlock();
  }
 }
 public final void release(){
  lock.lock();
  try{
   releaseCount++;
   goodToGo.signal();
  } finally{
   lock.unlock();
  }
 }
 
}

Thread -> multithread -> Locks

Thread
A thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler (typically as part of an OS).

A thread goes through various stages in its life cycle.

Image source: http://www.tutorialspoint.com/java/java_multithreading.htm

New: A new thread begins its life cycle in the new state. It remains in its state until the program starts the thread. It is also referred to as a born thread. 

Runnable: After a newly born thread is started, the thread becomes runnable. A thread in this state is considered to be executing its task. 

Waiting: Sometimes, a thread transitions to the waiting state while the thread wait for another thread to perform a task. A thread transitions back to the runnable state only when another thread signals the waiting thread to continue executing. 

Time waiting: A runnable thread can enter the timed waiting state for a specified interval of time. A thread in this state transitions back to the runnable state when that time interval expires or when the event it is waiting for occurs. 

Terminated: A runnable thread enters the terminated state when it completes its task or otherwise terminates. 

There are two basic strategies for using Thread objects to create a concurrent application.

• To directly control thread creation and management, simply instantiate Thread each time the application needs to initiate an asynchronous task. 
• To abstract thread management from the rest of your application, pass the application's tasks to an executor. 

There are two ways to run a Thread instance:

1. A runnable object.

public class HelloRunnable implements Runnable{
 /**
  * First, provide a Runnable object. The runnable interface defines a single method, 
  * run(), meant to contain the code executed in the thread. 
  */
 public void run(){
  System.out.println("Hello Shirley! -- from a thread");
 }

 public static void main(String[] args) {
  (new Thread(new HelloRunnable())).start();
 }

}

2. A subclass Thread.

public class HelloThread extends Thread{
  public void run(){
   System.out.println("Hello Shirley! -- from another thread");
  }

 public static void main(String[] args) {
  (new HelloThread()).start();

 }
}

The first way, which employs a Runnable object, is more general, because the Runnable object can subclass a class other than Thread. The second way is easier to use, but is limited by the fact that the task class must be a descendant of Thread.

Thread.sleep causes the current thread to suspend execution for a specified period. this is an efficient means of making processor time available to other threads of an application or other applications that might be running on a computer system.

/**
  * throws InterruptedException, this is an exception that 
  * sleep throws when another thread interrupts the current 
  * thread while sleep is active. 
  * @throws InterruptedException
  */
 public void print() throws InterruptedException{
  String importantInfo[] = {
    "Shirley is awesome", 
    "Shirley is smart", 
    "The above two statements are not true",
    "The above statement may not be true"
  };
  for(int i = 0; i < importantInfo.length; i++){
   //need to throw exception
   //otherwise use try block
   //sleep 0.1 seconds
   Thread.sleep(100);
   System.out.println(importantInfo[i]);
  }
 }
  public void run() {
   try {
   print();
   } catch(InterruptedException e){
    System.err.println(e);
   }
  }

 public static void main(String[] args) {
  (new HelloThread()).start();

 }

Here is a simple thread example.

public class SimpleTreads {
 static void threadMessage(String message){
  String threadName = Thread.currentThread().getName();
  System.out.format("%s: %s%n", threadName, message);
 }
 private static class MessageLoop implements Runnable{
  public void run(){
   String importantInfo[] = {
     "Shirley is awesome", 
     "Shirley is smart", 
     "The above two statements are not true",
     "The above statement may not be true"
   };
   try{
    for(int i = 0; i < importantInfo.length; i++){
     //this is a stupid thread the main thread to 
     //let it execute first but runs very slow
     Thread.sleep(4000);
     threadMessage(importantInfo[i]);
    } 
   } catch (InterruptedException e){
    threadMessage("I was interrupted...-_-||");
   }
  }
 }

 public static void main(String[] args) throws InterruptedException{
  //the longest time the main thread is willing to wait
  //before intrupt the executing thread
  long patience = 100 * 60;
  threadMessage("Starting MessageLoop thread");
  long startTime = System.currentTimeMillis();
  Thread t = new Thread(new MessageLoop());
  t.start();
  while(t.isAlive()){
   threadMessage("I am waiting...");
   //wait 500 ms for t to execute and die...
   t.join(1000);
   //after 500 ms, main comes back in
   //if t is still alive and main has waited longer than its patience
   if(((System.currentTimeMillis() - startTime) > patience) && t.isAlive()){
    threadMessage("I am tired of waiting!");
    t.interrupt();
    //t.join();
   }
  }
  threadMessage("I told you to run faster!");
 }

}

Multithreading

When there are two or more threads within a program, there may be a situation when multiple  threads try to access the same resource and finally they can produce unforeseen result due to concurrency issue. Thus there is a need to synchronize the action of multiple threads and make sure that only one thread can access the resource at a given point in time. This is implemented using a concept called intrinsic lock/monitor locks/monitors. Monitor enforce exclusive access to an object's state and establish happens-before relationships that are essential to visibility. Each object in Java is associated with a monitor. By convention, a thread that needs exclusive and consistent access to an object's fields has to acquire the object's intrinsic lock before accessing them(lock), and then release the intrinsic lock when it's done with them(unlock). As long as a thread owns an intrinsic lock, no other thread can acquire the same lock. The other thread will block when it attempts to acquire the lock.
When a thread releases an intrinsic lock, a happens-before relationship is established between that action and any subsequent acquisition of the same lock.

Example

The first example is an example of creating threads without synchronization. 

public class GuessANumber extends Thread {
 private int number;
 public GuessANumber(int number) {
  this.number = number;
 }
 public synchronized void run() {
  int counter = 0;
  int guess = 0;
  do {
   guess = (int) (Math.random() * 10 + 1);
   System.out.println(this.getName() + " guesses " + guess);
   counter++;
  } while (guess != number);
  System.out.println("** Correct! " + this.getName() + " in " + counter + " guesses. **");
 }

}

public class ThreadTester {

 public static void main(String[] args) {

                System.out.println("\nStarting guess number thread first...");
  Thread thread3 = new GuessANumber(1);
  thread3.start();
  System.out.println("Starting guess number thread second...");
  Thread thread4 = new GuessANumber(9);
  thread4.start();
  try {
   //The current thread invokes this method on a second thread, 
   //causing the current thread to block 
   //until the second thread terminates or the specified number 
   //of milliseconds passes.
   thread3.join();
   thread4.join();
  }
  catch (InterruptedException e) {
   System.out.println("Thread interrupted. ");
  }
  System.out.println("Ending program");
  
 }

}

And the result looks like:

As you can see, it runs two threads simultaneously, and every time we run it, it produces different result based on CPU availability to a thread.

Now if we modify the code and a simple magic word "synchronized" to our run method:

public class GuessANumber2 {
 private int number;
 private String name;
 public GuessANumber2(int n, String name) {
  number = n;
  this.name = name;
 }
 public void guessANumber () {
  int counter = 0;
  int guess = 0;
  do {
   guess = (int) (Math.random() * 10 + 1);
   System.out.println(name + " guesses " + guess);
   counter++;
  } while (guess != number);
  System.out.println("** " + name + " got correct answer in " + counter + " guesses. **"); 
 }

}
public class GuessThread extends Thread {
 private Thread t;
 private String threadName;
 GuessANumber2 gan;
 GuessThread(String name, GuessANumber2 gan) {
  threadName = name;
  this.gan = gan;
 }
 public void run() {
  //***adding synchronized***
  synchronized(gan) {
   gan.guessANumber();
  }
  System.out.println("Thread " +  threadName + " exiting.");
 }
 public void start() {
  System.out.println("Starting " +  threadName );
       if (t == null)
       {
          t = new Thread (this, threadName);
          t.start ();
       }
 }
}

The result would become:

Neat! :)

Thread Interference
Interference happens when two operations, running in different threads, but acting on the same data, interleave. This means that the two operations consist of multiple steps, and the sequences of steps overlap. Interleaving is unpredictable.

happens-before: A guarantee that memory writes by one specific statement are visible to another specific statement. If a field is shared by two threads, without happens-before relationship, the change of the field made by thread A may not be visible by thread B, thus B may output an unchanged field (See here).

When a statement invokes Thread.start, every statement that has a happens-before relationship with that statement also has a happens-before relationship with every statement executed by the new thread.
When a thread terminates and causes a Thread.join in another thread to return, then all the statements executed by the terminated thread have a happens-before relationship with all the statements following the successful join.

Synchronized method: 
When one thread is executing a synchronized method for an object, all other threads that invoke synchronized methods for the same object block until the first thread is done with the object.
When a synchronized method exits, it automatically establishes a happens-before relationship with any subsequent invocation of a synchronized method for the same object. This guarantees that changes to the state of the object are visible to all threads.
Constructors CANNOT be synchronized.

When a thread invokes a synchronized method, it automatically acquires the intrinsic lock for that method's object and releases it when the method returns. The lock release occurs even if the return was caused by an uncaught exception.
When a static synchronized method is invoked, the thread acquires the intrinsic lock for the Class object associated with the class. Thus access to class's static fields is controlled by a lock that is distinct from the lock for any instance of the class.

Synchronized statements:
Must specify the object that provides the intrinsic lock.

public void run() {
  //synchronized "gan" object, which is an instance of GuessANumber2
  synchronized(gan) {
   gan.guessANumber();
  }
  System.out.println("Thread " +  threadName + " exiting.");
 }

Reentrant Synchronization
Allowing a thread to acquire the same lock more than once. This describes a situation where synchronized code, directly or indirectly, invokes a method that also contains synchronized code, and both sets of code use the same lock (two methods is invoked by same object). Without reentrant synchronization, synchronized code would have to take many additional precautions to avoid having a thread cause itself to block.

Atomic Access
An atomic action is one that effectively happens all at once. It cannot stop in the middle" it either happens completely, or it doesn't happen at all. No side effects of an atomic action are visible until the action is complete.

• Reads and writes are atomic for reference variables and for most primitive variables(except long and double). 
• Reads and writes are atomic for all variables declared volatile(including long and double)

volatile: variable's value will be modified by different threads.

Atomic actions cannot be interleaved. Using volatile variables reduces the risk of memory consistency errors, because any write to a volatile variable establishes a happens-before relationship with subsequent reads of that same variable. Changes to a volatile variable are always visible to other threads. When a thread reads a volatile variable, it sees not just the latest change to the volatile, but also the side effects of the code that led up the change.


Deadlock 
Deadlock: In concurrent programming, a deadlock is a situation in which two or more competing actions are each waiting for the other to finish, and thus neither ever does.

In order for a deadlock to occur, there are four conditions:

1. Mutual Exclusion: Only one process can use a resource at a given time;
2. Hold and Wait: Processes already holding a resource can request new ones.
3. No Preemption: One process cannot forcibly remove another process' resource.
4. Circular Wait: Two or more precesses form a circular chain where each process is waiting on another resource in the chain.

"Process deadlock" by The source code of this SVG is valid. This vector image was created with Dia by VolodyA! V Anarhist. - Own work. Licensed under FAL via Wikimedia Commons: 

The above example: Both processes need resources to continue execn. P1 requires additional resource R1 and is in possession of resource R2, P2 requires additional resource R2 and is in possession of R1; neither process can continue.

An example:

public class DeadLock {
 static class Friend{
  private final String name;
  public Friend(String name){
   this.name = name;
  }
  public String getName(){
   return this.name;
  }
  public synchronized void bow(Friend bower){
   System.out.format("%s: %s" + " has bowed to me!%n", this.name, bower.getName());
   //bower wants to access bowBack but it is waiting for its bow to exit
   bower.bowBack(this);
  }
  public synchronized void bowBack(Friend bower){
   System.out.format("%s: %s" + " has bowed back to me!%n", this.name, bower.getName());
  }
 }

 public static void main(String[] args) {
  final Friend alphonse = new Friend("Alphonse");
  final Friend gaston = new Friend("Gaston");
  new Thread (new Runnable() {
   public void run(){
    alphonse.bow(gaston);
   }
  }).start();
  new Thread(new Runnable (){
   
   public void run(){
    gaston.bow(alphonse);
   }
  }).start();
  
 }
}

Deadlock prevention
Essentially entails removing one of the above conditions, but many of these conditions are difficult to satisfy. For instance, removing #1 is difficult because many of the resources can only be used by one process at a time (e.g., printers). Algorithms that avoid mutual exclusion are called non-blocking synchronization. Most deadlock prevention algorithms focus on avoiding condition #4, circular wait. Approaches that avoid circular waits include disabling interrupts during critical sections and using a hierarchy to determine a partial ordering of resources. If no obvious hierarchy exists, even the memory address of resources has been used to determine ordering and resources are requested in the increasing order of enumeration.


Starvation and Livelock
Starvation: 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, if one thread invokes this method frequently, other threads that also need frequent synchronized access to 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.

Guarded Blocks
Threads often have to coordinate their actions. The most common coordination idiom is the guarded block. Such a block begins by polling a condition that must be true before the block can proceed.
A more efficient guard invokes Object.wait to suspend the current thread. When wait is invoked, the thread releases the lock and suspends execution. At some future time, another thread will acquire the same lock and invoke Object.notifyAll, informing all threads waiting on that lock that it has acquired the lock. Some time after the second thread has released the lock, the first thread reacquires the lock and resumes by returning from the invocation of wait.

Below is an example from the Oracle tutorial. Both Producer and Consumer objects access the Drop object, and create two threads. In the take method, the guarded block only allows the method to proceed if the producer finishes sending message (empty = false). In the put method, the guarded block proceeds when the consumer finishes receiving the message(empty = true). Two threads are coordinating with each other by the two guarded blocks.

public class Drop {

 private  String message;
 //True if consumer should wait
 //for the producer to send message, 
 //false if producer should wait 
 //for consumer to retrieve message
 private boolean empty = true;
 public synchronized String take(){
  //wait for the producer
  //to send the message
  while(empty){
   try{
    System.out.println("Waiting for producer to send the message...");
    wait();
   }catch(InterruptedException e){};
  }
  empty = true;
  //Notify producer that
  //status has changed
  notifyAll();
  return message;
 }
 
 public synchronized void put(String message){
  while(!empty){
   try{
    System.out.println("Waiting for consumer to receive the message...");
    wait();
   }catch (InterruptedException e) {};
  }
  empty = false;
  this.message = message;
  //notify consumer that status has changed
  notifyAll();
 }

}
import java.util.*;
/**
 * Producer sends a series of familiar messages
 * The string "DONE" indicates that all messages have been sent. 
 * To simulate the unpredictable nature of real-world applications, 
 * the producer thread pauses for random intervals between messages.
 * @author shirleyyoung
 *
 */
public class Producer implements Runnable{
 private Drop drop;
 public Producer(Drop drop){
  this.drop = drop;
 }
 public void run(){
  String importantInfo[] = {
    "Shirley is awesome", 
    "Shirley is smart", 
    "The above two statements are not true",
    "The above statement may not be true"
  };
  Random random = new Random();
  for(int i = 0; i < importantInfo.length; i++){
   drop.put(importantInfo[i]);
   System.out.println("MESSAGE SENT");
   try{
    Thread.sleep(random.nextInt(5000));
   } catch(InterruptedException e){};
  }
  drop.put("DONE");
 }

}
/**
 * simply retrieves the messages and prints them out, 
 * until it retrieves the "DONE" string. 
 * This thread also pauses for random intervals.
 * @author shirleyyoung
 *
 */
import java.util.*;
public class Consumer implements Runnable{
 private Drop drop;
 public Consumer(Drop drop){
  this.drop = drop;
 }
 public void run(){
  Random random = new Random();
  for(String message = drop.take(); !message.equals("DONE"); message = drop.take()){
   System.out.format("MESSAGE RECEIVED: %s%n", message);
   try{
    Thread.sleep(random.nextInt(5000));
   }catch(InterruptedException e){};
  }
 }

}
public class ProducerConsumerExample {

 public static void main(String[] args) {
  Drop drop = new Drop();
  (new Thread(new Producer(drop))).start();
  (new Thread(new Consumer(drop))).start();

 }

}

Process and thread

A process can be thought of as an instance of a program in execution. A process generally has a complete, private set of basic run-time resources(CPU time, memory, etc); in particular, each process is executed in a separate memory space. Processes are often seen as synonymous with programs or applications. One process CANNOT access the variables and data structures of another process. If you wish to access another process' resources, Inter Process Communication(IPC) resources have to be used such as pipes, files, sockets, etc.

Threads exist within a process: every process has at least one thread. Threads share the process's resources, including memory and open files. A process can have multiple threads. A key difference between processes and threads is that multiple threads share parts of their state. Typically, one allows multiple threads to read and write the same memory (no processes can directly access the memory of another process). However, each thread still has its own registers and its own stack, but other threads can read and write the stack memory.

A thread is a particular execution path of a process; when one thread modifies a process resource, the change is immediately visible to sibling threads.