无锁编程

DevLGQ

Concurrent

发布于：2021年1月28日

次浏览

字数：458字

时长：1分钟

无锁编程

Lock-Free Programming.

思考 a=a+1 的问题.

使用CAS解决问题

int a = 0   
update() {
    while(true) {
        if( cas(&a, a, a+1) ) {     
          return "done";
        }
  }
}

解决ABA问题, 使用二元组描述数据, 带值和版本.

Pair a = <0, 0> 
update() {
    ver = a.version
    val = a.value
    while(true) {
        if( cas(&a, <val, ver>, <val+1, ver+1>) ) {     
            return "done";
        }
  }
}

与上锁的区别:

CAS的程序不是一种排队结构, 一个线程休眠, 不会引起另外一个线程等待. 上锁就是一种排队的结构, 如果拥有锁的线程休眠, 置换等等, 都会导致其他线程阻塞.
CAS的程序, 同一时刻总有一个线程可以进步. synchronized, 如果拥有锁的线程发生故障, 可能导致没有线程可以继续运行.

Lock Free 定义

隔离: 线程之间互相隔离(一个线程的延迟, 阻塞, 故障)不会影响其它线程.
进步: 同一时刻且至少有一个线程可以进步(线程的失败, 意味着另一个线程是成功的).

场景举例: CLH 队列(链表+CAS实现, 一头添加, 一头删除), 出队操作都利用CAS Loop进行循环运算。

场景举例: SynchronousQueue, cas 竞争实现 transfer 操作(双向队列, 双向栈)

SpinLock 是不是 Free Lock?

不是。

// 实现 i++
volatile int lock = 0;
spinLock(){
    // 加锁, 0 -> 1, 失败就自旋
    while(!cas(&lock, 0, 1)) Thread.onSpinWait();
}
unlock(){
    while(!cas(&lock, 1, 0)) Thread.onSpinWait();
}

// 如果某个线程在此发生了故障, 这样的话, 锁就没有人释放了!!!
spinLock();
i++;
unlock();

// CAS Loop
do{
    a = i;
}while(!cas(&i, a, a+1));

最大的区别在于自旋锁还是上锁，本质是排队，对临界区进行保护。