Wednesday, October 21, 2015

[Multithreading - Deadlock]


DeadLock
Semaphore
Mutex
spin-lock
Difference between Synchronized method and Synchronized block?

Synchronized method: Methods of a class which need to be synchronized are declared with “synchronized” keyword. If one thread is executing a synchronized method , all other threads which want to execute any of the synchronized method on the same object get blocked.
public class SynchronizedMethod
{
          public synchronized returntype Method1()
          {...}
          public synchronized retruntype Method2()
          {...}
}
Synchronized block: It provides the synchronization for a group of statements rahter than a method as a whole. It needs to provide the object which these synchronized statements will be applied, unlike in a synchronized method. This is to make sure that the object will not be alterted by other threads when executing the block by setting the monitor to the monitor of he object
synchronized(this) // on this object
{
          ….
}

public class WaitNotifyTest {
   public static void main(String[] args) {
       Message msg = new Message("process it");
       Waiter waiter = new Waiter(msg);
       new Thread(waiter,"waiter").start();
        
       Waiter waiter1 = new Waiter(msg);
       new Thread(waiter1, "waiter1").start();
        
       Notifier notifier = new Notifier(msg);
       new Thread(notifier, "notifier").start();
       System.out.println("All the threads are started");
   }
}
waiter waiting to get notified at time:1356318734009
waiter1 waiting to get notified at time:1356318734010
All the threads are started
notifier started
waiter waiter thread got notified at time:1356318735011
waiter processed: notifier Notifier work done


public class Waiter implements Runnable{
    
   private Message msg;
    
   public Waiter(Message m){
       this.msg=m;
   }
   @Override
   public void run() {
       String name = Thread.currentThread().getName();
       synchronized (msg) {
           try{
               System.out.println(name+" waiting to get notified at time:"+System.currentTimeMillis());
               msg.wait();
           }catch(InterruptedException e){
               e.printStackTrace();
           }
           System.out.println(name+" waiter thread got notified at time:"+System.currentTimeMillis());
           //process the message now
           System.out.println(name+" processed: "+msg.getMsg());
       }
   }
}


public class Notifier implements Runnable {
   private Message msg;
    
   public Notifier(Message msg) {
       this.msg = msg;
   }
   @Override
   public void run() {
       String name = Thread.currentThread().getName();
       System.out.println(name+" started");
       try {
           Thread.sleep(1000);
           synchronized (msg) {
               msg.setMsg(name+" Notifier work done");
               msg.notify();
               // msg.notifyAll();
           }
       } catch (InterruptedException e) {
           e.printStackTrace();
       }
        
   }
}
Deadlock conditions

1. no preemption
2. shared resource: hold and wait
3. one lock: mututal inclusion
4.circular wiat

i.mutual exclusion: only one process can use a resource at a given time
ii. hold and wait: process already holding a reosurce can reuest new ones
iii. no preemption: one process cannot forcibly remvoe another process’s resource
iV. circular wait: two or more process form a cicular chain where each process is waiting another resource in the chain
Deadlock Prevention

Most deadlock prevention algorithms foucs on avoiding condition #4: circular wait.
Thread VS process

process independently address space, cannot access other’s stack
thread share address space, modify other’s stack
1.an instance of a program in execution
2.Each process is an independent entity to which system resources (CPU time, memory, etc.) are allocated and each process is executed in a separate address space
3.One process cannot access the variables and data structures of another process.
4.If you wish to access another process’ resources, inter-process communications have to be used such as pipes, files, sockets etc.
5.A process can have multiple threads
1. uses the same stack space of a process, t multiple threads share parts of their state
2.one allows multiple threads to read and write the same memory (no processes can directly access the memory of another process
3.each thread still has its own registers and its own stack, but other threads can read and write the stack memory
4.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

A thread: a flow of execution inside a process, share address space (don’t confuse with stack memory, every thread has its own stack ,store local data )

A process: a program, more state information, memory ,distinct address space
independent to each other, has at least one thread inside

Threads are used for small tasks, whereas processes are used for more 'heavyweight' tasks – basically the execution of applications.
Another difference between a thread and a process is that threads within the same process share the same address space, whereas different processes do not.
Time spent in a context switch

context switch : swap thread
T1 lock -> T1 release lock -> T2 get lock

A context switch is the time spent switching between two processes (e.g., bringing a waiting process into execution and sending an execution process into waiting / terminate state )

This happens in multi-tasking. The operating system must
bring the state information of waiting processes into memory and
save the state information of the running process

In order to solve this porblem, we would like to record timestamps of the last and first instruction of the swapping processes.
The context switching time would be the difference in the timestamps between two processes.

Let’s take an easy example: Assume there are only two processes, P1 and P2.
P1 is executing and P2 is waiting for execution. At some point, the OS must swap P1 and P2 - let’s assume it happens at teh Nth instruction of P1. So, the context switch time for this would be Time_stamp(P2_1) - Time_stamp(P1_N)

Easy enough.

PROBLEM1: The tricky part is this: how do we know when this swapping occurs? Swapping is governed by the scheduling alogrithm of the OS. We can not, of course, record the timestamp of every instruction in the process.

PROBLEM2: another issue is there are many kernel level threads which are also doing context switches, and the user does not have any control over them.

Overall, we can say that this is mostly an approximate calculation which depends on the underlying OS. One approximation could be to record the end instruction timestamp of a process and start timestamp of a process and waiting time in queue.

It this total time of execution of all the processes was T, then the context switch time = T - (SUM for all processes (waiting time + execution time))
Singleton design pattern


acquire()
release()
Thread-safe(Synchronized) and Exception-safe(notify) try catch


Not thread-safe
public class singleton
{
         singleton s;
         // Private constructor
        private singleton(){} // override the default construtor
        public singleton getInstance()
        {
                    if (s== null)
                           s = new singleton();
                    return s;
         }

}


thread-Safe
public classs singelton
{
        singleton s;
        // private constructor
        private signleton(){}
        public synchronized singleton getInstance()
        {
                    if (s== null)
                            s=  new singleton();
                    return s;
         }
}

OR

public class singleton
{
          singleton s;
          // private construtor
           private singleton(){}
          public singleton getIsntance()
          {
                     Synchronized(this) {
                             if (s == null )
                                    s = new singleton();
                             return;
                     }
          }
}



public class singleton
{
            singleton s;
            Lock lock = new ReentantLock();
            // private ocnstructor
           private singleton(){};
          public singleton getInstance(){
                       // /* if object is not initialized, acquire lock */
                       if (s== null)
                      {
                              lock.lock(); // acquire lock
// /* If two threads simultaneously check and pass the first “if” * condition, then only the one who acquired the lock first * should create the instance */
                              if ( s== null)
                                       s = new singleton();
                               lock.unlock(); // release lock
                        }     
          }
}

Reference: https://hellosmallworld123.wordpress.com/2014/05/21/threads-and-locks/
DEADLOCK EXAMPLE
DiningPholisphers

Problem 1: This application deadlocks when all philosophers have simultaneously picked up their left fork: Because no right fork is available to any philosopher, no philosopher can eat

Solution1: One solution is to add a timeout to the waiting: If a philosopher is not able to eat within a predetermined amount of time after acquiring the first fork, then the philosopher drops the fork and tries again.

Problem2: The flaw with this solution is that it’s possible for one or more philosophers to starve because they never acquire both forks. This is referred to as livelock.

Solution2:The best solution requires a very simple change to the application. Instead of having all the philosophers pick up the left fork first, have one of the philosophers pick up the right fork first:

public class DiningPholisphers
{
       // Field
      // Each “fork” is just an object we synchronize on
      private Object[] forks;
      private PhilosophersThread[] philosopherThreads;// Thread Example
      

      // Constructor
      // prepare the forks and philosophers
     private DiningPholosophers( int num )
     {
             forks = new Object[num];
            philosopherThreads = new PhilosophersThread[ num];
             for (int i = 0 ; i < num ; i ++ )
             {
                         forks[i] = new Object();
                         int fork1 = i;
                        int fork2 = (i+1)%num;
                        philosopherThreads[i] = new PhilosophersThread(fork1, fork2, (i+1)%num );                           //   ‘A’ B’ C’ D’ E’ (5+1)%5 = 1 ⇒ E’s right fork == fork1 = A’s left fork


// This one change to the fork pickup order is enough to break the deadlock and ensure that forks are always available to enable hungry philosophers to eat.

// Ori   : 0,1 ; 1,2 ; 2,3; 3,4 ; 4,0;
// New : 1,0; 1,2 ; 2, 3; 3,4 ;4, 0
int fork1 = i;
int fork2 = (i+1)%num;
if (i == 0)
      philosopherThreads[0] = new PhilosophersThread(0, fork2, fork1);
else
      philosopherThreads[i] = nwe PhilosophersThread(i, fork1, fork2);



             }
     }


     // Main funtion
     public void startEating() throws InterrupedException
     {
                     for (int i = 0; i < philosopherThreads.length;i++)
                            philosopherThreads[i].start();


                     // suspend the main thread until the first philosopher stops eating, which will never happen -- this keeps the simulation running indefinitely
                    philosopherThreads[0].join();
      }
         public static void main (Stirng[] args)
        {
                try
                {
                         DiningPhilosophers d = new DiningPhilosohers(5);
                         d.startEating();
                }
                catch (InterruptedException e)
                {
                }
         }
}

// Each philosophers run in its own thread
private class PhilosophersThread extends Thread
{
         // Field
         private itn id;
         private int fork1;
         private int fork2;

        // Constructor
         PhilosophersThread(int id , int fork1, int fork2)
          {
                   this.id = id;
                   this.fork1 = fork1;
                  this.fork2 = fork2;
         }
         public void run()
         {
                     status (“Ready to eat using forks” + fork1 + “ and “+ fork2);
                     pause(); // pause to let others get ready [to get fork1]
                     while (true)
                     {
                                  status(“Picking up fork ” + fork1);
                                  Synchronized (   forks[fork1] )
                                  {
                                               status (“ Picking up fork” + fork2);
                                             synchronized ( forks[fork2])
                                              {
                                                          status(“Eating”);
                                              }  
                                  }
                       }
         }

         private void pause()
          {
                   try{
                         sleep(200);
                   }
                    catch (InterruptedException e)
                  {
                         // do nothing
                   }
          }
          
         private void status (String msg)
        {
                  System.out.println(“Pholisopher ” +id + “;” + msg);
         }
}
DEADLOCK EXAMPLE

Provide Two locks if there are no possible deadlocks
Deadlock
when two or more thread wait for each other to release lock and get stuck for infinite time, only happen in multitaking.
1. Detect Deadlock
nested synchronized block or
calling one synchronized method from other or
trying to get lock on different object
Way1:  Take thread dump, in Linux “kill -3”, this will print status of all the thread in application log file and you can see which thread is locked on which object.
Way2: jconsole, it will slow you exactly which threads are get locked and on which object.

DEADLOCK EXAMPLE

public class DeadLockDemo
{
            /* this method request two locks ,first String and then Integer
            public void mehtod1 ()
            {
                       Synchronized(String.class)
                       {
                                  System.out.println(“Acquired lock on String.class object”);
                                  Synchronized (Integer.class)
                                  {
                                         System.out.println(“Acquired lock on Integer.class object”);
                                   }
                         }           
            }

            /* this method requests same two locks but in exactly Opposite order i.e., first Integer and the nString. This creates potential deadlock , if one thread holds String lock and other holds Integer lock and they wait for each other, for ever*/
            public void mehtod2 ()
            {
                       Synchronized(Integer.class)
                       {
                                  System.out.println(“Acquired lock on Integer.class object”);
                                  Synchronized (String.class)
                                  {
                                         System.out.println(“Acquired lock on String.class object”);
                                   }
                         }           
            }
}
if thread 1 acquires lock on Sting object while executing method1() and thread 2 acquires lock on Integer object while executing method2() both will be waiting for each other to release lock on Integer and String to proceed further which will never happen
  T1                       T2
hold obj1          hold obj2
want obj2         want obj1

If you have looked above code carefully then you may have figured out that real reason for deadlock is not multiple threads but the way they are requesting lock
avoids deadlock by avoiding circular wait with no preemption.


DEADLOCK EXAMPLE


Both method are requesting lock in the same order

public class DeadLockFixed
{
   /* this method request two locks ,first String and then Integer
            public void mehtod1 ()
            {
                       Synchronized(String.class)
                       {
                                  System.out.println(“Acquired lock on String.class object”);
                                  Synchronized (Integer.class)
                                  {
                                         System.out.println(“Acquired lock on Integer.class object”);
                                   }
                         }           
            }

            public void mehtod2 ()
            {
                       Synchronized(String.class)
                       {
                                  System.out.println(“Acquired lock on String.class object”);
                                  Synchronized (Integer.class)
                                  {
                                         System.out.println(“Acquired lock on Integer.class object”);
                                   }
                         }         
            }
}
DEADLOCK EXAMPLE

Deisgn a class which Provide a lock if there are no possible deadlocks
lock should be released at amount of time, no one hold the lock and wait for release lock  and also keep others waiting
  1. mutual inclusion: only one thread access at a time
  2. hold and wait: holding one lock and wait another
  3. no preemption
  4. circular wait
we can foucs on preemption and circular wait.
For preemption,
we can set a timeout and when hit, release the lock.
For circular wait,
we can try to enforce an order of acquiring the locks so that each thread must acquire the locks in a specific order, in that way there will be no thread holding one lock and waiting another


DEADLOCK EXAMPLE

Provide a lock M1
class MyThread extends Thread
{


        long time;
        List<Resource> res = new ArrayLsit<Resource>();



        MyThread(String name)
        {
              super(name);
        }
        public List<Resource> getRes() { return res;}
        public void setRes( List<Reosurce> res ) {this.res = res;}
        public long getTime() {return time;}


    
        public void run()
        {
                 /*run indefinitely*/
                 time = System.currentTimeMillis();
                 int count = 0;

                 while ( true)
                 {
                              if (count < 4)
                              {
                                         if ( Question.canAcquireResource(this, Question.r[count])   )
                                         {
                                                      res.add(Question.r[count]);
                                                      count++;
                                                      System.out.println(   “Resource ” + Question.r[count-1].getId() + “acquired by Thread” + this.getName()    );
                                                       try
                                                        {
                                                                  sleep(1000);
                                                      }
                                                       catch (InterruptedException e)
                                                       {
                                                                  e.printStackTrace();
                                                       }
                                         }
                                                  
                              }
                              else
                              {
                                          this.stop();
                              }
                 }

        }

}

DEADLOCK EXAMPLE

Provide a lock M2

// wait and die deadlock prevention scheme
const int NUM_REOSURCES = 100;
Resource rscs[NUM_REOSURCES];
thread thds[2];
boolean can_acquire_resource(Thread t, Reosurce r)
{
             Thread ot = ( thds[0] == t) ? thds[0] : thds[1];

             if ( ! is_resource_acquired(t, r)   )
                      return true;

             if (   timestamp(t) < timestamp(ot) )
             {
                       // t is older
                       os_wait_for_response(  t, r);
                      return true;
            }
            else
             {
                       // t is younger
                      os_finish_process(t);
                      return false;
           }
}

DEADLOCK EXAMPLE

Provide a lock M3


  1. class DeadLockDemo{  
  2.    public static void main(String[] args){  
  3.  
  4.        Ticket t=new Ticket();  
  5.        Thread t1=new Thread(t);  
  6.        Thread t2=new Thread(t);  
  7.        Thread t3=new Thread(t);  
  8.        Thread t4=new Thread(t);  
  9.  
  10.        t1.start();  
  11.        t2.start();  
  12.        t3.start();  
  13.        t4.start();  
  14.  
  15.    }  
  16. }

class Ticket implements Runnable
{
     private int tick = 100;
     Object obj = new Object();
     boolean flag = true;
     public void run()
      {
                  if ( flag )
                  {
                           while (  true )
                           {
                                    Synchronized(Ticker.class)// Lock the class
                                    {
                                            if ( tick > 0)
                                                System.out.println( curretnThread().getName() + tick--  );
                                    }
                           }
                  }
                  else
                  {
                           while ( true )
                                  show();
                  }
      }

      public static synchronized void show()
      {
                 synchronized(obj)
                  {
                             if (tick > 0)
                              {
                                          try
                                         {
                                                Thread.sleep(10);
                                         }
                                         catch ( Exception e )
                                         {
                                               System.out.println( curretnThread().getName() + tick--  );
                                         }
                             }
                  }
      }
}
Design a mechanism to make sure all the mehtods will be executed in sequence?
know preceding method has finished and notify
semaphores insures that only n required threads are using the resources
i)make sure that B is executed after A, and C is executed after B
Class Foo
{
         public :
         A(); // a new thread  will be created and the corresponding function will be executed
         B();
         C();
}
Foo f;
f.A();
f.B();
f.C();

Solution1: user semaphores, semaphores insures that only n required threads are using the resources
// Goal: B follow A and C follow B
public class Foo
{
    public semaphores s1 = new semaphores(1);
    public semaphroes s1 = new semaphores(1);
    public Foo()
    {
          s1.acquire();   //First acquire both semaphore
          s2.acquire();
    }
    public void A()
    {
           ……
           s1.release();
    }
    public void B()
    {
           s1.acquire(); // wait until A finish and then acquire
           …..
           s1.release();
    }
    public void C()
    {
           s1.acquire(); // wait until B finish and then acquire
     }

}
iii) Suppose we have the following code to use class Foo. We do not know how the threads will be scheduled in the OS.
Foo f;
f.A(.....); f.B(.....); f.C(.....);
f.A(.....); f.B(.....); f.C(.....);
make sure that all the methods will be executed in sequence?
Solution2: user semaphores, semaphores insures that only n required threads are using the resources
// Goal: B follow A and C follow B, A must follow C
public class Foo {
   public semaphore s1 = new semaphore(1);
   public semaphore s2 = new semaphore(1);
   public semaphore s3 = new semaphore(1);
   public Foo () {
       s1.acquire(); //first acquire s1 and s2
       s2.acquire();
   }
   public void A () {
       s3.acquire();
       .....
       s1.release();
   }
   public void B () {
       s1.acquire(); //wait until A finish then acuqire s1, s1 will keep locked until another finish of A.
       .....
       s2.release();
   }
   public void C () {
       s2.aquire(); //wait until B finish then we can acquire s2.
       ....
       s3.release(); // release s3 so that next A can start.
   }
}
Two threads call synchronized method at the same time
Two thread call synchronized and not synchronized at the same time
a class with synchronized method A, and a normal mehtod C. If you have two threads in one instance of a program, can they call A at the same time ? Can they call A and C at the same time?’
i) two threads call synchronized method at the same time
No, they can not. Synchronzed method can be run only from one thread.
ii)two thread call synchronized and not synchronized at the same time
Yes. IF C(normal method) is not protected , hten it can be run by both thread at the same time.
e.g.1 Implement a thread-safe blocking queue.(LinkedIn interview)
  1. template <typename T>
  2. class BlockingQueue{
  3.   private:
  4.       queue<T> _queue;
  5.       mutex _mutex;
  6.       condition_variable _cond;
  8.   public:
  10.       void push( const T& item){
  11.           unique_lock<mutex> locker(_mutex);
  12.           _queue.push(item);
  13.           locker.unlock();
  14.           _cond.notify_one();
  15.       }
  18.       T pop(){
  19.           unique_lock<mutex> locker(_mutex);
  20.           _cond.wait(locker, [=](){ return !_queue.empty() ;} );  //lambda function, capture by value
  21.           T item = _queue.front();
  22.           _queue.pop();
  23.           return item;
  24.       }
  25. };
mutex
semaphore
a lock,
lock()
…
unlock()
  1. Producer-Comsumer: only one part can get the mutex at a time, cannot not work at the entire buffer at the same time


-a thread can get more than one mutex
-a mutex can be locked more than once, recursive lock
- a deadlock: a non-recurive lock being locked more than once
signaling,
si.acruire()
….
si.release()
  1. Producer-Consumer: split buffer into 4 parts and each part with a semaphore, they can work at different part of buffer at the same time

- binary semaphore(signal) not the same as mutex(lock),
- Interrupted Service routine can signal a semaphore or unlock a mutex
- when blocking by mutex or semaphore, running list to waiting list
mutex
spin-lock
a lock sleep
1.wana acquire a lock and not available,
go to sleep and wait for being woke up



2. Problem: holding thread lock time < current thread sleep time




3. Solution: a hybrid mutex, first spin lock at multi-core, lock can not be obtained at a amount of time, put to sleep

  1. go to sleep, immediately allowing another thread to run.
  2. continue to sleep until being woken up, which will be the case once the mutex is being unlokced by whatever thread was holding the lock before
class lock
{
int held = 0;
}
void acquire( lock)
{
Disable Interrupt;
    while (lock.held == 1)
         enqueue(lock.queue, current_thread);
         thread_sleep(current_thread)
lock.held = lock.held +1; // occupy lock.held = 1
Enable Interrupt;
}
void release(lock)
{
Disable Interrupt;
thread = dequeue(lock.queue);
thread_start(thread);
lock.held = lock.held -1; // make lock.held = 0
Enable Itnerrupt;
}
a lock retrying
1.wanna acquire a lock and not available,
keep trying until current thread exceed CPU runtime quantum and being forced to switch by OS

2. Problem: holding thread lock time > INF,
current thread block forever
    Problem: for single-core/single CPU, blocking the only available CPU core

3. Solution : a hybrid spin lock, avoid wasting too much CPU time, back-off strategy,  lock can not be obtained at a amount of time, put to sleep
  1. will not allow another thread to take its place
  2. opertaitng system will forcely switch to another thread, once the CPU runtime quantum of the current thread has been exceeded
class lock
{
int held = 0;
}
void acquire(lock) {
  while (  test-and-set( lock.held) )
}
void release(lock)
{
     lock.held = 0;
}
Lock ordering (break circular wait)
Lock timeout (break no preemption)
deadlock detect (use map to record lock acquirer and waiter)
http://crunchify.com/what-is-java-semaphore-and-mutex-java-concurrency-multithread-explained-with-example/


Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)