Archive for ‘ April, 2014

并发数据结构-1.4 池

原文链接译文链接,译者:huavben,校对:周可人

实现高效并发栈和队列的大部分挑战来自于一个被插入的元素可以被删除这一需求。并发池是一种支持插入和删除操作的数据结构,它允许删除操作移除任何一个已经被插入的,并且没有在随后被删除的元素。这样的弱需求提供了提高并发性能的机会。

一个高效的并发池可以使用任意静态一致的计数器来构建。在这样的并发池中,元素被置于数组当中,fetch-and-inc操作决定插入操作在哪个位置存储元素,同样的,fetch-and-inc操作决定删除操作在哪个位置获得元素。每一个数组元素都包含了一个表示满/空的比特位或者等效的机制,来表明在相应的位置,将要删除的元素已经存在。在这种策略下,使用combining tree,combining funnel,counting network,diffracting tree中的任何一个技术都可以并行化共享技术器,解决这一主要的瓶颈来创建出一个高吞吐量的共享并发池。此外,一个类似栈的池可以使用一个允许增加和减少操作的计数器来实现,然后利用以上技术中的一种来并行化.
Read more

JVM的重排序

感谢同事【沐剑】的投稿

重排序通常是编译器或运行时环境为了优化程序性能而采取的对指令进行重新排序执行的一种手段。重排序分为两类:编译期重排序运行期重排序,分别对应编译时和运行时环境。

在并发程序中,程序员会特别关注不同进程或线程之间的数据同步,特别是多个线程同时修改同一变量时,必须采取可靠的同步或其它措施保障数据被正确地修改,这里的一条重要原则是:不要假设指令执行的顺序,你无法预知不同线程之间的指令会以何种顺序执行。

但是在单线程程序中,通常我们容易假设指令是顺序执行的,否则可以想象程序会发生什么可怕的变化。理想的模型是:各种指令执行的顺序是唯一且有序的,这个顺序就是它们被编写在代码中的顺序,与处理器或其它因素无关,这种模型被称作顺序一致性模型,也是基于冯·诺依曼体系的模型。当然,这种假设本身是合理的,在实践中也鲜有异常发生,但事实上,没有哪个现代多处理器架构会采用这种模型,因为它是在是太低效了。而在编译优化和CPU流水线中,几乎都涉及到指令重排序。 Read more

并发数据结构-1.7 查找树

原文链接译文链接,译者:iDestiny,校对:周可人

任何查找树的并发实现都可以通过用一个独占锁保护来完成。通过使用读写锁对并发性能有一定提升,读写锁允许所有只读(查找)操作并发地执行,因为读操作是以共享模式持有锁,然而更新(插入或删除)操作持有独占模式的锁,从而排斥其他所有操作。如果更新操作比较少,这还能接受,但是只要有适量的更新操作,那么更新操作所持有的独占锁将产生线性的瓶颈,从而大大降低性能。通过使用细粒度的锁策略——比如每个节点一个锁,而不是整棵树使用同一个锁——这样我们进一步地提升了并发性能。
Read more

并发数据结构-1.6 哈希表

原文链接译文链接,译者:iDestiny,校对:周可人

典型可扩展的哈希表即一个可调整大小的桶数组(buckets), 每一个桶存放预期数量的元素,因此哈希表平均在常量时间内进行插入,删除,查询操作。哈希表调整大小的主要成本—–在于新旧桶(buckets)之间进行重新分配操作,该操作被分摊到所有表操作上,所以平均操作时间也是常量的。哈希表调整大小就是扩容,在实践中,哈希表仅需要增加数组大小即可。

Michael实现了一个可并发,不可扩展的哈希表(通过对哈希表中每个桶进行读写锁约束)。然而,为了保证元素数量增长时的性能,哈希表必须可扩展。
Read more

中断与性能

感谢同事【空蒙】的投稿

中断,会导致正在运行的CPU要停下手头的工作去响应,这需要工作任务的切换,就带来了我们熟知的上下文切换,而频繁上下文切换,是对系统性能的重要影响因素。

那怎么减少中断带来的影响呢?

现在CPU往往是多核,如16、32核,是否可以把中断绑定到其中一个CPU上,再把其他剩余的cpu用于应用的计算。因为之前是单核的原因,传统的很多做法是会把中断扔给cpu0处理,在linux下,可执行mpstat -P ALL 1,查看各个cpu上的中断情况。

Read more

Tomcat7.0.26的连接数控制bug的问题排查

感谢同事[空蒙]的投稿。

首先感谢@烈元一起排查此问题。今天发现线上一台机器,监控一直在告警,一看是健康检查不通过,就上去查看了下,首先自己curl了下应用的url,果然是超时没有响应,那就开始按顺序排查了:

1、 load非常低,2、gc也正常,3、线程上也没死锁,4、日志一切正常。那是什么情况呢,不能忘记网络啊。果然,netstat命令一把,结果如下:

TIME_WAIT 68
CLOSE_WAIT 194
ESTABLISHED 3941
SYN_RECV 100

问题出来了,SYN_RECV竟然达到100个,正常情况下,半连接的请求应该是很小的。而且我们机器是内部的,不是lvs,不太会有半连接攻击,怎么可能达到这么大呢?

Read more

更快的AtomicInteger

感谢同事【空蒙】的投稿

之前看了java8的longadder实现,最近又看到一篇文章介绍longadder实现的。其实现思路也是分段,最后需要get的时候,再进行sum计算。其核心思路就是减少并发,但之前老的Atomic,难道就没有提升的空间了吗?昨晚进行了一次测试。测试代码如下:

Read more

聊聊并发(十)生产者消费者模式

本文首发于InfoQ   作者:方腾飞  校对:张龙

在并发编程中使用生产者和消费者模式能够解决绝大多数并发问题。该模式通过平衡生产线程和消费线程的工作能力来提高程序的整体处理数据的速度。

为什么要使用生产者和消费者模式

在线程世界里,生产者就是生产数据的线程,消费者就是消费数据的线程。在多线程开发当中,如果生产者处理速度很快,而消费者处理速度很慢,那么生产者就必须等待消费者处理完,才能继续生产数据。同样的道理,如果消费者的处理能力大于生产者,那么消费者就必须等待生产者。为了解决这种生产消费能力不均衡的问题,所以便有了生产者和消费者模式。

什么是生产者消费者模式

生产者消费者模式是通过一个容器来解决生产者和消费者的强耦合问题。生产者和消费者彼此之间不直接通讯,而通过阻塞队列来进行通讯,所以生产者生产完数据之后不用等待消费者处理,直接扔给阻塞队列,消费者不找生产者要数据,而是直接从阻塞队列里取,阻塞队列就相当于一个缓冲区,平衡了生产者和消费者的处理能力。
Read more

Java8之使用新JS解释器Nashorn编译Lambda表达式

Nashron.mainImage.fw_
原文链接 作者:Tal Weiss  CEO of Takipi  译者:踏雁寻花,xbkaishui  校对:方腾飞

在最近的一篇文章中,我了解了一下Java8和Scala是如何实现 Lambda 表达式的。正如我们所知道的,Java8不仅对javac编辑器做了很大改进,它还加入了一个全新的项目—Nashorn。这个新的解释器将会代替Java现有的Rhino解释器。据说它执行JavaScript的速度非常之快,就像世界上最快的跑车 V8s,所以,我觉得现在很有必要打开Nashorn源码,看看它是如何编译 Lambda 表达式的(着重于Java 和 Scala的对比)。

Read more

自己动手写GC

原文链接译文链接,原文作者: Robert Nystrom,译者:有孚

当事情多得我喘不过气来的时候,我会出现一种异常的反应,就是找点别的事做,就能摆脱烦恼了。通常我会自己写一些独立的小程序。

有一天早上,我正在写书,工作,还要为Strang Loop准备的分享,这些东西让我感到快崩溃了,突然间我想到,“我要写一个垃圾回收程序”。

是的,我知道这听起来有点疯狂。不过你可以把我这个神经的想法当成是一堂编程语言基础的免费教程。通过百来行普通的C代码,我实现了一个标记删除的收集器,你懂的,它的确能回收内存。

在程序开发领域,垃圾回收就像一片鲨鱼出没的水域,不过在本文中,这只是个儿童池,你可以随意玩耍。(说不定还是会有鲨鱼,不过至少水浅多了不是?)

Read more

Java中的5种同步辅助类

原文地址 译者:何一昕 校对:方腾飞

概述

当你使用synchronized关键字的时候,是通过互斥器来保障线程安全以及对共享资源的同步访问。线程间也经常需要更进一步的协调执行,来完成复杂的并发任务,比如wait/notify模式就是一种在多线程环境下的协调执行机制。

通过API来获取和释放锁(使用互斥器)或者调用wait/notify等方法都是底层调用的方式。进一步来说,有必要为线程同步创建更高层次的抽象。通常用到的同步辅助类,就是对2个或多个线程间的同步活动机制做进一步封装,其内部原理是通过使用现有的底层API来实现复杂的线程间的协调。

Read more

并发数据结构- 1.8 优先队列&1.9 总结

原文链接译文链接,译者:郭振斌,校对:周可人

1.8 优先队列

并发的优先队列是一个可线性化到顺序优先队列的数据结构,能够通过常用的优先队列语义提供insert和delete-min操作。

基于堆的优先队列

许多文献中提到的并发优先队列结构,其实是本书前面提到的可线性化堆结构。再一次的,这种结构的基本思想是在个别堆节点上使用细粒度锁,使线程在并行下也能够尽可能的访问数据结构的不同部分。设计这种并发堆的关键问题,在于传统自底向上的insert和自顶向下的delete-min操作有可能造成死锁。Biswas和Brown[17]提出基于锁的堆算法,通过专门的“清理”线程解决死锁。Rao和Kumar[116]建议通过一个将insert和delete-min操作都自顶向下处理的算法[17]来解决问题。Ayani[11]在他们算法基础上做了改善,即通过一种方式在堆两侧进行连续插入。Jones[68]提出一种基于类似斜堆的方案[116]。
Read more

关于同步操作实现机制的一则注解

原文地址译文地址,译者:南约克郡,校对:郑旭东

多数硬件对数据操作与同步操作并不做区分,不同硬件平台的并发内存访问的语义也与我们这里讨论的有较大差别。对于熟悉硬件内存模型的读者,我们对于如何组织内存操作和同步访问的介绍会基于一种假定的硬件平台(类似最近的ARM处理器,但使用Itanium汇编语法)。

首先要说明一点的是我们这种描述并不精确,因为我们缺乏熟悉编译器的人,并且那也不在我们讨论编程模型的范围内。我们希望它能帮助读者理解本文后续章节而提前给出一个概念. Read more

Storm入门之第7章使用非JVM语言开发

本文翻译自《Getting Started With Storm》译者:吴京润    编辑:郭蕾 方腾飞

有时候你可能想使用不是基于JVM的语言开发一个Storm工程,你可能更喜欢使用别的语言或者想使用用某种语言编写的库。

Storm是用Java实现的,你看到的所有这本书中的spoutbolt都是用java编写的。那么有可能使用像Python、Ruby、或者JavaScript这样的语言编写spoutbolt吗?答案是当然

 

可以!可以使用多语言协议达到这一目的。

多语言协议是Storm实现的一种特殊的协议,它使用标准输入输出作为spoutbolt进程间的通讯通道。消息以JSON格式或纯文本格式在通道中传递。

我们看一个用非JVM语言开发spoutbolt的简单例子。在这个例子中有一个spout产生从1到10,000的数字,一个bolt过滤素数,二者都用PHP实现。

Read more

并发数据结构-1.1.4 复杂度测量&1.1.5 正确性

原文链接译文链接,译者:张军,校对:周可人

1.1.4 复杂度测量

一个被广泛研究的方向是在理想化模型,如并行随机存取机上分析并发数据结构和算法的渐进复杂度[35, 122, 135]。然而,很少有将这些数据结构放在一个真实的多处理器上进行建模的。这里有多种原因,大部分原因跟系统硬件架构与线程异步执行的相互作用有关。想想组合树(combining tree)的例子,虽然我们能通过计算(指令数)得到O(P/logP)的加速比,但这无法反映在实证研究中[52, 129]。真实世界的行为是被上述其他因素支配的,如竞争开销,缓存行为,同步操作(例如CAS)开销,请求到达率,退避延时,数据结构在内存中的布局等等。这些因素很难用一个精确的涵盖目前所有架构的模型来量化。 Read more

return top