In concurrent programming, it is common to encounter multiple threads accessing the same shared resource. At this time, developers must consider how to maintain data consistency. Synchronized keyword is often used to maintain data consistency in Java. The synchronized mechanism locks the shared resource, and only the thread that obtains the lock can access the shared resource. In this way, the access to the shared resource is forced to be sequential, because it is necessary and necessary to access the property of the shared resource. To understand the locking mechanism, we need to understand the concurrency architecture in Java: java.util.concurrent(J.U.C).
Atomic operation
Start with relatively simple Atomic (java.util.Concurrent is queue-based and sends packets, whereas Queue, in many cases, uses Atomic operations, so start there first). In many cases we simply need a simple, efficient, thread-safe incrementing and decrement scheme. Note that there are three conditions:
Simple, which means that programmers need to work as little as possible on the bottom layer, or it should be easier to implement.
High efficiency means less resource consumption and faster program processing;
Thread safety is also very important, which ensures data correctness in multiple threads. These three conditions may seem simple, but the implementation is not satisfactory.
Older versions were implemented in pure Java and inevitably used the synchronized keyword.
public final synchronized void set(int newValue);
public final synchronized int getAndSet(int newValue);
public final synchronized int incrementAndGet();
Volatile is also used on variables to ensure that get() does not lock. While synchronized is still expensive, the pure Java language can’t do it without JNI. In JDK 5.0, modern CPU features are reused to reduce lock consumption. These principles and properties are discussed in the final summary of this chapter. Before we do that, let’s look at the use of the API. Everything from Java. Util. Concurrent. Atomic. AtomicInteger began.
TomicIntegerArray AtomicLongArray/AtomicReferenceArray API similar, choose typical AtomicIntegerArray to describe these issues. Int get(int I) Gets the current value of position I. Obviously, as a result of this is array operations, there is an index of crossing problem (IndexOutOfBoundsException exception).
2. Volatile semantics
Volatile exists extensively in J.U.C, but the semantics of volatile are still not understood.
Volatile is a weak implementation of synchronized, which means that volatile implements synchronized semantics without locking. It ensures that updates to volatile fields inform other threads in a predictable manner. Volatile contains the following semantics:
(1) The Java storage model does not reorder operations on valatile instructions: this ensures that operations on volatile variables are performed in the order in which the instructions appear.
(2) Volatile variables are not cached in registers (visible only to owning threads) or elsewhere invisible to the CPU. The results of volatile variables are always read from main memory. This means that changes to volatile variables are always visible to other threads and are not used by variables inside their own thread stack. That is, in the happens-before rule, after a write to a valatile variable, any read understands the result of that write.
While volatile variables are good, they are not thread-safe. That is, operations on volatile fields are not atomic. Volatile variables are only visible (changes made by one thread can be understood by other threads). The only way to keep atomicity is to lock it so far!
There are three principles for using volatile variables:
(1) Writing variables does not depend on the value of the variable, or only one thread modifies the variable
(2) The state of a variable does not need to participate in invariant constraints with other variables
(3) Access variables do not need to be locked
3. Happens-before rule
The Java storage model has A happens-before principle, which states that if action B wants to see the result of action A (whether or not A/B is executed in the same thread), then A/B needs to satisfy the happens-before relation. Before introducing the happens-before rule, I introduce one concept: JMM Action (Java Memeory Model Action), Java Storage Model Action. An Action includes reading and writing variables, monitor locking and releasing locks, and thread start() and join(). We’ll talk about locks later.
————- Next, we’ll look at the types of locks and their use ————-
1. Pessimistic lock optimistic lock
1. The pessimistic locking
They distrust the world and believe that conflicts are bound to occur, so they lock up resources before using them and have strong characteristics of exclusivity and exclusivity. Pessimistic lock thinks that someone will access the target resource at the same time with it, so it must be locked first. Common exclusive locks such as synchronized and ReentrantLock are the realization of pessimistic lock thought.
Each time a thread accesses the resource (method), count is 1, meaning that only one thread is accessing it, and that thread locks the resource before accessing it, causing the other threads to wait.
Two. Optimistic lock
Optimistic locking is when an operation is performed each time without locking, assuming no conflicts, and if it fails due to conflicts, retry until it succeeds. The mechanism used for optimistic locking is CAS, Compare and Swap. CAS has three operands, the memory value V, the old expected value A, and the new value B to modify. Change the memory value V to B if and only if the expected value A and memory value V are the same, otherwise nothing is done.
Take out AtomicInteger and investigate how data correctness can be achieved without locking. private volatile int value; First of all, without locking, volatile primitives may be needed to ensure that data is visible (shared) between threads. So that when we get the value of the variable, we can read it directly.
An important prerequisite for CAS algorithm implementation is to take out the data in memory at a certain time and compare and replace it at the next time, so the time difference class will lead to data changes at this time. Let’s say one thread fetches A from location V, and two thread two fetches A from location V, and two does something to change it to location B, and then two changes the data from location V to location A, Thread one performs the CAS operation and finds that A is still in memory. Then thread ONE succeeds. Although the CAS operation on thread one was successful, it does not mean that the process was problem-free. If the head of the list changes twice and then returns to its original value, it does not mean that the list has not changed. So the aforementioned atomic operation AtomicStampedReference/AtomicMarkableReference is very useful. This allows atomic manipulation of a pair of changing elements. ABA problem
Three AQS.
AbstractQueuedSynchronizer, referred to as “AQS, abstract queue type synchronizer, AQS defines a set of synchronizer framework for multithreaded access to a Shared resource, many synchronization class implements are dependent on it, such as commonly used already, below is a simple model:
AQS has a volatile int state (a shared resource, volatile is visible to other threads if the current thread changes the valotile variable) and a FIFO thread wait queue (a FIFO thread wait queue if a multithreaded contention resource is blocked). Essentially a bidirectional linked list, each node holds a blocked thread, multiple threads compete for limited resources, the thread blocking arrangement).
In general, state is initialized to 0, indicating an unlocked state. If thread A can get the lock, 0→1, set the current thread as the exclusive lock; Otherwise, enter the wait queue.
The basic idea is to represent a synchronizer that supports the following two operations:
Lock acquisition: First determine whether the current state allows lock acquisition, if yes, lock acquisition, otherwise the operation or acquisition failure, that is, if the exclusive lock may be blocked, if the shared lock may fail. In addition, if it is a blocking thread, then the thread needs to enter the blocking queue. The state is modified when the status bit allows the lock to be acquired, and removed from the queue if it is enqueued.
Release lock: This process is to modify the status bit and wake up one or more threads in the queue if one thread is blocked because of the status bit.
To support the above two operations, the following conditions must exist:
The state bit of the atomic operation synchronizer — CAS
Block and wake up the thread
An ordered queue –CLH
Fair lock and unfair lock
If a lock is acquired in the order requested, it is a fair lock, otherwise it is an unfair lock. Before diving into the internal mechanics and implementation, let’s understand why fair and unfair locks exist. Fair locking guarantees that a blocked thread will eventually acquire the lock, and because it is ordered, it can always acquire the lock in the order requested. An unfair lock means that the thread that requested the lock later may acquire it before the dormant thread in front of it resumes, potentially improving concurrency performance. This is because there is usually a significant delay between the restart of a suspended thread and the actual running of it. Therefore, an unfair lock can use this time to complete the operation. This is one of the reasons unfair locks perform better than fair locks some of the time.
The biggest difference is mainly lies in the fact that both the fairness of fair lock mainly reflects in acquiring a lock whether the thread is waiting for the head of the queue nodes, so every time to judge whether the current thread has a precursor node in the waiting queue: if there are instructions to have the request of the earlier than the current thread, according to fairness, the current thread request resource failure; If the premise prev=null is true, the subsequent judgment will be made.
Exclusive and shared locks
Exclusive lock: also called exclusive lock, mutex, only one thread at a time can hold a critical resource.
Shared lock: Allows multiple threads to access a critical resource simultaneously. This is most commonly seen with ReadLock, which allows multiple threads to read data and improves performance. However, it should be noted that the purpose of read lock sharing is to improve efficiency under the high frequency access of multiple threads. If the thread traffic is not large, the cost of maintaining read lock will be too high, and the loss will be felt as if the gain is outweighed by the loss.
6. Built-in lock
Built-in lock is also known as implicit lock. Java has built-in lock realized by synchronized. Synchronized is very convenient to maintain multithreaded synchronization, without manually obtaining and releasing the lock.
Features:
Synchronized is a mutex that allows only one thread at a time to access modified code;
Atomicity: Blocks of code modified by synchronized are atomicity and are executed once.
Visibility: After the execution of synchronized modified code, the results are visible to other threads.
Explicit locking
Lock An explicit Lock is an interface to obtain the Lock in the Lock mode. The Lock mode can be interrupted, not obtained after timeout, and is non-blocking. It improves semantics, where locks are placed and unlocked have to be written out. Lock explicit locks give us great flexibility, but at the same time we have to release the locks manually. It supports Condition objects that allow multiple reader threads to access shared resources simultaneously.
A good example of an explicit lock is ReentrantLock, so let’s talk about this in more detail.
reentrancy
In ReentrantLock, state is initialized to 0, indicating that the state is not locked. When thread A locks (), tryAcquire() is called to monopolize the lock and state+1. After that, another thread will fail to tryAcquire() until the unlock() of thread A reaches state=0. Of course, thread A can repeatedly acquire the lock itself before releasing it (state will accumulate), which is the concept of reentrant. But be careful to release it as many times as you get it, so that state can go back to zero.
Support fair lock ReentrantLock(true)
Support unfair lock ReentrantLock()/ReentrantLock(false)
A brief process for fair locking:
If state=0, the current lock has not been acquired by any thread. If the current thread is the oldest node in the queue, return false. If so, prove that the current thread is the first node in AQS waiting to acquire the lock, and try to acquire the lock based on CAS operation (0→1). If successful, set the current thread as an exclusive lock with state=1.
If the state! =0, prove that the lock is held by a thread, then determine whether the thread holding the lock is the current thread. If so, try to acquire the lock again (reflecting ReentrantLock). If the number of times of acquiring the lock does not exceed the upper limit, then update state is the final number of times that the current thread acquired the lock, and the result returns true. Otherwise, false is returned if the number of times the current thread has acquired the lock exceeds the upper limit, or if the current thread is not the thread holding the lock.
Based on the CAS operation, if successful, the thread currently set as the exclusive lock; If it fails, judge the state again. If it is 0, try the CAS operation 0→1 again. If it succeeds, set the current thread as the thread with the exclusive lock. In case of failure or state! =0, check whether the current thread is the exclusive lock thread (yes: state+1; No: encapsulate the thread in a node and queue it.
A brief procedure for unfair locking:
Determine whether the state representing the lock state is 0: if state=0, it proves that the lock is not currently held by any thread, and the current thread can try to obtain an unfair lock based on CAS operation (0→1). If it succeeds, the current thread will be set as the thread holding the lock. If this fails, it proves that another line acquired the lock first, and returns false. If the state! Therefore, it is necessary to determine whether the current thread is the thread that holds the lock. If so, try to acquire the lock again. If the total number of times that the current thread holds the lock does not exceed the upper limit, it means that the current thread has successfully acquired the lock. Otherwise, return false.
Eight Condition.
Condition variables is a big part in order to solve the Object. The wait/notify/notifyAll hard to use.
A condition (also known as a conditional queue or condition variable) provides a meaning for a thread to keep it suspended (that is, let it “wait”) until it is notified by another thread whose state condition may now be true. Because access to this shared state information occurs in different threads, it must be protected, so some form of lock is associated with this condition. The main attribute of waiting to provide a condition is to release the associated lock atomically and suspend the current thread, just as Object.wait does.
9. Atresia
Latch: Stands for CountDownLatch, a synchronization method that delays the progress of a thread until it reaches an endpoint state. Popular speak be, a closure is equivalent to a gate, all threads are blocked before the doors opened, once the doors open all threads will be through, but once the door opened, all threads are passed, then the blocking state of failure, the state of the door also cannot be changed, can only be open. This means that the state of the lock is one-time, which ensures that all specific activities before the lock is opened need to be completed after the lock is opened.
Semaphore: A Semaphore is a counter that releases threads if the counter is not zero. Once it reaches zero, all new threads requesting resources are blocked, including adding requests to permitted threads, meaning Semaphore is not reentrant. Each time a license is requested, the counter decreases by 1, and each time a license is released, the counter increases by 1. Once 0 is reached, the new license request thread is suspended.
Distributed locking
To ensure that a method or attribute can only be executed by the same thread at the same time in the case of high concurrency, Java concurrent processing apis (such as ReentrantLock and Synchronized) can be used for mutual exclusion control in the case of single application deployment. In a stand-alone environment, Java provides many apis for concurrent processing. But with the needs of the development of business, the original single standalone deployment system was evolved into the distributed cluster system, due to the distributed system multithreading, multi-process and distribution on different machines, it will make the original single deployment of concurrency control lock strategy fails, pure Java API does not provide the ability of distributed lock. To solve this problem, you need a mutual exclusion mechanism across JVMS to control access to shared resources, and that’s where distributed locking comes in!
What are the conditions for a distributed lock?
1. In distributed system environment, a method can only be executed by one thread of a machine at a time;
2. Highly available lock acquisition and lock release;
3. High-performance lock acquisition and lock release;
4. Reentrant characteristics;
5. Have lock failure mechanism to prevent deadlock;
6. Has the non-blocking lock feature, that is, if the lock is not obtained, the system directly returns the lock acquisition failure.
Distributed locks are implemented in three ways:
Implement distributed lock based on database
Disadvantages:
1. This lock is strongly dependent on the availability of the database. The database is a single point, once the database fails, the business system will become unavailable.
2. The lock has no expiration time. If the unlocking operation fails, the lock record will remain in the database and other threads will not be able to obtain the lock.
3. The lock must be non-blocking because an insert error is reported when the insert fails. A thread that does not acquire the lock is not enqueued, and the lock acquisition operation must be triggered again to acquire the lock again.
4. The lock is non-reentrant and cannot be acquired again by the same thread without releasing it. Because the data in the data already exists.
Solution:
1. Is the database a single point? Have two databases, two-way synchronization before data. If you fail, quickly switch to the standby database.
2. No expiry time? Just do a scheduled task to clean up the timeout data in the database at regular intervals.
3. Non-blocking? Do a while loop until insert succeeds and then return success.
4. Non-reentrant? Add a field in the database table, record the host information and thread information of the current machine to obtain the lock, then the next time to obtain the lock when the first query database, if the host information and thread information of the current machine can be found in the database, directly assign the lock to him.
2. Distributed lock based on cache (Redis, etc.)
Use the lock command setnx
Disadvantages:
There are obvious races in this scenario (master-slave) :
Client A obtains the lock from the master,
The master crashed before the master synchronized the lock to the slave.
The slave node is promoted to master node.
Client B has obtained another lock on the same resource already obtained by client A. Safety failure!
3. Implement distributed lock based on Zookeeper
Realize the principle of
Using zookeeper node to implement distributed lock, create a temporary sequence is suitable for the sequential program, general idea is to create a temporary sequence nodes, find out the minimum sequence nodes, access to distributed lock, disappear after completion of the program execution sequence nodes, through the watch to monitor the change of the nodes, find the smallest sequence from the rest of the node, Obtain distributed locks, perform corresponding processing, and so on.
Implementation steps
Multiple JVMS simultaneously create the same node on Zookeeper (/Lock)
Zk node unique! Can’t repeat! The node type is temporary. When JVM1 is created successfully, an error message is displayed when JVM2 and JVM3 are created, indicating that the node already exists. At this point jVM2 and JVM3 wait.
Jvm1’s program is now complete, performing the lock release. Close the current session. The temporary node no longer exists and the event notifies Watcher, JVM2, and JVM3 to continue creation.
Ps: Notification will be delayed when zK forcibly shuts down. However, when the close() method is closed, the delay is small
If the program never completes, it may cause a deadlock (others wait). Set the validity period ~ directly close() off actually the connection is also set the validity period.