Wednesday, 26 April 2017

Deadlock and Deadlock prevention

Deadlock occurs because:

Mutual exclusion: There is a resource which can be accessed only by one thread at any point in time.

Resource holding: While having locked one resource, the thread tries to acquire another lock on some other exclusive resource.

No preemption: there is any mechanism, which frees the resource if one thread holds the lock for a specific period of time.

Circular wait: During runtime a constellation occurs in which two (or more) threads are each waiting on the other thread to free a resource that it has locked.

Prevent deadlocks:

In order to prevent deadlocks one (or more) of the requirements for a deadlock has to be eliminated:

Mutual exclusion: In some situation it is possible to prevent mutual exclusion by using optimistic locking.

Resource holding: A thread may release all its exclusive locks, when it does not succeed in obtaining all exclusive locks.

No preemption: Using a time-out for an exclusive lock frees the lock after a given amount of time.

Circular wait: When all exclusive locks are obtained by all threads in the same sequence, no circular wait occurs.

Tuesday, 25 April 2017

Create Deadlock between two threads in Java

Deadlock describes a situation where two or more threads are blocked forever, waiting for each other.

Deadlock occurs because:

Mutual exclusion - Two processes cannot simultaneously control the same resource or be in their critical section.

Hold and Wait - processes currently holding resources can request new resources.

No preemption - Once a process holds a resource, it cannot be taken away by another process or the kernel.

Circular wait - Each process is waiting to obtain a resource which is held by another process.

Deadlocks in Java:
Deadlocks can occur in Java when the synchronized keyword causes the executing thread to block while waiting to get the lock, associated with the specified object. Since the thread might already hold locks associated with other objects, two threads could each be waiting for the other to release a lock. In such case, they will end up waiting forever.


Deadlock Example in java
 class Thread1 implements Runnable {
     public Object obj1;
     public Object obj2;
     public Thread1(Object obj1, Object obj2) {
           this.obj1 = obj1;
           this.obj2 = obj2;
     }

     public void run() {
           while(true) {
                synchronized (obj1) {
                     System.out.println("Thread1 : obj1");
                     synchronized (obj2) {
                           System.out.println("Thread1 : obj2");
                     }
                }
           }
     }
}

class Thread2 implements Runnable {
     public Object obj1;
     public Object obj2;
     public Thread2(Object obj1, Object obj2) {
           this.obj1 = obj1;
           this.obj2 = obj2;
     }
     public void run() {
           while(true) {
                synchronized (obj2) {
                     System.out.println("Thread2 : obj2");
                     synchronized (obj1) {
                           System.out.println("Thread2 : obj1");
                     }
                }
           }
     }
}

public class DeadLock {
     public static void main(String args[]) throws InterruptedException {
           Object obj1 = new Object();
           Object obj2 = new Object();

           Thread2 runn2 = new Thread2(obj1, obj2);
           Thread1 runn1 = new Thread1(obj1, obj2);

           Thread thrd2 = new Thread(runn2);
           Thread thrd1 = new Thread(runn1);

           thrd1.start();
           thrd2.start();

           while(!thrd2.isAlive() || !thrd1.isAlive()) {
                System.out.println("No deadlock found");
           }

     }
}

Saturday, 22 April 2017

Naïve String Matching Algorithm


It employs a Brute Force technique to identify the presence of a pattern in the given text.

It is not efficient algorithm because it takes the time complexity of the algorithm to check for a substring is O((m-n)n) where m is the length of the text and n is the length of the pattern (substring) to be searched.
There is no preprocessing is required for this algorithm, unlike KMP algorithm.

Preprocessing time: 0 (no preprocessing)
Matching time: O((n-m)m).

Pseudo Code:
NaiveStringMatcher(text, pattern)
tLen ← length [text]
pLen ← length [pattern]

for i ← 0 to tLen - pLen do
     mCount = 0;
for j ← 0 to pLen do
    if text[i] != pattern[j+i]
        break;
    mCount++;
     if(mCount == pLen)
           return Valid match found at position: + i!!

Implementation:
public class NaiveStringMatch {
      public static void main(String[] args) {
            String text = "I love to work on the algorithms!";
            String pattern = "the algorithms";
            naiveStringMatcher(text, pattern);
      }

      /**
       * Implementation of Naive String matching algorithm.
       * @param text
       * @param pattern
       */
      private static void naiveStringMatcher(String text, String pattern) {

            char[] txtArr = text.toCharArray();
            char[] patArr = pattern.toCharArray();

            int tLen = txtArr.length;
            int pLen = patArr.length;

            for (int i = 0; i < tLen - pLen; i++) {

               int charMatchCount = 0;
               for (int j = 0; j < pLen; j++) {

                    /**
                     * If pattern mismatch, break next searching point.
                     **/
                     if (patArr[j] != txtArr[i + j]) {
                          break;
                     }
                     charMatchCount++;

               }
               if (charMatchCount == pLen) {
                     print("String found at "+(i+1)+" position!!");
                     break;
               }
            }
      }

      private static void print(String string) {
            System.out.println(string);
      }
}
Output:
String found at 19 position!!

Sunday, 16 April 2017

volatile is not always enough?


Even if the volatile keyword guarantees that all reads of a volatile variable are read directly from main memory, and all writes to a volatile variable are written directly to main memory, there are still situations where it is not enough to declare a variable volatile.

In fact, multiple threads could even be writing to a shared volatile variable, and still have the correct value stored in main memory, if the new value written to the variable does not depend on its previous value. In other words, if a thread writing a value to the shared volatile variable does not first need to read its value to figure out its next value.

As soon as a thread needs to first read the value of a volatile variable, and based on that value generate a new value for the shared volatile variable, a volatile variable is no longer enough to guarantee correct visibility. The short time gap in between the reading of the volatile variable and the writing of its new value creates a race condition where multiple threads might read the same value of the volatile variable, generate a new value for the variable, and when writing the value back to main memory - overwrite each other's values.

The situation where multiple threads are incrementing the same counter is exactly such a situation where a volatile variable is not enough.

Explain with an example:
Imagine if Thread 1 reads a shared counter variable with the value 0 into its CPU cache, increment it to 1 and not write the changed value back into main memory. Thread 2 could then read the same counter variable from main memory where the value of the variable is still 0, into its own CPU cache. Thread 2 could then also increment the counter to 1, and also not write it back to main memory.


                   


Thread 1 and Thread 2 are now practically out of sync. The real value of the shared counter variable should have been 2, but each of the threads has the value 1 for the variable in their CPU caches, and in main memory, the value is still 0. Even if the threads eventually write their value for the shared counter variable back to main memory, the value will be wrong.

When is volatile enough?
As I have mentioned earlier, if two threads are both reading and writing to a shared variable, then using the volatile keyword for that is not enough. You need to use a synchronized in that case to guarantee that the reading and writing of the variable is atomic. Reading or writing a volatile variable does not block threads reading or writing. For this to happen you must use the synchronized keyword around critical sections.

As an alternative to a synchronized block, we can use one of the many atomic data types found in the java.util.concurrent package (=AtomicLong, AtomicReference or one of the others).

In case only one thread reads and writes the value of a volatile variable and other threads only read the variable, then the reading threads are guaranteed to see the latest value written to the volatile variable. Without making the variable volatile, this would not be guaranteed.


The volatile keyword is guaranteed to work on 32 bit and 64 variables.

Friday, 14 April 2017

Sort HashMap in Java based on Values

Using AraryList with Comparator:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;

public class SortByKeyListComp {
     private static void printSortedMap(Map<String, Integer> map) {
           /* Create the entry set. */
           Set<Entry<String, Integer>> set = map.entrySet();
          
           /* Create a list from EntrySet. */
           List<Entry<String, Integer>> list = new ArrayList<Entry<String, Integer>>(set);
          
           /* Sort List using the comparator. */
           Collections.sort( list, new Comparator<Map.Entry<String, Integer>>() {
                public int compare( Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                     return (o2.getValue()).compareTo(o1.getValue() );
                }
           });
          
           /* Print data. */
           for(Map.Entry<String, Integer> entry: list) {
                System.out.println("key#"+entry.getKey()+" value#"+entry.getValue());
           }
     }
    
     /**
      * Driver Method.
      */
     public static void main(String[] args) {
           Map<String, Integer> map = new HashMap<String, Integer>();
           map.put("geeks", 3);
           map.put("nerd", 2);
           map.put("test", 7);
          
           printSortedMap(map);
     }
}


Using TreeMap with Comparator:
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;


class ValueComparator implements Comparator {
     Map map;

     /* Set Map in Constructor. */
     public ValueComparator(Map map) {
           this.map = map;
     }

     /**
      * Compare the values using the default value of the Map.
      */
     public int compare(Object keyA, Object keyB) {
           Comparable valueA = (Comparable) map.get(keyA);
           Comparable valueB = (Comparable) map.get(keyB);
           return valueB.compareTo(valueA);
     }
}

public class SortByKeyTreeComp {

     public static Map sortByValue(Map unsortedMap) {
           /* Pass Map to ValueComparator so we can compare on the basic from defualt key.*/
           ValueComparator vc = new ValueComparator(unsortedMap);
           Map sortedMap = new TreeMap(vc);
           sortedMap.putAll(unsortedMap);
           return sortedMap;
     }

     public static void main(String[] args) {
           HashMap<String, Integer> map = new HashMap<String, Integer>();
           map.put("geeks", 3);
           map.put("nerd", 2);
           map.put("test", 7);

           System.out.println(map);
           Map sortedMap = sortByValue(map);
           System.out.println(sortedMap);
     }

}
Related Posts Plugin for WordPress, Blogger...