Yebangyu's Blog

Fond of Concurrency Programming, Distributed System and Performance Optimization.

Singleton与多线程

如果您和我一样,都只有C++背景,之前对设计模式也一窍不通,那么也没有关系,因为本文不需要您对设计模式有多么了解。

Singleton模式

所谓的单例模式,single instance模式,简单实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Singleton
{
  public:
    static Singleton* instance();
  private:
    static Singleton* pInstance;
};

Singleton* Singleton::pInstance = NULL;

Singleton* Singleton::instance()
{
  if (pInstance == NULL) {
    pInstance = new Singleton();
  }
  return pInstance;
}

Lock Free中的Hazard Pointer(下)

在前面几篇文章里,我们介绍了Hazard Pointer,一种用于lock free data structure设计中内存管理的利器,这个利器不仅思想简单,还可以用来防止ABA问题,读者诸君务必掌握。

本文作为第三部分,给出工业级代码中,实现Hazard Pointer的一些策略和需要注意的点。

Hazard Pointer管理

我们知道Hazard Pointer封装了原始指针,那么Hazard Pointer的内存和生命周期本身如何管理呢?以下是常见的策略:

性能优化的那些传说和迷思

相信你在很多书籍中见到很多代码调优(tuning code)的建议和方法。这些书籍可能包括《编程珠玑》、《深入理解计算机系统》、《程序设计实践》、《Optimized C++》等等。坦白说,这些书我都看过,它们确实提供了不少有意思的性能调优的方法,那么我们的问题是,这些建议和方法有效吗?所谓有效,一种衡量途径是,假如我们不那么做,是否编译器已经会自动优化了呢?

本文我们举几个例子,然后开启编译器优化选项后,看看发生了什么。

本文环境为:Ubuntu 14.04 32bit + Intel I7 CPU + GCC 4.8

生成汇编代码的语句是:g++ -S -O2 code.cpp

循环展开

对于下面的函数

1
2
3
4
5
6
void f1(int *a)
{
  for (int i = 0; i < 3;i++) {
    a[i] = a[i] + 2;
  }
}

它们建议可以将循环展开,变成这样:

1
2
3
4
5
6
void f2(int *a)
{
  a[0] = a[0] + 2;
  a[1] = a[1] + 2;
  a[2] = a[2] + 2;
}

一个轻量的lock free程序调试工具

lock free 程序时序混乱,逻辑复杂,反直觉的地方很多,心智负担很重,因此调试起来也非常困难。

下面用C++编写了一个用于调试lock free代码的程序,非常轻量,代码如下,只适用于linux环境。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//xx.h
#include <pthread.h>
class LockFreeLogger
{
public:
  struct Event
  {
    char *message;
    pthread_t thread_id;
    int info;
  };
  LockFreeLogger()
  {
    pos_ = 0;
    buffer_ = new Event[SIZE];
  }
  void log(char *message, int info)
  {
    int pos = __sync_fetch_and_add(&pos_, 1);
    buffer_[pos].message = message;
    buffer_[pos].info = info;
    buffer_[pos].thread_id = pthread_self();
  }
  void report()
  {
    //single thread code
    for (int i = 0; i < pos_; i++) {
      //cout or fwrite buffer_[i];
    }
  }
private:
  int pos_;
  Event *buffer_;
  static const int SIZE = 1234567;
};

extern LockFreeLogger logger;

#define LOG(message, info) logger.log(message, info)

Lock Free中的Epoch Based Reclamation

楔子

一般认为,用C/C++编写Lock Free代码非常困难,主要原因无非是两个:

  • 内存模型
  • 内存回收

C++11引入了标准的内存模型,在此之前,C++程序员依赖于具体的体系结构特点和编译器提供的feature来保证正确的内存访问语义。C++11出来后,程序员编写健壮的、可移植的lock free代码成为可能。

但是内存回收问题依旧存在。我们知道,和Java这种提供自动gc的语言相比,C++程序员刀耕火种,得自己管理内存。当一个线程正在访问某块内存,而另外一个线程将它释放将是一个灾难行为。解决内存回收问题在lock free里显得更加困难。

目前用于lock free代码的内存回收的经典方法有:Lock Free Reference Counting、Hazard Pointer、Epoch Based Reclamation、Quiescent State Based Reclamation等。上回我们简单介绍了Hazard Pointer,本文我们介绍Epoch Based Reclamation方法。据我所知,这是第一篇介绍这个方法的中文资料。

MCS Lock

回顾

上回 我们介绍了Ticket Lock算法,和传统的简单的CAS操作来实现spin lock相比,它提供了不少很好的性质:比如FIFO、没有饥饿等等。

但是根据论文,ticket lock的scalability很差。我们不妨简单回顾一下(代码片段也摘自该论文):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct spinlock_t
{
  int current_ticket ;
  int next_ticket ;
}
void spin_lock (spinlock_t *lock)
{
  int t = atomic_fetch_and_inc(&lock -> next_ticket );
  while (t != lock->current_ticket )
  ; /* spin */
}
void spin_unlock (spinlock_t *lock)
{
  lock->current_ticket++;
}

实现可重入锁

基本概念

可重入锁(Reentrant Lock),是指允许同一个线程多次对该锁进行acquire动作。对于不可重入的锁,当一个线程多次调用acquire后将造成死锁。可重入锁具有广泛的应用,例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Routine
{
  void f()
  {
    lock_.lock();
    h();
    g();
    lock_.unlock();
  }
  void g()
  {
    lock_.lock();
    cout<<"abc"<<endl;
    lock_.unlock();
  }
  void h()
  {
    lock_.lock();
    cout<<"def"<<endl;
    lock_.unlock();
  }
  Lock lock_;
};

Sequence Lock

在读多写少(Read Mostly)的场景里,我们可能会使用的同步设施包括:

  • Mutex / Spin Lock
  • Reader Writer Lock
  • Sequence Lock
  • Read Copy Update

前面两种一般人都很清楚了,如雷贯耳、妇孺皆知。如果您对Spin Lock的实现细节有兴趣,建议您阅读我的这几篇博客:

Peterson Lock

Ticket Lock

MCS Queue Lock

从今天起,我们介绍后面两种同步设施。今天我们先介绍Sequence Lock。

String与Copy On Write

什么是Copy On Write

Copy On Write(COW)作为一种优化技术被广泛使用,在string的实现中也不例外。考虑如下的代码:

1
2
3
string s("1234");
string t = s;
cout<<t[1]<<endl;

第二行,通过调用copy constructor(注意,这里调用的是copy constructor,而不是copy assignment,因为它是从无到有构造对象,而不是设置已有对象)构造对象t,第三行对t中的某个元素进行只读操作。

如果让你实现copy constructor,你会怎么做呢?教科书里的、简单的实现大概是这样:

Ticket Lock

简单回顾

上回 我们介绍了peterson算法来实现spin lock,算法简单,实现简单,但是值得注意和留心的点很多。

粗略说来,peterson算法的主要缺点在于:

1,很难推广到n个线程(n>=3)。原始的算法针对两个线程,如果想应用在多个线程的场景里,需要做一定的修改。

2,peterson算法的动机是仅仅使用load和store来实现互斥访问。然而,我们知道,现代体系结构下,CPU和编译器会对读写操作进行乱序,仅仅依靠读写操作而不使用memory barrier就编写正确的程序非常困难。

Ticket Lock

在介绍Ticket Lock之前,我们首先分析一个妇孺皆知、地球人都知道的实现spin lock的方法(伪代码):