preface

Dear readers, I am writing a series of articles on Java multithreading, and this one will focus on locking

Locks are a regular part of the interview process, and they’re essential to multi-threaded coding, whether it’s to “win an interview” or “write high-quality code.”

According to the author: this article is arranged according to their own limited knowledge, if there are fallacies, please feel free to point out in the comments section

Understand the series and overview: Java Multithreading series

This article is long and skip, please refer to the map to read:

Previous gAP-Java object structure

I’ve published a series of articles on Overcoming Anxiety: Illustrating the JVM memory model and JVM threading model

There is one key piece of knowledge left unexplored: “What Java objects contain”, which has to do with the implementation of locks, and this article will continue from there.

To put it simply, in the HotSpot VIRTUAL machine, an object instance can be divided into three pieces of information:

  • The Header object head
  • Instance Data, also known as object body
  • Alignment Padding

Where alignment padding may exist, instance data is supplied to the application logic and stores instance field information. Next, focus on the object header.

Java object head

The information in the object header is jVM-specific and contains:

  • Mark Word
  • Kclass, the metadata pointer to the corresponding class of the object
  • Array Length, which is only available to array objects

The overall division is shown in the figure:

Image from web search, watermark for Java help

Mark Word

Mark Word is used to store object runtime data: hashes, GC generation age, lock status flags, locks held by threads, biased thread ids, biased timestamps, etc.

Find doc for markOop in HotSpot:

// The markOop describes the header of an object.
// Note that the mark is not a real oop but just a word.
// It is placed in the oop hierarchy for historical reasons.
//
// Bit-format of an object header (most significant first, big endian layout below):
//
// 32 bits:
// --------
// hash:25 ------------>| age:4 biased_lock:1 lock:2 (normal object)
// JavaThread*:23 epoch:2 age:4 biased_lock:1 lock:2 (biased object)
// size:32 ------------------------------------------>| (CMS free block)
// PromotedObject*:29 ---------->| promo_bits:3 ----->| (CMS promoted object)
//
// 64 bits:
// --------
// unused:25 hash:31 -->| unused:1 age:4 biased_lock:1 lock:2 (normal object)
// JavaThread*:54 epoch:2 unused:1 age:4 biased_lock:1 lock:2 (biased object)
// PromotedObject*:61 --------------------->| promo_bits:3 ----->| (CMS promoted object)
// size:64 ----------------------------------------------------->| (CMS free block)
//
// unused:25 hash:31 -->| cms_free:1 age:4 biased_lock:1 lock:2 (COOPs && normal object)
// JavaThread*:54 epoch:2 cms_free:1 age:4 biased_lock:1 lock:2 (COOPs && biased object)
// narrowOop:32 unused:24 cms_free:1 unused:4 promo_bits:3 ----->| (COOPs && CMS promoted object)
// unused:21 size:35 -->| cms_free:1 unused:7 ------------------>| (COOPs && CMS free block)
Copy the code

If the compression pointer is disabled for a 32-bit OR 64-bit VM, the value is 32bit and 64bit respectively. If compression is enabled, the value is 32bit

Comb the object headers of 64-bit VMS in the following five states:

|------------------------------------------------------------------------------------------------------------------|
|                                     Object Header(128bits)                                                       |
|---------------------|--------------------------------------------------------------------------------------------|
|       State         |                                   Mark Word(64bits)               |  Klass Word(64bits)    |
|---------------------|--------------------------------------------------------------------------------------------|
|       Nomal         | unused:25|identity_hashcode:31|unused:1|age:4|biase_lock:1|lock:2 | OOP to metadata object |
|---------------------|--------------------------------------------------------------------------------------------|
|       Biased        | thread:54|      epoch:2       |unused:1|age:4|biase_lock:1|lock:2 | OOP to metadata object |
|---------------------|--------------------------------------------------------------------------------------------|
|  Lightweight Locked |                     ptr_to_lock_record:62                 |lock:2 | OOP to metadata object |
|---------------------|--------------------------------------------------------------------------------------------|
|  Heavyweight Locked |                    ptr_to_heavyweight_monitor:62          |lock:2 | OOP to metadata object |
|---------------------|--------------------------------------------------------------------------------------------|
|     Marked for GC   |                                                           |lock:2 | OOP to metadata object |
|---------------------|--------------------------------------------------------------------------------------------|
Copy the code

If typesetting is inconvenient, see the picture below:

If running on HotSpot openJdk VM, you can print the object header with “org.openJDK. Jol :jol-core:0.9” for comparison.

A reference blog for analyzing object headers in five states

Author press: here’s the knowledge we leave an impression, Android students may only be boasting

The summary of knowledge is shown as follows:

Note: a 32-bit

Common concepts and classifications of locks

We usually hear a variety of concepts about lock nouns, in the previous table, we also see a preference for lightweight lock heavyweight lock figure, next briefly talk about classification and common concepts.

Optimistic lock/pessimistic lock

The optimistic lock and the pessimistic lock are opposite attitudes. In the context of concurrency, “conflicts” can occur when accessing critical sections, with different attitudes evolving into different strategies.

On a pessimistic note, we can assume that conflicts must occur: when accessing a critical section, one thread’s write behavior must affect another thread’s write behavior, and one thread’s read behavior must be affected by another thread’s write behavior! So must carry on the lock protection, through “exclusive”, “exclusive” and other characteristics, guarantee no conflict. That is, pessimistically, a concurrent operation without locking is bound to conflict and must be locked

Optimistically, you can think of collisions as scenario-limited events: reads have no collisions, but writes have the possibility of collisions. Therefore, conflicts are detected only during write operations. When conflicts are detected, the operation fails and an error message is returned

In Java, pessimistic locking refers to various actual lock implementations, while optimistic locking refers to lockless programming that moves to CAS algorithms.

Exclusive lock/shared lock

Locks can be owned or shared by visitors. To put it bluntly, an exclusive lock can only be acquired by one thread at a certain point in time. Other threads must wait for the lock to be released by the owner before they can acquire the lock, while a shared lock can be acquired by multiple threads.

Enjoy a lock to weigh exclusive lock again, row its lock.

Apparently, a shared lock assumes that the threads that hold it do not conflict when operating concurrently.

Reentrant lock/non-reentrant lock

Conceptually, if a thread holds a lock, it can apply for the lock again (multiple times), if so, it is reentrant lock, otherwise, it is not reentrant lock.

It is obvious: non-reentrant greatly increases the chance of deadlock.

However, non-reentrant will be important when implementing a coroutine like mechanism on a threading basis.

Fair lock/unfair lock

Locks need to be acquired through competition. Fair/unfair refers to whether locks are acquired on a first-come-first-served basis.

If the lock is assigned in the order requested, it is a fair lock; otherwise, it is an unfair lock.

Synchronized is an unfair lock. Java ReentrantLock is an unfair lock by default, but can be instantiated as a fair lock.

The advantage of an unfair lock is that the throughput is greater than that of a fair lock.

Mutex, read/write lock

The specific realization of exclusive lock, shared lock, read and write lock as read mode is shared lock.

In Java, ReentrantLock is a mutex lock, and ReadWriteLock is a read-write lock implementation.

Segmented lock

Segmented locking is not a lock, but a design idea to improve efficiency. The critical area is divided. When the writing of a certain area does not affect the reading of other areas, the segmented idea can be used to lock the writing area, while the reading of other areas does not need to compete for locks, thus improving efficiency. ConcurrentHashMap, for example, uses this design

Bias lock/lightweight lock/heavyweight lock

Refers specifically to the three states of synchronized lock, and is related to the lock upgrade part of the later article.

In the previous article, we have spent a lot of time organizing the Mark Word in the object header. There are three states: Biased, Lightweight Locked, and Double Locked.

  • Lock bias: If the synchronized code is always accessed by the same thread, the thread automatically acquires the lock, reducing the cost of acquiring the lock.
  • Lightweight lock state: in the biased lock state, once another thread contests the lock, it is upgraded to lightweight lock, and the competing thread passesFinite spinTry to acquire the lock if the lock holder is in the processRelease the lock, and is successfully acquired by the thread, blocking can be avoided, thread switching is reduced, and suspending and resuming threads is more expensive *.
  • Heavyweight lock status: When a thread has completed a limited spin and still cannot acquire the lock, it has to block to avoid using up CPU, and the lock is upgraded to heavyweight

Understandably, with Java’s threading model, it makes sense to use lightweight locking and spin only with multi-core cpus. With a single-core CPU, there is no real concurrency in the sense of time. At spin, the thread holding the lock is suspended and there is no possibility of releasing the lock

Java’s threading model can be found in my book:Overcoming Anxiety — Illustrating the JVM memory model and JVM threading model

spinlocks

This method is based on CAS to realize synchronization by using spin contention lock. As mentioned above, when spin contention occurs, the current thread will not block, so it will not directly lead to system call and reduce the overhead of context switch. However, if there is no lock contention all the time, the CPU will idle, the so-called busy-waiting. For computationally intensive programs, this can have negative effects.

We can use Atomic to implement a simple reentrant spin lock

public class ReentrantSpinLock {
    private AtomicReference<Thread> cas = new AtomicReference<Thread>();
    private int count;

    public void lock(a) {
        Thread current = Thread.currentThread();
        if (current == cas.get()) {
            count++;
            return;
        }
        while(! cas.compareAndSet(null, current)) {
            // Do nothing}}public void unlock(a) {
        Thread cur = Thread.currentThread();
        if (cur == cas.get()) {
            if (count > 0) {
                count--;
            } else {
                cas.compareAndSet(cur, null); }}}}Copy the code

Obviously, this is also an unfair lock, exclusive lock

Synchronized lock

Synchronized, as a Java keyword, provides synchronization capability. Its core relies on the object header of a Java object. When a class object is used as a synchronized lock object, it is called Monitor

class Foo {

    synchronized static foo(a) {}synchronized void bar(a) {}void baz(a) {
        synchronized (Foo.class) {
            / / the synchronized block}}}Copy the code

Three types of synchronization are shown in the code above:

  • foo()The Monitor corresponding to the lock isFoo.class
  • bar()Is an instance of an object whose Monitor is Foo
  • baz()The synchronization block in the Monitor can use any object as Monitor, as demonstrated in the demoFoo.classAs a Monitor

Note that Monitor must be carefully selected, not only to avoid performance loss from the perspective of synchronization requirements, but also to pay attention to the problem that the lock does not take effect normally. Such as:

We simulate 5 threads competing for a number (starting with 6) and doing –. Does the reader think it will output in order of 5, 4, 3, 2, 1?

class Foo {

  Integer integer = 6;

  void minus(a) {
    synchronized (integer) {
      if (integer > 0) {
        integer--;
      }
      System.out.println(Thread.currentThread().getId() + " -> i:"+ integer); }}static class MThread extends Thread {
    final Foo foo;
    final CountDownLatch latch;

    MThread(Foo foo, CountDownLatch latch) {
      this.foo = foo;
      this.latch = latch;
    }

    @Override
    public void run(a) {
      super.run();
      try {
        latch.await();
        foo.minus();
      } catch(InterruptedException e) { e.printStackTrace(); }}}public static void main(String[] args) {
    Foo foo = new Foo();
    CountDownLatch latch = new CountDownLatch(1);

    for (int i = 0; i < 5; i++) {
      new MThread(foo,latch).start();
    }
    latch.countDown();
    try {
      Thread.sleep(1000);
    } catch(InterruptedException e) { e.printStackTrace(); }}}Copy the code

A few more times, you might find something like the following, which is not the result of a synchronous case. If you want to simulate the problem more smoothly, increase the number of threads

> Task :Foo.main()
13 -> i:3
15 -> i:4
12 -> i:3
14 -> i:1
11 -> i:2
Copy the code

If you are paying attention to Lint, you will notice the prompt: Synchronization on a non-final field ‘INTEGER’

It is clear that the above code does not use the correct Monitor, and the integer instance has changed during integer– :

System.out.println(Thread.currentThread().getId() + 
        " -> i:" + integer+","+System.identityHashCode(integer));
Copy the code

We add identityHashCode and increase the number of concurrent requests to 10.

13 -> i:0.482590393
15 -> i:1.1722967101
11 -> i:3.1130778910
16 -> i:0.482590393
17 -> i:0.482590393
20 -> i:0.482590393
12 -> i:4.685260083
14 -> i:2.1983109557
19 -> i:0.482590393
18 -> i:0.482590393
Copy the code

Apparently, locked up a lonely. Of course, if you dig deeper into this problem, you can dig all the way to the dynamic constant pool.

Therefore, it is important to keep good habits in your coding: Monitor objects are immutable and bugs are invisible.

Lock escalation

Lock upgrades have already been mentioned:

Partial lock -> Lightweight lock -> heavyweight lock, lock upgrade is one-way

This is actually an optimization of synchronized’s internal implementation

Transformation reason

Obviously, this process takes into account the advantages and disadvantages of various locks in order to achieve the best performance in the appropriate scenario.

  • Biased lock: No spin, no system call, soLow consumption and high performance, and has reentrant characteristics, inThe same thread executes synchronized codeScenario is optimal, but it hasHigh cost of unlockingFaults.
  • Lightweight locks: As mentioned earlier, CAS is used instead of blocking inLock holding time is shortScenario is the optimal choice, can be pursuedA quick response, but the disadvantage is that the spin consumes CPU resources when the lock cannot be acquired for a short period of time.
  • Heavyweight lock: YesBig throughputThreads that do not compete for locks do not spin to consume resourcesLocking takes a long time and requires a large throughputThe scene of

Moving from a biased lock to a lightweight lock means that multiple threads compete, assuming that the lock is held for a short time and that the limited spin can wait until the holder releases the lock. Upgrading from a lightweight lock to a heavyweight lock means that this assumption is not true and that the spin is simply wasted, increasing throughput by suspending and waiting for wake up

The conversion process

This is available from OpenJdk’s WIKI — Synchronization.

For the widely circulated image of the original

A picture is worth a thousand words. The picture is very clear, and readers can understand it by themselves based on the WIKI content.

In a diagram often advertised for courses, collecting does not equal learning:

Image watermark blog.dreamtobe.cn

A long postscript

In the series outline, the original title of this article was: Java multithreaded series – control interview, a thorough understanding of the Lock, however, when writing to the JDK Lock interface, the realization of the realization will have to go deep into the source code and involves AQS, AQS content in the outline has a single plan, the length is too long is not conducive to reading, not to expand is really no content to write.

The content of the original chapter is reserved as the beginning and introduction at the end of the article:

Lock interface in the JDK

After Jdk1.5, there is the Lock interface:

public interface Lock {
    / / acquiring a lock
    void lock(a);

    // Get the lock and throw an exception if the thread's blocking state is interrupted
    void lockInterruptibly(a) throws InterruptedException;

    // Try to get the lock
    boolean tryLock(a);

    // Try to acquire the lock within the given time,
    boolean tryLock(long var1, TimeUnit var3) throws InterruptedException;

    void unlock(a);

    Condition newCondition(a);
}
Copy the code

The first four apis are lock acquiring apis, unlock releases locks, and Condition provides thread communication capabilities. Condition will be expanded in a future article

Unlike the language keyword synchronized, Lock requires the user to acquire and release the Lock. In terms of internal implementation, different from Monitor mode, richer functions are added:

  • supportFairness of locks
  • To obtainThe number of times the current thread called lock
  • To obtainNumber of threads waiting for a lock
  • The queryWhether there is a thread waiting to acquire the lock
  • The queryWhether the specified thread is waiting to acquire the lock
  • The queryWhether the current thread holds the lock
  • judgeWhether the lock is already held
  • If the lock is interrupted, the lock is not locked and an exception is thrown
  • Attempt to acquire a lockIf the lock is not held by another thread, it succeeds; otherwise, it returns failure and does not block directly

Obviously, due to the limitations of goal and length, this article will not explore the source code with the readers, and at this point, I realize that it is really not possible to do the title: “one article can be locked.” There are also lock implementations in the JDK, for example:

  • ReentrantLock
  • ReadWriteLock, generally using implementation classesReentrantReadWriteLock

Once we get into it, we will have to talk about AQS. As planned, this will be developed in a subsequent article, so we will not do so in this article. I hope you’ll forgive me

Real postscript

This article wrote more than a week off and on again, I also suspected, do you want to continue this series, for readers to buy a book to study may be more really than watching this series of behaviors, tasks savants do famously well-proofreading knowledge accuracy, the text, better accuracy, expressing the structural of the blog can only rely on fragmentation characteristics of cheap.

But one thing confirmed my commitment to writing this story. I looked at past blogs and it became clear to me:

  • Put the knowledge in your mind, and then do itStructured output, can grasp these knowledge reliably, and can complete fluent expression at any time
  • Through comparison, I can clearly see my own growth
  • Writing skills can be greatly improved through practice