Rust中的无锁编程技术(三)

证券日报:区块链技术将使数字底座安全可信

《证券日报》刊发文章《数字化转型浪潮滚滚,区块链造就可信“数字经济底座”》,文章指出:多位业内人士认为,以区块链、隐私计算为代表的技术正在为人类协作建立信任基础、确保数据安全有序流动提供了“革命性”的工具,这些技术形成的产业本身也是可信经济的重要组成部分。伴随…

在前面两篇博客中,我们从两方面介绍了“锁”。第一个方面就是我们常说的“锁”其实是一个协议,这个协议从外部给出了锁的行为规范。另一个方面是“锁”和数据的绑定。但是我们一直没有提及究竟如何实现“原始锁”(请参考前文,“原始锁”即是上面提到的协议),这个就是本博客要解释的。

Atomic以及Memory Ordering

在介绍如何实现原始锁前,我们要对最基本的概念有一定的了解。对于原子类,我会做简单的介绍,因为原子类的实现牵扯到CPU的架构,牵扯到ISA,我尽量从一个软件工程师的角度来解释这个基础类。而Memory Ordering我将会在后面的博客花大篇幅来介绍。

Atomic

Atomic类是多线程编程最基础的一个类型。Rust里面提供了`AtomicBool`,`AtomicUsize`等基础的atomic类型。Atomic类和普通的类型基本一样,即`Usize`和`AtomicUsize`,`AtomicBool`和`Bool`基本上没有太多区别,只是一个可以在多线程环境下使用的,另一个更加适用于单线程,我认为掌握Atomic类型的几个特有的属性就可以。

首先,无论在任何情况下,Atomic类型读写一定是完整的。

举个例子,比如`AtomicUsize`,这个类型要看具体的CPU的架构,如果是32位的机器,那么我们可以确保的是在内存中或者是在寄存器里面,我们读取的时候一定是32位一起读取,赋值也是如此。一定不会出现只读`AtomicUsize`高16位,再去读别的数据的低16位这样的情况。在多线程编程中,如果对Atomic类赋值,那么结果一定要么成功,要么失败。同理如果读取Atomic的值,那么结果一定是一个完整的值。

Atomic类有自己的一套读写数据的方法,`load`, `set`,以及类似`compare_and_set`的函数。对一个原子类进行读写,这个类常用的函数有`load`,`set`,而`compare_and_set`是我们在用原子类实现锁或者无锁数据结构常用到的方法。如其名,这个函数其中一个参数是旧的值,另一个参数是新的值,如果当前原子类里面的值和所提供的旧值一致,那么将会把这个原子类里面的值换成新的值。

举个例子,假设有两个线程同时对一个atomic进行`compare_and_set`的操作,两个线程在这个函数里面也提供了相同的旧值以及和旧值不相符的新值,那么只有一个线程会成功,另一个会失败。`compare_and_set`返回值要看具体的接口定义,比如crossbeam所定义的`compare_and_set`和Rust所提供的原子类的`compare_and_swap`语义类似,但是返回值是不一样的。

`AtomicUsize`经常用作`Atomic<T>`。首先正如上面提到`usize`是随着CPU位数变化而变化的,`usize`可以用来存地址,所以当我们有一个在heap上线程共享的数据,我们可以将其地址存到`AtomicUsize`里面。所以`AtomicUsize`也可以理解为原子指针, Rust中可以这样使用:

let data = unsafe { &(*(atomic_usize as *const _ as *const Atomic<T>)) };

总的来说,我们可以这样理解原子类,就好像地铁入口的旋转栏杆一样,对于原子类的任何操作,load,set,compare_and_set,都是独立且完整的,任意一个时刻仅有一个操作在进行。如果还有不清楚的地方,后面的例子或许能更容易理解。

Memory Ordering

这里我暂时不会提及特别多关于内存模型的知识点,因为这个后面会花大篇幅来详细聊聊到底什么是内存模型。这里我会用最简单的例子来解释一下这个概念。

假设现在有两个线程,一个线程进行读操作,另一个线程进行写操作,而操作的数据是`AtomicBool`类型。这个数据的初始数据是`false`,进行写操作的线程想把这个值改成`true`。现在写操作已经执完了,那么进行读操作的线程是否一定读到的是`true`呢?

答案是否定的,因为写操作刚执行完的时候,最新的数据还存在于CPU的寄存器当中,还没有正式写到内存中(当然这个得基于编译器的实现以及CPU的具体优化策略),因此,非常有可能当写线程执行完了,也就是其对应的汇编已经执行完了,但是最新的数据却还仅仅存在于寄存器当中(针对的是物理多核的CPU)。

那么,我们怎么保证当最新的数据只要出现在寄存器中,就立马同步到内存中呢,这就是Memory Ordering的作用。我们现在只要记住,当我们用原子类的`set`方法,提供的内存顺序是`Release`,在`load`的时候,提供的内存顺序是`Acquire`就可以保证进行读的线程,读到的一定是寄存器里面最新的值。换句话说,我们可以暂时这样理解,`Release`是将寄存器里面的值和内存的值同步,`Acquire`是忘记自己当前寄存器的值,而直接去内存里面读取最新的值。如果对这一段解释还是感到困惑,就先暂时记住:对于原子类的操作,如果是写,那么内存顺序提供Release,如果是读,那么内存顺序提供Acquire

自旋锁

我们以自旋锁为例子来看看到底是怎么实现原始锁的:

pub struct SpinLock {    inner: AtomicBool,}
impl Default for SpinLock { fn default() -> Self { Self { inner: AtomicBool::new(false), } }}
impl RawLock for SpinLock { type Token = ();
fn lock(&self) { ...
while self.inner.compare_and_swap(false, true, Ordering::Acquire) { ... } }
unsafe fn unlock(&self, _token: ()) { self.inner.store(false, Ordering::Release); }}

自旋锁其实就是个`AtomicBool`,初始值为`false`,在lock的时候,我们用了原子类的特性,如果`compare_and_swap`失败了,抢锁的线程就会卡在`while`循环处。`unlock`也很清晰,就是将`AtomicBool`的值设置成`false`。我们来试想一下自旋锁的工作机制。

一开始有很多线程同时在调用`lock`函数,仅有一个线程,成功地将`AtomicBool`设置成了`true`,其余的线程因为在`compare_and_swap`提供的旧值都是`false`,与当前在`AtomicBool`里面的值不相符,因此其余线程会卡在`while`处并且一直循环。当抢到了锁的线程对共享资源的操作结束后,这个线程会调用`unlock`函数,在`unlock`函数里面,我们强行将`AtomicBool`设置成`false`,并且我们强行将这个在寄存器里面的新值,也就是false,和内存同步(Release),其中一条卡在`while`处的线程将会从内存中读取最新的值(Acquire),它将会是下一个可以对共享资源进行操作的线程。

其实自旋锁就是内存中一块线程共享的标识符,当其为`false`的时候,表示当前共享资源没有在被使用,当其为`true`的时候,表示当前共享资源在被某个线程占用着。

#[repr(C)]pub struct Lock<L: RawLock, T> {    lock: L,    data: UnsafeCell<T>,}
unsafe impl<L: RawLock, T: Send> Send for Lock<L, T> {}unsafe impl<L: RawLock, T: Send> Sync for Lock<L, T> {}

后,我们就可以将这个自旋锁放到之前的代码里面,也就是上述代码的`lock: L`,我们就得到了一个完整的锁的实现了。

我们能做得更好吗

我们现在对于锁有一个相对完整的认识了,自旋锁只是一个例子,方便大家理解锁的本质。但实际上自旋锁是相当粗糙的。

我们仔细想想自旋锁的工作原理就会发现,线程与线程之间是毫无公平性可言的比如线程A,B,C,D是四个正在抢锁的线程,这时候新加入了一个线程E,对于自旋锁是完完全全有可能让线程E抢到了锁,而ABCD均处在饿死的状态。

细心的读者应该已经发现了,自旋锁的`token`也就是证明其实就是个`()`。自旋锁的实现并没有好好利用这个`token`,我们是可以利用`token`来克服上面提到的自旋锁的缺陷的,这个就是我下个博客会提到的关于其他锁的实现方式。之后在介绍完锁的相关知识后,我会带大家重新认识Memory Ordering。

世界第二大快餐店汉堡王与 Robinhood 合作奖励狗狗币、比特币和以太坊

汉堡王计划与 Robinhood 合作,向其客户提供狗狗币、以太坊和比特币的奖励。 汉堡王奖励客户狗狗币、比特币和以太坊 快餐巨头汉堡王周一宣布与Robinhood建立合作伙伴关系,为其客户带来加密奖励。该奖励从11 月 1 日持续到 11 月 21 日在美国…

Click to rate this post!
[Total: 0 Average: 0]

人已赞赏
名家说每日优选

想当好配角,你配吗?

2021-11-6 15:50:16

Rust开发每日优选

RFC 导读 | 构建安全的 I/O

2021-11-6 15:52:03

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
有新消息 消息中心
搜索