资源互斥（Resources Mutex）：当一个线程正在访问某共享资源（如：共享变量、共享数据结构）时，就不允许其他线程对其访问。
线程同步（Thread Synchronization）：多个相关线程在执行次序上的协调。具体分为用户模式下的线程同步和基于内核对象的线程同步。
用户模式下的线程同步有：Interlocked函数、临界区段（CriticalSection）、自旋锁（SpinLock，又称旋转锁）、排号自旋锁（TicketLock）、Slim读写锁（SRWLock）。注：CriticalSection及各种锁的内部都直接或间接使用了Interlocked函数
内核对象的线程同步有：事件对象（Event）、互斥量对象（Mutex，或互斥体对象）、信号量对象（Semaphore）等。基于内核对象的同步，会带来昂贵的上下文切换（用户态切换到内核态，占用1000个以上的cpu周期）。
临界资源（Critical Resource）：一段时间内仅允许一个线程使用的资源。
临界区段（Critical Section）：访问临界资源的程序片段。特点：当有线程进入临界区段时，其他线程必须等待。
锁（Lock）：一个代表资源状态的变量，通常用0表示资源可用（开锁，即不锁），用1表示资源已被占用（关锁，即锁住）。
原子性
原子操作（又称原子访问，Atomic Access）：硬件支持的特性。在多线程并发情况下，一个操作的状态要么没有发生，要么发生。即：一个线程不会看到另外一个线程执行的中间状态。
可简单地理解为：线程A在执行原子操作时，其他线程像全部暂停了一样。线程A执行完原子操作后，其他线程才继续执行。
即使是简单的语句也不保证是原子操作。如：int64_t n = 100; // 即使地址对齐的情况下，在x86的CPU架构中，写入int64需要2个CPU指令 x64下则是1个CPU指令
另外，仅仅使用一条CPU指令的内存操作，在个别CPU架构上也是非原子的。
无锁（lock free）的数据结构正是通过原子操作其内部共享数据来实现的。常见的有：无锁队列（lock free queue）、无锁栈
常见的原子操作有：
1. 对齐读（Aligned Read）
如：C++11标准中的load函数
2. 对齐写（Aligned Write）
如：C++11标准中的store函数
3. TSL（Test & Set wiki，chs）：设置成1，并返回原来的值。伪代码如下：
int test_and_set(int* lockPtr) { int oldValue = *lockPtr; *lockPtr = 1; return oldValue; }
可用来实现自旋锁（SpinLock，又称旋转锁），伪代码如下：
volatile int lock_val = 0; void CriticalTest() { while (test_and_set(&lock_val) == 1); // 后续线程会在此死循环等待 // 临界段（critical section） // 同时只能有一个线程执行该逻辑 lock_val = 0; // 临界段结束后，释放锁 }
自旋锁是多线程同步的一种锁，线程反复检查锁变量是否可用（线程在这一过程中保持执行，处于忙等待状态）。一旦获取了自旋锁，线程会一直保持该锁，直至显式释放自旋锁。
可用来实现Slim读写锁（SRWLock，Slim Reader Writer Lock），伪代码如下：
volatile int read_lock = 0; // 读线程使用的旋转锁，用于互斥访问 volatile int write_lock = 0; int read_count = 0; // 读线程 获取锁 void acquire_lock_share { while (test_and_set(&read_lock) == 1); // 后续读线程会在此死循环等待 read_count++; if (read_count == 1) { while (test_and_set(&write_lock) == 1); // 有写线程时，当前读线程在此死循环等待 } // 没有写线程时，所有的读线程都可以执行该逻辑 read_lock = 0; } // 读线程 释放锁 void release_lock_share { while (test_and_set(&read_lock) == 1); // 后续读线程会在此死循环等待 read_count--; if (read_count == 0) { write_lock = 0; } read_lock = 0; } // 写线程 获取锁 void acquire_lock_exclusive { while (test_and_set(&write_lock) == 1); // 有读线程或写操作线程时，后续写线程会在此死循环等待 // 没有读线程时，当且仅有一个写线程执行该逻辑 } // 写线程 释放锁 void release_lock_exclusive { write_lock = 0; }
由于读线程并不会破坏数据，因此Slim读写锁将对锁操作的线程分成：读线程和写线程。以提高并发效率。
读线程以共享模式（share）来获取和释放锁，写线程以独占模式（exclusive）来获取和释放锁。
当没有写线程时，各个读线程可并发运行。写线程与写线程是互斥的；写线程与读线程也是互斥的。
Test and Test-and-set，用来降低Test & Set的资源争夺情况。用它来实现的自旋锁的伪代码如下：
volatile int lock_val = 0; void CriticalTest() { do { while (lock_val == 1) yield(); // 如果lock住，释放cpu占用 } while (test_and_set(&lock_val) == 1) // lock住，继续循环等待 // 临界段（critical section） // 同时只能有一个线程执行该逻辑 lock_val = 0; // 临界段结束后，释放锁 }
4. CAS（ Compare & Swap wiki，chs）：比较并交换操作，若交换成功则返回true，否则返回失败。伪代码如下：
bool compare_and_swap(int* reg, int comparand, int exchange) { int old_reg_val = *reg; if (old_reg_val == comparand) { *reg = exchange; return true; } return false; }
在x86/64 和 Itanium 架构，CAS被认为是最基础的一种原子性的RMW（Read-Modify-Write wiki，chs）操作。RMW：读一个内存位置，修改其值，再写回原位置。
而在PowerPC、MIPS 和 ARM 架构，通过 Load-Link/Store-Conditional (LL/SC wiki，chs) 方式来实现最基础的一种原子性的RMW操作，然后通过LL/SC对来实现CAS，但在一些情况下，实现出来的CAS并不具有原子性。
问题1：为什么在PowerPC、MIPS 和 ARM 架构上，会存在LL/SC对的使用，而不直接实现CAS原语呢？
主要是为了解决ABA问题（又称掉包问题）。
下面以CAS原语实现的无锁栈，来讲解什么是ABA问题。
① 有一个栈(先入后出)中有top和节点A，节点A目前位于栈顶top指针指向A。
top
|
V
0x0014
| Node A | --> | Node X | --> ……
② 现在有一个进程P1想要pop一个节点，因此按照如下无锁操作进行
pop() { do{ ptr = top; // ptr = top = NodeA next_prt = top->next; // next_ptr = NodeX } while(CAS(top, ptr, next_ptr) != true); return ptr; }
③而进程P2在执行CAS操作之前打断了P1，并对栈进行了一系列的pop和push操作：首先pop出NodeA，之后又Push了两个NodeB和C
由于内存管理机制中广泛使用的内存重用机制，导致NodeC的地址与之前的NodeA一致。使栈变为如下结构：
top
|
V
0x0014
| Node C | --> | Node B | --> | Node X | --> ……
④这时P1又开始继续运行，在执行CAS操作时，由于top依旧指向的是NodeA的地址(实际上已经变为NodeC)，因此将top的值修改为了NodeX，这时栈结构如下：
top
|
0x0014 V
| Node C | --> | Node B | --> | Node X | --> ……
最后使得top指针错误的指向了NodeX而不是NodeB。
结论：通过 "值相同" 来判定 "值没变"是不可靠的。后面的线程可能多次修改了该值，这样就相当于欺骗了前面的线程，使其认为 "值没变"，实际上值已经被篡改过了。
LL和SC的伪代码实现如下：
int LL( int* pAddr ) { return *pAddr ; } bool SC( int* pAddr, int New ) { if ( data in pAddr has not been changed since the LL call) // LL调用后，pAddr指向的数据没有发生变化时 { *pAddr = New; return true; } else { return false; } }
注：在实现上，处理器开发者给每个Cahce Line添加额外的比特状态值（status bit）。一旦LL执行读运算，就会关联此比特值。任何的缓存行一旦有写入，此比特值就会被重置；
在存储之前，SC操作会检查此比特值是否针对特定的缓存行。如果比特值为1，意味着缓存行没有任何改变，pAddr 地址中的值会变更为新值，SC操作成功。否则本操作就会失败，pAddr 地址中的值不会变更为新值。
问题2：LL/SC对实现的CAS，但在一些情况下，为什么不具有原子性？
实现的CAS的伪代码如下：
int CAS( int* pAddr, int nExpected, int nNew ) { if ( LL( pAddr ) == nExpected ) return SC( pAddr, nNew ); return false; }
该CAS在执行过程中，可能会被中断，例如：线程X在执行LL后，OS决定将X调度出去，等OS重新调度恢复X之后，SC将不再响应，CAS失败的原因不在数据本身是否有变化，而是其他外部事件(线程被中断导致的)。
注：正是因为如此，C++11标准中添入两个compare_exchange原语分别被命名为compare_exchange_weak和compare_exchange_strong
任何weak CAS都可能破坏CAS语义，失败并返回false，而它本应返回true。而Strong CAS会严格遵循CAS语义。
我们可以非常简单地利用CAS来实现一个自旋锁，伪代码如下：
volatile int lock_val = 0; void CriticalTest() { while (compare_and_swap(&lock_val, 0, 1)); // 后续线程会在此死循环等待 // 临界段（critical section） // 同时只能有一个线程执行该逻辑 lock_val = 0; // 临界段结束后，释放锁 }
5. value CAS（ Compare & Swap wiki，chs）：比较并交换操作并返回原来的值。伪代码如下：
int compare_and_swap(int* reg, int comparand, int exchange) { int old_reg_val = *reg; if (old_reg_val == comparand) *reg = exchange; return old_reg_val; }
6. FAA（Fetch & Add wiki，chs）：进行加法操作并返回原来的值。伪代码如下：
int fetch_and_add(int* reg, int amount) { int old_reg_val = *reg; *reg = old_reg_val + amount; return old_reg_val; }
FAA也是一种原子性的RMW操作，可通过最基础的RMW操作CAS来实现。
可用来实现排号自旋锁（TicketLock），伪代码如下：
typedef struct lock_t { int ticket; int turn; } lock_t g_lock; g_lock.ticket = 0; g_lock.turn = 0; void CriticalTest() { int myturn = fetch_and_add(g_lock->ticket, 1); while (g_lock->turn != myturn) ; //后续各线程按进入的先后顺序在此死循环等待 // 临界段（critical section） // 同时只能有一个线程执行该逻辑 fetch_and_add(g_lock->turn, 1); // 临界段结束后，将turn变量也+1 }
排号自旋锁是多线程同步的一种锁，类似于自旋锁，但每一个申请排队自旋锁的线程获得一个排队号（ticket）。
至多一个线程拥有自旋锁，当它释放锁时，把自身的ticket加1作为下一个可获得锁的ticket，持有该ticket的线程在自旋检查时就可发现已经获得了自旋锁，是一种先进先出(FIFO)的公平锁。
这种机制类似于一些提供社会服务的场所（如银行）：进门的顾客从排号机获取一个等待号，然后不断检查当前可服务的号，直至轮到其手持的号。
Interlocked函数原子性的实现原理
Interlocked函数会编译成特定的汇编指令，该指令在执行时会在总线上维持一个硬件信号，来阻止其他cpu核心访问同一个内存地址。
与切换到内核模式然后等待相比，Interlocked函数执行是极快的，只占用几个cpu周期（通常小于50）。但与普通的mov等指令相比，Interlocked函数的汇编指令是很昂贵的，要避免滥用。
需要注意的是：传给Interlocked函数的变量的地址必须是经过对齐的，否则这些函数可能会失去原子性。
顺序性
编译期乱序：编译器优化而调整了代码指令的先后顺序。
int x = 0; // global variable int y = 0; // global variable // Thread-1: // Thread-2: x = 100; while (y != 200) y = 200; ; std::cout << x;
如果 CPU 没有乱序执行指令，那么 Thread-2 将输出100。然而，对于 Thread-1 来说，x = 100;和y = 200;这两个语句之间没有依赖关系，因此，Thread-1 允许调整语句的执行顺序：
// Thread-1: y = 200; x = 100;
在这种情况下，Thread-2 将输出0或100。
运行期乱序：各个cpu有自己独立的cache，变量被cpu1修改后，为了提升运行效率没有及时通知其它cpu，导致在其他cpu上读到了老的数据。
下面的例子中，假设从时间上来讲，A 操作先于 B 操作发生：
int x = 0; // global variable // Thread-1: // Thread-2: x = 100; /* A */ std::cout << x; /* B */
尽管从时间上来讲，A 先于 B，但 CPU cache 的影响下，Thread-2 不能保证立即看到 A 操作的结果，所以 Thread-2 可能输出0或100。
当然这些乱序指令都是为了同一个目的，优化执行效率。
但是也不能无止境的乱序，至少要保证这一原则：不能改变单线程程序的执行行为。
内存屏障（Memory Barriers），也称内存栅栏、内存栅障、屏障指令，是编译器或CPU在对内存随机访问的操作中的一个同步点。通过此机制来解决编译期和运行期乱序问题。
在内存屏障之前的指令一定在内存屏障之后的指令之前执行。并保证如下内存序（Memory order）：内存屏障之前的所有写操作都要写入内存；内存屏障之后的读操作都可以获得同步屏障之前的写操作的结果。
因此，对于敏感的程序块，写操作之后、读操作之前可以插入内存屏障。
windows下通过_mm_sfence()函数来实现，其他平台通过__sync_synchronize()函数来实现。
写单线程代码的程序员不需要关心内存乱序的问题。在多线程编程中，由于互斥量，信号量和事件等在设计的时候都阻止了它们调用点中的内存乱序（已经隐式包含memory barrier），内存乱序的问题同样不需要考虑了。
只有当使用无锁(lock-free)技术时，内存在线程间共享而没有任何的互斥量，内存乱序的效果才会显露无疑，这样我们才需要考虑在合适的地方加入合适的memory barrier。
volatile关键字
① 用volatile修饰的基本类型变量能保障内存对齐
② 始终从内存中读取volatile变量的值（而不是从寄存器cache中） 注：volatile本意是“易变的”
③ 告诉编译器，volatile变量可能会被操作系统、硬件或一个并发的线程进行修改，不要对其进行各种激进的优化（如：将变量直接消除）
④ 保证Volatile变量与Volatile变量之间的顺序性，编译器不会进行乱序优化。注：Volatile变量与非Volatile变量的顺序，编译器不保证顺序，可能会进行乱序优化。
注1：给一个结构体加volatile，等于给结构体所有的成员加上valatile限定符。
注2：对volatile基本类型变量的操作是原子的；但其他类型不是原子的。
注3：vloatile不会有任何的Memory Barrier(内存栅栏)的保证。
注4：vloatile不会有任何的线程同步的保证。
参考