一月 2017

问题在哪

首先明确问题，我们需要一种用户态实现的线程同步机制，正确性当然是最重要的。本文的目的是实现正确的自旋锁（自旋锁比较简单轻量，但了解了原理后实现互斥锁并不困难，自行维护等待关系并通过 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内存模型），不具备可移植性。

先看一段代码：

#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;

}

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

继续阅读：→

Kongfy's Blog

good good code, day day up!

用户态同步之自旋锁

问题在哪

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