星期日, 六月 03, 2007

多线程环境下的Observer pattern

在“The Problem with Threads"论文中提到的用来抨击线程模型的实例。懒得说了,看代码直接:
public class ValueHolder{
private List listeners = new LinkedList();
private int value;

public interface Listener{
public void valueChanged(int newValue);
}

public void addListener(Listener listener){
listeners.add(listener);
}

public void setValue(int newValue){
value = newValue;
Iterator i = copyOfListeners.iterator();
while(i.hasNext()){
((Listener)i.next()).valueChanged(newValue);
}
}
}
以上代码存在问题是多线程环境下对listeners的竞争访问。既然如此,那在addListener和setValue方法前添加synchronzied。好了些,不过有死锁的可能,这主要是因为你不知道别人在valueChanged方法中会做什么,在调用这个方法时,你手中已经紧紧握住一把锁了。继续改进:
public class ValueHolder{
private List listeners = new LinkedList();
private int value;

public interface Listener{
public void valueChanged(int newValue);
}

public synchronized void addListener(Listener listener){
listeners.add(listener);
}

public void setValue(int newValue){
List copyOfListeners;

synchronized(this){
value = newValue;
copyOfListeners = new LinkedList(listeners);
}

Iterator i = copyOfListeners.iterator();
while(i.hasNext()){
((Listener)i.next()).valueChanged(newValue);
}
}
}
此种实现跟JDK源码util包中Observable实现类似,把竞争访问和死锁都排除了。不过此种实现仍存在问题。比如线程A和线程B依次调用setValue,然后线程B抢在线程A之前通知大家。这样就搞得大家认为ValueHolder中最终value值是线程A设置的值,而实际上是线程B设置的值。没办法,只能继续改进。
public class ValueHolder{
private List listeners = new LinkedList();
private int value;
private int seqnum = 0;
private int globalNum = 1;

public interface Listener{
public void valueChanged(int newValue);
}

public synchronized void addListener(Listener listener){
listeners.add(listener);
}

public void setValue(int newValue){
List copyOfListeners;
int localSeqnum;

synchronized(this){
value = newValue;
copyOfListeners = new LinkedList(listeners);
seqnum++;
localSeqnum = seqnum;
}
while(localSeqnum != globalNum){
//Only to wait
}
Iterator i = copyOfListeners.iterator();
while(i.hasNext()){
((Listener)i.next()).valueChanged(newValue);
}
globalNum++;
}
}
以上是我提供的一个实现,不知还有没有问题。关键一点,保证setValue按序执行。

注意:在Java中,局部变量都是线程私有的,不用担心访问冲突,要担心的就是实例变量和类变量。

星期六, 六月 02, 2007

Thread的层次结构

要弄清楚Thread的层次结构,必须先弄清楚它的参照系。看看“The Futures of Ruby Threading”这段话:“Current stable releases of Ruby use user space threads (also called "green threads"), which means that the Ruby interpreter takes care of everything to do with threads. This is in contrast to kernel threads, where the creation, scheduling and synchronization is done with OS syscalls, which makes these operations costly, at least compared to their equivalents in user space threads.”这里的用户空间线程和内核线程是相对于Ruby解释器来说的。如果把参照系换成操作系统,此处的内核线程只是一个用户空间线程。

常说Java线程是Native thread,是说Java的一个线程映射到操作系统上的一个用户线程。往下随后怎么映射就要看操作系统的实现了。可以看看Solaris的线程模型这里也有些说明资料。

不过Java线程也并不一定是一一映射的,比如Jikes RVM虚拟机,采用了M:N模型,而不是大家经常看到的1:1,具体资料可以看这里。BEA的JRockit是两个都有,既支持1:1模型,也支持M:N模型,叫Thin Thread。

在JVM上实现了M:N模型,当然在操作系统上也可以实现M:N模型,只是层次不同,抽象级别不同。象Solaris就实现了M:N模型,不过这个模型在Solaris 9中已经放弃,为什么?实现太难。“It is not to say that a good implementation of the M:N model is impossible,but simply that a good 1:1 implementation is probably sufficient. ”想更进一步了解Solaris多线程的发展历程,看这个pdf吧(www.sun.com/software/whitepapers/solaris9/multithread.pdf)。

了解清楚Thread的层次结构,碰到Green Thread,Native Thread,User space Thread,Kernel Thread时才不会糊涂。

Thread被过度使用

既然Thread质疑声一片,为什么它仍能够存在呢?原因有:
(1)某些应用程序天生就具有并发特性,而且需要共享地址空间和各种资源,比如数据库服务器。
(2)进程方案开销大。
(3)Java语言大行其道,使得绝大部分程序员认为并发编程唯一也是最好的方式就是采用多线程,而且在Java语言中创建一个线程非常简单。

对于第二点,只有线程创建,线程同步,线程加锁等开销比进程方案开销小,才会真正获益。只是来个线程创建和进程创建开销的比较,那也太天真了。此处,我认为还要包括开发,维护进程并发程序和线程并发程序两种方式之间的开销对比。毕竟,除了机器时间,人的时间也很宝贵。

对于第三点,Java是不是会在以后考虑另外的并发模式。象建立在JVM之上的Scala语言就在采用Actor模式。多个选择,总是不错的主意。不然搞得我们这些开发人员都去用Thread,使得Thread被过度使用,破坏Thread的名声。


附:如果想了解Thread在哪些方面被广泛批评,请参考如下资料:
(1)《The Art of Unix Programming》的“Threads-Threat or Menace?”
(2)“Why Threads Are a Bad Idea”
(3)“The Problem with Threads”

星期四, 五月 31, 2007

Green Thread不比Native Thread差

在Ruby实现中,Ruby1.8采用的是Green thread,JRuby和XRuby采用的是Native thread,Rubinius既支持Green thread,也支持Native thread。Ruby1.9将由Green thread转向Native thread。Green thread有哪些不足呢?

在“Ruby Userspace Threads vs GUI tookits Roundup”中重点强调了Green Thread的一个不足:Blocking syscall将阻塞所有其余的线程,而且这个问题在GUI和网络开发中将随处碰到。另外,Green Thread不能有效挖掘多核和多CPU的性能。于是大家都把视线转向Native thread。我对Native thread不感冒,主要是因为shared state concurrency问题多多。具体有哪些,相信你看完“The problem with threads”就会很清楚了。

现在,Erlang很好的解决了Green Thread存在的问题。它没有采用m:1模式,而是采用了m:n模式。Erlang runtime以n个native thread运行,每个都有一个自己的调度器。而且,Erlang采用shared nothing concurrency,可以把Native Thread存在的问题都抛之脑后。

看来XRuby的thread实现可以好好借鉴一下Erlang的并发范式。在看了“The Futures of Ruby Threading”之后,更坚定了应该朝这方面努力。

星期三, 五月 30, 2007

有了OpenMP,MPI,为什么还要MapReduce?

OpenMP和MPI是并行编程的两个手段,对比如下:
  • OpenMP:线程级(并行粒度);共享存储;隐式(数据分配方式);可扩展性差;
  • MPI:进程级;分布式存储;显式;可扩展性好。
OpenMP采用共享存储,意味着它只适应于SMP,DSM机器,不适合于集群。MPI虽适合于各种机器,但它的编程模型复杂:
  • 需要分析及划分应用程序问题,并将问题映射到分布式进程集合;
  • 需要解决通信延迟大和负载不平衡两个主要问题;
  • 调试MPI程序麻烦;
  • MPI程序可靠性差,一个进程出问题,整个程序将错误;
其中第2个问题感受深刻。每次听我们部门并行组的人做报告,总是听到他们在攻克通信延迟大和负载不平衡的问题。一种并行算法的好坏就看它有没有很好的解决这两个问题。

与OpenMP,MPI相比,MapReduce的优势何在呢?
  • 自动并行;
  • 容错;
  • MapReduce学习门槛低。
附:
  • SMP(Symmetric multi-processing),共享总线与内存,单一操作系统映象。在软件上是可扩展的,而硬件上不能。
  • DSM(distributed shared memory),SMP的扩展。物理上分布存储;单一内存地址空间;非一致内存访问;单一操作系统映象。

多核意味着什么?

过去,提升CPU性能的方法有:
  • 时钟速度
  • 执行优化
  • 缓存
此时用户程序无须修改,就可以获得CPU性能提升所带来的好处。现在,提升CPU性能的方法:
  • 超线程
  • 多核
  • 缓存
此时虽然缓存能,但超线程和多核CPU对现在的绝大多数应用,几乎不会有任何影响。多核还说不定会降慢程序的运行,因为多核带来的是更强的并行处理能力、更高的计算密度和更低的时钟频率。如果不采用并发好好利用硬件资源,多核CPU真的是浪费。

另外,还有一些问题需要注意。有了多核,有时候还是感觉应用程序慢,此时问题可能就不是出在CPU上。要知道就算是单核,在日常工作中,CPU的利用率远没有达到100%。有时候,应用程序的瓶颈可能是在I/O,可能在网络,或者数据库,等等。有了计算能力,还有很多工作要做。

Google Groups:JVM Languages

通过Charles Oliver Nutter博客了解到,他弄了一个Google Groups,目的是讨论如何在JVM之上搞一个框架,以便有更多的语言落户在JVM之上。Motivation何在,我猜是想搞一个“DLR-like”平台。
目前,我主要关注的是xruby,jruby,scala在JVM平台上的实现。

附:
(1)DLR(Dynamic Language Runtime)是Microsoft搭建在CLR之上的一个框架,用来更好的支持动态语言;
(2)Scala:引入Erlang并发范式,建立在JVM之上的语言。

星期一, 五月 28, 2007

测试Hadoop Trunk代码

从SVN上checkout代码,然后部署在了两台Linux机器之上。Hadoop版本为0.12.4。过程还是挺顺利的,这得益于以前折腾过Hadoop 0.5版。

如果你在安装的过程中,发现问题,可以参考用Hadoop搭建分布式存储和分布式运算集群。 当然你可以通过Email或者Gtalk与我联系。好久没有关注Hadoop了,发现它已经越来越成熟,开始步入实际使用阶段,比如Amazon 的 EC2 S3

另外,令人非常兴奋的是,Yahoo推出Pig。从介绍可知,这是一个非常有意思的项目,建立在Hadoop之上。

星期日, 五月 27, 2007

与搜索相关的研发工作

想从事与搜索相关的研发工作,需要哪些知识。带着这个疑问,我查看了包括Google,Baidu,Yahoo,腾讯,Sohu,Sina,阿里巴巴等公司的招聘信息。自我总结如下:
  • 为什么要从事研发工作?
  1. 在公司处于核心地位;
  2. 把研究和开发紧密而完美的结合在一起;
  • 研发职责是什么?
  1. 负责搜索引擎系统的架构设计以及核心模块的系统设计;
  2. 进行搜索引擎系统核心模块的编码和技术研发;
  3. 重点技术难题的攻关;
  • 想从事研发工作,需要什么?
  1. 强烈责任心,开放的性格,良好的沟通能力;拥有极强的发现问题、分析问题、解决问题的能力;
  2. Fluency in English(Reading and Writing);
  3. 对算法设计、数据结构有深刻的理解;
  4. 精通Linux/Unix平台上的C/C++语言编程,熟练使用调试工具;熟悉网络、多线程编程技术(熟悉Unix系统调用io, socket, process, signal);如果懂Java,将更好;
  5. 能够使用一种脚本语言(perl,shell或者python);
  6. 具有搜索、信息检索相关领域开发经验者优先;
  7. 至少熟悉一种数据库系统,你可以选择MySql作为自己重点攻克的对象。
  • 想成为架构师,还需要什么?
  1. 熟悉分布式系统架构设计,具备大流量、大访问量、高负载环境下的系统开发及优化经验;
  2. 知识面广,思路开阔,对业界的最新技术发展动态有比较密切的关注;
  3. 对软件开发生命周期比较熟悉,具备较强的文档编写能力及项目管理能力。
想从事研发工作的朋友可以对照上面的要求,找出自己的不足。对于你来说,那些不足就是最重要的。缺什么,什么就最重要。

Update:一些更加细化的指标,比如:
  • 搜索引擎各子系统(Spider、Indexer、Searcher、分词、网页仓库)的设计和实现。
  • 搜索引擎的性能优化分析和功能升级。

星期二, 五月 15, 2007

继续写博客,记录自己的成长

开博多处,不过全都停了下来。今天,重新开始,将在这里记录自己的每一天生活。

(1)嘻嘻哈哈才是我:http://zyxt.blogdriver.com(最早的地方,也是所呆时间最长的地方)。
(2)飞翔的章鱼:http://zyxt.blog.hexun.com/(目前内容已经全部删除!)。
(3)naivebaby:http://blog.csdn.net/naivebaby(技术blog)。
(4)我是一只小小鸟:现在这个(由于当初google blog被禁,于是放弃)。
(5)**blog:(暂且保密)。

btw:这里主要记录我在技术上的一些感悟,要了解我的生活,请访问链接中的"My Childlike Life"!