起初是看这篇文章写的挺好的，介绍了无锁队列的实现。按照它的说法我们来实现一下:

public class ConcurrentListQueue<T> {
  private Node<T> head, tail;
  private AtomicInteger producerLock, consumerLock;
  private static class Node<T> {
      private T data;
      private Node<T> next;
      private Node(T d) {
          this.data = d;
      }
  }
  public void add(T data) {
      Node<T> n = new Node<>(data);
      while (!producerLock.compareAndSet(0, 1)) {
      }
    
      tail.next = n;
      tail = n;
      producerLock.set(0);
  }
  
  public T poll() {
      T d = null;
      while (!consumerLock.compareAndSet(0, 1)) {
      }
    
      Node<T> h = head;
      Node<T> next = h.next;
      if (next != null) {
          d = next.data;
          next.data = null;
          head = next;
          h.next = null;
      }
    
      consumerLock.set(0);
      return d;
  }
}

这里需要注意 Producer 只能访问 tail，而 Consumer 只能访问 head，不然无法做到 Producer 和 Consumer 相互不竞争。很多队列的实现会使用一个固定的哑元做 Head，这个哑元从始至终是不变的，每次出队只是修改哑元的 next 引用，例如单线程版的 poll 可以实现成：

public void poll() {
    if (head != tail) {
        Node<T> next = head.next;
        head.next = next.next;
        if (next == tail) {
            tail = head;
        }
        next.data = null;
        next.next = null;
    }
}

这种实现下通过加锁改成并发队列，因为当出队后队列为空时由于需要调整 tail 引用指向 Head 哑元，所以在 poll 的时候也访问了 tail，这么一来按前述 Producer 和 Consumer 分别加锁的方式就不成立了，所以需要改成每次出队后，修改 Head 哑元变成刚出队的这个 Node。并且要将 Node 的 data 引用清空，帮助出队的数据 GC。

这个文章中还提到一个问题就是 False Sharing，关于这个问题还有好多地方在做解释：比如这个、这个

作者是通过添加一堆无用的 padding 字段来解决 False Sharing 的，但是在上面 Java 版本实现中该怎么解决 False Sharing 问题呢？

直接在 producerLock 和 consumerLock 前后添加 padding 是没用的，有好两个原因。一是 JVM 会对对象内的 Field 做重新排序和内存对齐，producerLock 和 consumerLock 是引用，他们两之间一定不会放入 long 型的数据（引用类型放在一起，long 类型也会放在一起，但两种类型不会穿插着放），他们两在一起声明，在内存中很有可能还是放在一起的；二是因为这两个 lock 都是引用，从始至终都不会被并发的修改，并发修改的是他们指向的 AtomicInteger 对象内的 value 字段，所以这两个引用本身就不会产生 False Sharing 问题，为它们增加 padding 完全没有效果，还会导致对象体积变大以及 producerLock 和 consumerLock 引用不能同时放入一个 Cache Line 中导致性能反而下降(可以试一下，加了 @Contended 之后性能反而会下降。因为当线程数超过机器 CPU 核数时，一个核很可能既要执行 producer 逻辑又要执行 consumer 逻辑，只是不是同时执行。如果 producerLock 和 consumerLock 不在一个 cache line 中，那么 CPU 比如从 consumer task 切换到 producer task 的时候就不能沿用之前的 cache line 需要读取主存或下一级 Cache，所以性能就会受到影响)。

AtomicInteger 是 JDK 的库，我们无法修改，不可能给它增加 padding，但我们能够继承它，从而改变其对象的内存布局。AtomicInteger 对象布局如下：

OFFSET	SIZE	TYPE	DESCRIPTION	VALUE
0	4		(object header)	01 00 00 00 (00000001 00000000 00000000 00000000) (1)
4	4		(object header)	00 00 00 00 (00000000 00000000 00000000 00000000) (0)
8	4		(object header)	f2 35 00 f8 (11110010 00110101 00000000 11111000) (-134203918)
12	4	int	AtomicInteger.value	0

我们继承 AtomicInteger 并添加 padding：

public static class PaddedAtomicInteger extends AtomicInteger{
    // 省略构造函数
    public volatile long p1, p2, p3, p4, p5, p6 = 7L;
}

其内存布局如下：

OFFSET	SIZE	TYPE	DESCRIPTION	VALUE
0	4		(object header)	01 00 00 00 (00000001 00000000 00000000 00000000) (1)
4	4		(object header)	00 00 00 00 (00000000 00000000 00000000 00000000) (0)
8	4		(object header)	05 07 02 f8 (00000101 00000111 00000010 11111000) (-134084859)
12	4	int	AtomicInteger.value	0
16	8	long	PaddedAtomicInteger.p1	0
24	8	long	PaddedAtomicInteger.p2	0
32	8	long	PaddedAtomicInteger.p3	0
40	8	long	PaddedAtomicInteger.p4	0
48	8	long	PaddedAtomicInteger.p5	0
56	8	long	PaddedAtomicInteger.p6	7

由于 PaddedAtomicInteger 是 AtomicInteger 的子类，其对象内存布局是在 AtomicInteger 的基础上进行的，父类对象的 Field 一定在子类对象之前，所以不会受到子类对象内存布局重排序的影响。

使用 PaddedAtomicInteger 之后平均性能确实比使用 AtomicInteger 好一些，但不是特别明显，平均下来只快了大概 20% 左右。但有意思的是他俩最快时间基本相同，最慢时间 AtomicInteger 要高的多，并且使用 AtomicInteger 的波动更大，慢的时候是快的时候的两倍，而 PaddedAtomicInteger 波动较小。猜想原因是 consumerLock 和 producerLock 指向的对象都在 Heap 上，我测试的时候每一轮测试都会重新构造队列对象，从而重新构造 consumerLock 和 producerLock，这两个对象虽然是连续分配的但是否一定相邻，能刚好放入一个 Cache Line 并不能说的清楚，Java 也缺乏工具去查看一个对象的内存地址。如果他俩没有分配在一个 Cache Line 上，那么使用 AtomicIntger 和使用 PaddedAtomicInteger 效果一样，所以性能结果也差不多，但是当他俩刚好分配在同一个 Cache Line 上时，AtomicInteger 性能要比 PaddedAtomicInteger 性能差一倍。巧的是我使用这篇文章给的例子在相同机器做测试，使用 PaddedAtomicInteger 的性能也是比使用 AtomicInteger 好一倍。

不过从平均性能上看这两者差别较小，并且在正常使用中由于 GC 的影响也许会让 PaddedAtomicInteger 的优势更不容易发现。

从上面叙述也能看出来，上面 False Sharing 问题不明显的原因就是 consumerLock 和 producerLock 都是引用类型，引用的对象在 Heap，所以是否会出现 False Sharing 得看对象是否刚好分配在同一个 Cache Line 上。如果我们想进一步观察到 False Sharing，我们可以将引用对象改成基本类型，使用 sun.misc.Unsafe 的 CAS 操作来实现 Atomic 库的 CAS 操作。

Unsafe 的获取能参考Netty 上的代码。在有了 Unsafe 之后我们能够重新声明 consumerLock 和 producerLock 将其改成 volatile 的基本类型：

private static final sun.misc.Unsafe UNSAFE;
private static final long producerLockOffset;
private static final long consumerLockOffset;
static {
  UNSAFE = getUnsafe();
  try {
      producerLockOffset = UNSAFE.objectFieldOffset
              (ConcurrentListQueue.class.getDeclaredField("producerLock"));
      consumerLockOffset = UNSAFE.objectFieldOffset
              (ConcurrentListQueue.class.getDeclaredField("consumerLock"));
  } catch (Exception ex) {
      throw new Error(ex);
  }
}
private volatile int producerLock;
private volatile int consumerLock;

自旋锁上锁要稍微修改一下，例如 Producer 的锁加锁逻辑改为：

1 2	while (!UNSAFE.compareAndSwapInt(this, producerLockOffset, 0, 1)) { }

解锁时候直接设置 producerLock 为 0 即可。

在上述实现下，性能非常差，比使用 PaddedAtomicInteger 时慢不止一倍。基本能确认是由 False Sharing 引起的。Java 8 之后不需要再通过 padding 的方式解决 False Sharing 问题，而是通过 @Contended 注解解决，但该注解目前还是默认不启用的，需要主动增加配置 -XX:-RestrictContended 才会产生效果。给 producerLock 和 consumerLock 增加 @Contended 注释之后，队列性能就变得跟使用 PaddedAtomicInteger 差不多了。

JOL 的使用

全名 Java Object Layout 探索对象内存布局时非常有用。下载下来 Jar 包后，比如要看自己的某个类对象的布局：
java -XX:-RestrictContended -jar jol-cli-0.8-full.jar internals my.ConcurrentListQueue -cp ~/Projects/mine/my/target/classes

如果是看内部类对象的布局，比如看 ConcurrentListQueue 下 Node 类对象的布局因为是命令行上使用，需要对 $ 转义：
java -XX:-RestrictContended -jar jol-cli-0.8-full.jar internals my.ConcurrentListQueue\$Node -cp ~/Projects/mine/my/target/classes

当然它不止是用来看内存布局奥，还有很多别的功能，非常推荐。

更进一步

实际上这里使用自旋锁在竞争激烈的时候并不适合，大量的线程资源消耗在竞争上而实际任务处理时间则花费的很少。一个典型的现象就是将 Producer 或 Consumer 并发线程数降低能显著增加性能。自旋锁上也能进行一些改进，可以参看这篇文章。实际这里将自旋锁改成 ReentrantLock 性能能比使用自旋锁高三四倍。

不过无论怎么对锁进行修改，锁的存在都是对性能影响很大的，可以参看 JUC 的 ConcurrentLinkedQueue 的实现，其性能比使用 ReentrantLock 的队列还要强两到三倍。

所有参考都在文章链接中，不一一列出了，感谢前辈的分享。

普通队列改造为并发队列

普通队列改造为并发队列

JOL 的使用

更进一步

普通队列改造为并发队列

普通队列改造为并发队列

不那么容易观察到的 False Sharing

非常容易观察到的 False Sharing

JOL 的使用

更进一步