关于锁的一点想法

考虑namenode或者某种rpc service队列.

假设有k个处理线程,每个请求处理时间是r的话.
则有t时间内的throughput T=k*r.

如果每个请求会收到一个global/share lock或者之类的互斥影响的话.
那么单个请求的开销r应该增加一个extra cost c.
即T=k*(r+c).

对于锁竞争之类的,cost c通常不会是一个常数.
考虑存在一个概率p能描述这个dynamic的话.
即c=p(c)

则每个请求的开销为r+p(c).
考虑有n个请求的话,那么在并行k的情况下.
每个线程处理m_i个请求,则该线程处理时长为\sum_{m_i} r+p(c).
->
cost of thread m_i = r*m_i + \sum p(c).

其中有n=\sum_k m_i即所有线程的处理请求总数加和为n.

当each m_i sufficient large的情况下,
cost of thread m_i ~ rm_i + m_imean(p(c)).
即竞争带来的dynamic cost趋向于它的期望.

考虑线程处理是work stealing的策略的话.
那么并行带来的处理时长应该是每条线程差不多.

因为考虑只有两条线程的情况.
其中a跑了一个task,那么另外一条b要么跑comparable的task,要么lighter,或者heavier.
如果是lither的话,那么b将先完成,并抢先执行下一个.
这时等价于将a的当前task的cost减去b的task的开销,重置回假设初始.
而如若是heavier的话,交换a b即可.

对于k>=2的情况可以将划分为logical两条线程divide and conquer.

于是在这种情况下每条线程都是equality comparable cost的.
而任意一条在m_i sufficient large的情况下有
cost=rm_i + m_imean(p(c))
->
per request cost=r+mean(p(c))

在p(c) dominate r的情况下.
比如在lock contention的情况下,process cost << wait lock.
实际请求开销小于锁竞争的情况下.

那么throuthput ~ mean(p(c))的.

那么考虑p的实际分布可能的形式.

以读写锁为例.
请求require read lock的概率为p,write lock的概率为1-p.
有k个线程竞争.

则,request read lock的情况.
当,all read lock的概率为p^k
因为shareable,所以cost=(p^k)*0 = 0

at least one write lock的概率为1-p^k.
如果获得锁,则有cost=0.

未获得锁的话,存在另外一个描述lcurrl,lock cost under read request lose.
即cost=(1-p^k) * (lcurrl)

请求为write lock的情况下,且获得的情况不论概率,其cost为零.
获取失败的情况下,存在yet another描述,lcuwrl,lock cost under write request lose.

那么mean cost=(p) * ((1-p^k) * (lcurrl)) + (1-p)lcuwrl.
->lcurrlp - lcurrlp^(k+1) + lcuwrl - plcuwrl
->(lcurrl-lcuwrl)p + lcuwrl - lcurrlp^(k+1)

由于lcurrl和lcuwrl都是在给定p下的某个分布的mean值.
所以对于给定的p,有
(lcurrl-lcuwrl)p + lcuwrl - lcurrlp^(k+1)
->
mean cost = a*p^(k+1) + b
其中,a>0,1>=p>=0,k>0,b>0

当p->0的时候,或者k越来越大的话,mean cost -> b -> lcuwrl.
即lock cost under write request lose.
也即写锁竞争失败之后的expected cost.

如果锁是fair的.
那么设计上来说,每个线程得到的几率都是对等的.
于是随着k的增加,lcuwrl也会相应增加.
因为稀释.

而如果是non-fair的,则依赖于具体实现了.