Thursday, May 2, 2013

Implement Lock using java primitives

Decided to check how fast I could write a working lock using Java primitives (popular interview question). Uncovered a few interesting facts:
1. I don't even remember how wait()/notify() works any more! I am so used to java.util.concurrent goodness... 30 minutes to understand the concept.
2. I needed to think about simplest design for about 10 minutes.
3. Code writing: 30 minutes. The result:

package bin.test;

import java.util.concurrent.ConcurrentLinkedQueue;

public class Lock
{
    public boolean shutdown = false;
    public boolean started = false;
    public static class Waiter
    {
        public Thread what;
        public Object itsLock;
        public Waiter(Thread what, Object myLock)
        {
            this.what = what;
            this.itsLock = myLock;
        }
    }
    public ConcurrentLinkedQueue<Waiter> waiters = new ConcurrentLinkedQueue<Waiter>();
    public Thread owner;
   
    public Lock()
    {
        Thread t = new Thread(new Dealer(), "Lock processor");
        t.setDaemon(true);
        t.start();
    }
   
    public class Dealer implements Runnable
    {

        @Override
        public void run()
        {
            started = true;
            while(!shutdown)
            {
                if(waiters.isEmpty())
                {
                    try {
                        System.out.println("1");
                        Thread.sleep(500);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                else
                {
                    if(owner != null)
                    {
                        try {
                            System.out.println("2");
                            Thread.sleep(500);
                        } catch (InterruptedException e) {
                            e.printStackTrace();
                        }
                       
                    }
                    else
                    {
                        System.out.println("3");
                        Waiter current = waiters.poll();
                        owner = current.what;
                        synchronized (current.itsLock) {
                            current.itsLock.notifyAll();
                        }
                    }
                }
                   
            }
           
        }
       
    }
    public void lock()
    {
        Object newLock = new Object();
        waiters.add(new Waiter(Thread.currentThread(), newLock));
        synchronized (newLock) {
            try {
                System.out.println(4+" for "+Thread.currentThread().getName());
                newLock.wait();
            } catch (InterruptedException e) {
                System.out.println(5);
                e.printStackTrace();
            }
        }
    }
   
    public void unlock()
    {
        System.out.println("7");
        owner = null;
    }
}

package bin.test;

public class LockTest {

    public static class LockHolder implements Runnable
    {

        public Lock l;
        public LockHolder(Lock l)
        {
            this.l = l;
        }
        @Override
        public void run()
        {
            System.out.println("h1 at:"+System.currentTimeMillis()+" for "+Thread.currentThread().getName());
            l.lock();
            System.out.println("h2 at:"+System.currentTimeMillis()+" for "+Thread.currentThread().getName());
            try {
                Thread.sleep(2000);
            } catch (InterruptedException e) {
                System.out.println("h3 at:"+System.currentTimeMillis()+" for "+Thread.currentThread().getName());
                e.printStackTrace();
            }
            System.out.println("h4 at:"+System.currentTimeMillis()+" for "+Thread.currentThread().getName());

            l.unlock();
            System.out.println("h5 at:"+System.currentTimeMillis()+" for "+Thread.currentThread().getName());

        }
       
    }
    /**
     * @param args
     */
    public static void main(String[] args)
    {
        Lock lock = new Lock();       
        while(!lock.started)
        {
            try {
                System.out.println("h10 at:"+System.currentTimeMillis()+" for "+Thread.currentThread().getName());
                Thread.sleep(500);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        System.out.println("h11 at:"+System.currentTimeMillis()+" for "+Thread.currentThread().getName());

        Thread t1 = new Thread(new LockHolder(lock), "holder 1");
        Thread t2 = new Thread(new LockHolder(lock), "holder 2");
        t1.setDaemon(true);
        t2.setDaemon(true);
        t1.start();
        t2.start();
        System.out.println("h6 at:"+System.currentTimeMillis()+" for "+Thread.currentThread().getName());
        try {
            Thread.sleep(10000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        lock.shutdown = true;
        System.out.println("h7 at:"+System.currentTimeMillis()+" for "+Thread.currentThread().getName());

    }

}

----
1
h10 at:1367557213231 for main
h11 at:1367557213731 for main
1
h6 at:1367557213731 for main
h1 at:1367557213731 for holder 1
h1 at:1367557213731 for holder 2
4 for holder 1
4 for holder 2
3
h2 at:1367557214231 for holder 1
2
2
2
2
2
h4 at:1367557216233 for holder 1
7
h5 at:1367557216233 for holder 1
3
1
h2 at:1367557216734 for holder 2
1
1
1
1
h4 at:1367557218736 for holder 2
7
h5 at:1367557218736 for holder 2
1
1
1
1
1
1
1
1
1
h7 at:1367557223731 for main