网站建设运营思路,中文商城html网站模板,网站备案 异地,aspcms网站无法打开文章目录1.锁的劣势2.硬件对并发的支持2.1 比较并交换2.2 非阻塞的计数器3.原子变量类3.1 原子变量是一种“更好的volatile”3.2 性能比较#xff1a;锁与原子变量4.非阻塞算法4.1 非阻塞的栈4.2 非阻塞的链表4.3 ABA问题非阻塞算法设计和实现上要复杂的多#xff0c;但在可伸…
文章目录1.锁的劣势2.硬件对并发的支持2.1 比较并交换2.2 非阻塞的计数器3.原子变量类3.1 原子变量是一种“更好的volatile”3.2 性能比较锁与原子变量4.非阻塞算法4.1 非阻塞的栈4.2 非阻塞的链表4.3 ABA问题非阻塞算法设计和实现上要复杂的多但在可伸缩性和活跃性上拥有巨大的优势。原子变量提供了与volatile变量相同的语义此外还支持原子的更新操作从而更适用于实现计数器、序列发生器和统计数据收集等。1.锁的劣势
多个线程请求锁时一些线程将被挂起并且在稍后恢复运行。当线程恢复执行时必须等待其他线程执行完他们的时间片后才能被调度执行。挂起和恢复线程等过程存在很大的开销并且通常存在较长时间的中断。 volatile更轻量级的同步机制不会发生上下文切换或线程调度等操作。局限虽然提供了可见性但不能用于构建原子的复合操作。因此当一个变量依赖其它变量或新值依赖于旧值时就不能用volatile例如i 包含了3个独立的操作–获取变量当前值加1写入新值整个过程必须是原子的。 锁定时当一个线程等待锁时它不能做其它的事情。如果一个线程在持有锁时被延迟执行如缺页错误、调度延迟等所有需要这个锁的其它线程都无法执行。如果持有锁的线程永久阻塞那么程序将永远无法继续执行。
2.硬件对并发的支持
独占锁是一种悲观锁–假设最坏的情况 对于细粒度的操作有一种乐观的方法可以不发生干扰的情况下完成更新操作。这种方法需要借助冲突检查机制来判断在更新过程中是否存在来自其他线程的干扰如果存在这个操作将失败并且可以重试CAS等。
2.1 比较并交换
CAS包含了3个操作数–需要读写的内存位置V、进行比较的值A和拟写入的新值B。当且仅当V的值等于A时CAS才会用原子方式用新值B来更新V的值否则不会执行任何操作。无论位置V的值是否等于A都将返回V原有的值。 CAS含义我认为V的值应该为A如果是那么将V的值更新为B否则不修改并告诉V的值实际为多少。 CAS是一项乐观的技术。如果有另一个线程在最近一次检查后更新了该变量那么CAS能检测到这个错误。
/*** 模拟CAS操作*/
public class SimulatedCAS {private int value;public synchronized int get() {return value;}public synchronized int compareAndSwap (int expectedValue,int newValue) {int oldValue value;if (oldValue expectedValue) {value newValue;}return oldValue;}public synchronized boolean compareAndSet(int expectedValue,int newValue) {return (expectedValue compareAndSwap(expectedValue,newValue));}
}多个线程尝试更新同一个变量时只有一个线程能更新变量的值而其他线程都将失败。失败的线程不会被挂起而是会再次尝试。由于线程竞争失败后不会阻塞因此他可以决定是否重新尝试或者执行一些恢复操作或者不执行任何操作。
2.2 非阻塞的计数器
使用CAS实现一个简单的非阻塞计数器
public class CasCounter {private SimulatedCAS value;public int getValue() {return value.get();}public int increment() {int v;do {v value.get();} while (v ! value.compareAndSwap(v,v 1)) {return v 1;}}
}通常反复的重试是一种合理的策略但一些竞争激烈的情况下更好的方式是在重试之前首先等待一段时间或者回退从而避免造成活锁问题。 CasCounter 不会阻塞如果其他线程同时更新计数器那么会多次执行重试操作。如果仅需要一个计数器或序列生成器那么可以直接使用AtomicInteger或AtomicLong他们能提供原子的递增方法 竞争程度不高时基于CAS的计数器在性能上远胜于基于锁的计数器。
3.原子变量类
原子变量类相当于一种泛化的volatile变量能够支持原子的和有条件的读-改-写操作。AtomicInteger表示一个int类型的值并提供了get和set方法。发生竞争时有很好的可伸缩性。 共12个原子变量类分为4组标量类更新器类数组类以及复合变量类。 最常用的原子变量就是标量类AtomicInteger、AtomicLong、AtomicBoolean以及AtomicReference。他们都支持CAS。 原子数组类只支持Integer、Long、Reference版本中的元素可以实现原子更新。原子数组类为数组的元素提供了volatile类型的访问语义这是普通数组不具备的特性–volatile类型的数组仅在数组引用上具有volatile在其元素上没有。 原子的标量类扩展了Number类但并没有扩展一些基本类型的包装类如Integer或Long因为基本类型的包装类是不可修改的而原子变量类是可修改的。
3.1 原子变量是一种“更好的volatile”
public class CasNumberRange {private static class IntPair {//不变形条件 lower upperfinal int lower;final int upper;private IntPair(int lower, int upper) {this.lower lower;this.upper upper;}}//使用AtomicReference和IntPair来保存状态private final AtomicReferenceIntPair values new AtomicReference(new IntPair(0, 0));public int getLower() {return values.get().lower;}public int getUpper() {return values.get().upper;}public void setLower(int i) {while (true) {IntPair oldv values.get();if (i oldv.upper) {throw new IllegalArgumentException(Can not set lower to i upper);}IntPair newv new IntPair(i, oldv.upper);//CAS 避免竞态if (values.compareAndSet(oldv, newv)) {return;}}}
}3.2 性能比较锁与原子变量
低竞争情况下原子变量的性能高于锁高竞争情况下锁性能高于原子变量 但实际情况中原子变量在可伸缩性上要高于锁因为在应对常见的竞争程度时原子变量的效率会更高。
4.非阻塞算法
4.1 非阻塞的栈
非阻塞算法通常比基于锁的算法更复杂。算法关键在于找出如何将原子修改的范围缩小到单个变量上同时还要维护数据一致性。 栈时最简单的链式数据结构 每个元素只指向一个元素
public class ConcurrentStackE {AtomicReferenceNodeE top new AtomicReference();public void push(E item) {NodeE newHead new Node(item);NodeE oldHead;do {oldHead top.get();//新节点的next指向当前栈顶newHead.next oldHead;//使用CAS把新节点放到栈顶//如果开始插入节点前栈顶没有发生变化CAS就会成功更新栈顶//如果栈顶发生变化被其他线程修改CAS会失败并根据新的栈状态来更新节点} while (top.compareAndSet(oldHead,newHead));}private static class NodeE {public final E item;public NodeE next;public Node(E item) {this.item item;}}
}非阻塞算法特性某工作的完成具有不确定性必须重新执行。 CAS既能提供原子性又能提供可见性所以非阻塞算法是线程安全的。
4.2 非阻塞的链表
链表需要单独维护头指针和尾指针来快速访问。有两个指针指向位于尾部的节点当前最后一个元素的next指针以及尾节点。当插入一个元素时这两个指针都需要采用原子操作来更新。 技巧
即使在一个包含多个步骤的更新操作中也要确保数据结构总是处于一致的状态。B线程到达时如果A正在执行更新操作B不能立即开始自己的更新操作。然后B可以等待通过反复检查队列的状态并直到A完成如果B到达时发现A正在修改数据结构那么在数据结构中应该有足够多的信息使得B能完成A的更新操作。如果B帮助A完成了更新操作那么B可以执行自己的操作而不用等A操作完成。当A恢复后视图完成其操作时会发现B已经替他完成了。 空队列通常包含一个“哨兵节点Sentinel”或者“哑节点Dummy”并且头结点和尾结点在初始化时都指向该哨兵节点。尾节点通常要么指向哨兵节点如果队列为空即队列的最后一个元素要么当有操作正在执行更新操作时指向倒数第二个元素。
public class LinkedQueueE {private static class NodeE {final E item;final AtomicReferenceNodeE next;private Node(E item, AtomicReferenceNodeE next) {this.item item;this.next next;}}private final NodeE dummy new Node(null,null);private final AtomicReferenceNodeE head new AtomicReference(dummy);private final AtomicReferenceNodeE tail new AtomicReference(dummy);//插入元素需要更新两个指针public boolean put(E item) {NodeE newNode new Node(item, null);while (true) {NodeE curTail tail.get();NodeE tailNext curTail.next.get();if (curTail tail.get()) {if (tailNext ! null) {//队列处于中间状态推进尾结点tail.compareAndSet(curTail,tailNext);} else {//处于稳定状态尝试插入新节点if (curTail.next.compareAndSet(null,newNode)) {//插入操作成功尝试推进尾结点tail.compareAndSet(curTail,newNode);return true;}}}}}
}插入元素需要更新两个指针。首先更新当前最后一个元素的next指针将新节点链接到队尾然后更新尾结点将其指向这个新的元素。 当队列处于稳定状态尾结点的next域降为空如果队列处于中间状态那么tail.next将为非空。因此任何线程都能通过检查tail.next来获取队列当前的状态。
4.3 ABA问题
CAS判断值相等的间隙值是否发生过改变 解决方法改变引用值的时候增加一个版本号。每次改变的操作都更新版本号。
