并发译文 ’ 目录归档

Java内存模型Cookbook(三)多处理器

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

作者:Doug Lea 翻译:古圣昌   校对:欧振聪,方腾飞

  1. 指令重排
  2. 内存屏障
  3. 多处理器
  4. 指南

本文总结了在多处理器(MPs)中常用的的处理器列表,处理器相关的信息都可以从链接指向的文档中得到(一些网站需要通过注册才能得到相应的手册)。当然,这不是一个完全详细的列表,但已经包括了我所知道的在当前或者将来Java实现中所使用的多核处理器。下面所述的关于处理器的列表和内容也不一定权威。我只是总结一下我所阅读过的文档,但是这些文档也有可能是被我误解了,一些参考手册也没有把Java内存模型(JMM)相关的内容阐述清楚,所以请协助我把本文变得更准确。
阅读全文

同步和Java内存模型 (三)可见性

原文:http://gee.cs.oswego.edu/dl/cpj/jmm.html 第三章
作者:Doug Lea 译者:程晓明 校对:方腾飞

只有在下列情况时,一个线程对字段的修改才能确保对另一个线程可见:

一个写线程释放一个锁之后,另一个读线程随后获取了同一个锁。本质上,线程释放锁时会将强制刷新工作内存中的脏数据到主内存中,获取一个锁将强制线程装载(或重新装载)字段的值。锁提供对一个同步方法或块的互斥性执行,线程执行获取锁和释放锁时,所有对字段的访问的内存效果都是已定义的。

注意同步的双重含义:锁提供高级同步协议,同时在线程执行同步方法或块时,内存系统(有时通过内存屏障指令)保证值的一致性。这说明,与顺序程序设计相比较,并发程序设计与分布式程序设计更加类似。同步的第二个特性可以视为一种机制:一个线程在运行已同步方法时,它将发送和/或接收其他线程在同步方法中对变量所做的修改。从这一点来说,使用锁和发送消息仅仅是语法不同而已。

阅读全文

看动画学并发编程

Java提供了并发库简化了并发编程,但这是很难用可视化的方式来学习。 Java Concurrent Animated项目用一系列的动画来演示每个java并发库组件和代码。看动画学并发编程

Java Concurrent Animated程序,为每一个并发组件的学习点,开发一个演示动画的程序,并配合代码和一张PPT进行知识点的说明。

官方网址是:http://sourceforge.net/projects/javaconcurrenta/

下载地址:http://sourceforge.net/projects/javaconcurrenta/files/latest/download?source=files

同步和Java内存模型(五)Volatile

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

作者:Doug lea 译者:杜建雄  校对者:方腾飞

Volatile

从原子性,可见性和有序性的角度分析,声明为volatile字段的作用相当于一个类通过get/set同步方法保护普通字段,如下:

[code lang=”java”]
final class VFloat {
private float value;

final synchronized void set(float f) { value = f; }
final synchronized float get() { return value; }
}
[/code]

与使用synchronized相比,声明一个volatile字段的区别在于没有涉及到锁操作。但特别的是对volatile字段进行“++”这样的读写操作不会被当做原子操作执行。

另外,有序性和可见性仅对volatile字段进行一次读取或更新操作起作用。声明一个引用变量为volatile,不能保证通过该引用变量访问到的非volatile变量的可见性。同理,声明一个数组变量为volatile不能确保数组内元素的可见性。volatile的特性不能在数组内传递,因为数组里的元素不能被声明为volatile。

阅读全文

Happens before

原文:http://www.cs.umd.edu/class/fall2010/cmsc433/lectures/happens-before.txt

译者:丁一

“Happens before”是由Leslie Lamport引入的用来描述程序事件的一种偏序关系。

将多线程的执行看作是事件E的轨迹R,定义如下(轨迹只是一种次序):

Events E ::= start(T)
	  |  end(T)
	  |  read(T,x,v)
  	|  write(T,x,v)
	  |  spawn(T1,T2)
	  |  join(T1,T2)
	  |  lock(T,x)
	  |  unlock(T,x)

这里T是一个线程标识符,x是一个变量,v是一个值。read(T,x,v)事件表示线程T从变量x中读出值v。同时假定轨迹R是结构良好的,即要求在R中,线程T的第一个事件必须是start(T)。在end(T)之后不再有线程T相关的事件。
阅读全文

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

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

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

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

[code lang=”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));
}
}
[/code]

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

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

阅读全文

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

阅读全文

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

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

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

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

Java Fork Join框架 (二) 简介

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

作者:Doug Lea
译者:Alex

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

[code lang=”java”]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
}
}[/code]

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内存模型

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

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

目录

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

同步和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位,全部都是由单个线程写入的)。但是,如下面(译注:指可见性章节)将要看到的,原子性不能确保你获得的是任意线程写入之后的最新值。 因此,原子性保证通常对并发程序设计的影响很小。

阅读全文

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

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

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

有序性 

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

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

 
阅读全文

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

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

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

阅读全文

return top