CASE STUDIES WITH CONCURRENCY

Example: Quick-sort

Following is a sequential implementation of quick-sort. Run the program as:

    $ time java QuickSort

The time command will report program performance.

    import java.io.Console;
    import java.util.Random;

    class QuickSorter {
        static void swap(int[] data, int i, int j){
            int tmp=data[i];
            data[i]=data[j];
            data[j]=tmp;
        }
        static int partition(int[] data, int start, int end) {
            if(start==end)
                return start;
            int pivot=data[end];
            int s=start-1;
            for(int i=start;i<end;i++)
                if(data[i]<=pivot)
                    swap(data,++s,i);
            swap(data,++s,end);
            return s;
        }
        static void quickSort(int[] data, int start, int end) {
            if (end<=start)
                return;
            int s=partition(data,start,end);
            quickSort(data,start,s-1);
            quickSort(data,s+1,end);
        }
        static int[] randomList(int n,int k) {
            Random random=new Random();
            int[] data=new int[n];
            for(int i=0;i<data.length;i++)
                data[i]=random.nextInt(k);
            return data;
        }
        public static void main(String[] args) {
            int[] data={3,1,2,8,5,6};
            quickSort(data,0,data.length-1);
            for(int i:data)
                System.console().format("%d ",i);
            System.console().format("\n");
            int n=10000000;
            quickSort(randomList(n,1000000),0,n-1);
        }
    }

Parallel quick-sort

In this example we partition the array once and run quick-sort in parallel for the two halves. Note that this is not the best approach, and we will see a better one later.

Note that this problem is embarrassingly parallel.

    import java.io.Console;
    import java.util.Random;

    class QuickSorter implements Runnable{
        int[] data;
        int start,end;
        QuickSorter(int[] data,int start,int end) {
            this.data=data;
            this.start=start;
            this.end=end;
        }
        public void run(){
            quickSort(this.data,this.start,this.end);
        }
        static void swap(int[] data, int i, int j){
            int tmp=data[i];
            data[i]=data[j];
            data[j]=tmp;
        }
        static int partition(int[] data, int start, int end) {
            if(start==end)
                return start;
            int pivot=data[end];
            int s=start-1;
            for(int i=start;i<end;i++)
                if(data[i]<=pivot)
                    swap(data,++s,i);
            swap(data,++s,end);
            return s;
        }
        static void quickSort(int[] data, int start, int end) {
            if (end<=start)
                return;
            int s=partition(data,start,end);
            quickSort(data,start,s-1);
            quickSort(data,s+1,end);
        }
        static int[] randomList(int n,int k) {
            Random random=new Random();
            int[] data=new int[n];
            for(int i=0;i<data.length;i++)
                data[i]=random.nextInt(k);
            return data;
        }
        public static void main(String[] args) {
            int[] data={3,1,2,8,5,6};
            quickSort(data,0,data.length-1);
            for(int i:data)
                System.console().format("%d ",i);
            System.console().format("\n");
            int n=10000000;
            data=randomList(n,1000000);
            int s=partition(data,0,n-1);
            Thread t1=new Thread(new QuickSorter(data,0,s-1));
            Thread t2=new Thread(new QuickSorter(data,s+1,data.length-1));
            t1.start();
            t2.start();
            try {
                t1.join();
                t2.join();
            }catch(InterruptedException e){
                System.out.println(e);
            }
        }
    }

Case study with synchronization: find primes

Consider the problem of finding all primes starting from 1. Following is the sequential program:

    import java.io.Console;
    import java.util.ArrayList;

    class PrimeFinder implements Runnable{
        ArrayList<Long> primes;
        PrimeFinder(ArrayList<Long> primes) { 
            this.primes=primes;
        }
        public void check(long n) {
            boolean isPrime=true;
            for(long i=2;i<n;i++) 
                if (n % i ==0) {
                   isPrime=false;
                   break;
                }
            if (isPrime) {
                System.console().format("New prime found: %d\n",n);
                primes.add(n);
            }
        }
        public void run() {
            for (long i=1;;i++) 
                check(i);
        }

        public static void main(String[] args) {
            ArrayList<Long> primes=new ArrayList<Long>();
            PrimeFinder pf=new PrimeFinder(primes);
            Thread runner=new Thread(pf);
            try {
                runner.start();
                Thread.sleep(5000);
                runner.interrupt();
                System.console().format("Number of primes found: %d\n",primes.size());
                System.exit(0);
            }catch(Exception e) {
                System.out.println(e);
            }
        }
    }

Find primes: parallel version

Following program finds primes using two threads instead. Note how synhronized is used, because the problem is not embarrassingly parallel.

The synchronization is necessary to protect the use of shared data (the ArrayList of primes) from concurrent modification:

    import java.io.Console;
    import java.util.ArrayList;

    class PrimeFinderParallel implements Runnable{
        ArrayList<Long> primes;
        int start,skip;
        PrimeFinderParallel(ArrayList<Long> primes,int start, int skip) { 
            this.primes=primes;
            this.start=start;
            this.skip=skip;
        }
        public void check(long n) {
            boolean isPrime=true;
            for(long i=start;i<n;i+=skip) 
                if (n % i ==0) {
                   isPrime=false;
                   break;
                }
            if (isPrime) {
                System.console().format("New prime found: %d\n",n);
                synchronized(primes){
                    primes.add(n);
                }
            }
        }
        public void run() {
            for (long i=1;;i++) 
                check(i);
        }

        public static void main(String[] args) {
            ArrayList<Long> primes=new ArrayList<Long>();
            PrimeFinderParallel pf1=new PrimeFinderParallel(primes,1,2);
            PrimeFinderParallel pf2=new PrimeFinderParallel(primes,2,2);
            Thread t1=new Thread(pf1);
            Thread t2=new Thread(pf2);
            t1.start();
            t2.start();
            try {
                Thread.sleep(5000);
                t1.interrupt();
                t2.interrupt();
                System.console().format("Number of primes found: %d\n",primes.size());
                System.exit(0);
            }catch(InterruptedException e){
                System.out.println(e);
            }
        }
    }

Case study: Buffer implementation

A buffer is a limited amount of ordered storage, common in many applications. It has a certain capacity, and one can push and pop values from it, as a queue. Thus an interace as follows can be used to represent a buffer:

    interface Buffer<T> {
        /**Returns true if the buffer has at least one empty slot*/
        boolean hasEmptySlot();

        /**Returns true if the buffer has no elements*/
        boolean isEmpty();

        /**Returns total capacity of the buffer*/    
        int totalCapacity();

        /**Pushes one element onto the end of buffer, throws exception if it has no empty space */
        void push(T) throws Exception;

        /**Pops one element from the top of the buffer */
        T pop() throws Exception;
    }

Unsafe buffer implementation

Implement a circular buffer using an array.

safe buffer implementation

HOME EXERCISES

  1. Write a class to manage the customer queue in a bank. Your class must have a int next() method which returns a unique number for the customer. It also has a method called int serve() which returns the number of the customer to serve next each time when it is called. If there is no customer in the queue server method must throw an Exception.
  2. Consider in the above problem that multiple ticket machines hand out tickets to customers in parallel, and also multiple bank workers serve customers in parallel. Modify your class so that it is safe against such concurrent modification.
  3. The Euler number is found as the following infinite series sum: \[e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!}+\cdots+ \frac{1}{n!}+\cdots\] Write a Java method to make the truncated computation up to \(n\)'th term, given \(n\).
  4. The process of finding the Euler number can be parallelized by computing even and odd terms in the series separately in parallel,i.e: \[e = 1+e_{odd}+e_{even}\] \[e_{odd}=\frac{1}{1!} + + \frac{1}{3!} + \frac{1}{5!}+\cdots+ \frac{1}{(2n+1)!}+\cdots\] \[e_{even}=\frac{1}{2!} + + \frac{1}{4!} + \frac{1}{6!}+\cdots+ \frac{1}{(2n)!}+\cdots\] Write a program which computes truncated versions of the two parts in parallel.
  5. Consider a good in a retail store. One needs the good's name and price to represent it in a Good class. The store also wants to keep track of the number of items in the stock inside Good class. Write a class to represent a good, which has void add(int numItems) and void remove(int numItems) methods which allow to modify the stock of the good by given amounts.
  6. Modify your class above so that it is safe against concurrent modifications.