Threads working at the same time

Question

I am trying to make my class as Queue such that if I have two threads, one that adds and other that removes elements - they could do that at the same time. Currently one gets blocked because the threads are competing for the same lock object.

public class Queue {

    private Cell head, tail;

    public synchronized void add(Object o){
        Cell c = new Cell(o);
        if (tail == null) { head = c; }
        else { tail.next = c; }
        c.next = null;
        tail = c;
        notifyAll();
    }

    public synchronized Object remove() 
    throws InterruptedException {
        while (head == null){
        wait();
    }   
        Cell c = head;
        head = head.next;
        if (head == null){ tail = null; };
        return c.contents; 
    }
}

class Cell {
    Cell next;
    Object contents;
    public Cell(Object o) { contents = o; }
}

Main:

public static void main(String[] args) throws InterruptedException {

    Queue q = new Queue();

    Thread thr = new Thread(new Runnable() {

        @Override
        public void run() {
            for (int i = 0; i < 1000; i++)
                q.add(new Integer(i));
        }

    });
    Thread thr1 = new Thread(new Runnable() {

        @Override
        public void run() {
            for (int i = 0; i < 10000; i++)
                try {
                    q.remove();
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
        }

    });

    thr.start();
    thr1.start();

}

Answer 1

Standard synchronisation techniques will not achieve what you require. That is, concurrent updates to the queue. This is because when one thread acquires a lock on the queue, another thread then cannot acquire a lock on the queue and so cannot proceed.

The technique that you have to implement in order to achieve concurrent updates to the queue is called lock stripping. This is how concurrent collections such as ConcurrentHashMap achieve concurrent reads and writes. Implementing lock stripping is not trivial.

You need to ask yourself whether if implementing a custom collection with lock stripping will be easier than if you choose a JDK collection such as ConcurrentLinkedDeque.