Dissecting the Disruptor: Demystifying Memory Barriers

原文地址:http://mechanitis.blogspot.com/2011/08/dissecting-disruptor-why-its-so-fast.html (因有墙,移到墙内)

My recent slow-down in posting is because I’ve been trying to write a post explaining memory barriersand their applicability in the Disruptor. The problem is, no matter how much I read and no matter how many times I ask the ever-patient Martin and Mike questions trying to clarify some point, I just don’t intuitively grasp the subject. I guess I don’t have the deep background knowledge required to fully understand.

So, rather than make an idiot of myself trying to explain something I don’t really get, I’m going to try and cover, at an abstract / massive-simplification level, what I do understand in the area.  Martin has written a post going into memory barriers in some detail, so hopefully I can get away with skimming the subject.

Read more

Dissecting the Disruptor: Why it’s so fast (part two) – Magic cache line padding

原文地址:http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-why-its-so-fast_22.html(因有墙移到墙内)

We mention the phrase Mechanical Sympathy quite a lot, in fact it’s even Martin’s blog title.  It’s about understanding how the underlying hardware operates and programming in a way that works with that, not against it.

We get a number of comments and questions about the mysterious cache line padding in theRingBuffer, and I referred to it in the last post.  Since this lends itself to pretty pictures, it’s the next thing I thought I would tackle.
Read more

Dissecting the Disruptor: Why it’s so fast (part one) – Locks Are Bad

原文地址:http://mechanitis.blogspot.com/2011/07/dissecting-disruptor-why-its-so-fast.html(因前方有墙,所以我移到墙内)

Martin Fowler has written a really good article describing not only the Disruptor, but also how it fits into the architecture at LMAX.  This gives some of the context that has been missing so far, but the most frequently asked question is still “What is the Disruptor?”.

I’m working up to answering that.  I’m currently on question number two: “Why is it so fast?”.

 

These questions do go hand in hand, however, because I can’t talk about why it’s fast without saying what it does, and I can’t talk about what it is without saying why it is that way.

So I’m trapped in a circular dependency.  A circular dependency of blogging.

To break the dependency, I’m going to answer question one with the simplest answer, and with any luck I’ll come back to it in a later post if it still needs explanation: the Disruptor is a way to pass information between threads.
Read more

并发译文翻译计划(二)

Doug Lea 的文献

  1. Synchronizer Framework  译者:ClarenceAu (已翻译完成,在校对)
  2. Fork/Join  译者:Alex(陆续发表中)
  3. Java Concurrency Constructs 译者:萧欢(已翻译完成)
  4. Cancellation 译者:丁一  (已翻译完成)

以下文章来自:https://code.google.com/p/disruptor/wiki/BlogsAndArticles

如何使用Disruptor

  1. What’s so special about a ring buffer? – A summary by Trisha of the data structure at the heart of the Disruptor patter, how it’s implemented and what’s so great about it. (译者:淘宝-欧立勇)
  2. How do I read from a ring buffer? – Trisha gives an overview of the Consumer and ConsumerBarrier, which allows you to read stuff off the ring buffer.(译者:古圣昌)
  3. Writing to the ring buffer – The third piece from Trisha explaining how to write to the ring buffer, and how it avoids wrapping.(译者:长源)
  4. Lock-free publishing – Danny outlines the concepts behind putting items into the ring buffer.(译者:行知)
  5. DSL for wiring up the Disruptor – Adrian came up with a cunning way to configure your Disruptor(译者:杨帆)
  6. Disruptor wizard now part of the Disruptor – Adrian’s wizard now makes it easy to configure your very own Disruptor straight out of the box (译者:杨帆)
  7. Disruptor version 2.0 – Trisha outlines the cosmetic changes to the Disruptor in version 2.0.(译者:杨帆)
  8. Sharing Data Among Threads Without Contention – An updated and summarised version of Trisha’s blogs in Oracle’s Java Magazine.(译者:同杰)

Disruptor为什么这么快

  1. Locks Are Bad – Trisha gives some basic concurrency background and explains why locks are evil. (译者:nick,潘曦,已经翻译完成)
  2. Magic cache line padding – An explanation around why the odd cache line padding variables are required, by Trisha.(译者:方腾飞,已经翻译完)
  3. Demystifying Memory Barriers – Trisha attempts to explain why memory barriers are important in the Disruptor. (译者:杜建雄)

其他人写的Disruptor文章

  1. LMAX 架构  by Martin Fowler (已翻译)
  2. Processing 1m TPS with the Axon Framework using the Disruptor.(译者,程晓明)

有兴趣的同学可以一起参与,有什么其他并发文献希望我们翻译的也可以通过留言告知我们。

如何翻译

  1. 你可从以上几篇文章中挑选某一篇进行翻译,翻译时间最好是一个星期以内,翻译前请发邮件到main_shorttime(AT)163.com告诉我你要翻译的文章和预计完成时间。
  2. 译者署名的顺序由翻译的字数确定。
  3. 与其他译者交叉校对,互相讨论翻译与技术问题。
  4. 提交翻译:在并发编程网用QQ登陆,然后发布译文。

注意事项

  1. 本文档的传播是基于学习研究而非商业,因此翻译纯属兴趣和分享精神。
  2. 对译者的要求,因为我们是出于学习和研究目的,所以对译者没有很高的要求,只要你只要你对并发编程感兴趣,并且愿意用心来翻译文章,翻译完的文章首先自己能读明白就行,放心我们会进行校对。

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

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

1.    引言

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

看动画学并发编程

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。

Read more

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相关的事件。
Read more

同步与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)。

Read more

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

Read more

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. 参考文献

return top