并行编程:Lock,Lock Free/STM vs No Lock

概要

Lock

锁(Lock)是最经典的线程/进程同步手段。当多个进程访问一个竞争资源(如共享内存)时,他们使用锁来进行顺序访问。

问题出在哪?

线程/进程会因为其他进程的影响,而没有办法完成自己想做的事情。主要表现在:如果一个线程/进程获得了锁,那么其他进程必须等待这个线程/进程释放这个锁。如果该线程/进程忘记做这件事情,那么其他所有等待该锁的线程/进程都将不能继续。

另外,锁影响了系统的全局性能。设想下以下情形:

  • 进程p1获得了锁
  • p1挂起,操作系统将执行权交给p2
  • p2执行中请求锁,挂起,操作系统将执行权交给p3
  • p3执行中请求锁,挂起,操作系统将执行权交给p4

在竞争该锁的线程/进程足够多是,你将发现,大量的时间被用于进程的切换(唤醒->挂起)。p2, p3, p4等进程均等待着p1结束自己的工作,让它们继续。可见,锁的影响是全局性的。而且这个问题随着多核的来临变得更加突出。

Lock-free/STM

正是由于锁(Lock)有以上这些问题,于是Lock-free/Wait-free出现了。

This means that no synchronization primitives such as mutexes or semaphores can be involved, as a lock-holding thread can prevent global progress if it is switched out. "Wait-free" refers to the fact that a thread can complete any operation in a finite number of steps, regardless of the actions of other threads. All wait-free algorithms are lock-free, but the reverse is not necessarily true.

CAS/CAS2/NCAS

Lock-free and wait-free algorithms are written using atomic primitives that the hardware must provide. The most notable of these is "compare and swap" (often notated "CAS"),

(although requiring to have actual atomic primitives may not be a hard requirement. See for example: Dekker's_algorithm)

CAS(addr, old, new) = atomic
if *addr = old
then *addr := new ;
return true
else return false
endif
endatomic

STM

ABA Problem

例子

考虑下面这个lock-free stack

/* Naive lock-free stack which suffers from ABA problem.*/
class Stack {
    volatile Obj* top_ptr;
// Pops the top object and returns a pointer to it.
Obj* Pop() {
    while(1) {
        Obj* ret_ptr = top_ptr;
        if (!ret_ptr) return;
        Obj* next_ptr = ret_ptr->next;
        // If the top node is still ret, then no one has changed the stack.
        // Atomically replace top with next.
        if (CompareAndExchange(top_ptr, ret_ptr, next_ptr)) {
            return ret_ptr;
        }
        // The stack has changed, start over.
    }
}
// Pushes the object specified by obj_ptr to stack.
void Push(Obj* obj_ptr) {
    while(1) {
        Obj* next_ptr = top_ptr;
        obj->next = next_ptr;
        // If the top node is still next, then no one has changed the stack.
        // Atomically replace top with obj.
        if (CompareAndExchange(top_ptr, next_ptr, obj_ptr)) {
            return;
        }
        // The stack has changed, start over.
    }
}

解决方案

No Lock

模式

Asynchronous I/O

Erlang

总结

参考资料

Lock

Lock Free

STM

Asynchronous I/O

Erlang

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License