无锁编程-番外篇(一):并发正确性条件

July 17, 2016 at 3:03 pm

关于并发条件下的正确性,实际上是并发编程的基础,在最初打算总结这个系列的时候,本来是将这部分内容放在第一篇来讲的,但是这部分东西比较偏理论,容易造成看了不知道在讲什么的感觉,所以最终还是把它移到了番外篇中,剧情则是接在正篇的第二篇之后。本文可能会引用第一篇和第二篇当中的一些内容作为补充的例子,但是整体上是偏于独立的。 文章的大概分布如下: (1)并发以及正确性条件 (2)静态一致性 (3)序列一致性 (4)线性一致性 (5) 阻塞与非阻塞、无锁 (6)静态一致性和序列一致性的差别 (7)序列一致性和线性一致性的差别 这部分网上的资料查找下来感觉相对较少,查到的资料也大多比较晦涩、术语比较多,本文还是希望可以以直白的语言介绍相关的概念,如果有空再补充上比较数学化的部分。 由于我对这部分的内容也是基本上从完全不知道到慢慢了解这样一个过程,所以本文的行文顺序不会从一开始就把每一个概念都解释得非常清楚,那样会导致关于每一个概念的东西一下子变得非常的多,而这些概念之间相互又有关系,最终就变成了一本难以阅读的教科书;本文的顺序是先初步这些概念,对这些概念一个模糊的影响之后,再逐步介绍、解释其中比较模糊的部分,并通过实例来进行更好地说明,希望通过这种方式可以达到先是“好像大概知道是个什么东西了”然后是“原来是这样一个东西”的感觉。 并发以及正确性条件 并发(concurrency)这个名词大家都不陌生,从单词的角度来说,就是指一些事情同时发生。从计算机的角度来讲,指的是对某些内容的同时访问,一个典型的例子就是多个线程对同一块内存进行并发的访问;对于一个实际例子来说的话,可能是多个线程同时往一个共享的队列里进行入队操作。在研究并发编程之前,我们首先回顾一下非并发的操作。所谓的非并发也称为序列(sequential),表示按照固定的顺序执行操作。在当前的线程模型中,如果是一个单线程程序,那么它执行操作的方式就是序列性的,最终它的操作会变成一条条按顺序执行的机器码。 在单线程模型中,对于一个功能,或者说一个数据结构,比如队列,它的实现是否正确,是很容易去判断的。一个队列A,如果先是1入队,再是2入队,那么接着进行出队操作,获得的必然是1;如果获得的不是1,那么显然这个数据结构的实现是有问题的。在这里,一个方法的调用可以看作一个点或者一个事件,不必考虑它执行的时间,而仅仅考虑这个方法所带来的对象状态的转变。对于方法enq(1),会将一个队列从空的状态到队列头部有1的状态。 但是在多线程模型中,要定义正确性就比较困难了。在多线程模型中,不能再将方法看成一个点了,而是看成一个区间。这个区间的起点是这个方法被调用(invocation)的时间,而这个区间的终点就是这个方法调用返回(response)的时间。或者说把一个方法看成两个事件,一个是被调用事件,一个是应答事件。如果一个方法已经发生了调用事件但还没有发生应答事件,那么称这个方法处于待定状态(pending)。简单地说,就是这个方法已经被调用了但是还没有返回。 假设一个队列Q,线程A将1入队,同时线程B将2入队,那么在这之后线程C进行出队操作,得到的是多少才算是正确的呢?这实际上取决于我们的应用场景的实际需求。为此,我们下面介绍三种用来衡量程序的实现是否正确的条件:静态一致性、序列一致性和线性一致性。在此之前,我们先给出这几个正确性条件都具有的一个通用的原则。 设想一个数据结构实现了类似寄存器的功能,线程A往里写入7,同时线程B往里写入-3,那么最终线程C从中读取时应该读取7还是读取-3呢,取决于具体的情况,但是我们显然不愿看到读到-7的情况,即读到的值是两个线程操作的一个混合。 原则1:所有的操作都必须按照某种顺序依次执行。 也就是说,不论中间发生的过程是怎么样的,最终给我们的结果和按照某一顺序依次执行这些操作的效果是一样的,我们不希望看到这种混合的无效状态,对于上面的例子,我们要么读到7,要么读到-3。 […]

工作间

July 17, 2016 at 12:36 pm

最近大有挖的坑越来越多、填的坑越来越少的趋势,所以这里大概列一下当前正在写的和将要写的文章吧: 1. 无锁编程(三):实现无锁的队列 100% 2. 最小费用流 50% 3. diff的基本原理(上):最长公共子序列 0% 4. diff的基本原理(下):简单diff的实现 0% 5. adventure time 听写与校对(SE01-EP01) 30% 6. 翻译习作:无影灯(一) […]

无锁编程(二):无锁的栈

July 16, 2016 at 11:28 am

在第一篇介绍了无等待(wait-free)和无锁(lock-free)的基本概念之后,第二篇通过实际的无锁的堆栈的例子,从代码的角度上去理解无锁。本文主要分成以下几个部分: 1. 普通的堆栈 2. 有锁的堆栈 3. CAS操作 4. 无锁的栈 由于仍然是本系列起步的部分,所以一步步从最普通的堆栈开始讲起。 普通的堆栈 这里所说的堆栈也就是传统意义上FILO的线性数据结构,这里我们采用链表的形式进行栈的设计,下面是一个简单的堆栈的实现。 template <typename T> class Stack { public: struct […]

无锁编程(一):无锁的基本概念

July 3, 2016 at 5:19 pm

不知不觉又要开一个新的系列了,之前还有无数的系列,还有无数的坑要填,接下来还有找工作...... 由于最近一直在接触无锁方面的内容,为了不让学到的东西打水漂,在这里开一个系列记录一下学习到的东西。理想中的目标是从无锁编程的基本概念讲起,逐步完成一个无锁的栈、无锁的队列、无锁的链表,最终实现一个无锁的跳表,当然,整个系列可能又会跨度很长甚至太监,一贯如此...... 作为本系列的第一篇文章,我们通过一些例子,理解所谓的无锁(lock-free),对“无锁”这个词有一个粗略的理解,在后续的文章中,会对这个概念进行展开,从而较为全面地理解无锁。 无锁(lock-free, lock-freedom)是一个比较难定义的概念。第一,这个概念在过去有很多不同的意思,近年才逐渐收敛,大家才统一了它的意思,这不仅仅是在国内如此,国外也是一样;第二,这个已经被统一的概念非常的拗口,而且初看时也很难理解到底为什么要有这样的定义。无论如何,这个概念在逐步的发展中,在很多地方发挥了传统的编程模型所不能做到的一些优美的特性。 我们先简单地回顾一下锁,这里以互斥锁为例。 pthread_mutex_t mutex; void *print_msg(void *arg) { pthread_mutex_lock(&mutex); for (int i=0; i<15; ++i) { printf("output […]