并发译文 ’ 目录归档

同步与Java内存模型(一)序言

原文:http://gee.cs.oswego.edu/dl/cpj/jmm.html

作者:Doug Lea 译者:萧欢  校对:丁一,方腾飞

先来看如下这个简单的Java类,该类中并没有使用任何的同步。

final class SetCheck {
private int  a = 0;
private long b = 0;

void set() {
a =  1;
b = -1;
}

boolean check() {
return ((b ==  0) ||
(b == -1 && a == 1));
}
}

如果是在一个串行执行的语言中,执行SetCheck类中的check方法永远不会返回false,即使编译器,运行时和计算机硬件并没有按照你所期望的逻辑来处理这段程序,该方法依然不会返回false。在程序执行过程中,下面这些你所不能预料的行为都是可能发生的:

  • 编译器可能会进行指令重排序,所以b变量的赋值操作可能先于a变量。如果是一个内联方法,编译器可能更甚一步将该方法的指令与其他语句进行重排序。
  • 处理器可能会对语句所对应的机器指令进行重排序之后再执行,甚至并发地去执行。
  • 
内存系统(由高速缓存控制单元组成)可能会对变量所对应的内存单元的写操作指令进行重排序。重排之后的写操作可能会对其他的计算/内存操作造成覆盖。
  • 编译器,处理器以及内存系统可能会让两条语句的机器指令交错。比如在32位机器上,b变量的高位字节先被写入,然后是a变量,紧接着才会是b变量的低位字节。
  • 编译器,处理器以及内存系统可能会导致代表两个变量的内存单元在(如果有的话)连续的check调用(如果有的话)之后的某个时刻才更新,而以这种方式保存相应的值(如在CPU寄存器中)仍会得到预期的结果(check永远不会返回false)。

阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 同步与Java内存模型(一)序言

Java Fork Join框架 (三) 设计

原文 http://gee.cs.oswego.edu/dl/papers/fj.pdf

作者:Doug Lea
译者:Alex

Fork/Join程序可以在任何支持以下特性的框架之上运行:框架能够让构建的子任务并行执行,并且拥有一种等待子任务运行结束的机制。然而,java.lang.Thread类(同时也包括POSIX pthreads, 这些也是Java线程所基于的基础)对Fork/Join程序来说并不是最优的选择:

  • Fork/Join 任务对同步和管理有简单的和常规的需求。相对于常规的线程来说,fork/join任务所展示的计算布局将会带来更加灵活的调度策略。例如,fork/join任务除了等待子任务外,其他情况下是不需要阻塞的。因此传统的用于跟踪记录阻塞线程的代价在这种情况下实际上是一种浪费。
  • 对于一个合理的基础任务粒度来说,构建和管理一个线程的代价甚至可以比任务执行本身所花费的代价更大。尽管粒度是应该随着应用程序在不同特定平台上运行而做出相应调整的。但是超过线程开销的极端粗粒度会限制并行的发挥。

简而言之,Java标准的线程框架对fork/join程序而言太笨重了。但是既然线程构成了很多其他的并发和并行编程的基础,完全消除这种代价或者为了这种方式而调整线程调度是不可能(或者说不切实际的)。

阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Java Fork Join框架 (三) 设计

如何显示海量用户网站的积分排名?

某海量用户网站,用户拥有积分,积分可能会在使用过程中随时更新。现在要为该网站设计一种算法,在每次用户登录时显示其当前积分排名。用户最大规模为2亿;积分为非负整数,且小于100万。

回答1:用map做的,key是分数,value是人数。查排名的失火遍历map里比他积分大key取出value的sum一下。

更多方法参考:http://www.ituring.com.cn/article/1169

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 如何显示海量用户网站的积分排名?

Java Fork Join框架 (二) 简介

原文 http://gee.cs.oswego.edu/dl/papers/fj.pdf

作者:Doug Lea
译者:Alex

Fork/Join并行方式是获取良好的并行计算性能的一种最简单同时也是最有效的设计技术。Fork/Join并行算法是我们所熟悉的分治算法的并行版本,典型的用法如下:

Result solve(Problem problem) {
	if (problem is small) 
		directly solve problem
		else {
			split problem into independent parts
			fork new subtasks to solve each part
			join all subtasks
			compose result from subresults
		}
}

Fork操作将会启动一个新的并行fork/join子任务。Join操作会一直等待直到所有的子任务都结束。Fork/Join算法,如同其他分治算法一样,总是会递归的、反复的划分子任务,直到这些子任务可以用足够简单的、短小的顺序方法来执行。

一些相关的编程技术和实例在Java并发编程——设计原则与模式 第二版 [7] 4.4章节中已经讨论过。这篇论文将讨论FJTask的设计(第2节)、实现(第3节)以及性能(第4节),它是一个支持并行编程方式的Java框架。FJTask 作为util.concurrent软件包的一部分,目前可以在http://gee.cs.oswego.edu.获取到。

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Java Fork Join框架 (二) 简介

Java Fork Join 框架

原文地址 作者:Doug Lea  译者:Alex

1. 摘要
2. 简介
3. 设计
4. 实现
5. 性能
6. 结论
7. 致谢
8. 参考文献

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Java Fork Join 框架

Java Fork Join框架 (一) 摘要

原文 http://gee.cs.oswego.edu/dl/papers/fj.pdf

作者:Doug Lea  译者:Alex  校对:方腾飞

这篇论文描述了Fork/Join框架的设计、实现以及性能,这个框架通过(递归的)把问题划分为子任务,然后并行的执行这些子任务,等所有的子任务都结束的时候,再合并最终结果的这种方式来支持并行计算编程。总体的设计参考了为Cilk(校注1:英特尔Cilk 语言)设计的work-stealing框架。就设计层面来说主要是围绕如何高效的去构建和管理任务队列以及工作线程来展开的。性能测试的数据显示良好的并行计算程序将会提升大部分应用,同时也暗示了一些潜在的可以提升的空间。

校注1:Cilk是英特尔Cilk 语言。英特尔C++ 编辑器的新功能 Cilk 语言扩展技术,为 C/C++ 语言增加了细粒度任务支持,使其为新的和现有的软件增加并行性来充分发掘多处理器能力变得更加容易。

 

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Java Fork Join框架 (一) 摘要

同步和Java内存模型

原文:http://gee.cs.oswego.edu/dl/cpj/jmm.html

作者:Doug Lea 译者:程晓明,萧欢,杜建雄  校对:方腾飞,丁一,欧振聪

目录

  1. 引言
  2. 原子性
  3. 可见性
  4. 有序性
  5. Volatile

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 同步和Java内存模型

同步和Java内存模型 (二)原子性

原文:http://gee.cs.oswego.edu/dl/cpj/jmm.html 第二章

作者:Doug Lea 译者:程晓明  校对:方腾飞

除了long型字段和double型字段外,java内存模型确保访问任意类型字段所对应的内存单元都是原子的。这包括引用其它对象的引用类型的字段。此外,volatile long 和volatile double也具有原子性 。(虽然java内存模型不保证non-volatile long 和 non-volatile double的原子性,当然它们在某些场合也具有原子性。)(译注:non-volatile long在64位JVM,OS,CPU下具有原子性)

当在一个表达式中使用一个non-long或者non-double型字段时,原子性可以确保你将获得这个字段的初始值或者某个线程对这个字段写入之后的值;但不会是两个或更多线程在同一时间对这个字段写入之后产生混乱的结果值(即原子性可以确保,获取到的结果值所对应的所有bit位,全部都是由单个线程写入的)。但是,如下面(译注:指可见性章节)将要看到的,原子性不能确保你获得的是任意线程写入之后的最新值。 因此,原子性保证通常对并发程序设计的影响很小。

阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 同步和Java内存模型 (二)原子性

同步和Java内存模型(四)有序性

原文链接: http://gee.cs.oswego.edu/dl/cpj/jmm.html

作者:Doug lea 译者:杜建雄  校对者:欧振聪,方腾飞

有序性 

有序性规则表现在以下两种场景: 线程内和线程间

  •  从某个线程的角度看方法的执行,指令会按照一种叫“串行”(as-if-serial)的方式执行,此种方式已经应用于顺序编程语言。
  •  这个线程“观察”到其他线程并发地执行非同步的代码时,任何代码都有可能交叉执行。唯一起作用的约束是:对于同步方法,同步块以及volatile字段的操作仍维持相对有序。

 
阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 同步和Java内存模型(四)有序性

Java内存模型FAQ(十三)为什么我需要关注java内存模型

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#conclusion
译者:Alex

为什么你需要关注java内存模型?并发程序的bug非常难找。它们经常不会在测试中发生,而是直到你的程序运行在高负荷的情况下才发生,非常难于重现和跟踪。你需要花费更多的努力提前保证你的程序是正确同步的。这不容易,但是它比调试一个没有正确同步的程序要容易的多。

阅读全文

Java内存模型FAQ(十二)如果我需要写一个VM,我需要做些什么

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#vmwriters
译者:Alex

参见:http://gee.cs.oswego.edu/dl/jmm/cookbook.html (译文参见:JMM Cookbook)
阅读全文

Java内存模型FAQ(十一)新的内存模型是否修复了双重锁检查问题?

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#dcl
译者:Alex

臭名昭著的双重锁检查(也叫多线程单例模式)是一个骗人的把戏,它用来支持lazy初始化,同时避免过度使用同步。在非常早的JVM中,同步非常慢,开发人员非常希望删掉它。 阅读全文

Java内存模型FAQ(十)volatile是干什么用的

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html#volatile
译者:Alex

Volatile字段是用于线程间通讯的特殊字段。每次读volatile字段都会看到其它线程写入该字段的最新值;实际上,程序员之所以要定义volatile字段是因为在某些情况下由于缓存和重排序所看到的陈旧的变量值是不可接受的。编译器和运行时禁止在寄存器里面分配它们。它们还必须保证,在它们写好之后,它们被从缓冲区刷新到主存中,因此,它们立即能够对其他线程可见。相同地,在读取一个volatile字段之前,缓冲区必须失效,因为值是存在于主存中而不是本地处理器缓冲区。在重排序访问volatile变量的时候还有其他的限制。 阅读全文

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Java内存模型FAQ(十)volatile是干什么用的

Java内存模型FAQ(九)在新的Java内存模型中,final字段是如何工作的

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html 第九章
译者:Alex

一个对象的final字段值是在它的构造方法里面设置的。假设对象被正确的构造了,一旦对象被构造,在构造方法里面设置给final字段的的值在没有同步的情况下对所有其他的线程都会可见。另外,引用这些final字段的对象或数组都将会看到final字段的最新值。 阅读全文

Java内存模型FAQ(八)Final字段如何改变它们的值

原文:http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html 第八章

译者:Alex

我们可以通过分析String类的实现具体细节来展示一个final变量是如何可以改变的。

String对象包含了三个字段:一个character数组,一个数组的offset和一个length。实现String类的基本原理为:它不仅仅拥有character数组,而且为了避免多余的对象分配和拷贝,多个String和StringBuffer对象都会共享相同的character数组。因此,String.substring()方法能够通过改变length和offset,而共享原始的character数组来创建一个新的String。对一个String来说,这些字段都是final型的字段。

String s1 = "/usr/tmp";
String s2 = s1.substring(4); 

字符串s2的offset的值为4,length的值为4。但是,在旧的内存模型下,对其他线程来说,看到offset拥有默认的值0是可能的,而且,稍后一点时间会看到正确的值4,好像字符串的值从“/usr”变成了“/tmp”一样。

旧的Java内存模型允许这些行为,部分JVM已经展现出这样的行为了。在新的Java内存模型里面,这些是非法的。

原文

How can final fields appear to change their values?

One of the best examples of how final fields’ values can be seen to change involves one particular implementation of the String class.

String can be implemented as an object with three fields — a character array, an offset into that array, and a length. The rationale for implementing String this way, instead of having only the character array, is that it lets multiple String and StringBufferobjects share the same character array and avoid additional object allocation and copying. So, for example, the method String.substring() can be implemented by creating a new string which shares the same character array with the original String and merely differs in the length and offset fields. For a String, these fields are all final fields.

String s1 = "/usr/tmp";
String s2 = s1.substring(4); 

The string s2 will have an offset of 4 and a length of 4. But, under the old model, it was possible for another thread to see the offset as having the default value of 0, and then later see the correct value of 4, it will appear as if the string “/usr” changes to “/tmp”.

The original Java Memory Model allowed this behavior; several JVMs have exhibited this behavior. The new Java Memory Model makes this illegal.

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: Java内存模型FAQ(八)Final字段如何改变它们的值

return top