CAS and synchronized knowledge

One . CAS

What is the CAS.

CAS（Compare And Swap ） It's an implementation of optimistic lock , It's a lightweight lock .JAVA1.5 It's starting to introduce CAS,JUC Many tool classes are based on CAS.

CAS How to implement

CAS Yes 3 Operands , Memory value V, Old expectations A, New value to modify B. If and only if expected A And memory values V Phase at the same time , Put the memory value V It is amended as follows B, Otherwise, do nothing . When multiple threads try to use CAS When updating a variable , Only one thread can update successfully at any time , If the update fails , The thread will re-enter the loop and try again .

CAS stay Java Application in

I said that before JUC Many tool classes below are used CAS. It mainly depends on Unsafe Of CAS Operation to realize .
for example AtomicInteger Under the incrementAndGet operation ：

Let's take a look at Unsafe Under the getAndAddInt Method

You can see Unsafe In the loop body, first read the in memory value value , then CAS to update , If CAS If the update is successful, exit , If the update fails , Then retry circularly until the update succeeds .

CAS The problems brought about by

ABA problem

For example, ：
One . Threads 1 Whether the query value is A
Two . Threads 2 Whether the query value is A
3、 ... and . Threads 2 Use CAS Update the value to B
Four . Threads 2 Whether the query value is B
5、 ... and . Threads 2 Use CAS Update the value to A
6、 ... and . Threads 1 Use CAS Update the value to C
Thread one and thread two execute alternately . Step 2 to step 5 , Thread 2 sets the value from A Updated to B From to A, But the thread didn't notice , Therefore, thread one can continue to execute . We call this phenomenon ABA problem .
resolvent ：
Use version number （ Time stamp ）, Every time you perform data modification , They all carry a version number , Once the version number is consistent with the version number of the data, you can perform the modification operation and add one to the version number , Otherwise, the execution fails . for example AtomicStampedReference By adding a stamp to the value (stamp) To solve “ABA” The problem of .

The cycle overhead is too high

CAS If the operation is unsuccessful , Will cause constant spin ,CPU There will be a lot of pressure . For example, Unsafe Under the getAndAddInt The method will always loop , It won't return until success .

Only atomic operation of one variable can be guaranteed

Two . synchronized

Compared with CAS Based on optimistic lock implementation ,synchronized It is based on pessimistic lock , When a thread tries to access a synchronized block of code , It must first get the lock , The lock must be released when exiting or throwing an exception .

When locking with common synchronization methods , The lock is the current instance object .

When locking the static synchronization method , The lock is for the current class Class object .

For synchronous method block locking , The lock is Synchonized Objects configured in parentheses .

Synchronized How to implement ：
Synchonized It's based on entry and exit Monitor Object to synchronize methods and code blocks , But the implementation details of the two are different .Synchronized When used in methods , In bytecode, it is through method ACC_SYNCHRONIZED Logo to achieve . Code block synchronization uses monitorenter and monitorexit Instruction implementation .
monitorenter Instructions are inserted at the beginning of a synchronized block of code after compilation , and monitorexit Is inserted at the end of the method and at the exception ,JVM Make sure that each monitorenter There must be a corresponding monitorexit Match it . Any object has one monitor Associated with it , When and one monitor After being held , It will be locked . Thread execution to monitorenter When the command , Will try to get the corresponding monitor The ownership of the , That is, trying to get the lock of the object , When getting the object monitor in the future ,monitor The internal counter will automatically increase （ For the initial 0）, When the same thread gets monitor When , The counter will self increment again . When the same thread executes monitorexit At the time of instruction , The counter will automatically decrease , When the counter is 0 When ,monitor Will be released , Other threads can get monitor.

Synchronized The optimization of the
Java SE 1.6 In order to reduce the performance consumption of acquiring lock and releasing lock , Introduced “ Biased locking ” and “ Lightweight lock ”, stay Java SE 1.6 in , There's a lock 4 States , The order of rank from low to high is ： No lock state 、 Biased lock state 、 Lightweight lock state and heavyweight lock state .

Biased locking
When a thread accesses a synchronization block and acquires a lock , The thread with lock bias will be stored in the lock record in the object header and stack frame ID, In the future, the thread does not need to enter or exit the synchronization block CAS Operate to lock and unlock , Just test the head of the object Mark Word Whether there are biased locks pointing to the current thread stored in . If the test is successful , Indicates that the thread has acquired the lock . If the test fails , It needs to be tested again Mark Word Whether the sign of the middle biased lock is set to 1（ Indicates that the current lock is biased ）, If not set , Then use CAS Competitive lock ; If set , Then try to use CAS Point the biased lock of the object header to the current thread .

Lightweight lock
Thread before executing synchronization block ,JVM The space used to store the lock record will be created in the current thread's stack frame first , And Mark Word Copy to lock record . Then the thread tries to use CAS Put the Mark Word Replace with a pointer to the lock record . If it works , Current thread gets lock , If you fail , Indicates that other threads are competing for locks , The current thread attempts to acquire a lock using spin .

Heavyweight lock
Heavyweight locks depend on the inside of the object monitor Lock to achieve . When the system checks that the lock is a heavyweight lock , The thread waiting for the lock will be blocked , Blocked threads don't consume cup. But when you block or wake up a thread , You need the operating system to help , Need to switch from user mode to kernel mode , And switching states takes a lot of time .