来源

High Performance

这个系列的原文

Talks in C++ Conference

[ ] CppCon 2016: Fedor Pikus “The speed of concurrency (is lock-free faster?)"
[x] CppCon 2017: Fedor Pikus “C\+\+ atomics, from basic to advanced\. What do they really do?”
[ ] CppCon 2017: Tony Van Eerd “An Interesting Lock-free Queue - Part 2 of N”
[ ] CppCon 2017: P. McKenney, M. Michael & M. Wong “Is Parallel Programming still hard? PART 1 of 2”
[ ] CppCon 2017: Jeffrey Mendelsohn “Reader-Writer Lock versus Mutex - Understanding a Lost Bet”

其他相关资料

锁

自旋锁：更快的 fast path 和更慢的 slow path。

互斥锁：更经济的 slow path 和更慢的 fast path。（即使上锁成功也需要进出内核 syscall）

Futex (Fast Userspace muTexes): Fast path 上锁成功立即返回，slow path 上锁失败执行系统调用睡眠

轻量级锁

并非锁本身慢，而是对锁的竞争导致程序慢。使用轻量级锁可以有效提高性能。

现有实现

Windows: Critical Section（针对没有其它线程竞争锁的情况优化）
- 使用 Mutex 会进入到内核，Critical Section 不会，代价是进程间不能共享 Critical Section
macOS: POSIX Threads API， NSLock
Ubuntu: POSIX Threads API（基于 Fast Userspace Mutetx 即 futex）
- Linux 下提供两种轻量级锁， pthread_spinlock_t 和 ptthread_mutex_t；前者属于 busy loop 类型，当没有获得锁时会通过一个 while 循环进行等待；后者当线程无法成功拿到锁时会调用 system_wait ，将当前线程加入到 mutex 对应的等待队列中

自己实现（用户空间下）

基本方法

Spin 锁 → MCS Queue Lock（高效）、Ticket Lock。
- 需要区分单处理器和多处理器的情况
- 多处理器下，自旋的过程中，随着尝试拿锁失败的次数越多，拿锁的间隔应该更长。 Exponential Backoff 策略
- pause 指令也长在此使用，可以优化性能节能减排
Peterson 算法，像是为两个线程准备的 spin 锁。出发点和核心是仅仅使用 store 和 load，不使用 CAS（compare and swap 原子操作等）来实现互斥访问。由于现有体系结构下乱序是常态，因此仅仅使用读写而不使用其它机制如 Memory Barrier 来实现非常困难，再加上推广到多个线程的方法并不明显。
Review of many Mutex implementations（需熟悉 C++ Atomic 和 Relacy）

具体实现

Benaphore

#include <windows.h>
#include <intrin.h>

class Benaphore
{
private:
	LONG m_counter;
	HANDLE m_semaphore;

public:
	Benaphore()
	{
		m_counter = 0;
		m_semaphore = CreateSeamaphore(NULL, 0, 1, NULL);
	}

	~Benaphore()
	{
		CloseHandle(m_semaphore);
	}

	void Lock()
	{
		if (_InterlockedIncrement(&m_counter) > 1)
		{
			WaitForSingleObject(m_semaphore, INFINITE);
		}
	}

	void UnLock()
	{
		if (_InterlockedDecrement(&m_counter) > 0)
		{
			ReleaseSeamphore(m_semaphore, 1, NULL);
		}
	}
}

spin lock

int flag = 0;
void lock()
{
	while(__sync_lock_test_and_set(&flag, 1)) {
	}
}

void unlock()
{
	__sync_lock_release(&flag, 0);
}