多线程 - CAS、ABA

妖狐艹你老母 2024-03-22 14:35 54阅读 0赞

## CAS ##

“CAS”通常是指“Compare and Swap”（比较并交换），它是一种用于实现并发算法的原子操作。  
它允许线程在修改共享变量之前比较该变量的值，并在值匹配时将其替换为新值。这种机制可用于实现非阻塞算法和无锁数据结构。

import java.util.concurrent.atomic.AtomicInteger;
    
    public class MyCASExample {
        
        private AtomicInteger count = new AtomicInteger(0);
    
        public void increment() {
        
            int expectedValue, newValue;
            do {
        
                expectedValue = count.get();
                newValue = expectedValue + 1;
            } while (!count.compareAndSet(expectedValue, newValue));
        }
    
        public int getCount() {
        
            return count.get();
        }
    
        public static void main(String[] args) {
        
            MyCASExample example = new MyCASExample();
    
            int numThreads = 100;
            Thread[] threads = new Thread[numThreads];
            for (int i = 0; i < numThreads; i++) {
        
                threads[i] = new Thread(() -> {
        
                    for (int j = 0; j < 1000; j++) {
        
                        example.increment();
                    }
                });
                threads[i].start();
            }
    
            for (int i = 0; i < numThreads; i++) {
        
                try {
        
                    // 等待所有线程完成
                    threads[i].join();
                } catch (InterruptedException e) {
        
                    e.printStackTrace();
                }
            }
    
            System.out.println("Count: " + example.getCount());
        }
    }

## ABA ##

ABA问题是一个与CAS操作相关的问题。假设一个线程读取了一个共享变量的值A，然后另一个线程将该变量的值从A更改为B，  
最后又将其改回A，然后第一个线程尝试使用CAS操作将该变量的值从A更改为C。  
由于第一个线程在进行CAS操作时，该变量的值仍然为A，因此CAS操作将成功，尽管在此期间该变量的值已经更改为B并再次更改回A。

import java.util.concurrent.atomic.AtomicStampedReference;
    
    public class MyABAExample {
        
        private static AtomicStampedReference<String> ref = new AtomicStampedReference<>("A", 0);
    
        public static void main(String[] args) {
        
            String initialRef = ref.getReference();
            int initialStamp = ref.getStamp();
            // A -> B -> A
            Thread thread1 = new Thread(() -> {
        
                ref.compareAndSet(initialRef, "B", initialStamp, initialStamp + 1);
                ref.compareAndSet("B", initialRef, initialStamp + 1, initialStamp + 2);
            });
            //  A -> C
            Thread thread2 = new Thread(() -> {
        
                int stamp = ref.getStamp();
                while (!ref.compareAndSet(initialRef, "C", stamp, stamp + 1)) {
        
                    stamp = ref.getStamp();
                }
            });
            thread1.start();
            thread2.start();
            try {
        
                thread1.join();
                thread2.join();
            } catch (InterruptedException e) {
        
                e.printStackTrace();
            }
            System.out.println("Final value: " + ref.getReference());
        }
    }

## 解决ABA ##

解决ABA问题的常见方法是使用版本号或标记，将变量的值与版本号或标记一起比较和交换。  
例如，在Java中，AtomicStampedReference类可以用于解决ABA问题。  
它存储一个对象引用和一个版本号，当使用CAS操作进行更新时，同时需要检查对象引用和版本号是否与期望值匹配。

import java.util.concurrent.atomic.AtomicStampedReference;
    
    public class MyAtomicStampedReferenceExample {
        
        private static AtomicStampedReference<String> ref = new AtomicStampedReference<>("a", 0);
    
        public static void main(String[] args) {
        
            Thread thread1 = new Thread(() -> {
        
                String expectedValue = "a";
                String newValue1 = "b";
                String newValue2 = "a";
                int expectedStamp = ref.getStamp();
                int newStamp1 = expectedStamp + 1;
                int newStamp2 = newStamp1 + 1;
    
                // 第一次更改，增加版本号
                ref.compareAndSet(expectedValue, newValue1, expectedStamp, newStamp1);
                // 第二次更改，再次增加版本号
                ref.compareAndSet(newValue1, newValue2, newStamp1, newStamp2);
            });
    
            Thread thread2 = new Thread(() -> {
        
                String expectedValue = "a";
                String newValue = "c";
                int expectedStamp = ref.getStamp();
                int newStamp = expectedStamp + 1;
    
                // 检查引用和版本号是否匹配
                while (!ref.compareAndSet(expectedValue, newValue, expectedStamp, newStamp)) {
        
                    // 不匹配，尝试重新更新，增加版本号
                    expectedStamp = ref.getStamp();
                    newStamp = expectedStamp + 1;
                }
            });
    
            thread1.start();
            thread2.start();
    
            try {
        
                thread1.join();
                thread2.join();
            } catch (InterruptedException e) {
        
                e.printStackTrace();
            }
    
            System.out.println("Final value: " + ref.getReference());
        }
    }

在解决ABA问题的算法中，当线程发现共享变量的值和自己的期望值不一致时，虽然可以重试多次，但是在每次重试时都会重新获取共享变量的当前值，并更新自己的期望值，直到CAS操作成功或达到最大重试次数为止。

重试的过程中，线程会比较当前共享变量的值和自己的期望值，并根据比较结果来判断是否存在ABA问题。如果发现共享变量的值被修改了多次，但是版本号仍然和自己的期望值相等，那么就说明存在ABA问题，此时线程会重新获取共享变量的当前值，并更新自己的期望值，使得期望值的版本号比共享变量的版本号更高，从而避免了ABA问题的影响。

每次重试时，线程都会将自己期望的版本号递增，这样可以保证自己期望的版本号始终比共享变量的版本号更高。这种方式可以有效避免ABA问题，并保证CAS操作的正确性和原子性。

因此，虽然解决ABA问题的算法会在操作失败时重试多次，并对自己的版本号加一，但这并不会影响操作的正确性和原子性，反而可以保证操作的正确性和原子性。