多线程网络库开发笔记

Tags:

wait-free V.S. lock-free

在wiki上这2个东西都是指Non-blocking algorithm

非阻塞

一个算法被称作非阻塞的前提是:线程的失败或挂起(failure or suspension),不会导致其他线程的失败或挂起。

lock-free:

在系统级别保证该系统(即用户程序)总是有进展的(progress)。换句话说,如果该系统的所有线程运行足够长时间,能保证至少有一个线程取得进展(make progress),就是lock-free。

在lock-free中,如果一个线程被挂起,其他线程依然能取得进展。lock-free优点在于CPU是可以一直繁忙的,当当前线程被挂起,CPU可以接着处理别的线程(没有核心处于空闲状态),因此增加了系统的吞吐量。但不足之处是,还是可能存在一些线程是被延迟处理的(waiting),也就意味着这些线程的工作有延时。

在lock-free系统中优化延时的办法是,建立调度器,维护一个较好的平均延时。

wait-free:

和lock-free的区别是,wait-free是在lock-free的前提上,进一步要求该系统的线程的操作在有限步骤内能保证完成。所以wait-free必然满足lock-free。

就上面说的吞吐量而言,wait-free更佳,因为保证了每个线程只要有机会被CPU载入执行,就总是能在有限步内完成,没有等待延时,no waiting。例如实时交易系统就需要wait-free。

Q&A

Q:为什么lock-free不等于wait-free?

A:假设一个情景,系统运行在n核环境,并且有n个线程在做一个长操作,其中有m个(m<n)线程能在有限步内完成操作,其他的n - m线程可能会操作失败(fail)并一直不断重试(retry on failure)(失败原因可能那n个线程有关),n-m线程是不能保证在有限步骤内完成操作的(也就是需要wait),所以这种系统就只是lock-free而已。而如果换作wait-free的话,每个线程都能保证操作能在有限步以内完成,并且每个线程和其他线程相互独立,没有依赖,就是无等待,即wait-free。

Q:lock-free是不是就是无锁?

A:确实是要求无锁。因为如果系统内有一个线程获得了锁,然后万一线程异常了没有释放锁(无法保证progress),就会导致等待该线程的其他线程永久饥饿。如果这个锁释不释放对其他线程无所谓,那这个锁也显然无意义。综上,lock-free必然要求无锁。

wait-free也是无锁?

A:wait-free是比lock-free更进一步的东西,当然也得是无锁。

ABA problem

指令重排和thread fence

指令重排:

(参考资料:http://preshing.com/20120625/memory-ordering-at-compile-time/)

编译器为了优化性能,可能会按和c/c++代码不一样的顺序重新排列指令。

指令重排需要打开编译优化选项。

指令重排保证对单线程程序没有影响。但对多线程程序来说,就惨了。

例子(Linux 3.10.0-514.26.2.el7.x86_64,gcc 4.8.5):

int A, B;

void foo()
{
    A = B + 1;
    B = 0;
}

执行 gcc -S -masm=intel test.c,得到:

    mov eax, DWORD PTR B[rip]   // 取出B值并写入eax
    add eax, 1                  // eax = eax + 1
    mov DWORD PTR A[rip], eax   // 把eax写入A
    mov DWORD PTR B[rip], 0     // B = 0

执行 gcc -S -masm=intel -O2 test.c,得到:

    mov eax, DWORD PTR B[rip]   // 取出B值并写入eax
    mov DWORD PTR B[rip], 0     // B = 0
    add eax, 1                  // eax = eax + 1
    mov DWORD PTR A[rip], eax   // 把eax写入A

显然,两者区别是第四行B=0指令被提前到第二行了,即B=0发生在对A的赋值之前,和c代码是不同的顺序。

单线程程序不会感知到这个区别。但考虑在多线程环境下,就容易引发一些问题。

一是影响到了lock-free代码,考虑下面的代码,用了一个共享变量IsPublished来标志Value是否有数据:

int Value;
int IsPublished = 0;

void sendValue(int x)
{
    Value = x;
    IsPublished = 1;
}

如果编译器重排了指令,使得IsPublished=1(Store)发生在Value = x(Store)之前。如果有一个线程在这2次store之间抢占了CPU,它看到IsPublished为1,但其实Value是还未赋值的,就引发了错误。

如果不想受到重排指令的危害,那就得考虑使用thread fence了。

memory_order(访存次序)和thread fence

中文:

http://zh.cppreference.com/w/cpp/atomic/memory_order

英文:

http://en.cppreference.com/w/cpp/atomic/memory_order

分成三大类:

一. 顺序一致性模型:

  • memory_order_seq_cst:

二. relax模型:

  • memory_order_relaxed:没有顺序限制,仅保证该操作的原子性。

三. Acquire-Release模型:

  • memory_order_consume:
  • memory_order_acquire:
  • memory_order_release:
  • memory_order_acq_rel:

cache line 和 cache line bouncing

little's law 律特定律

consistent hashing 一致性哈希

参考代码(python):https://github.com/goller/hashring

参考代码(go):https://godoc.org/stathat.com/c/consistent#example-New

https://github.com/ioriiod0/consistent_hash

(未经授权禁止转载)
Written on March 29, 2018

博主将十分感谢对本文章的任意金额的打赏^_^