Hello, I am Java No doubt (WX public account of the same name), this is the third article in the column.

In the previous two articles, I introduced volatile, CAS, and their implementation in the processor.

It is important to remember that volatile and CAS are the most basic tools, and that synchronization of shared variables in real business scenarios is very complex, so they are rarely used directly to deal with synchronization.

Based on this tool above we can be encapsulated into a “lock”, convenient for us to solve the multithreaded synchronization problem. Today I’ll talk about synchronization based on Volatile + CAS, which is semaphores and tubes.

A semaphore

The concept of semaphores was invented by Dutch computer scientist Edsger W. Dijkstra in 1965 and is widely used in different operating systems. In the system, each process is given a semaphore, which represents the current state of each process. The process without control is forced to stop at a specific place and wait for a signal to continue. If the semaphore is an arbitrary integer, it is often called a counting semaphore.

Semaphores should have been studied in the book “Computer Operating System”, and I will briefly introduce them.

Semaphores can be thought of as special variables that can be increased or decreased, and are atomic.

Integer semaphore

First let me look at an integer semaphore. An integer semaphore is defined as an integer number of resources, S, which can only be operated by atomic operations P and V.

When a thread wants to use a shared variable, it obtains the semaphore first. If it does, it is allowed to use the shared variable.

Wait (S): while(S <= 0) {// wait(S) = s-1; Signal (S): S = S + 1;Copy the code

As an example, let’s say we have a conference room that has a limited number of participants (no standing allowed) because of the limited number of chairs in the conference room. In this case, we use the conference room as a shared variable and the participants as threads. In order to prevent multiple people (threads) from entering the conference room at the same time (shared variables), the organizer placed a box at the door of the conference room. Inside the box were some tickets (semaphore S). The small box only allowed one person to reach for the tickets (atomic).

When there is only one ticket in the box (the semaphore S value is 1), the meeting room (shared variable) allows only one person (thread) to enter, and the meeting room (shared variable) is mutually exclusive.

Ok, so that’s the introduction to integer semaphores. Using integer semaphores, we have a very simple lock. We abstracted the concept of tickets, and only need to get tickets (semaphore S) to access the shared variable synchronously.

Recording semaphore

The integer semaphores above are very crude and flawed. In wait operations, for example, the loop continues as long as S<=0, and multiple threads accessing the same semaphore can consume CPU resources.

The solution is also simple, we add a linked list (queue) L, the process fails to acquire the semaphore resource, will call the block primitive to self-block, and insert in the linked list L to wait.

When another thread releases the semaphore, it performs signal to release the resource. If there is a process in list L, the wakeup primitive is called to wakeup the first waiting process in list L, and the waiting thread attempts to acquire the semaphore.

AND type semaphore

The above problem is to solve the problem that multiple processes share the same shared variable. If multiple processes share multiple shared variables, deadlock will occur.

In the following example, process A obtains resources from S1, and process B obtains resources from S2. When process A attempts to obtain resources from S2, the process is blocked, and process B tries to obtain resources from S1. Therefore, in the absence of external force, neither of them can be recovered in the blocking state and deadlock occurs.

process A: wait(S1);
process B: wait(S2);
process A: wait(S2);
process B: wait(S1);
Copy the code

The idea of the AND synchronization mechanism is to consistently allocate resources required by a process during its entire running process to the process. If one resource fails to be allocated to the process, other resources need to be released.

Wait (S1,... , Sn) : the if (S1 > = 1 and... and Sn >= 1) { for(int i = 1; i <= n; i++) { Si = Si - 1; }} else {// put into wait queue} signal(S1,...... ,S3): for(int i = 1; i <= n; i++) { Si = Si + 1; } // The wait queue is removedCopy the code

Semaphores can solve synchronization problems in concurrency, and only Semaphore in the JUC concurrency utility class in Java implements semaphores. Semaphore in Java is not very useful, as multiple threads accessing a critical section at the same time can cause atomicity problems. You can of course set it to allow only one thread to enter, but it might be better to use a pipe in that case.

Java implements locking based on pipe procedures. Let’s take a look at what pipe procedures are and how they are implemented in Java.

Tube side

The tube process (Monitor, also known as Monitor) is proposed by Tony Hall and Bo parker Hansen, and first implemented by Bo parker Hansen in parallel Pascal. Tony Hall has shown that this is equivalent to the semaphore.

For the pipe process, we directly look at the following figure (picture source network) :

First, when multiple threads want to enter the critical area, they will acquire the lock first. If they cannot obtain the lock, they will enter the synchronization queue, and the thread in the synchronization queue waits for other threads to release the lock. If the condition is not met, it will enter the waiting queue. In order to obtain the lock again, it must wait for other threads to call notify to wake up the first thread in the waiting queue, and enter the queue in the synchronization queue. Or wait for another thread to call notifyAll to put all threads in the wait queue into the synchronization queue.

Synchronized in Java uses a pipe procedure.

Synchronized and monitor

Synchronized has only one condition variable (condition), which is different from the above figure.

In Java, every Object corresponds to a monitor, so there are wait(), notify(), and notifyAll () methods in the Object class.

final Object lock = new Object(); Synchronized (lock) {while(condition not satisfied) {lock.wait(); } // The process is complete // the resource is released, and the condition is lock.notifyall (); }Copy the code

As shown in the code above, when a thread enters a pipe, it first adds a lock. If it obtains the lock, it enters the pipe. If it does not acquire the lock, it enters the synchronization queue.

So how do synchronized locks work? There are two variables in monitor. One is the _owner variable, which holds which thread enters the pipe. This variable is similar to the semaphore S. Synchronized is a reentrant lock, so you need a counter to keep the number of reentrants. The counter variable is: count.

Once the lock is acquired, enter the pipe, which is the synchronized curly brace in the code above.

Once in the pipe, you can use while() to determine if the condition variable is satisfied. Of course, in the actual development process, the condition variable is seldom used.

If the conditions are not met, the wait() method in Object is called to enter the wait queue.

NotifyAll () calls notifyAll. NotifyAll () calls notifyAll. NotifyAll () calls notifyAll.

The above procedure also explains why wait(), notify(), and notifyAll () require locks to execute.

conclusion

In this article, I’ve introduced semaphores and pipe procedures, as well as the implementation of pipe procedures in Java. I hope you have a harvest after reading, limited to personal level, if the article is wrong, but also hope readers don’t hesitate to comment.

In the following articles, I’ll dive into the topic of this column, which is the introduction and implementation of JUC concurrent classes.

Finally, if my article is helpful to you, please help me like and forward!

If you’re not familiar with volatile and CAS, take a look at the first article, “Getting to the bottom of it”, which gives you an in-depth understanding of the JUC concurrency utility classes — Volatile and CAS.

If you want to learn more about how Valatile works, take a look at the second article, “Get to the bottom of it”, which gives you an insight into the JUC Concurrency utility Class — Cache consistency and memory barriers.

You can also visit the column’s navigation article, “Get to the Bottom of it: An inside Look at the JUC Concurrency Tool Class — The Beginning.”