分享
 
 
 

Java 理论与实践: 非阻塞算法简介

王朝java/jsp·作者佚名  2008-05-31
窄屏简体版  字體: |||超大  

java™ 5.0 第一次让使用 Java 语言开发非阻塞算法成为可能,java.util.concurrent 包充分地利用了这个功能。非阻塞算法属于并发算法,它们可以安全地派生它们的线程,不通过锁定派生,而是通过低级的原子性的硬件原生形式 —— 例如比较和交换。非阻塞算法的设计与实现极为困难,但是它们能够提供更好的吞吐率,对生存问题(例如死锁和优先级反转)也能提供更好的防御。在这期的 Java 理论与实践 中,并发性大师 Brian Goetz 演示了几种比较简单的非阻塞算法的工作方式。

在不只一个线程访问一个互斥的变量时,所有线程都必须使用同步,否则就可能会发生一些非常糟糕的事情。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 不成功可能不得不重做。非阻塞算法通常叫作乐观算法,因为它们继续操作的假设是不会有干扰。假如发现干扰,就会回退并重试。在计数器的示例中,冒险的步骤是递增 —— 它检索旧值并在旧值上加一,希望在计算更新期间值不会变化。假如它的希望落空,就会再次检索值,并重做递增计算。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有