Saturday, 17 June 2017

Make a bootable flash drive from an ISO image on Ubuntu

Background

There are many times you download an ISO file from internet and want to install it on your machine. For eg. Windows or Ubuntu image. What you really wish is flash it iso image into a bootable drive like USB drive or a CD drive and install it from there on your machine.

 Make a bootable flash drive from an ISO image on Ubuntu

You have following options -
  1. Etcher- is a free and open-source image burner with support for Windows, OS X and GNU/Linux.
  2. Easy2Boot- Flexible and configurable USB drive multiboot solution which also supports UEFI booting.
  3. LiveUSB Install- is a free software for GNU/Linux and Windows. With LiveUSB Install you can effortlessly install various Linux distros.
  4. Multisystem- is an awesome tool created by LiveUSB.info that works similar to our Windows based MultiBootISOs USB creator.
  5. WinUSB - is a simple tool that enable you to create your own usb stick windows installer from an iso image or a real DVD.
  6. Unetbootin - UNetbootin allows you to create bootable Live USB drives for Ubuntu and other Linux distributions without burning a CD.
 Let's see some of the options -

Unetbootin

To install this run following command in your terminal -
  • sudo apt-get install unetbootin


Once installed you can  open the app. Now you can either select one of the given linux distros (those will get downloaded automatically) or  provide it an iso file from local machine.



WinUsb

To install winusb run following commands on your linux terminal -
  • sudo add-apt-repository ppa:colingille/freshlight
  • sudo apt-get update
  • sudo apt-get install winusb
Once installed you can open up the app select iso file and target usb and start creating bootable usb drive for windows.



NOTE : If you are looking for rufus then it is for Windows only. You cannot use it on your Linux machine.

Counting Semaphore, CountDownLatch, CyclicBarrier - synchronization methods for concurrency

Background

With Java 5 a lot of concurrency mechanisms were introduced for synchronization.



In one of the previous posts we saw what Reentrant locks are and how they help us achieve concurrency. -
We also saw 
Along with ReentrantLock and ExecutorService there were other concurrency elements that were introduced in Java 5 like -
  • Counting Semaphore
  • CountDownLatch
  • CyclicBarrier
Today we will try to understand these. Not only their understanding helps us with multi threading they are also popular topic of Java interview question. Lets see them one by one.

Counting Semaphore

Semaphore maintains a number of permits for a resource and only that many number of threads can access the resource. If the maximum permits allowed is reached then threads will have to wait till some other thread owing a permit releases it. 

As an example lets consider a simple semaphore with 1 permit. It's called binary semaphore. It's similar to wait and notify on same object. 

    public static void main(String args[])
    {
        Semaphore binarySemaphore = new Semaphore(1);
        new Thread(() -> {
            try {
                binarySemaphore.acquire();
                System.out.println("Semaphore permit acquired by : " + Thread.currentThread().getName());
                
            } catch (Exception e) {
                e.printStackTrace();
            }
            finally {
                System.out.println("Semaphore permit getting released by : " + Thread.currentThread().getName());
                binarySemaphore.release();            }
            
        }).start();
        new Thread(() -> {
            try {
                binarySemaphore.acquire();
                System.out.println("Semaphore permit acquired by : " + Thread.currentThread().getName());
                
            } catch (Exception e) {
                e.printStackTrace();
            }
            finally {
                System.out.println("Semaphore permit getting released by : " + Thread.currentThread().getName());
                binarySemaphore.release();
            }
            
        }).start();
    }
and the output would be -
Semaphore permit acquired by : Thread-0
Semaphore permit getting released by : Thread-0
Semaphore permit acquired by : Thread-1
Semaphore permit getting released by : Thread-1


 As you can see from code above you acquire a permit using acquire() method and release a permit using release() method.


NOTES :
  1. You can also acquire permit using acquireUninterruptibly(). This is a blocking call and the thread cannot be interrupted.
  2. Now acquire() is also a blocking call however it can be interrupted unlike acquireUninterruptibly() call
  3. You can also use tryAcquire() call which will try to acquire the permit and if available will return immediately with true. If it is not available it will also return immediately with false. So this is a non blocking call.

CountDownLatch

This is another synchronization mechanism in which a resource is not allowed access till predefined number of threads don't complete their operations. So lets say there are 10 threads making a bread slice. As soon as we are ready with 5 slices we can lets say back it together for selling. In this case we can use a CountDownLatch. Initialize one with 5 and as soon as 5 threads acknowledge they have finished making slices we can start packing (probably a new thread).

So a thread will wait for n other threads. Let's see an example -

    public static void main(String args[])
    {
        CountDownLatch countDownLatch = new CountDownLatch(2);
        new Thread(() -> {
            try {
                Thread.sleep(2000);
                System.out.println("Calling countdown by : " + Thread.currentThread().getName());
                countDownLatch.countDown();
            } catch (Exception e) {
                e.printStackTrace();
            }
           
        }).start();
        new Thread(() -> {
            try {
                Thread.sleep(2000);
                System.out.println("Calling countdown by : " + Thread.currentThread().getName());
                countDownLatch.countDown();
            } catch (Exception e) {
                e.printStackTrace();
            }
           
        }).start();
       
        try {
            System.out.println("Waiting for all other threads finish operation");
            countDownLatch.await();
            System.out.println("All other threads finish operation!");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }


Output :
Waiting for all other threads finish operation
Calling countdown by : Thread-1
Calling countdown by : Thread-0
All other threads finish operation!
As you can see main thread calls await() on the countdownlatch and wait for 2 threads to call countDown() on it. Here n is 2 but you can configure it in the constructor.

You need to use this when your use case is to wait for some other initial operations to finish before starting some other operation.

NOTE :
  1.  CountDownLatch is not reusable. So once the count reaches 0 i.e n threads have called countdown() the latch is unusable.

CyclicBarrier

CyclicBarrier is yet another synchronization mechanism. In this all n threads will wait for each other to reach the barrier. Such waiting threads are called parties. Number of parties are set in the CyclicBarrier during its creation. All parties reach the barrier and call await() which is a blocking call. Once all parties reach the barrier i.e all call await() then all threads get unblocked and proceed for next execution.

Simple usecase that you can think of is a multiple game scenario is which a game would not start untill all the players have joined. Here all the players are parties where as game start is a barrier.

Eg -

    public static void main(String args[])
    {
        CyclicBarrier cyclicBarrier = new CyclicBarrier(3);
        new Thread(() -> {
            try {
                Thread.sleep(2000);
                System.out.println("Player joining : " + Thread.currentThread().getName());
                cyclicBarrier.await();
                System.out.println("Game starting from : " + Thread.currentThread().getName());
            } catch (Exception e) {
                e.printStackTrace();
            }
           
        }).start();
        new Thread(() -> {
            try {
                Thread.sleep(2000);
                System.out.println("Player joining : " + Thread.currentThread().getName());
                cyclicBarrier.await();
                System.out.println("Game starting from : " + Thread.currentThread().getName());
            } catch (Exception e) {
                e.printStackTrace();
            }
           
        }).start();
        new Thread(() -> {
            try {
                Thread.sleep(2000);
                System.out.println("Player joining : " + Thread.currentThread().getName());
                cyclicBarrier.await();
                System.out.println("Game starting from : " + Thread.currentThread().getName());
            } catch (Exception e) {
                e.printStackTrace();
            }
           
        }).start();
       
    }

and the output is -
Player joining : Thread-0
Player joining : Thread-1
Player joining : Thread-2
Game starting from : Thread-2
Game starting from : Thread-0
Game starting from : Thread-1

As you can see all threads (3 in above case) will wait for each other to reach the barrier. Once they all reach and call await() they can all proceed to their further tasks.
NOTE :
  1. cyclicBarrier.reset() will put barrier on its initial state, other thread which is waiting or not yet reached barrier will terminate with java.util.concurrent.BrokenBarrierException. So CyclicBarrier can be reused unlike CountDownLatch.

Summary

Semaphore : Manages a fixed sized pool of resources.
CountDownLatch : One or more threads wait for a set of threads to finish operations.
CyclicBarrier : Set of threads wait for each other until they  reach a specific point.

Related Links

Tuesday, 23 May 2017

Print binary tree in Spiral order

Background

Sometime back we had seen how to traverse a binary tree and print it. We saw -
  • Pre-order 
  • post-order
  • In-order
  • level order traversals
Binary Tree Traversal

In this post we will see how to print them in a spiral order.  Consider following tree -




We need to print the tree in following order - 1, 2, 3, 4, 5, 6, 7.




Code

Following recursive approach will help achieve this. Idea is to keep a boolean toggle param to print nodes either from left to right or right to left.


    public static int getHeight(BTreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = getHeight(root.getLeft());
            int rightHeight = getHeight(root.getRight());
            return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
        }
    }


    /**
     * 
     * @param root
     *            if the btrr Worst case time complexity - O(N^2) for skewed
     *            trees No extra space
     */
    public static void printSpiralRecurssive(BTreeNode root) {
        boolean leftToRight = false;
        int height = getHeight(root);
        for (int i = 1; i <= height; i++) {
            printLevelRecurssive(root, i, leftToRight);
            leftToRight = !leftToRight;
        }
    }

    public static void printLevelRecurssive(BTreeNode root, int level, boolean leftToRight) {
        if (level == 1) {
            System.out.println(root.getData());
        } else {
            if (leftToRight) {
                printLevelRecurssive(root.getLeft(), level - 1, leftToRight);
                printLevelRecurssive(root.getRight(), level - 1, leftToRight);
            } else {
                printLevelRecurssive(root.getRight(), level - 1, leftToRight);
                printLevelRecurssive(root.getLeft(), level - 1, leftToRight);
            }
        }
    }

Logic : We first calculate the height of the tree which are basically levels. We then iterate from 1 to height (basically all levels) and print them from left to right or right to left based on the boolean toggle. We toggle this value after each level. For each recursive call we start from root and we go down till we reach the level we want it to be (one next to previously iterated on) based on the height and print nodes.

Complete solution with example is provide under my github repo of Data Structures -
In the same link there is a recursive solution as well that takes O(N) extra space to give same result. Iterative solution  -

private static Stack<BTreeNode> leftToRight = new Stack<>();
private static Stack<BTreeNode> rightToLeft = new Stack<>();
public static void printSpiralIterative(BTreeNode root) {

        rightToLeft.push(root);

        while (!rightToLeft.isEmpty() && !leftToRight.isEmpty()) {
            while (!rightToLeft.isEmpty()) {
                BTreeNode node = rightToLeft.pop();
                System.out.println(node.getData());
                if (node.getLeft() != null) {
                    leftToRight.push(node.getLeft());
                }
                if (node.getRight() != null) {
                    leftToRight.push(node.getRight());
                }
            }

            while (!leftToRight.isEmpty()) {
                BTreeNode node = rightToLeft.pop();
                System.out.println(node.getData());
                if (node.getLeft() != null) {
                    rightToLeft.push(node.getLeft());
                }
                if (node.getRight() != null) {
                    rightToLeft.push(node.getRight());
                }
            }
        }

}


Let me know if you have any questions.

Related Links

Saturday, 20 May 2017

How ConcurrentHashMap Works Internally in Java

Background

In one of the previous posts we saw how HashMap works -
and how it's time complexity of insertion and deletion is O(1) is normal case. Though this is a great data structure to work with in terms of time complexity it is not thread safe which means you cannot use it directly in multi threaded environments without taking additional precautions like synchronizing put/get on your own. Instead Java has provided a thread safe implementation of concurrent hashmap. We can directly use it in case of multi threaded environments for thread safety. Eg. in case of parallel stream introduced in java 8.

How ConcurrentHashMap Works Internally in Java

Before we see how it is implemented in Java lets give it some though. What are possible problems with a HashMap. Race condition, invalid state. Lets say two writes happen at the same time. Since write is not an atomic operation one value may overwrite other and Map may go in inconsistent state. We can obviously add synchronization over read/writes of a HashMap but it would be very inefficient and have performance impact. I would be like single threaded application certainly the behavior we don't expect. To solve this issue Java provides ConcurrentHashMap that has built in thread safety. Let see how -

We know how HashMap works. Internally it stores an array of Entry object which essentially has key, value and pointer to next Entry object (linked list used in case of collision). You can think of each array element as bucket and each Entry object as a data point containing key (in case 2 keys have same hash - collision), value  and pointer to next data element. 

Working :
ConcurrentHashMap as the name suggests allows concurrent read/writes to the Map. But there are limitations. ConcurrentHashMap maintains another data structure internally called segments. Each bucket of HashMap is part of one of the segments. Number of segments is called Concurrency-Level which determines number of thread that can write simultaneous. This Segments gets locked when writing/updating/removing data. Think of Segments as locks used to prevent concurrent write to same bucket of hashmap leading to inconsistency. So as long as write to concurrent hashmap is on different segments it can happen in parallel. Reads are completely lock free i.e No need to acquire lock for reading. Last updated value is returned.


 Now lets go step by step -

 Concurrency-Level , Segment array and initialization :
  • First when you create a ConcurrentHashMap you can provide concurrency level. This determines size of Segment array. Size of segment array will always be equal or more than the concurrency level. If this is not provided default is used - 
    • static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
  • Note that the size of segment table will always be power of 2. So if you give  concurrency level as 10 then next best power of 2 match will be picked up i.e 16 and Segment array of size 16 will be created which implies 16 threads can simultaneously operate on the map.
static final class Segment<K,V> extends ReentrantLock implements Serializable {

    //The number of elements in this segment's region.
    transient volatile int count;
    //The per-segment table. 
    transient volatile HashEntry<K,V>[] table;
}

Putting element in ConcurrentHashMap :

  • For putting element in Map we first need to determine which segment the element should be processed for. For this we first get hascode of the key. Next we do a rehash of the existing hash to ensure
     /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because ConcurrentHashMap uses power-of-two length hash tables,
     * that otherwise encounter collisions for hashCodes that do not
     * differ in lower or upper bits.
     */
    private static int hash(int h) {
        // Spread bits to regularize both segment and index locations,
        // using variant of single-word Wang/Jenkins hash.
        h += (h <<  15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h <<   3);
        h ^= (h >>>  6);
        h += (h <<   2) + (h << 14);
        return h ^ (h >>> 16);
    }
  •  Once hash is calculated you can get the segment which it belongs to and delegate put method to segments put method as follows -
    public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, false);
    }

    final Segment<K,V> segmentFor(int hash) {
        return segments[(hash >>> segmentShift) & segmentMask];
    }


We will see how segment is computed in some time with a proper example. Once put is delegated to segment , segment will add it to the appropriate bucket in the segment.

        V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();
            try {
                int c = count;
                if (c++ > threshold) // ensure capacity
                    rehash();
                HashEntry<K,V>[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<K,V> first = tab[index];
                HashEntry<K,V> e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;
                if (e != null) {
                    oldValue = e.value;
                    if (!onlyIfAbsent)
                        e.value = value;
                }
                else {
                    oldValue = null;
                    ++modCount;
                    tab[index] = new HashEntry<K,V>(key, hash, first, value);
                    count = c; // write-volatile
                }
                return oldValue;
            } finally {
                unlock();
            }
        }


Now this is very interesting method. Lets understand whats happening here.

  • First call is to lock(). Since it is a write/update operation on a bucket of same segment we need a lock. If you recollect Segment class it extends ReentrantLock so each segment is a lock. So you can call lock() and unlock() directly in Segment class.
  • Next it's like a normal HashMap. You find the index of the Entry table where your elements hash falls and add it there as linked list.
  • You can see similar code has HashMap that updates value if key is same, inserts in array if there is no element in the table and adds it in the linked list of the table if element already exists.
  • Finally once operation is complete it calls unlock() so that other threads can continue update.
  • Note the lock is a blocking call. 
  • You can also see call for rehash if threshold is reached. Like Entry array Segment also has a threshold and when it is reached Segment array is resized for performance. That's what rehash. 
NOTE : For getting index of Segment table first n bits are used where as for getting index of Entry table last N bits are used from enhanced hash integer (See details in example below).

Getting element from  ConcurrentHashMap : 

Get on ConcurrentHashMap is very simple no locks involved. You simply read the data and return -

        public V get(Object key) {
                int hash = hash(key.hashCode());
                return segmentFor(hash).get(key, hash);
        }

        V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry<K,V> e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }


NOTE  : readValueUnderLock method is used as a backup in case a null (pre-initialized) value is ever seen in an unsynchronized access method.

Example

Above was just all code and some understanding. Now lets take an actual example.

Let's say we have created a ConcurrentHashMap with concurrency level lets say 10. Based on this Segment array will be created based on following code -

    private static void printSegmentDetails(int concurrencyLevel) {
        int sshift = 0;
        int segmentMask = 0;
        int segmentShift = 0;

        int ssize = 1;
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        segmentShift = 32 - sshift;
        segmentMask = ssize - 1;
        System.out.println("Segment array size :" + ssize);
        System.out.println("segmentShift : " + segmentShift);
        System.out.println("segmentMask : " + segmentMask);
    }


Output for 10 concurrency level:
Segment array size : 16
segmentShift : 28
segmentMask : 15

NOTE  :As mentioned before segment array is of size 2^n such that 2^n >= concurrency level. In this case 2^4

Now that we have segment table in place lets simulate put. We need to put a String called "Aniket" as key. We don't care about value. Just make sure it's not null.

  1. First we will calculate hascode of the key.
  2. Then hash it so for better hash (as mentioned above)
  3. Then based on the result hash we will find which segment will it belong
Remember of Segment table was >= 2^N we now want first N bits to determine which segment this hash falls into. Since N bits will vary from 1 - 2^N which is our segment array size. Also remember code to get this index from above? -
  • int segmentIndex = (hash >>> segmentShift) & segmentMask
This essentially means logically right shift hash with segmentShift bits. Since int is 32 bit and segmentShift = 32 - sshift, hash >>> segmentShift will essentially give you first sshift bits (sshift is nothing but N in 2^N we saw above). segmentMask is to get the N bits post shift.

So in this case,
N  = sshift =  4
2^N = 16 -> Size of segment array
segmentShift = 32 - 4 = 28 (as we saw in output above)
segmentMask = 16 -1 - 15

    public static void main(String args[]) {    
        String key = "Aniket";
        //hascode of key
        System.out.println(key.hashCode());
        //better hash
        System.out.println(hash(key.hashCode()));
        //better hash in binary
        System.out.println(Integer.toBinaryString(hash(key.hashCode())));
        //logical right shift by segmentShift
        System.out.println("Right shifter hash : " + Integer.toBinaryString(hash(key.hashCode()) >>> 28));
        // segment index as binary and of right shift and segmentMask
        System.out.println("Segment Index : " + Integer.toBinaryString((hash(key.hashCode()) >>> 28 ) & 15));
        // segment index as decimal
        System.out.println("Segment Index : " + ((hash(key.hashCode()) >>> 28 ) & 15));
    }


Output :
1965716254
1839402854
1101101101000110000111101100110
Right shifter hash : 110
Segment Index : 110
Segment Index : 6


NOTE : 1101101101000110000111101100110 is 31 bits as rightmost bit is 0 and ignored.  Same goes for all subsequent binmary bit formats.

So your element with key "Aniket" will go in Segment array of index 6. Inside segments it's pretty simple to calculate index of Entry array.

  •  int entryArrayindex = hash & (tab.length - 1);
         int entryArrayindex = (hash(key.hashCode()) & (16 - 1));
         System.out.println("Entry array index : " + entryArrayindex);
         System.out.println("Entry array index in binary : " + Integer.toBinaryString(entryArrayindex));


Output :
Entry array index : 6
Entry array index in binary : 110


So finally Entry is inserted at index 6 of Entry table.

So to summarize for getting index of Segment table first n bits are used where as for getting index of Entry table last N bits are used from enhanced hash integer.


Related Links 

Left shift and right shift operators in Java

Left shift and right shift operators in Java

A lot of time we use >> , >>> or << and <<< operators in Java for bit operations. These operations essentially shift bits left or right depending on the operator. In this post we will see what exactly is the difference.
  • >> is arithmetic or signed shift right
  • >>> is logical or unsigned shift right
  • << is arithmetic or signed shift left
The signed left shift operator "<<" shifts a bit pattern to the left, and the signed right shift operator ">>" shifts a bit pattern to the right. The bit pattern is given by the left-hand operand, and the number of positions to shift by the right-hand operand.

The unsigned right shift operator ">>>" shifts a zero into the leftmost position, while the leftmost position after ">>" depends on sign extension.

NOTE : There is no logic left shift as it is same as arithmetic left shift.

Example :

        System.out.println(Integer.toBinaryString(-121));
        // prints "11111111111111111111111110000111"
        System.out.println(Integer.toBinaryString(-121 >> 1));
        // prints "11111111111111111111111111000011"
        System.out.println(Integer.toBinaryString(-121 >>> 1));
        // prints "1111111111111111111111111000011"
        
        System.out.println(Integer.toBinaryString(121));
        // prints "1111001"
        System.out.println(Integer.toBinaryString(121 >> 1));
        // prints "111100"
        System.out.println(Integer.toBinaryString(121 >>> 1));
        // prints "111100"


As you can see in case of -121 since it is a negative number arithmetic or signed shift right adds a 1 to the rightmost bit where as in case if 121 it adds 0.

logical or unsigned shift does not care about sign. It just adds 0 to the shifted bits.


Related Links

t> UA-39527780-1 back to top