文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

关于多线程同步的一切:lock-free/wait-free

2024-12-01 16:25

关注

程序对共享资源的访问任务,一般包括三步骤,读原值,修改值,将新值写回,用锁同步的话,就是在确保这三个步骤,不会被打断,访问共享资源的临近代码区只有一个线程在同时运行,第一个获得锁的线程能往前推进,其他线程只能等着直到持有锁的线程释放锁。

线程同步分为阻塞型同步和非阻塞型同步。

互斥量、信号、条件变量这些系统提供的机制都属于阻塞型同步,在争用资源的时候,会导致调用线程阻塞。

而非阻塞型同步是在无锁的情况下,通过某种算法和技术手段实现不用阻塞而同步。

锁是阻塞(Blocking)同步机制,阻塞同步机制的缺陷是可能挂起你的程序,如果持有锁的线程crash,则锁永远得不到释放,而其他线程则将陷入无限等待,另外,它也可能导致优先级倒转等问题。

所以,我们需要非阻塞(Non-Blocking)的同步机制。

什么是lock-free?

lock-free没有锁同步的问题,所有线程无阻碍的执行原子指令,而不是等待。

比如一个线程读atomic类型变量,一个线程写atomic变量,它们没有任何等待,硬件原子指令确保不会出现数据不一致,写入数据不会出现半完成,读取数据也不会读一半。

那到底什么是lock-free?

有人说lock-free就是不使用mutex / semaphores之类的无锁(lock-Less)编程,这句话严格来说并不对。

我们先看一下wiki对Lock-free的描述:

> Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes progress (for some sensible definition of progress). All wait-free algorithms are lock-free.

> In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)

第一段是给lock free下定义,第二段是解释。

因此,如果2个线程竞争同一个互斥锁或者自旋锁,那它就不是lock-free的。

因为如果我们暂停持有锁的线程,那么另一个线程会被阻塞。

wiki的这段描述很抽象,它不够直观,稍微再解释一下:

lock-free描述的是代码逻辑的属性,不使用锁的代码,大部分具有这种属性。所以,我们经常会混淆这lock-free和无锁这2个概念。

其实,lock-free是对代码(算法)性质的描述,是属性,而无锁是说代码如何实现,是手段。

lock-free的关键描述是:如果一个线程被暂停,那么其他线程应能继续前进,它需要有系统级(system-wide)的吞吐。

我们从反面举例来看,假设我们要借助锁实现一个无锁队列,我们可以直接使用线程不安全的std::queue + std::mutex来做:

template <typename T>
class Queue {
public:
void push(const T& t) {
q_mutex.lock();
q.push(t);
q_mutex.unlock();
}
private:
std::queue<T> q;
std::mutex q_mutex;
};

如果有线程A/B/C同时执行push方法,最先进入的线程A获得互斥锁。

线程B和C因为获取不到互斥锁而陷入等待。

这个时候,线程A如果因为某个原因(如出现异常,或者等待某个资源)而被永久挂起,那么同样执行push的线程B/C将被永久挂起,系统整体(system-wide)没法推进。这显然不符合lock-free的要求。

因此:所有基于锁(包括spinlock)的并发实现,都不是lock-free的。

因为它们都会遇到同样的问题:即如果永久暂停当前占有锁的线程/进程的执行,将会阻塞其他线程/进程的执行。

而对照lock-free的描述,它允许部分process(理解为执行流)饿死但必须保证整体逻辑的持续前进,基于锁的并发显然是违背lock-free要求的。

CAS loop实现lock-free

Lock-Free同步主要依靠CPU提供的read-modify-write原语,著名的“比较和交换”CAS(Compare And Swap)在X86机器上是通过cmpxchg系列指令实现的原子操作,CAS逻辑上用代码表达是这样的:

bool CAS(T* ptr, T expect_value, T new_value) {
if (*ptr != expect_value) {
return false;
}
*ptr = new_value;
return true;
}

CAS接受3个参数:

逻辑描述:CAS比较内存地址中的值和期望值,如果不相同就返回失败,如果相同就将新值写入内存并返回成功。

当然这个C函数描述的只是CAS的逻辑,这个函数操作不是原子的,因为它可以划分成几个步骤:读取内存值、判断、写入新值,各步骤之间是可以插入其他操作的。

不过前面讲了,原子指令相当于把这些步骤打包,它可能是通过`lock; cmpxchg`实现的,但那是实现细节,程序员更应该注重在逻辑上理解它的行为。

通过CAS实现Lock-free的代码通常借助循环,代码如下:

do {
T expect_value = *ptr;
} while (!CAS(ptr, expect_value, new_value));

第三步是关键,虽然CAS是原子的,但加载expect_value跟CAS这2个步骤,并不是原子的。

所以,我们需要借助循环,如果ptr内存位置的值没有变(*ptr == expect_value),那就存入新值返回成功;否则说明加载expect_value后,ptr指向的内存位置被其他线程修改了,这时候就返回失败,重新加载expect_value,重试,直到成功为止。

CAS loop支持多线程并发写,这个特点太有用了,因为多线程同步,很多时候都面临多写的问题,我们可以基于cas实现Fetch-and-add(FAA)算法,它看起来像这样:

T faa(T& t) {
T temp = t;
while (!compare_and_swap(x, temp, temp + 1));
}

第一步加载共享数据的值到temp,第二步比较+存入新值,直到成功。

lock-free栈

下面是C++ atomic compare_exchange_weak()实现的一个lock-free堆栈(来自CppReference):

template <typename T>
struct node {
T data;
node* next;
node(const T& data) : data(data), next(nullptr) {}
};

template <typename T>
class stack {
std::atomic<node<T>*> head;
public:
void push(const T& data) {
node<T>* new_node = new node<T>(data);
new_node->next = head.load(std::memory_order_relaxed);
while (!head.compare_exchange_weak(new_node->next, new_node,
std::memory_order_release,
std::memory_order_relaxed));
}
};

代码解析:

这样的行为逻辑显然符合lock-free的定义,注意用cas+loop实现自旋锁不符合lock-free的定义,注意区分。

ABA问题

CAS经常伴随ABA问题,考虑前面的CAS逻辑,CAS里会做判等,判等的2个操作数,一个是前步加载的内存地址的值,另一个是再次从内存地址读取的值,如果2个操作数相等,它便认为内存位置的值没变。

但实际上,如果“两次读取一个内存位置的值相同,则说明该内存位置没变”,这个假设不一定成立,为什么呢?

假设线程1在前面一步从内存位置加载数据后。

线程2切入,将该内存位置的数据从A修改为B,然后又修改为A。

等到线程1继续执行CAS的时候,它观测到的内存位置值未变(依然是A),因为线程2将数据从A修改到B,再修改成A。

线程1两次读到了相同的值,它便断定内存位置没有被修改,实际并非如此,线程2改了内存位置。

基于上述逻辑行事,就有可能出现未定义的结果。

这就是经典的ABA问题,会不会出问题,完全取决于你的程序逻辑,有些逻辑可以容忍ABA问题,而有些不可以。

ABA问题很多时候由内存复用引起,比如一块内存被回收后又被分配,地址值不变,但这个对象已经不是之前的那个对象了,有很多解决ABA问题的技术手段,比如增加版本号等等,目的无非是去识别这种变化。

何为wait-free?

wiki关于wait-free的词条解释:

> Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with starvation-freedom

> An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes.[15] This property is critical for real-time systems and is always nice to have as long as the performance cost is not too high

翻译过来就是:wait-free有着最强的非阻塞进度保证,wait-free有系统级吞吐兼具无饥饿特征。

如果一个算法的每个操作完成都只有有限操作步数,那么这个算法就是wait-free的。

这个特征对于实时系统非常关键,且它的性能成本不会太高。

wait-free比lock-free更严格,所有wait-free算法都是lock-free的,反之不成立,wait-free是lock-free的子集。

wait-free的关键特征是所有步骤都在有限步骤完成,所以前面的`cas + loop`实现的lock-free栈就不是wait-free的。

因为理论上,如果调用push的线程是个倒霉蛋,一直有其他线程push且恰好又都成功了,则这个倒霉蛋线程的cas会一直失败,一直循环下去,这与wait-free每个操作都必须在有限步骤完成的要求相冲突。wait-free的尝试次数通常跟线程数有关,线程数越多,则这个有限的上限就越大。

但前面讲的atomic fetch_add则是wait-free的,因为它不会失败。

简单点说,lock-free可以有循环,而wait-free连循环都不应该有。

wait-free非常难做,以前一直看不到wait-free的数据结构和算法实现,直到2011才有人搞出了一个wait-free队列,虽然这个队列也用到了cas,但是它为每一步发送的操作提供了一个state array,为每个操作赋予一个number,从而保证有限步完成入队出队操作,论文链接:

(wait-free queue):[http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf]

何为Obstruction-free?

Obstruction-free提供比lock-free更弱的一个非阻塞进度保证,所有lock-free都属于Obstruction-free。

Obstruction-free翻译过来叫无障碍,是指在任何时间点,一个孤立运行线程的每一个操作可以在有限步之内结束。只要没有竞争,线程就可以持续运行,一旦共享数据被修改,Obstruction-free要求中止已经完成的部分操作,并进行回滚,obstruction-free是并发级别更低的非阻塞并发,该算法在不出现冲突性操作的情况下提供单线程式的执行进度保证。

obstruction-freedom要求可以中止任何部分完成的操作并且能够回滚已做的更改,为了内容完备性,把obstruction-free列在这里。

无锁数据结构

一些无锁(阻塞)数据结构不需要特殊原子操作原语即可实现,例如:

无锁数据结构实现起来比较困难,非必要不要自己去实现。

自旋锁

在cpu核上自旋,粘着cpu不停的测试,直到其他cpu解锁,这是一种消耗cpu的加锁方式,适合持有锁的时间非常短的情况,它基于一种假设:睡眠导致的调度开销大于在cpu上自旋测试的开销。

来源:码砖杂役内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯