How to solve thread starvation?

Question

I have the following locking mechanism for my class. When I run this program, one thread continuously acquires and reacquires the lock without giving any of the other threads a chance at acquiring the lock, leading to starvation. How can I restructure my locking mechanism such that once a thread gives up a lock, another one acquires it? I'd like to see other threads acquire the lock and not have to wait until the one that has the lock stops running.

  private final ReentrantLock lock = new ReentrantLock();
  private final Condition condition = lock.newCondition();

  private final Map<Integer, Long> locksMap = new HashMap<Integer, Long>();

  /** {@inheritDoc} */
  @Override
  public long lock(int recNo) throws RecordNotFoundException {
    ValidationUtils.checkNegative(recNo);

    lock.lock();
    long id = Thread.currentThread().getId();
    try {
      while (locksMap.get(recNo) != null) {
        try {
          System.out.println("Thread " + id + " is waiting.");
          condition.await();
        }
        catch (InterruptedException e) {
          LOGGER.log(Level.SEVERE, e.getMessage());
          return -1;
        }
      }
      Long prevValue = locksMap.put(recNo, id);
      if (prevValue != null) {
        String msg = "Expected no value for " + recNo + " but was ";
        msg += prevValue + ".";
        throw new IllegalStateException(msg);
      }
      System.out.println("Thread " + id + " has the lock.");
    }
    finally {
      lock.unlock();
    }
    return id;
  }

  /** {@inheritDoc} */
  @Override
  public void unlock(int recNo, long cookie) throws RecordNotFoundException, SecurityException {
    ValidationUtils.checkNegative(recNo);
    if (cookie < 0) {
      throw new IllegalArgumentException("cookie is negative.");
    }

    lock.lock();
    try {
      if (locksMap.get(recNo) == cookie) {
        locksMap.remove(recNo);
      }
      else {
        String msg = "Wrong lock cookie. Expected " + locksMap.get(recNo);
         msg += ", was " + cookie + ".";
        throw new IllegalStateException(msg);
      }
      long id = Thread.currentThread().getId();
      System.out.println("Thread " + id + " no longer has the lock.");
      condition.signalAll();
    }
    finally {
      lock.unlock();
    }
  }

  /**
   * Tests the locking mechanism in this class.
   * 
   * @param args None.
   */
  public static void main(String... args) {
    ExecutorService threadPool = Executors.newFixedThreadPool(5);
    final CountDownLatch latch = new CountDownLatch(5);
    final Data data = new Data();
    Runnable task = new Runnable() {
      @Override
      public void run() {
        try {
          for (int index = 0; index < 10; index++) {
            long cookie = data.lock(1);
            Thread.sleep(1000); // Do something.
            data.unlock(1, cookie);
          }
        }
        catch (SecurityException e) {
          e.getStackTrace();
        }
        catch (RecordNotFoundException e) {
          e.getStackTrace();
        }
        catch (InterruptedException e) {
          e.getStackTrace();
        }
        finally {
          latch.countDown();
        }
      }
    };
    for (int index = 0; index < 5; index++) {
      threadPool.execute(task);
    }
    try {
      latch.await();
    }
    catch (InterruptedException e) {
      e.getStackTrace();
    }
    threadPool.shutdown();
  }

Here's the output. Note that Thread 9 will stop acquiring the lock only after the loop finishes.

Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 9 has the lock.
Thread 13 is waiting.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 9 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 13 has the lock.
Thread 12 is waiting.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 13 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 12 has the lock.
Thread 11 is waiting.
Thread 10 is waiting.
Thread 12 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 11 has the lock.
Thread 10 is waiting.
Thread 11 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.
Thread 10 has the lock.
Thread 10 no longer has the lock.

Answer 1

I know you already have an acceptable answer, but I just want to add my 2¢.

If you're running on a single core machine or maybe even a dual core machine or something the problem could simply be that the JVM isn't swapping threads often enough to give another thread a chance at the lock.

In any case, simply calling Thread.yield() after releasing the lock should be sufficient to allow the other threads a chance to acquire the lock before the original thread grabs it again.

Answer 2

use ReetrantLock with Fair policy. Fair policy avoid thread starvation.

private final ReentrantLock lock = new ReentrantLock(true);

Java doc

public ReentrantLock(boolean fair) Creates an instance of ReentrantLock with the given fairness policy. Parameters: fair - true if this lock will be fair; else false