用户态同步之自旋锁

最近花了一些时间研究如何在用户态实现自旋锁，这里简单的总结一下。本文的所有代码以及配套的测试用代码都可以在我的github上找到。

问题在哪

首先明确问题，我们需要一种用户态实现的线程同步机制，正确性当然是最重要的。本文的目的是实现正确的自旋锁（自旋锁比较简单轻量，但了解了原理后实现互斥锁并不困难，自行维护等待关系并通过 futex 对线程执行挂起、唤醒操作就可以了）。

概念上这个问题很简单啊，是不是我们只要用一个线程共享的变量做互斥，然后在线程获得和释放锁时修改这个变量就行了？比如像下面这样：

#ifndef _FAKELOCK_H_
#define _FAKELOCK_H_

class FakeLock
{
public:
  FakeLock() {};
  virtual ~FakeLock() {};

  FakeLock(const FakeLock&) = delete;
  FakeLock &operator=(const FakeLock&) = delete;

  virtual int lock()
  {
    while (1L == lock_) {
      asm volatile("pause\n" ::: "memory");
    }
    lock_ = 1L;
    return 0;
  }

  virtual int unlock()
  {
    lock_ = 0L;
    return 0;
  }

 private:
  int64_t lock_;
};

#endif /* _FAKELOCK_H_ */

#ifndef _FAKELOCK_H_

#define _FAKELOCK_H_

class FakeLock

{

public:

FakeLock() {};

virtual ~FakeLock() {};

FakeLock(const FakeLock&) = delete;

FakeLock &operator=(const FakeLock&) = delete;

virtual int lock()

{

while (1L == lock_) {

asm volatile("pause\n" ::: "memory");

}

lock_ = 1L;

return 0;

}

virtual int unlock()

{

lock_ = 0L;

return 0;

}

private:

int64_t lock_;

};

#endif /* _FAKELOCK_H_ */

然而事情没这么简单，因为对这个变量的操作不是原子的，所以会导致这个锁无法正确的运行（即使在单核环境也如此），因此我们需要利用硬件提供的原子操作来实现锁（FYI. 一种不需要原子操作的锁实现方法见前文中提到过的Dekker算法，非常漂亮，但通用性不足）。

除此之外，另一个问题是多核争用的性能问题，这一点我会在后文中提到。

另外由于在用户态实现锁对硬件体系结构提供的一致性保证非常相关，所以必须注明，本文中所有实现针对于x86体系结构（~~也就是acquire-release语义~~TSO内存模型），不具备可移植性。

继续阅读：→

多核并发编程中的cache line对齐问题

先看一段代码：

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

static const int64_t MAX_THREAD_NUM = 128;

static int64_t n          = 0;
static int64_t loop_count = 0;

#pragma pack (1)
struct data
{
  int32_t pad[15];
  int64_t v;
};
#pragma pack ()

static data value __attribute__((aligned(64)));
static int64_t counter[MAX_THREAD_NUM];

void worker(int *cnt)
{
  for (int64_t i = 0; i < loop_count; ++i) {
    const int64_t t = value.v;

    if (t != 0L && t != ~0L) {
      *cnt += 1;
    }

    value.v = ~t;
    asm volatile("" ::: "memory");
  }
}

int main(int argc, char *argv[])
{
  pthread_t threads[MAX_THREAD_NUM];

  /* Check arguments to program*/
  if(argc != 3) {
      fprintf(stderr, "USAGE: %s <threads> <loopcount>\n", argv[0]);
      exit(1);
  }

  /* Parse argument */
  n          = min(atol(argv[1]), MAX_THREAD_NUM);
  loop_count = atol(argv[2]); /* Don't bother with format checking */

  /* Start the threads */
  for (int64_t i = 0L; i < n; ++i) {
    pthread_create(&threads[i], NULL, (void* (*)(void*))worker, &counter[i]);
  }

  int64_t count = 0L;
  for (int64_t i = 0L; i < n; ++i) {
    pthread_join(threads[i], NULL);
    count += counter[i];
  }

  printf("data size: %lu\n", sizeof(value));
  printf("data addr: %lX\n", (unsigned long)&value.v);
  printf("final: %016lX\n", value.v);

  return 0;
}

#include <pthread.h>

#include <stdlib.h>

#include <stdio.h>

#include <algorithm>

using namespace std;

static const int64_t MAX_THREAD_NUM = 128;

static int64_t n = 0;

static int64_t loop_count = 0;

#pragma pack (1)

struct data

{

int32_t pad[15];

int64_t v;

};

#pragma pack ()

static data value __attribute__((aligned(64)));

static int64_t counter[MAX_THREAD_NUM];

void worker(int *cnt)

{

for (int64_t i = 0; i < loop_count; ++i) {

const int64_t t = value.v;

if (t != 0L && t != ~0L) {

*cnt += 1;

}

value.v = ~t;

asm volatile("" ::: "memory");

}

int main(int argc, char *argv[])

{

pthread_t threads[MAX_THREAD_NUM];

/* Check arguments to program*/

if(argc != 3) {

fprintf(stderr, "USAGE: %s <threads> <loopcount>\n", argv[0]);

exit(1);

}

/* Parse argument */

n = min(atol(argv[1]), MAX_THREAD_NUM);

loop_count = atol(argv[2]); /* Don't bother with format checking */

/* Start the threads */

for (int64_t i = 0L; i < n; ++i) {

pthread_create(&threads[i], NULL, (void* (*)(void*))worker, &counter[i]);

}

int64_t count = 0L;

for (int64_t i = 0L; i < n; ++i) {

pthread_join(threads[i], NULL);

count += counter[i];

}

printf("data size: %lu\n", sizeof(value));

printf("data addr: %lX\n", (unsigned long)&value.v);

printf("final: %016lX\n", value.v);

return 0;

}

这段代码的逻辑很简单，开多个线程并行执行一个不断对全局变量取反的操作，你觉得最后的结果会是什么呢？

继续阅读：→

Sequential Consistency，Cache-Coherence及Memory barrier

如今多核CPU在服务器中已经是标配，如何更好的发挥多核CPU进行并行计算相信是每个后端开发都会遇到的难题。这篇文章主要是梳理一下我最近学习的一些关于C++多线程编程的知识。

并发 VS 并行

提到并发编程，有很多不同的编程模型，如多进程、多线程、协程，还可以结合使用I/O多路复用技术来进行异步并发编程，由此产生了很多不同类型的并发编程技巧来解决各类场景下的问题。

其中，协程模型也称为“用户态线程”，在用户态对程序流进行切换，避免了系统上下文切换的开销，属于并发而不是并行的（协程也可以和多进程、多线程模型结合，此处不做探讨），多进程和多线程的编程模型是真正并行的，即多个程序流是真正同时运行的，因此可以更好的利用多核优势，由于多线程之间共用进程地址空间，所以多线程模型相对多进程模型而言可以减少一些进程间的通信开销。

多线程同步

然而，凡事有利必有弊，共用进程地址空间带来了性能上的提高必然也会产生一些复杂的问题，及引入了线程间同步的问题。多个线程如果不加保护的访问共享的变量，必然会引发严重问题，这些在线程间共享的变量被称为“临界区”，最为经典的例子就是多个线程同时对单变量执行递增操作，相信诸位都已经听到耳朵起茧，就不再展开了。

在多线程编程中，常用的同步方式是使用pthread库中提供的线程同步手段（暂不考虑C++11中提供的线程库），如互斥锁、自旋锁、信号量、条件变量等等，但这些方法不是本文的主要内容，因此也不做展开，有兴趣的同学可以自行阅读《UNIX环境高级编程》中关于多线程同步的章节。

PS：在Linux内核中由于内核线程共用内核地址空间，所以内核线程之间也需要使用线程同步机制进行保护，Linux内核中所使用的几种常见同步机制分析见我之前的文章。

继续阅读：→

Kongfy's Blog

good good code, day day up!

多线程

用户态同步之自旋锁

问题在哪

多核并发编程中的cache line对齐问题

Sequential Consistency，Cache-Coherence及Memory barrier

并发 VS 并行

多线程同步