专栏首页Rust语言学习交流【crossbeam系列】1有锁并发、无锁并发和crossbeam极简介

【crossbeam系列】1有锁并发、无锁并发和crossbeam极简介

随着计算机硬件和软件的发展,个人计算机里动辄几千几万线程已经成为家常便饭。而在程序中大量使用并发也成为了一个主流,因为这样的程序有更小的延迟,并且对多核CPU也有更充分的利用。

有锁并发

对于大多数程序员(当然我也基本上是其中一员),并发编程几乎就等价于给相关数据结构加上一个锁(Mutex)。比如如果我们需要一个支持并发的栈,那最简单的方法就是给一个单线程的栈加上锁std::sync::Mutex。(加上Arc是为了能让多个线程都拥有栈的所有权)

use std::sync::{Mutex, Arc};

#[derive(Clone)]
struct ConcurrentStack<T> {
    inner: Arc<Mutex<Vec<T>>>,
}

impl<T> ConcurrentStack<T> {
    pub fn new() -> Self {
        ConcurrentStack {
            inner: Arc::new(Mutex::new(Vec::new())),
        }
    }

    pub fn push(&self, data: T) {
        let mut inner = self.inner.lock().unwrap();
        (*inner).push(data);
    }

    pub fn pop(&self) -> Option<T> {
        let mut inner = self.inner.lock().unwrap();
        (*inner).pop()
    }

}

这样做的好处是显而易见的:代码写起来十分方便,毕竟和单线程版本的几乎一样。只需要按照单线程的版本写完,然后给数据结构加上锁,然后在必要的时候获取和释放(在Rust中基本上是自动的)锁即可。

那么问题是什么呢?首先不谈你可能会忘记获取和释放锁(这一点要感谢Rust,在Rust中几乎不可能发生),你可能会面临死锁的问题(哲学家就餐问题)。然后也不谈一些低优先级的任务可能会长期抢占高优先级任务的资源(因为锁是第一位的),当线程数量比较大的时候,大部分的时间都被用在了同步上(等待锁能被获取),性能就会变得非常差。考虑一个大量读取而偶尔写入的并发数据库,如果用锁去处理,即使数据库没有任何更新,每两个读之间也需要做一次同步,代价太大!

无锁并发

于是,大量计算机科学家和程序员就把目光转向了无锁(lock-free)并发。无锁对象:如果一个共享对象保证了无论其他线程做何种操作,总有一些线程会在有限的系统操作步骤后完成一个对其的操作Her91。也就是说,至少有一个线程对其操作会取得成效。使用锁的并发明显就不属于这一范畴:如果获取了锁的线程被延迟,那么这段时间里没有任何线程能够完成任何操作。极端情况下如果出现了死锁,那么没有任何线程能够完成任何操作。

CAS(compare and swap)原语

那大家可能会好奇,无锁并发要怎么实现呢?有没有例子呢?在此之前让我们先看一下一个公认的在无锁并发中非常重要的原子原语:CAS。CAS的过程是用指定值去比较一储存值,只有当他们相同时,才会修改储存值为新的指定值。CAS是个原子操作(由处理器支持,比如x86的compare and exchange (CMPXCHG)),该原子性保证了如果其他线程已经改变了储存值,那么写入就会失败。Rust标准库中的std::sync::atomic中的类型就提供了CAS操作,比如原子指针std::sync::atomic::AtomicPtr

pub fn compare_and_swap(
    &self,
    current: *mut T,
    new: *mut T,
    order: Ordering
) -> *mut T

(在这里,不用纠结ordering是什么,也就是说请尽管忽略忽略Acquire, Release, Relaxed

无锁栈(天真版)

#![feature(box_raw)]

use std::ptr::{self, null_mut};
use std::sync::atomic::AtomicPtr;
use std::sync::atomic::Ordering::{Relaxed, Release, Acquire};

pub struct Stack<T> {
    head: AtomicPtr<Node<T>>,
}

struct Node<T> {
    data: T,
    next: *mut Node<T>,
}

impl<T> Stack<T> {
    pub fn new() -> Stack<T> {
        Stack {
            head: AtomicPtr::new(null_mut()),
        }
    }

    pub fn pop(&self) -> Option<T> {
        loop {
            // 快照
            let head = self.head.load(Acquire);

            // 如果栈为空
            if head == null_mut() {
                return None
            } else {
                let next = unsafe { (*head).next };

                // 如果现状较快照并没有发生改变
                if self.head.compare_and_swap(head, next, Release) == head {

                    // 读取内容并返回
                    return Some(unsafe { ptr::read(&(*head).data) })
                }
            }
        }
    }

    pub fn push(&self, t: T) {
        // 创建node并转化为*mut指针
        let n = Box::into_raw(Box::new(Node {
            data: t,
            next: null_mut(),
        }));
        loop {
            // 快照
            let head = self.head.load(Relaxed);

            // 基于快照更新node
            unsafe { (*n).next = head; }

            // 如果在此期间,快照仍然没有过时
            if self.head.compare_and_swap(head, n, Release) == head {
                break
            }
        }
    }
}

我们可以看到,无论是pop还是push思路都是一样的:先在快照上pop或者是push,然后尝试用CAS替换原来的数据。如果快照和数据一致,说明这一期间数据没有被写操作过,于是更新成功。如果不一致,说明在此期间有其他线程修改过数据,那么一切从头再来。这就是一个无锁的栈。似乎一切都已经大功告成了!

内存释放

确实你可能已经大功告成了,但前提是你在写Java,或者是其他有GC的语言。现在的问题在于,在Rust这种没有GC的语言中,pop中

 return Some(unsafe { ptr::read(&(*head).data) })

并没有人去释放head,这是一个内存泄漏!哎,看来无锁并发好不容易呢。

crossbeam

在简单看了有锁和无锁并发的例子之后,我们发现并发还真不是那么容易的呢。什么都加个锁虽然简单粗暴但是恐怕成不了大气候。现在我们终于可以有请主角crossbeam了。该库最初的重点就是提供一些无锁的数据结构,让我们能免于绞尽脑汁去和这一难题较劲以及提供了内存管理工具,用来解决刚才我们提到的内存释放问题。现在已经演变成一个并发编程的军火库,提供各种大大小小有关并发编程的工具。再举个细节的小例子,为什么我们上边的ConcurrentStack需要Arc呢,就是因为普通的线程只能使用move而不能引用,而crossbeam也提供了工具去方便我们更容易的写出代码。

下回就让我们深入crossbeam-epoch去看一下基于epoch的垃圾收集工具,以及如何使用它来完成我们的无锁并发栈。

本文分享自微信公众号 - Rust语言学习交流(rust-china),作者:黑豆腐

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【crossbeam系列】2 crossbeam-epoch:基于epoch的无锁“垃圾收集”

    上次我们试图实现一个无锁的并发栈,但是发现由于Rust没有GC,简单的实现会导致内存泄漏。于是crossbeam提供了一个基于epoch的“垃圾收集”(epoc...

    MikeLoveRust
  • 【连载】两百行Rust代码解析绿色线程原理(四)一个绿色线程的实现

    在我们开始之前,我得提醒你我们编写的代码非常不安全,并且这也不是编写 Rust 代码的 “最佳实践”。我希望在不引入很多不必要的复杂性的前提下使其尽可能安全,所...

    MikeLoveRust
  • 【翻译】200行代码讲透RUST FUTURES (2)

    在我们深入研究 Futures in Rust 的细节之前,让我们快速了解一下处理并发编程的各种方法,以及每种方法的优缺点。

    MikeLoveRust
  • python并发编程-多线程实现服务端并发-GIL全局解释器锁-验证python多线程是否有用-死锁-递归锁-信号量-Event事件-线程结合队列-03

    正确,如果解释型语言能够利用多核优势,并行地执行代码,就会出现垃圾回收机制干扰线程数据的情况,CPython中就采用了CIL全局解释器锁来解决这一问题,牺牲多核...

    suwanbin
  • 浏览器进程?线程?傻傻分不清楚!

    进程和线程是操作系统的基本概念,许多人会有所了解,但不能较为清晰的分辨。 这里我们需要了解下面几个点。

    IMWeb前端团队
  • Python进阶(三十四)-Python

      线程在执行过程中与进程还是有区别的。每个独立的线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行,必须依存在应用程序中,由应用程序提...

    py3study
  • 浏览器进程?线程?傻傻分不清楚!

    本文作者:IMWeb coverguo 原文出处:IMWeb社区 未经同意,禁止转载 在生活中,浏览器和我们的工作和生活息息相关。做为前端开发,我们...

    IMWeb前端团队
  • 蒙特卡洛法应用

    在世界上最著名的赌城 —— 蒙特卡洛(摩纳哥)。有一种著名的数学方法,它通过对大量事件的统计结果来实现对确定性事件的计算,这就是蒙特卡洛法,也叫做随机模拟方法。

    matlab爱好者
  • golang 标准库 time/rate 介绍

    golang官方库中有一个rate包,实现了令牌桶算法。仓库地址:https://github.com/golang/time

    用户5705150
  • react-native学习之环境安装

    1、首先是java环境安装-安装JDK 2、安装Android-SDK,推荐以下地址:http://tools.android-studio.org/index...

    用户1141560

扫码关注云+社区

领取腾讯云代金券