无锁的数据结构（Lock-Free）及CAS（Compare-and-Swap）机制

栏目: IT技术 · 发布时间: 8年前

内容简介：当同时存在读写线程时，默认情况下是不保证线程安全的，因而需要利用信号量来进行线程同步（Synchronization），如关键代码段、互斥体等，同时操作系统也提供了相应的API。然而同步并不总是满足条件的且有效率的，比如陷入内核时会有性能损失、死锁、活锁以及资源浪费等。于是Lock-Free和Wait-Free的思想出现了

当同时存在读写线程时，默认情况下是不保证线程安全的，因而需要利用信号量来进行线程同步（Synchronization），如关键代码段、互斥体等，同时操作系统也提供了相应的API。然而同步并不总是满足条件的且有效率的，比如陷入内核时会有性能损失、死锁、活锁以及资源浪费等。

于是Lock-Free和Wait-Free的思想出现了，由于此时不存在读写线程的同步，因而在写线程运行时，读线程也在运行（多核中两个线程在不同的核上被调度运行），而且代码量减少，程序运行更快。而这一思想是通过CAS机制来实现，如下

template<typename T>
bool CAS(T* ptr, T expected, T fresh)
{
    if(*ptr != expected)
         return false;
    *ptr = fresh;
    return true;
}

template<typename T>

bool CAS(T* ptr, T expected, T fresh)

{

if(*ptr != expected)

return false;

*ptr = fresh;

return true;

}

CAS的原理是，将旧值与一个期望值进行比较，如果相等，则更新旧值，类型T = {char, short, int, __int64, …}等，以及指针（pointer to any type）。

注意CAS这里只是说明了原理，并不是真实的源代码实现，具体实现请参考操作系统。

在Windows API中，提供了很多原子操作（Atomic Operatoration），如InterlockedCompareExchange等一系列InterLocked函数，从汇编的角度来讲，intel的XCHG指令即可以一个时钟周期内完成数据的交换（寄存器和内存的数据交换），使用方法可参考InterlockedCompareExchange的反汇编代码。

考虑这样一种情况：存在多个读线程和一个写线程，在使用同步方法时，很可能写线程并不能立即获得锁，最坏的情况下是写线程永远得不到锁，即进入活锁状态。但是使用CAS的方法时，便可以让读写线程并行运行，当写线程一旦更新为新的共享数据时，读线程便能即时读出更新后的数据。

如下示例

class Widget
{
    Data* p_;
    ...
    void Use() { ... use p_ ... }
    void Update() {
    Data * pOld, * pNew = new Data;
    do
    { 
    pOld = p_;
    ...
    }while (!CAS(&p_, pOld, pNew));
    }
};

class Widget

{

Data* p_;

...

void Use() { ... use p_ ... }

void Update() {

Data * pOld, * pNew = new Data;

{

pOld = p_;

...

}while (!CAS(&p_, pOld, pNew));

}

};

但随之而来会有一个疑问，Update函数中该何时删除旧数据呢，由于很有可能有别的读线程在使用旧数据。对于 JAVA 等有自动内存回收（GC）机制的语言环境而言，这不是问题，但对于C/C++等无GC机制的环境而言，旧数据的回收就比较棘手的问题了。

当然也存在很多的解决方法，这也成为CAS机制中最有趣最受讨论的问题，而且在不同条件下方法也不同，这里便不一一赘述了，具体可以查看“参考文献”部分的论文。

参考文献：

（1）Andrei Alexandrescu论文集

（2）maged michael论文集

原文出处： lifesider

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持码农网

查看所有标签

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

Data Structures and Algorithms in Java

Robert Lafore / Sams / 2002-11-06 / USD 64.99

Data Structures and Algorithms in Java, Second Edition is designed to be easy to read and understand although the topic itself is complicated. Algorithms are the procedures that software programs use......一起来看看《Data Structures and Algorithms in Java》这本书的介绍吧!

码农工具

SHA 加密

SHA 加密工具

RGB CMYK 转换工具

RGB CMYK 互转工具