摘要：大多数保证线程安全的方法是添加各种类型锁，使用各种同步机制，用限制对共享的可变的类变量并发访问的方式来保证线程安全。只有保证这两条语句及中间语句以原子方式执行，才能避免多线程覆盖问题。
前言
对于线程安全，我们有说不尽的话题。大多数保证线程安全的方法是添加各种类型锁，使用各种同步机制，用限制对共享的、可变的类变量并发访问的方式来保证线程安全。文本从另一个角度，使用“比较交换算法”（CompareAndSwap）实现同样的需求。我们实现一个简单的“栈”，并逐步重构代码来进行讲解。
本文通俗易懂，不会涉及到过多的底层知识，适合初学者阅读（言外之意是各位大神可以绕道了）。
“栈”（stack）是大家经常使用的抽象数据类型（啥？！不知道，请自行百度）。“栈”满足“后进先出”特性。我们用链表数据结构完成一个简单的实现：
public class Stack{ //链表结构头部节点 private Node head; /** * 入栈 * @param item */ public void push(E item) { //为新插入item创建一个新node Node newHead = new Node<>(item); if(head!=null){ //将新节点的下一个节点指向原来的头部 newHead.next = head; } //将头部指向新的节点 head=newHead; } /** * 出栈 * @return */ public E pop() { if(head==null){ //当前链表为空 return null; } //暂存当前节点。 Node oldHead=head; //将当前节点指向当前节点的下一个节点 head=head.next; //从暂存的当前节点记录返回数据 return oldHead.item; } /** * 链表中的节点 * @param */ private static class Node { //节点保存的数据 public final E item; //指向下一个链表中下一个节点 public Node next; public Node(E item) { this.item = item; } } }
代码使用链表数据结构实现“栈”，在Stack中维护一个链表的“头部节点”，通过对头部节点的操作完成入栈和出栈操作。
我们运行代码测试一下：
public static void main(String[] args) {
Stack stack=new Stack<>();
for (int i = 0; i < 3; i++) {
//入栈1、2、3
stack.push(i+1);
}
for (int i = 0; i < 3; i++) {
//出栈3、2、1
System.out.println(stack.pop());
}
}
结果为：
3 2 1
我们使用入栈方法向Stack插入1、2、3，使用出栈方法打印为3、2、1，符合预期。
2.让多线程捣捣乱前面我们已经测试过我们的方法，符合我们对Stack功能的预期，那是不是任何情况先我们的“栈”都能正常工作呢？
我们运行如下代码：
public static void main(String[] args) {
Stack stack=new Stack<>();
int max=3;
Thread[] threads=new Thread[max];
for (int i = 0; i < max; i++) {
int temp=i;
//入栈1、2、3
Thread thread=new Thread(new Runnable() {
@Override
public void run() {
stack.push(temp+1);
}
});
thread.start();
threads[temp]=thread;
}
//等待所有线程完成。
for (int i = 0; i < max; i++) {
try {
threads[i].join();
} catch (InterruptedException e) {
}
}
for (int i = 0; i < max; i++) {
//出栈3、2、1
System.out.println(stack.pop());
}
}
你可能运行了很多次，每次运行时除了打印顺序（3、2、1或2、3、1或1、2、3）有变化之外也没有发现其他异常，你可能会说打印顺序变化很正常呀，因为我们的将入栈操作放到异步线程中操作，三个线程的执行过程由系统调度，所以入栈操作的内容自然每次都有可能不同。
好吧，你说的没错，至少从大量运行的结果上看是这样的，但是这就是多线程编程的奇（tao）幻(yan)之处，也许你运行一次没有问题，两次没有问题，一万次也没有问题，但是终有一次你会得到那个意想不到的结果（你也不想得到，因为那是bug）。这就像一个“黑天鹅事件”，小概率但是一定会发生，且发生后对你的系统影响不堪设想。
下面让我带你看看如何得到意料之外的结果：
我们使用调试模式运行上面的程序在Stack中push()方法第一行打一个断点，然后按照表格中的顺序切换不同的线程以单步调试（step over）方式运行run方法中的每一步，直到遇到Resume。
| 执行顺序 | thread-0 | thread-1 | thread-2 |
|---|---|---|---|
| 1 | Node |
-- | -- |
| 2 | head=newHead; | -- | -- |
| 3 | (Resume) | -- | -- |
| 4 | -- | Node |
-- |
| 5 | -- | -- | Node |
| 6 | -- | newHead.next = head; | -- |
| 7 | -- | -- | newHead.next = head; |
| 8 | -- | head=newHead; | -- |
| 9 | -- | -- | head=newHead; |
| 10 | -- | (Resume) | |
| 11 | -- | -- | (Resume) |
当你再次看到打印结果，你会发现结果为3、1、null，“黑天鹅”出现了。
异常结果是如何产生的？
当thread-0执行到顺序3时，head表示的链表为node(1)。
当thread-1执行到顺序10时，head表示的链表为node(2)->node(1)。
当thread-2执行到顺序11时，head表示的链表为node(3)->node(1)。
当三个线程都执行完毕之后，head的最终表示为node(3)->node(1)，也就是说thread-2将thread-1的执行结果覆盖了。
语句newHead.next = head;是对头部节点的读取。语句head=newHead;是对头部节点的写入操作。这两条语句组成了一个“读取——设置——写入”语句模式（就像n=n+1）。
如果一个线程执行了共享头部变量读取语句，切换其他线程执行了修改共享变量的值，再切回到第一个线程后，第一个线程中修改头部结点的数据就不是最新的数据为依据的，所以修改之后其他线程的修改就被覆盖了。
只有保证这两条语句及中间语句以原子方式执行，才能避免多线程覆盖问题。
大家可以任意调整代码中读取头部节点和写入头部节点的调试顺序，制造多线程交错读写观察不同的异常结果。
为什么我们直接执行无法看到异常结果呢？
因为我们的run方法很简单，在CPU分配的时间片内能运行完，没有出现在不同的运行周期中交错运行的状态。所以我们才要用调试模式这种交错运行。
为什么上文中我说过这种异常一定会发生？
原因在于我们在Stack类中对共享的、可变的变量head进行的多线程读写操作。
怎么才能保证类Stack在多线程情况下运行正确？
引用一段《JAVA并发编程实践》中的话：
无论何时，只要有多于一个的线程访问给定的状态变量，而且其中某个线程会写入该变量，此时必须使用同步来协调线程对该变量的访问。
好吧，看来我们必须采用“同步”方法了，来保障我们的Stack类在多线程并行和单线程串行的情况下都有正确的结果，也就是说将Stack变成一个线程安全的类。
3.让你捣乱，请家长！既然多线程总来捣乱，我们就请他的家长，让家长管管他，守守规矩，不在捣乱。
我们已经知道了Stack类问什么不能再多线程下正确的运行的原因，所有我们要限制多线程对Stack类中head变量的并发写入，Stack方法中push()和pop()方法都会对head进行写操作，所以要限制这两个方法不能多线程并发访问，所以我们想到了synchronized关键字。
程序重构：
public class SynchronizedStack{ //链表结构头部节点 private Node head; /** * 入栈 * @param item */ public synchronized void push(E item) { //为新插入item创建一个新node Node newHead = new Node<>(item); if(head!=null){ //将新节点的下一个节点指向原来的头部 newHead.next = head; } //将头部指向新的节点 head=newHead; } /** * 出栈 * @return */ public synchronized E pop() { if(head==null){ //当前链表为空 return null; } //暂存当前节点。 Node oldHead=head; //将当前节点指向当前节点的下一个节点 head=head.next; //从暂存的当前节点记录返回数据 return oldHead.item; } /** * 链表中的节点 * @param */ private static class Node { //节点保存的数据 public final E item; //指向下一个链表中下一个节点 public Node next; public Node(E item) { this.item = item; } } }
将Stack类替换为SynchronizedStack类的测试方法。
public static void main(String[] args) {
SynchronizedStack stack=new SynchronizedStack<>();
int max=3;
Thread[] threads=new Thread[max];
for (int i = 0; i < max; i++) {
int temp=i;
//入栈1、2、3
Thread thread=new Thread(new Runnable() {
@Override
public void run() {
stack.push(temp+1);
}
});
thread.start();
threads[temp]=thread;
}
//等待所有线程完成。
for (int i = 0; i < max; i++) {
try {
threads[i].join();
} catch (InterruptedException e) {
}
}
for (int i = 0; i < max; i++) {
//出栈3、2、1
System.out.println(stack.pop());
}
}
我们再次运行第二章为多线程准备的测试方法，发现当执行一个线程的方法时，其他线程的方法均被阻塞，只能等到第一个线程方法执行完成之后才能执行其他线程方法。
我们只不过是在push()和pop()方法上加入了synchronized 关键字，就将这两个方法编程了同步方法，在多线程并发的情况下也如同单线程串行调用一般，方法再不能在线程间交替运行，也就不能对head变量做并发更改了，这样修改的Stack类就是线程安全的了。
除了synchronized关键字，还有其他的方式实现加锁吗？
除了synchronized关键字还可以使用java.util.concurrent.locks包中各种锁来保证同步，但是大概思路都是相同的，都是使用阻塞其他线程的方式在达到防止并发写入的目的。
阻塞线程是否会影响执行效率？
如果和不加通过的“栈”类相比，在多线程执行的之后效率一定会有影响，因为同步方法限制了线程之间的并发性，但是为了保证“栈”类的在多线程环境时功能正确，我们不得不做出效率和正确性的权衡。
必须要对整个方法加上锁吗？
我们上面已经分析了需要加锁的范围，只要保证读取头部节点和写入头部节点之间的语句原子性就可以。所以我们可以这样执行。
/**
* 入栈
*
* @param item
*/
public void push(E item) {
//为新插入item创建一个新node
Node newHead = new Node<>(item);
synchronized (this) {
if (head != null) {
//将新节点的下一个节点指向原来的头部
newHead.next = head;
}
//将头部指向新的节点
head = newHead;
}
}
/**
* 出栈
*
* @return
*/
public E pop() {
synchronized (this) {
if (head == null) {
//当前链表为空
return null;
}
//暂存当前节点。
Node oldHead = head;
//将当前节点指向当前节点的下一个节点
head = head.next;
//从暂存的当前节点记录返回数据
return oldHead.item;
}
}
通过synchronized 块实现，因为方法比较简单，所以也没有很明显的缩小加锁范围。
除了加锁的方式，是否还有其他方式？
当然，我们还有无锁化编程来解决线程之间同步的问题。这就是下面要介绍的比较交换算法。
加锁实现线程同步的方式是预防性方式。无论共享变量是否会被并发修改，我们都只允许同一时刻只有一个线程运行方法来阻止并发发生。这就相当于我们假设并发一定会发生，所以比较悲观。
现在我们换一种思路，乐观一点，不要假设对变量的并发修改一定发生，这样也就不用对方法加锁阻止多线程并行运行方法了。但是一旦发生了并发修改，我们想法发解决就是了，解决的方法就是将这个操作重试一下。
继续重构“栈”代码：
