Fair vs NonFair

Question

I have been tested fair and non fair disciplines via RentrantLock. I wrote a small program that simulates dinning philosophers.

Each philospher has left and right fork which are ReentrantLocks. I have simulated 1000 times act of thinking and eating:

 for (int i = 0; i < ACT_TIMES; i++) {
            act();
        }

where act is

private void act() {
        think();
        eat();

    }

Think is not interesting it just sleeps for some amount of time. Here is eat method

private void eat() {
        try {
            if (left.tryLock(0, TimeUnit.MILLISECONDS)) {
                if (right.tryLock(0, TimeUnit.MILLISECONDS)) {
                    log("eating");
                    eatCount++;
                    try {
                        Thread.sleep(EAT_TIME);
                    } catch (InterruptedException e) {
                    } finally {
                        left.unlock();
                        right.unlock();
                    }
                } else {
                    left.unlock();
                }
            }
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

Main method:

 Lock[] forks = new Lock[5];
        for (int i = 0; i < forks.length; i++) {
            forks[i] = new ReentrantLock();
        }
        Philosopher p1 = new Philosopher(0, forks[1], forks[0]);
        Philosopher p2 = new Philosopher(1, forks[2], forks[1]);
        Philosopher p3 = new Philosopher(2, forks[3], forks[2]);
        Philosopher p4 = new Philosopher(3, forks[4], forks[3]);
        Philosopher p5 = new Philosopher(4, forks[0], forks[4]);
        ExecutorService exec = Executors.newFixedThreadPool(5);
        exec.submit(p1);
        exec.submit(p2);
        exec.submit(p3);
        exec.submit(p4);
        exec.submit(p5);

After all 5 threads finishes, I print eatCount for each philosopher. And these values don't differ too much for fair(new ReentrantLock(true)) and unfair(new ReentrantLock()) discipline.

(first number is a number of a philospher)

Fair lock:

0 344
1 348
2 366
3 359
4 363
Total number of eating 1780

Unfair Lock:

0 338
1 338
2 339
3 341
4 352
Total number of eating 1708

I have expected some starvation for unfair lock, I mean some philosopher/philosophers have to have eatCount much greater than others, but starvation didn't happen. why?

Answer 1

The thread which releases a lock has a much better chance of regaining the lock as it is busy while the other threads could be blocked. Busy waiting won't show this as each thread will have an equal chance of grabbing the lock. Possibly the one to release the lock could be at a slight disadvantage.

final ReentrantLock lock = new ReentrantLock();
for (int i = 0; i < 5; i++) {
    final int finalI = i;
    new Thread(new Runnable() {
        @Override
        public void run() {
            for (int j = 0; j < 5; j++) {
                lock.lock();
                System.out.println("locked by " + finalI);
                lock.unlock();
            }
        }
    }).start();
}

prints

locked by 0
locked by 0
locked by 0
locked by 0
locked by 0
locked by 1
locked by 1
locked by 1
locked by 1
locked by 1
locked by 2
locked by 2
locked by 2
locked by 2
locked by 2
locked by 3
locked by 3
locked by 3
locked by 3
locked by 3
locked by 4
locked by 4
locked by 4
locked by 4
locked by 4

but if I make the lock fair with true I see

locked by 0
locked by 1
locked by 2
locked by 3
locked by 4
locked by 0
locked by 1
locked by 2
locked by 3
locked by 4
locked by 0
locked by 1
locked by 2
locked by 3
locked by 4
locked by 0
locked by 1
locked by 2
locked by 3
locked by 4
locked by 0
locked by 1
locked by 2
locked by 3
locked by 4

Answer 2

remove all sleep(), you may see some unfairness.