聊聊并发(六)ConcurrentLinkedQueue的实现原理分析

本文是作者原创,首发于InfoQ:http://www.infoq.com/cn/articles/ConcurrentLinkedQueue

1.    引言

在并发编程中我们有时候需要使用线程安全的队列。如果我们要实现一个线程安全的队列有两种实现方式一种是使用阻塞算法,另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁(入队和出队用同一把锁)或两个锁(入队和出队用不同的锁)等方式来实现,而非阻塞的实现方式则可以使用循环CAS的方式来实现,本文让我们一起来研究下Doug Lea是如何使用非阻塞的方式来实现线程安全队列ConcurrentLinkedQueue的,相信从大师身上我们能学到不少并发编程的技巧。
阅读全文

看动画学并发编程

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同步方法保护普通字段,如下:

final class VFloat {
    private float value;

    final synchronized void set(float f) { value = f; }
    final synchronized float get()       { return value; }
}

与使用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类,该类中并没有使用任何的同步。

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)。

阅读全文

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

阅读全文

ConcurrentHashMap能完全替代HashTable吗?

回答:hash table虽然性能上不如ConcurrentHashMap,但并不能完全被取代,两者的迭代器的一致性不同的,hash table的迭代器是强一致性的,而concurrenthashmap是弱一致的。 ConcurrentHashMap的get,clear,iterator 都是弱一致性的。 Doug Lea 也将这个判断留给用户自己决定是否使用ConcurrentHashMap。

 

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

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

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

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

CopyOnWriteArrayList类set方法疑惑?

在淘宝内网有位同事提了一个很好的问题,大家能否帮忙解答下?

在CopyOnWriteArrayList类的set方法中有一段setArray(elements)代码,实际上这段代码并未对elements做任何改动,实现的volatile语意并不对CopyOnWriteArrayList实例产生任何影响,为什么还是要保留这行语句?见以下代码红体部分:

    /** The array, accessed only via getArray/setArray. */
    private volatile transient Object[] array;

    /**
     * Replaces the element at the specified position in this list with the
     * specified element.
     *
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            E oldValue = get(elements, index);

            if (oldValue != element) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

    /**
     * Sets the array.
     */
    final void setArray(Object[] a) {
        array = a;
    }

    /**
     * Gets the array.  Non-private so as to also be accessible
     * from CopyOnWriteArraySet class.
     */
    final Object[] getArray() {
        return array;
    }

这个问题在concurrency-interest邮件列表里也有人讨论:

http://cs.oswego.edu/pipermail/concurrency-interest/2010-February/006886.html

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

原文: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字段的操作仍维持相对有序。

 
阅读全文

return top