高性能并发双向队列算法

背景

在LRU的算法实现中，一个双向队列用来计算节点热度是不可少的。但是jdk自带的实现中，是一个单线程的双向队列实现。多线程的安全性则需要依靠锁来实现，性能很低。在这种情况下，开发设计了并发双向队列算法。主要目的是通过cas操作来屏蔽锁争夺。主要提供三个操作：a.添加节点到队列末尾。b.移动节点到队首。c.删除节点
由于将锁的力度降低到了每一个节点，所以在多线程并发操作下，性能会有很大的提高。

双向队列如下图，每一个节点均含有pre和next指针。并且队列具有head指针和tail指针。head指针和tail指针都指向一个初始的head节点。该节点仅作为标识，不具有其他作用。

基本操作

基本思想 ： 对一个节点的操作，在于争夺尾节点的控制权；对于一个节点的删除或者移动操作，则在于争夺该节点和前置节点的控制权。对于当前节点和前置节点控制权的争夺，会使得写操作被顺序化，保证了正确性

将一个节点添加到尾节点

将一个节点删除

移动节点到队首

算法变种

不具有tail节点