A "starvation-free" implementation in Java

Question

While using a simple mutex in and condition variable for worker threads, my program gets some rare and sporadic thread starvation errors, and I'd like to prevent this.

The following is a simple example of what I'm doing. There are 4 worker threads call "Producer"s and a main thread that calls prod.getTasks().

This code is "deadlock-free" but due to the errors, obviously not "starvation-free".

When I get a Thread starvation or clock leap detected (housekeeper delta=1m18s317ms137µs765ns) error is it:

A) Because a Producer thread is sitting in a wait state for too long? (I don't think so because I believe a thread could wait an arbitrary amount of time before it's ready for use. Certainly longer than 1 min).

B) Because one of the waiting worker threads has been passed up too many times?

Basically any good tips as to help make this starvation free would be appreciated.

class Producer implements Runnable
{
    private static ArrayList<Task> arrTasks = new ArrayList<Task>();

    void getTasks()
    {
        Task t = getTask(); // get Tasks from a producer specific recordset.    
        synchronized (arrTasks)
        {
            arrTasks.add(t);
            arrTasks.notify();
        }
    }

    void run()
    {
        while (true) 
        {
            Task t = null;

            synchronized (arrTasks)
            {
                if (arrTasks.size() == 0)
                    arrTasks.wait();

                if (arrTasks.size() > 0)
                    t = arrTasks.remove(0);
            }

            if (t != null)
                processTask(t);

            if (mExit) 
                break;
        }
    }
}

Answer 1

A producer/consumer pattern will always either starve, be overloaded, or pointless. This is not a performance patter, it is used for abstraction.

Your code can be made a lot easier if you use a concurrent BlockingQueue, which allow to remove all your synchronized.