语义与并行不可分,兼回qiezi的Blog

也就是不考虑转发这种情况?

转发也是一样的，只是少一次销毁和一次创建，本来是要把消息复制了再发出去的。

约定消息在被发送以后，不得继续使用该消息对象。

注：这个有兴趣可以玩下，看看Erlang可以达到什么样的效率。 
Java代码 
% 以下表示a的权重是1，b的权重是2，依次类推   
Weights = [{a, 1}, {b, 2}, {c, 3} ... {j, 10}]  

% 以下表示a的权重是1，b的权重是2，依次类推
Weights = [{a, 1}, {b, 2}, {c, 3} ... {j, 10}]

要求生成一个随机数，按权重选出a-j，要求10000次执行的结果，a-j被选出的几率和它们的权重相近即可。 
也可以调整数据结构，但要求能够保证可以随时更新权重值，插入和删除。 
实际应用比这个稍复杂一些，数据量多一些，算法部分主要是这个。 

这里表述有问题吧，a-j出现的概率总是(0-1)怎么可能和weights相近?你到底想求什么?
另外,这个问题个人初步的感觉完全没有必要做10000次循环的啊.
某个weights出现的概率和试验次数没有关系,而是取决于你的随机函数采用什么样的分布,一般的编程语言都是用线性同余法做的其实就是均匀分布,在区间[a,b]上任意x的分布函数是p(x)=(x-a)/(b-a).那么这个问题就很简单了,在[minweights,maxweights]中的某个weights的概率就是p(x)=(x-minweights)/(maxweights-minweights).然后求数列{p(x)*10-x|x∈[minweights,maxweights]}的最小值就ok了。如果为了寻求更大的随机性你也可以用二项式分布或者泊松分布.


如果说你的意思是把Weights的数值当作Weights本身出现的次数算该Weights出现的概率那个最高.那么每次weights出现都是独立随机事件,于是在10000次试验中出现n次weights的概率就是应该呈n重贝努力分布.

K是出现试验次数,p是某个weights在随机函数分布中的概率.那么带入公式算应该很快的吧.如果不是，其实其他的问题也是一样在这几个分布里面到来到去。如果嫌算阶乘还是慢，可以像概率论教科书后面的正太分布表一样建一张密度函数表，然后直接查就OK了啊,每个weights的概率计算复杂度是O(1).当然每次更新Weights的时候要从新建表.但是这种样本在100以内的表，就算是按正态分布建消耗也是小菜吧.

那就是用copy了,这个时候用reference counting吧，会少很多麻烦.

注：这个有兴趣可以玩下，看看Erlang可以达到什么样的效率。

% 以下表示a的权重是1，b的权重是2，依次类推
Weights = [{a, 1}, {b, 2}, {c, 3} ... {j, 10}]

要求生成一个随机数，按权重选出a-j，要求10000次执行的结果，a-j被选出的几率和它们的权重相近即可。
也可以调整数据结构，但要求能够保证可以随时更新权重值，插入和删除。
实际应用比这个稍复杂一些，数据量多一些，算法部分主要是这个。

[Servers]
ServerCount = 3
Server0 = 127.0.0.1:1601 5
Server1 = 127.0.0.1:1602 5
Server2 = 127.0.0.1:1603 5

是想实现类似下面这样的多机负载均衡的功能吧？
在下面的这个配置中，Server0，Server1，Server2 的权重都是 5 ，即负载平均分布。

[Servers]
ServerCount = 3
Server0 = 127.0.0.1:1601 5
Server1 = 127.0.0.1:1602 5
Server2 = 127.0.0.1:1603 5

IBM的jvm在很早就实现了所谓的concurrent gc的算法，应该说ibm的jvm要hot spot好的多.但是IBM的JVM仍然无法避免stop whole world,只是通过某些算法来降低stop whole world的时间.我记得02年的时候在csnd上发过一篇关于ibmjvm gc的分析文章,有兴趣的可以找来看一下.IBM jvm这几年或许有些其他的改进，但是没有仔细关心过,这里就粗粗的根据当时的印象，简单说一下.
一般Mark-sweep算法分成两个步骤Mark(标记)和Sweep(清扫)(Ibm jvm实际上是三个还有一个是Compaction(内存紧缩)这一部分可以完全并行的执行).Ibm的concurrent gc主要集中于Mark阶段.在Mark阶段主要采用Parallel Mark和Concurrent mark.前者的主要目的是为了在SMP上降低Mark phase的执行时间,在N路SMP上，除了一个main GC thread以外，还可以开启N-1路helper gc thread.main gc的工作主要是扫描C stack以便收集Heap roots,收集完成之后把Heap roots平均分配到N条Helper gc上去.而Concurrent mark的目的则是在于降低stop whole world的时间,即便由N个gc thread进行mark,它也必须打断当前working thread的执行.但是很多working thread工作并不繁忙，因此IBM jvm就想办法让每一个working thread在空闲时自己清扫自己的heap root.当一个working thread没有获取一个global heap lock时,由普通GC或者Parallel Mark清扫.一旦某个working thread要获取global heap lock的时候就代表它自己的heap耗尽.那么这时就启动Concurrent mark,让这个working thread自己清扫自己的stack.
这样做的好处在于GC可以在global heap用尽的同时完成标记工作。此时GC就开始stop whole world,进入清扫阶段。
所以IBM的concurrent gc仍然无法避免stop whole world.因为只要内存模型中允许指针互相引用,stop whole world就无法避免.在这种情况下,GC无法保证Concurrent gc完成以后所有的reachable objects都被mark到,所以必须进行一次stop whole world进行remark.当然分代收集的GC这个pause会比较小，但是这也仅仅是统计意义上的保证,对于一个长时间运行的服务器来说运行时间越长(样本的越大)统计意义的保证就越不可靠(大数定理咯).因此这种concurrent gc一般称为Mostly-Concurrent Collector.

另外对于VM模型上还有一个影响并发/并行的因素忘记说了,就是在分代收集过程中的write barrier.分代收集里根据统计把内存分为yong和old,因为由于指针互相指引的问题,不能总保证内存指针是从yong指向old,如果出现old指向yong的情况，那么就需要从新调整分代。但是从统计上这种情况比较少见，所以进行全局扫描的cost就太高，于是就设计一个write barrier当应用程序把指针从old指向yong的时候就进行自陷然后写入一个卡表.这个自陷的过程也是一个麻烦的根源,也就是说每当你做一次refernce赋值实际上就要进行一次write barrier 检测.这个消耗一般来说在3-5个机器指令左右，当频繁写Heap时造成的消耗也非常可观.而FP语言就没有这种问题了.

至于真正的concurrent gc,据说能做到zero latency不过要付出的代价也不少。这方面我不熟悉,不过Elminster在这方面很有造纸，可以请他来讲一下。