潍坊网站建设首荐创美网络,怎么做品牌推广和宣传,江门网站制作建设,交互设计研究生1、什么是无锁(Lock-Free)编程 当谈及 Lock-Free 编程时#xff0c;我们常将其概念与 Mutex(互斥) 或 Lock(锁) 联系在一起#xff0c;描述要在编程中尽量少使用这些锁结构#xff0c;降低线程间互相阻塞的机会#xff0c;以提高应用程序的性能。类同的概念还有 Lock… 1、什么是无锁(Lock-Free)编程 当谈及 Lock-Free 编程时我们常将其概念与 Mutex(互斥) 或 Lock(锁) 联系在一起描述要在编程中尽量少使用这些锁结构降低线程间互相阻塞的机会以提高应用程序的性能。类同的概念还有 Lockless 和 Non-Blocking 等。实际上这样的描述只涵盖了 Lock-Free编程的一部分内容。本质上说Lock-Free 编程仅描述了代码所表述的性质而没有限定或要求代码该如何编写。 基本上如果程序中的某一部分符合下面的条件判定描述则我们称这部分程序是符合 Lock-Free的。反过来说如果某一部分程序不符合下面的条件描述则称这部分程序是不符合 Lock-Free 的。 上面的英文翻译成中文就是很简单的如果你的应用程序是多线程并且它们之间都有访问共享内存但是访问时并没有相互阻塞那它就是lock-free编程。注意lock-free只是强调了编程概念并没指定其具体的实现形式其强调的概念是「线程间访问共享内存时不会相互阻塞」。那如果没有lock或者Mutex就一定是lock-free编程了吗看下面的代码片段 x 0;while(x 0){x 1 - x;} 假设有线程T1,T2同时调用这段代码T1,T2都判断x 0,进行到循环。T1先执行 x 1 - 0此时 x 1后 T2 执行 x 1 - 1。x 0。T1,T2此时判断x 0结果两者又进入了循环。。。线程T1,T2相互影响两者都陷入了死循环这种某种意义也算得上是相互阻塞使线程,所以这不算是lock-free编程。 ok了解了lock-free编程的相关概念那要怎么实现呢。在开始说无锁队列之前我们需要知道一个很重要的技术就是CAS操作——Compare Set或是 Compare Swap现在几乎所有的CPU指令都支持CAS的原子操作X86下对应的是 CMPXCHG 汇编指令。有了这个原子操作我们就可以用其来实现各种无锁lock free的数据结构。 这个操作用C语言来描述就是下面这个样子意思就是说看一看内存*reg里的值是不是oldval如果是的话则对其赋值newval。 1 2 3 4 5 6 7 int compare_and_swap (int* reg, int oldval, int newval) { int old_reg_val *reg; if (old_reg_val oldval) *reg newval; return old_reg_val; } 用JAVA语言则是 public final boolean compareAndSet(int expect, int update) {return unsafe.compareAndSwapInt(this, valueOffset, expect, update);}了解了CAS操作之后实现lock-free数据结构思路是怎样呢这里就有篇论文讲述了思路http://citeseerx.ist.psu.edu/viewdoc/download?doi10.1.1.53.8674reprep1typepdf。其中里面就提到了如何用数组实现一个lock-free队列。有兴趣的朋友可以参考上面链接阅读里面的第5章节。现在说一下我自己具体的实现思路 数组队列是一个循环数组队列少用一个元素当头等于尾标示队空尾加1等于头标示队满。数组的元素用EMPTY无数据标示可以入队和FULL有数据标示可以出队标记指示数组一开始全部初始化成 EMPTY标示空队列。EnQue 操作如果当前队尾位置为EMPTY标示线程可以在当前位置入队通过CAS原子操作把该位置设置为FULL避免其它线程操作这个位置操作完后修改队尾位置。各个线程竞争新的队尾位置。如下图所示 下面是贴上具体的代码 import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceArray;/*** 用数组实现无锁有界队列*/public class LockFreeQueue {private AtomicReferenceArray atomicReferenceArray;//代表为空没有元素private static final Integer EMPTY null;//头指针,尾指针AtomicInteger head,tail;public LockFreeQueue(int size){atomicReferenceArray new AtomicReferenceArray(new Integer[size 1]);head new AtomicInteger(0);tail new AtomicInteger(0);}/*** 入队* param element* return*/public boolean add(Integer element){int index (tail.get() 1) % atomicReferenceArray.length();if( index head.get() % atomicReferenceArray.length()){System.out.println(当前队列已满, element无法入队!);return false;}while(!atomicReferenceArray.compareAndSet(index,EMPTY,element)){return add(element);}tail.incrementAndGet(); //移动尾指针System.out.println(入队成功! element);return true;}/*** 出队* return*/public Integer poll(){if(head.get() tail.get()){System.out.println(当前队列为空);return null;}int index (head.get() 1) % atomicReferenceArray.length();Integer ele (Integer) atomicReferenceArray.get(index);if(ele null){ //有可能其它线程也在出队return poll();}while(!atomicReferenceArray.compareAndSet(index,ele,EMPTY)){return poll();}head.incrementAndGet();System.out.println(出队成功! ele);return ele;}public void print(){StringBuffer buffer new StringBuffer([);for(int i 0; i atomicReferenceArray.length() ; i){if(i head.get() || atomicReferenceArray.get(i) null){continue;}buffer.append(atomicReferenceArray.get(i) ,);}buffer.deleteCharAt(buffer.length() - 1);buffer.append(]);System.out.println(队列内容: buffer.toString());}}代码很简单相应的注释也写上了相信大家都应该看得懂~。 这里说明一下JDK提供的CAS原子操作类都位于 java.util.concurrent.atomic下面。这里用到的是数组我用的是AtomicReferenceArray类当然你也可以用AtomicIntegerArray。这里用到了两个原子类的作为指针head,tail利用mod队列的长度来实现一个循环数组。 下面测试我们的代码 import java.util.stream.IntStream;public class LockFreeDemo {public static void main(String[] args) {LockFreeQueue queue new LockFreeQueue(5);IntStream.rangeClosed(1, 10).parallel().forEach(i - {if (i % 2 0) {queue.add(i);} else {queue.poll();}});queue.print();}
}这里面用了JDK8的lambda并行流的特性起了Ncpu线程去并发得入队和出队。运行结果如下 入队成功!2
当前队列为空
当前队列为空
入队成功!6
当前队列为空
入队成功!8
出队成功!2
入队成功!10
出队成功!6
入队成功!4
队列内容:[4,8,10]因为是并发打印所以打出来的信息整体是无序的但是对于同一个元素的操作我们看到是相对有序的~ 转载于:https://www.cnblogs.com/linlinismine/p/9263426.html
