Sunday, March 8, 2015

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.svg
"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.

No comments:

Post a Comment