企业应该如何建设网站,做网站设计提成赚钱吗,最便宜 双网站建设,怎样找外贸公司合作在不只一个线程访问一个互斥的变量时#xff0c;所有线程都必须使用同步#xff0c;否则就可能会发生一些非常糟糕的事情。Java 语言中主要的同步手段就是 synchronized 关键字#xff08;也称为内在锁#xff09;#xff0c;它强制实行互斥#xff0c;确保执行 synchron…在不只一个线程访问一个互斥的变量时所有线程都必须使用同步否则就可能会发生一些非常糟糕的事情。Java 语言中主要的同步手段就是 synchronized 关键字也称为内在锁它强制实行互斥确保执行 synchronized 块的线程的动作能够被后来执行受相同锁保护的 synchronized 块的其他线程看到。在使用得当的时候内在锁可以让程序做到线程安全但是在使用锁定保护短的代码路径而且线程频繁地争用锁的时候锁定可能成为相当繁重的操作。 在 “流行的原子” 一文中我们研究了原子变量原子变量提供了原子性的读-写-修改操作可以在不使用锁的情况下安全地更新共享变量。原子变量的内存语义与 volatile 变量类似但是因为它们也可以被原子性地修改所以可以把它们用作不使用锁的并发算法的基础。 非阻塞的计数器 清单 1 中的 Counter 是线程安全的但是使用锁的需求带来的性能成本困扰了一些开发人员。但是锁是必需的因为虽然增加看起来是单一操作但实际是三个独立操作的简化检索值给值加 1再写回值。在 getValue 方法上也需要同步以保证调用 getValue 的线程看到的是最新的值。虽然许多开发人员勉强地使自己相信忽略锁定需求是可以接受的但忽略锁定需求并不是好策略。 在多个线程同时请求同一个锁时会有一个线程获胜并得到锁而其他线程被阻塞。JVM 实现阻塞的方式通常是挂起阻塞的线程过一会儿再重新调度它。由此造成的上下文切换相对于锁保护的少数几条指令来说会造成相当大的延迟。 清单 1. 使用同步的线程安全的计数器 public final class Counter {private long value 0;public synchronized long getValue() {return value;}public synchronized long increment() {return value;}
} 清单 2 中的 NonblockingCounter 显示了一种最简单的非阻塞算法使用 AtomicInteger 的 compareAndSet() CAS方法的计数器。compareAndSet() 方法规定 “将这个变量更新为新值但是如果从我上次看到这个变量之后其他线程修改了它的值那么更新就失败”请参阅 “流行的原子” 获得关于原子变量以及 “比较和设置” 的更多解释。 清单 2. 使用 CAS 的非阻塞算法 public class NonblockingCounter {private AtomicInteger value;public int getValue() {return value.get();}public int increment() {int v;do {v value.get();while (!value.compareAndSet(v, v 1));return v 1;}
} 原子变量类之所以被称为原子的是因为它们提供了对数字和对象引用的细粒度的原子更新但是在作为非阻塞算法的基本构造块的意义上它们也是原子的。非阻塞算法作为科研的主题已经有 20 多年了但是直到 Java 5.0 出现在 Java 语言中才成为可能。 现代的处理器提供了特殊的指令可以自动更新共享数据而且能够检测到其他线程的干扰而 compareAndSet() 就用这些代替了锁定。如果要做的只是递增计数器那么 AtomicInteger 提供了进行递增的方法但是这些方法基于 compareAndSet()例如 NonblockingCounter.increment()。 非阻塞版本相对于基于锁的版本有几个性能优势。首先它用硬件的原生形态代替 JVM 的锁定代码路径从而在更细的粒度层次上独立的内存位置进行同步失败的线程也可以立即重试而不会被挂起后重新调度。更细的粒度降低了争用的机会不用重新调度就能重试的能力也降低了争用的成本。即使有少量失败的 CAS 操作这种方法仍然会比由于锁争用造成的重新调度快得多。 NonblockingCounter 这个示例可能简单了些但是它演示了所有非阻塞算法的一个基本特征 —— 有些算法步骤的执行是要冒险的因为知道如果 CAS 不成功可能不得不重做。非阻塞算法通常叫作乐观算法因为它们继续操作的假设是不会有干扰。如果发现干扰就会回退并重试。在计数器的示例中冒险的步骤是递增 —— 它检索旧值并在旧值上加一希望在计算更新期间值不会变化。如果它的希望落空就会再次检索值并重做递增计算。 非阻塞堆栈 非阻塞算法稍微复杂一些的示例是清单 3 中的 ConcurrentStack。ConcurrentStack 中的 push() 和 pop() 操作在结构上与 NonblockingCounter 上相似只是做的工作有些冒险希望在 “提交” 工作的时候底层假设没有失效。push() 方法观察当前最顶的节点构建一个新节点放在堆栈上然后如果最顶端的节点在初始观察之后没有变化那么就安装新节点。如果 CAS 失败意味着另一个线程已经修改了堆栈那么过程就会重新开始。 清单 3. 使用 Treiber 算法的非阻塞堆栈 public class ConcurrentStackE {AtomicReferenceNodeE head new AtomicReferenceNodeE();public void push(E item) {NodeE newHead new NodeE(item);NodeE oldHead;do {oldHead head.get();newHead.next oldHead;} while (!head.compareAndSet(oldHead, newHead));}public E pop() {NodeE oldHead;NodeE newHead;do {oldHead head.get();if (oldHead null) return null;newHead oldHead.next;} while (!head.compareAndSet(oldHead,newHead));return oldHead.item;}static class NodeE {final E item;NodeE next;public Node(E item) { this.item item; }}
} 性能考虑 在轻度到中度的争用情况下非阻塞算法的性能会超越阻塞算法因为 CAS 的多数时间都在第一次尝试时就成功而发生争用时的开销也不涉及线程挂起和上下文切换只多了几个循环迭代。没有争用的 CAS 要比没有争用的锁便宜得多这句话肯定是真的因为没有争用的锁涉及 CAS 加上额外的处理而争用的 CAS 比争用的锁获取涉及更短的延迟。 在高度争用的情况下即有多个线程不断争用一个内存位置的时候基于锁的算法开始提供比非阻塞算法更好的吞吐率因为当线程阻塞时它就会停止争用耐心地等候轮到自己从而避免了进一步争用。但是这么高的争用程度并不常见因为多数时候线程会把线程本地的计算与争用共享数据的操作分开从而给其他线程使用共享数据的机会。这么高的争用程度也表明需要重新检查算法朝着更少共享数据的方向努力。“流行的原子” 中的图在这方面就有点儿让人困惑因为被测量的程序中发生的争用极其密集看起来即使对数量很少的线程锁定也是更好的解决方案。 非阻塞的链表 目前为止的示例计数器和堆栈都是非常简单的非阻塞算法一旦掌握了在循环中使用 CAS就可以容易地模仿它们。对于更复杂的数据结构非阻塞算法要比这些简单示例复杂得多因为修改链表、树或哈希表可能涉及对多个指针的更新。CAS 支持对单一指针的原子性条件更新但是不支持两个以上的指针。所以要构建一个非阻塞的链表、树或哈希表需要找到一种方式可以用 CAS 更新多个指针同时不会让数据结构处于不一致的状态。 在链表的尾部插入元素通常涉及对两个指针的更新“尾” 指针总是指向列表中的最后一个元素“下一个” 指针从过去的最后一个元素指向新插入的元素。因为需要更新两个指针所以需要两个 CAS。在独立的 CAS 中更新两个指针带来了两个需要考虑的潜在问题如果第一个 CAS 成功而第二个 CAS 失败会发生什么如果其他线程在第一个和第二个 CAS 之间企图访问链表会发生什么 对于非复杂数据结构构建非阻塞算法的 “技巧” 是确保数据结构总处于一致的状态甚至包括在线程开始修改数据结构和它完成修改之间还要确保其他线程不仅能够判断出第一个线程已经完成了更新还是处在更新的中途还能够判断出如果第一个线程走向 AWOL完成更新还需要什么操作。如果线程发现了处在更新中途的数据结构它就可以 “帮助” 正在执行更新的线程完成更新然后再进行自己的操作。当第一个线程回来试图完成自己的更新时会发现不再需要了返回即可因为 CAS 会检测到帮助线程的干预在这种情况下是建设性的干预。 这种 “帮助邻居” 的要求对于让数据结构免受单个线程失败的影响是必需的。如果线程发现数据结构正处在被其他线程更新的中途然后就等候其他线程完成更新那么如果其他线程在操作中途失败这个线程就可能永远等候下去。即使不出现故障这种方式也会提供糟糕的性能因为新到达的线程必须放弃处理器导致上下文切换或者等到自己的时间片过期而这更糟。 清单 4 的 LinkedQueue 显示了 Michael-Scott 非阻塞队列算法的插入操作它是由 ConcurrentLinkedQueue 实现的 清单 4. Michael-Scott 非阻塞队列算法中的插入 public class LinkedQueue E {private static class Node E {final E item;final AtomicReferenceNodeE next;Node(E item, NodeE next) {this.item item;this.next new AtomicReferenceNodeE(next);}}private AtomicReferenceNodeE head new AtomicReferenceNodeE(new NodeE(null, null));private AtomicReferenceNodeE tail head;public boolean put(E item) {NodeE newNode new NodeE(item, null);while (true) {NodeE curTail tail.get();NodeE residue curTail.next.get();if (curTail tail.get()) {if (residue null) /* A */ {if (curTail.next.compareAndSet(null, newNode)) /* C */ {tail.compareAndSet(curTail, newNode) /* D */ ;return true;}} else {tail.compareAndSet(curTail, residue) /* B */;}}}}
} 像许多队列算法一样空队列只包含一个假节点。头指针总是指向假节点尾指针总指向最后一个节点或倒数第二个节点。图 1 演示了正常情况下有两个元素的队列 图 1. 有两个元素处在静止状态的队列 如 清单 4 所示插入一个元素涉及两个指针更新这两个更新都是通过 CAS 进行的从队列当前的最后节点C链接到新节点并把尾指针移动到新的最后一个节点D。如果第一步失败那么队列的状态不变插入线程会继续重试直到成功。一旦操作成功插入被当成生效其他线程就可以看到修改。还需要把尾指针移动到新节点的位置上但是这项工作可以看成是 “清理工作”因为任何处在这种情况下的线程都可以判断出是否需要这种清理也知道如何进行清理。 队列总是处于两种状态之一正常状态或称静止状态图 1 和 图 3或中间状态图 2。在插入操作之前和第二个 CASD成功之后队列处在静止状态在第一个 CASC成功之后队列处在中间状态。在静止状态时尾指针指向的链接节点的 next 字段总为 null而在中间状态时这个字段为非 null。任何线程通过比较 tail.next 是否为 null就可以判断出队列的状态这是让线程可以帮助其他线程 “完成” 操作的关键。 图 2. 处在插入中间状态的队列在新元素插入之后尾指针更新之前 插入操作在插入新元素A之前先检查队列是否处在中间状态如 清单 4 所示。如果是在中间状态那么肯定有其他线程已经处在元素插入的中途在步骤C和D之间。不必等候其他线程完成当前线程就可以 “帮助” 它完成操作把尾指针向前移动B。如果有必要它还会继续检查尾指针并向前移动指针直到队列处于静止状态这时它就可以开始自己的插入了。 第一个 CASC可能因为两个线程竞争访问队列当前的最后一个元素而失败在这种情况下没有发生修改失去 CAS 的线程会重新装入尾指针并再次尝试。如果第二个 CASD失败插入线程不需要重试 —— 因为其他线程已经在步骤B中替它完成了这个操作 图 3. 在尾指针更新后队列重新处在静止状态 幕后的非阻塞算法 如果深入 JVM 和操作系统会发现非阻塞算法无处不在。垃圾收集器使用非阻塞算法加快并发和平行的垃圾搜集调度器使用非阻塞算法有效地调度线程和进程实现内在锁。在 MustangJava 6.0中基于锁的 SynchronousQueue 算法被新的非阻塞版本代替。很少有开发人员会直接使用 SynchronousQueue但是通过 Executors.newCachedThreadPool() 工厂构建的线程池用它作为工作队列。比较缓存线程池性能的对比测试显示新的非阻塞同步队列实现提供了几乎是当前实现 3 倍的速度。在 Mustang 的后续版本代码名称为 Dolphin中已经规划了进一步的改进。 结束语 非阻塞算法要比基于锁的算法复杂得多。开发非阻塞算法是相当专业的训练而且要证明算法的正确也极为困难。但是在 Java 版本之间并发性能上的众多改进来自对非阻塞算法的采用而且随着并发性能变得越来越重要可以预见在 Java 平台的未来发行版中会使用更多的非阻塞算法。 本文来至 https://www.ibm.com/developerworks/cn/java/j-jtp04186/转载于:https://www.cnblogs.com/rinack/p/10037012.html
