面试二十七、 CAS和Atomic

CAS锁机制（无锁、自旋锁、乐观锁、轻量级锁）-CSDN博客

1. ABA问题

在C++中，可以使用std::atomic和版本号来解决ABA问题。C++标准库没有直接提供类似Java的AtomicStampedReference，但可以通过将版本号和指针组合在一起实现类似的效果。

#include <atomic>
#include <iostream>
#include <thread>

template <typename T>
class AtomicStampedReference {
public:
    AtomicStampedReference(T initial_value, int initial_stamp)
        : value_(initial_value), stamp_(initial_stamp) {}

    bool compare_and_set(T expected_value, T new_value, int expected_stamp, int new_stamp) {
        auto current_value = value_.load();
        auto current_stamp = stamp_.load();
        return (current_value == expected_value && current_stamp == expected_stamp) &&
               value_.compare_exchange_strong(current_value, new_value) &&
               stamp_.compare_exchange_strong(current_stamp, new_stamp);
    }

    T get_reference() const {
        return value_.load();
    }

    int get_stamp() const {
        return stamp_.load();
    }

private:
    std::atomic<T> value_;
    std::atomic<int> stamp_;
};

void aba_example() {
    AtomicStampedReference<int> atomicStampedRef(100, 0);

    auto thread1 = [&atomicStampedRef]() {
        int stamp = atomicStampedRef.get_stamp();
        int reference = atomicStampedRef.get_reference();
        std::cout << "Thread 1 initial stamp: " << stamp << "\n";
        std::cout << "Thread 1 initial value: " << reference << "\n";
        if (atomicStampedRef.compare_and_set(reference, reference + 1, stamp, stamp + 1)) {
            std::cout << "Thread 1 new stamp: " << atomicStampedRef.get_stamp() << "\n";
            std::cout << "Thread 1 new value: " << atomicStampedRef.get_reference() << "\n";
        }
    };

    auto thread2 = [&atomicStampedRef]() {
        int stamp = atomicStampedRef.get_stamp();
        int reference = atomicStampedRef.get_reference();
        atomicStampedRef.compare_and_set(reference, reference + 1, stamp, stamp + 1);
        atomicStampedRef.compare_and_set(reference + 1, reference, stamp + 1, stamp + 2);
        std::cout << "Thread 2 stamp after ABA: " << atomicStampedRef.get_stamp() << "\n";
        std::cout << "Thread 2 value after ABA: " << atomicStampedRef.get_reference() << "\n";
    };

    std::thread t1(thread1);
    std::thread t2(thread2);

    t1.join();
    t2.join();
}

int main() {
    aba_example();
    return 0;
}

2. 自旋时间长开销大

循环时间长开销大

描述：当多个线程竞争同一个CAS操作时，如果一直失败，线程会不断自旋重试，造成CPU资源的浪费。尤其在高并发情况下，频繁的CAS重试会导致较高的CPU开销。
解决办法：可以使用自适应自旋锁或其他锁机制来减轻自旋的开销。

自旋锁在高竞争情况下会导致大量CPU资源浪费。可以使用自适应自旋锁或结合其他锁机制来减轻这种开销。以下是一个简单的自适应自旋锁实现示例。

#include <atomic>
#include <thread>
#include <iostream>
#include <chrono>

class AdaptiveSpinLock {
public:
    AdaptiveSpinLock() : flag(ATOMIC_FLAG_INIT) {}

    void lock() {
        int spin_count = 0;
        while (flag.test_and_set(std::memory_order_acquire)) {
            ++spin_count;
            if (spin_count > max_spin_count) {
                std::this_thread::yield(); // 出让CPU
                spin_count = 0;
            }
        }
    }

    void unlock() {
        flag.clear(std::memory_order_release);
    }

private:
    static const int max_spin_count = 1000; // 自适应阈值
    std::atomic_flag flag;
};

void spinlock_example() {
    AdaptiveSpinLock lock;
    int counter = 0;

    auto increment = [&lock, &counter]() {
        for (int i = 0; i < 1000; ++i) {
            lock.lock();
            ++counter;
            lock.unlock();
        }
    };

    std::thread t1(increment);
    std::thread t2(increment);

    t1.join();
    t2.join();

    std::cout << "Final counter value: " << counter << "\n";
}

int main() {
    spinlock_example();
    return 0;
}

3. 多变量原子操作

CAS只能保证单个变量的原子操作，要保证多个变量的原子操作，可以使用锁机制。以下是使用std::mutex来保证多个变量的原子操作的示例。

#include <mutex>
#include <thread>
#include <iostream>

class MultiVariable {
public:
    void update(int a, int b) {
        std::lock_guard<std::mutex> lock(mtx);
        var1 = a;
        var2 = b;
    }

    void get(int& a, int& b) {
        std::lock_guard<std::mutex> lock(mtx);
        a = var1;
        b = var2;
    }

private:
    int var1 = 0;
    int var2 = 0;
    std::mutex mtx;
};

void multivariable_example() {
    MultiVariable mv;

    auto writer = [&mv]() {
        for (int i = 0; i < 1000; ++i) {
            mv.update(i, i * 2);
        }
    };

    auto reader = [&mv]() {
        for (int i = 0; i < 1000; ++i) {
            int a, b;
            mv.get(a, b);
            std::cout << "Read values: " << a << ", " << b << "\n";
        }
    };

    std::thread t1(writer);
    std::thread t2(reader);

    t1.join();
    t2.join();
}

int main() {
    multivariable_example();
    return 0;
}