先定一个全文的基调,本文只是自己对锁相关东西的一点想法，写下来整理下，前文写了点对锁的理解，后文贴了点自己尝试的无锁数据结构，不是特别严谨，只是我的一点尝试和探索。
just my humble opinion, for reference only
在并发程序中，保证访问的有序性是非常重要的，内存模型也规范了代码来访问共享变量的顺序，本文不太涉及虚拟机的一些实现，只是在应用层面分析下各自的有点与取舍。
在Java中，最简单的保证访问顺序的就是用锁了
Synchronized关键字
Synchronized这个关键字使用是最简单的，可以加在普通方法名上相当于用this来加锁，用在静态方法名上相当于this.class来加锁，也可以单独加在代码块上自己制定某个对象来加锁，这样的例子网上数不胜数，我也不就在这多展开了，底层实现是虚拟机在字节码上价了个montior，抛开底层，从应用层讲的话，就是对对象的对象头通过CAS重写，简单说下这个过程，就是每个对象都有一部分叫做“Mark Word”的空间，一般是32位，上面有着对象的类信息指针、年龄（用于GC）、hash值、以及相关锁的信息，synchronized关键字其实就是每个线程走到这后去改对象头里面锁的信息，改成自己的了就是获取到锁了，改几次都改失败了，那么就得等着挂起了，这里我只是粗略的描述了下过程，大家可以网上搜搜synchronized底层实现，包括JVM优化的偏向锁轻量级锁等，都值得深究。
显示锁
Java中的显示锁最多的就是ReentrantLock了，在我的上一篇文章中分析AQS时花了很多笔墨分析其实现与特性，有问题的读者可以点链接阅读我前一篇博文。
Synchronized VS ReentrantLock
对于这两者的比较，相同点很简单，都是为了保证对于某些非线程安全的区域的顺序访问，不同点的话，我从功能和实现去比较下两者
功能
synchronized这个关键字呢，这样说，就是他一旦开始等这个锁，他就会认为自己有朝一日定能拿到执行权，无比自信，然而ReentrantLock就不这样，他并不那么坚定的认为自己一定能拿到锁，他会试探，就有了tryLock方法，他会给自己留退路，就有了lockInterruptly方法，他不像synchronizd那样执拗，所以tryLock方法还有带超时机制的版本。除此之外，ReetrantLock还有绑定多个Condition功能，以及公平非公平模式，其实还有些api，可以看看源码里面返回boolean值的方法，在这不多说啦，这就是他们在功能上的差异。实现
在文章开头已经说到了这两者实现的差异，一个是由JVM去实现，加个monitor保证访问时的排他性，一个是基于AQS实现的排他类工具，也因为两者出生的不同，synchronized未来有更多的优化余地，现在两者性能上几乎也没差距，官方建议是除非你需要ReentrantLock的功能，不然就用synchronized关键字，最后选哪个还是看你自己咯。
Lock-Free 无锁
说完锁，说说无锁把，无锁的核心就是CompareAndSet(CAS)了，并发包里面以CAS为核心实现的工具类也特别多，可以说整个Atomic包都是把，但是CAS算法也不是万能的，在极大的并发程度下性能是不如锁的，这也很好理解，一群人占着仅有的资源重复做一些事，这些事又注定只有少部分人能成功，大部分的人效率自然低，Atomic包中的AtomicLong就是以CAS去实现加减操作，但是新版本的JDK中又多了LongAdder类，这是为什么？原因就是为了尽量避免前面提到的那种“大部分人都失败少部分人成功”的现象，其思路就是分散热点域，比如a要加1，AtomicLong就是先取出a的值，再用a+1的值去覆盖，不断尝试直至成功，LongAdder的思路就是把a 分为多个数值，比如a-3, 2 ,1三个部分，然后选中一部分，做AtomicLong做的事，最后全部累加起来，但是因为a被分为多个部分，多个线程执行操作时可以很好的分散开来，不会集中在一个地方不断尝试，这样做正确性也是毋庸置疑的，毕竟整体+1和部分+1肯定是相等的。
Atomic包有很多这样的类，都可以研究研究，而对于无锁数据结构的编写，那就是一些experts要研究的东西了，在这里我写两个玩具demo，让大家体会下。
Lock Free Queue
无锁的队列自己写起来也不是太难，因为出队入队只在头尾节点，所以只要处理下头尾节点就可以，无锁队列的问题在于我在尾节点插入时，可能此时此刻有同样的操作在另一个线程进行，所以我拿到的尾节点可能是过期的，所以要通过CAS尝试。
我们拿尾节点插入来展示，头节点读者可以对照实现
public class LockFreeQueue<V> {
private class Node<V> {//内部节点
V value = null;
AtomicReference<Node<V>> next = null;
Node(V value, Node next) {
this.value = value;
this.next = new AtomicReference<>(next);
}
}
private AtomicReference<Node<V>> head = null;
private AtomicReference<Node<V>> tail = null;
public LockFreeQueue(){
Node<V> dummy = new Node<V>(null,null);
head = new AtomicReference<>(dummy);
tail = new AtomicReference<>(dummy);
}
public boolean enQueue(V value) {
Node<V> newNode = new Node<V>(value,null);
boolean success=false;
while(!success){//插入的时候可能有其他节点抢先入队，tail会失效
Node<V> oldTail = tail.get();
AtomicReference<Node<V>> nextNode = oldTail.next;
success=nextNode.compareAndSet(null,newNode);
if(success) return true;
}
return false;
}
}
Lock Free List
队列还是挺好理解的，下面我贴下我写了大半天的无锁单链表，不保证可伸缩性，简单测试了下，因为单链表插入会有这样的问题，比如A->B->C->D的链表，我想在BC间插一个X，当我拿到B时，按理说我应该连成B->X->C这样的，但是有可能我拿到B的时候，C被人删了，但是我不知道，我还是按B->X->C连的话，链表就被我弄断了，同理，如果此时此刻B被人删了，还这么连，链表一样会断，同理的同理，如果这时候有人在BC中已经差了个Y，链表已经是B->Y->C了，我还按B->X->C连，Y就丢了，所以要顾及的情况很多，remove方法也有如上所述的问题，网上对于无锁链表的实现不多，我是参考这篇论文实现的，这篇论文将删除分为两步，即先标记（逻辑删除），再实际删除，我找了下JDK的工具类，认为AtomicMarkableReference这个类。这个类内部有个Pair（和C++中的pair差不多）就是一个二元组，第一个是持有的对象，第二个boolean标记值，符合要求，下面我贴一下代码。
public class ConcurrentLinkedList<T> {
private class Node<T> {
public Node(T value, AtomicMarkableReference<Node<T>> next) {
this.value = value;
this.next = next;
}
T value;
AtomicMarkableReference<Node<T>> next;
}
AtomicMarkableReference<Node<T>> head
= new AtomicMarkableReference<>(new Node<>(null, null), false);
//其实这里还有逻辑分支要处理，就是尾端插入时node.next.isMarked()会
//有null异常，但因为知识演示核心思路，所以就略去了（因为水平有限，
//代码会写的很丑，有心的读者可以自己实现，让我学习学习）
public boolean insert(T after, T value) {
boolean success = false;
while (!success) {
for (Node<T> node = head.getReference(); node != null && !node.next.isMarked(); node = node.next.getReference()) {
if (node.value.equals(after) && !node.next.isMarked()) {
Node<T> nextNode = node.next.getReference();
Node<T> insertNode = new Node<>(value, new AtomicMarkableReference<>(nextNode, false));
success = node.next.compareAndSet(nextNode, insertNode, false, false);
if (success) return true;
} else if (node.next == null) {//如果已经是最后一个结点，还没有匹配到就返回false
return false;
}
}
}
return false;
}
public boolean remove(T aim) {
boolean success = false;
while (!success) {
for (Node<T> predecessor = head.getReference(); predecessor != null && !predecessor.next.isMarked();
predecessor = predecessor.next.getReference()) {
AtomicMarkableReference<Node<T>> target = predecessor.next; //要删除的目标节点
AtomicMarkableReference<Node<T>> successor = target.getReference().next;//目标节点的后继结点
if (target.getReference().equals(aim) && !successor.isMarked()) {
while (!target.attemptMark(target.getReference(), true)) {}//标记已经删除，即逻辑删除
success = predecessor.next.compareAndSet(target.getReference(), successor.getReference(), true, false);//这里是物理删除
if (success) return true;
} else if (successor == null)
return false;//如果目标节点的后继结点已经是null了，说明已经到链表结尾了，
}
}
return false;
}
}
我自己实现的代码已经贴出来了，就当成伪代码看吧！自己也花了很多时间，我手动构造了点数据没出现什么问题，但是我不知道更加复杂的场景会不会出现问题，这只是我给出的思路，not solution,just my opinion,网上我也没找到很好的关于无锁链表的实现，只有一些论文，给出了思路，当然思路和实现细节还是有差距，我贴出了我的看法，如果有读者有更好的实现希望能放出来也让我学习学习。
我写这篇文章不是希望用这么点篇幅就能把很多锁和无锁的细节都描述的淋漓尽致甚至庖丁解牛，我更多的目的只是希望能作为一篇“杂谈”谈谈我对无锁和锁的看法，给读者提供一些我的理解，帮助读者在自己的“深究之路上”提供更多的垫脚石，可能很多细节还是比较粗糙，欢迎吐槽。
最后再声明下Just my humble opinion，I'm open to discussion
参考论文：（那个插图我很早保存的，实在记不起哪里来的了，如有侵权，望通知，必删）
