Lock by synchronize is acquired by shortest waiting threads

user_1271094 0
Viewed 152

I know that the synchronize(LOCK) is unfair, which means there is no guarantee that the longest waiting thread will win the lock. However in my little experiment below it seems that the lock was acquired by shortest waiting threads...

public class Demo {
    public static final Object LOCK = new Object();

    public void unfairDemo(){

        // Occupy the lock for 2 sec
        new Thread(() -> {
            synchronized (LOCK) {
                try {
                    Thread.sleep(2000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();

        // Spawn 10 new threads, each with 100ms interval, to see which can win the lock
        // If lock is fair then it should print the i in asc order
        for (var i = 0; i < 10; i++) {
            int finalI = i;
            new Thread(() -> {
                System.out.println("Added " + String.valueOf(finalI) + "th element to wait for lock");

                synchronized (LOCK) {
                    System.out.println("I got the lock, says " + String.valueOf(finalI) + "-th thread");
                }
            }).start();
            try {
                Thread.sleep(100);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        try {
            // Keep the program alive
            Thread.sleep(5000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

}

Running unfairDemo() prints the following:

Added 0th element to wait for lock
Added 1th element to wait for lock
Added 2th element to wait for lock
Added 3th element to wait for lock
Added 4th element to wait for lock
Added 5th element to wait for lock
Added 6th element to wait for lock
Added 7th element to wait for lock
Added 8th element to wait for lock
Added 9th element to wait for lock
I got the lock, says 9-th thread
I got the lock, says 8-th thread
I got the lock, says 7-th thread
I got the lock, says 6-th thread
I got the lock, says 5-th thread
I got the lock, says 4-th thread
I got the lock, says 3-th thread
I got the lock, says 2-th thread
I got the lock, says 1-th thread
I got the lock, says 0-th thread

I expected that the order would be scrambled, but no matter how I tried the results are in reverse order. What did I do wrong here?

jvm locking multithreading java
2 Answers

There are many sources, such as this, that already indicate that there should be no assumption regarding the order in which threads acquire locks. But it doesn't mean the order has to be scrambled.

It probably depends at the very least on the JVM implementation. For example, this document about HotSpot says:

Contended synchronization operations use advanced adaptive spinning techniques to improve throughput even for applications with significant amounts of lock contention. As a result, synchronization performance becomes so fast that it is not a significant performance issue for the vast majority of real-world programs.

...

In the normal case when there's no contention, the synchronization operation will be completed entirely in the fast-path. If, however, we need to block or wake a thread (in monitorenter or monitorexit, respectively), the fast-path code will call into the slow-path. The slow-path implementation is in native C++ code while the fast-path is emitted by the JITs.

I'm not an expert on HotSpot (maybe someone else can provide a more authoritative answer), but based on the C++ code, it looks like the contending threads will be pushed onto a LIFO structure, which may explain the stack-like order you observed:

// * Contending threads "push" themselves onto the cxq with CAS
//   and then spin/park.
...
//   Cxq points to the set of Recently Arrived Threads attempting entry.
//   Because we push threads onto _cxq with CAS, the RATs must take the form of
//   a singly-linked LIFO.
user_10642450

What did I do wrong here?

You do all right.

Your expirement shows program execution order in this particular case. Java do not guarantee any order of threads execution without special efforts from programmer's side.

Try this to see chaos:

public class Demo {
    public static final Object LOCK = new Object();

    public void unfairDemo() {
        createThread(0).start();
        for (var i = 1; i < 5; i++) {
            createThread(i).start();
        }
    }

    private static Thread createThread(final int number) {
        return new Thread(() -> {
            System.out.println("Added " + number + "th element to wait for lock");
            synchronized (LOCK) {
                System.out.println("I got the lock, says " + number + "-th thread");
                try {
                    Thread.sleep(number == 0 ? 2000 : 100);
                } catch (InterruptedException ex) {
                    ex.printStackTrace();
                }
            }
        });
    }

    public static void main(String[] args) {
        new Demo().unfairDemo();
    }

}
user_152700430
Related