作者归档

Java Fork Join 框架(三)实现

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

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

这个框架是由大约800行纯Java代码组成,主要的类是FJTaskRunner,它是java.lang.Thread的子类。FJTasks 自己仅仅维持一个关于结束状态的布尔值,所有其他的操作都是通过当前的工作线程来代理完成的。JFTaskRunnerGroup类用于创建工作线程,维护一些共享的状态(例如:所有工作线程的标示符,在偷取操作时需要),同时还要协调启动和关闭。

更多实现的细节文档可以在util.concurrent并发包中查看。这一节只着重讨论两类问题以及在实现这个框架的时候所形成的一些解决方案:支持高效的双端列表操作(push, pop 和 take), 并且当工作线程在尝试获取新的任务时维持偷取的协议。 阅读全文

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程序而言太笨重了。但是既然线程构成了很多其他的并发和并行编程的基础,完全消除这种代价或者为了这种方式而调整线程调度是不可能(或者说不切实际的)。

阅读全文

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.获取到。

Java Fork Join 框架

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

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

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++ 语言增加了细粒度任务支持,使其为新的和现有的软件增加并行性来充分发掘多处理器能力变得更加容易。

 

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变量的时候还有其他的限制。 阅读全文

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.

Java内存模型FAQ(七)同步会干些什么呢

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

译者:Alex

同步有几个方面的作用。最广为人知的就是互斥 ——一次只有一个线程能够获得一个监视器,因此,在一个监视器上面同步意味着一旦一个线程进入到监视器保护的同步块中,其他的线程都不能进入到同一个监视器保护的块中间,除非第一个线程退出了同步块。

阅读全文

Java内存模型FAQ(六)没有正确同步的含义是什么?

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

译者:Alex

没有正确同步的代码对于不同的人来说可能会有不同的理解。在Java内存模型这个语义环境下,我们谈到“没有正确同步”,我们的意思是:

  1. 一个线程中有一个对变量的写操作,
  2. 另外一个线程对同一个变量有读操作,
  3. 而且写操作和读操作没有通过同步来保证顺序。

当这些规则被违反的时候,我们就说在这个变量上有一个“数据竞争”(data race)。一个有数据竞争的程序就是一个没有正确同步的程序。

阅读全文

Java内存模型FAQ(五)旧的内存模型有什么问题?

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

译者:Alex

旧的内存模型中有几个严重的问题。这些问题很难理解,因此被广泛的违背。例如,旧的存储模型在许多情况下,不允许JVM发生各种重排序行为。旧的内存模型中让人产生困惑的因素造就了JSR-133规范的诞生。

阅读全文

Java内存模型FAQ(三)JSR133是什么?

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

译者:Alex

从1997年以来,人们不断发现Java语言规范的17章定义的Java内存模型中的一些严重的缺陷。这些缺陷会导致一些使人迷惑的行为(例如final字段会被观察到值的改变)和破坏编译器常见的优化能力。
阅读全文

return top