无等待是不够的

原文地址译文链接,译者:许巧辉,校对:周可人

无等待是不够的

以目前针对演进条件(progress condition,注:参考[1])的算法和数据结构的分类来看,是不足以区分不同演进条件的能力和每一个演进条件的性能/延迟。

我们提出了一种新的“大O”记号来表示无等待的算法和数据结构。下面是它的工作原理:

一个算法或功能被称为“Wait-Free O(x)“,表示需要最多O(x)操作完成。


一些示例:

  • a)”Wait-Free O(NThreads)“表示:一个算法,扫描每个活动线程的状态
  • b)”Wait-Free O(ln NThreads)“表示:一个算法,需要自身插入到活动的线程(使用二分法)的排序列表
  • c)”Wait-Free O(NThreads^2)“表示:一个算法,扫描活动线程的每个状态平方次数
  • d)”Wait-Free O(1)“表示:一个算法,做3次操作,不论活动线程和其他变量数目
  • e)”Wait-Free O(N)“表示:一个算法,获取确定数值N,比如一个数列当前元素的数量N,并且做了O(N)操作
  • f)”Wait-Free O(N^2)“表示:一个算法,获取确定数值N,并且做了O(N^2)操作

根据当前表示法,示例a)、b)和c)都是”Wait-Free Bounded”,但示例b)显然比c)或a)更好。

根据当前表示法,示例d)、e)和f)都是”Wait-Free Population Oblivious”,崦示例d)显然比e)或f)更好

也许更有意思的是,示例b)可能比示例f)更好。特别地,如果N > NThreads,即使b)是”Bounded”而f)是”Population Oblivious”,它只是用来显示”Wait-Free Population Oblivious”未必比”Wait-Free Bounded”更好。

无锁如何?

那么,在这个新的表示法中,无锁也可以写成”Wait-Free O(infinity)”形式,但要注意的是,尽管所有的无锁算法都有一个最坏情况O(infinity),它们大多数都有一个预计的操作数O(1)或O(N),并且不依赖于线程的数量。

再比方说:

一个链表,对于contains()方法是无等待(Wait-Free)的,但这永远不会比”Wait-Free O(N_elements)”更好(N_elements是在某个时刻contains()操作时,链表中元素的数量)

匹配新旧之间的分类:

  • Wait-Free Bounded:O(ln NThreads), O(NThreads), O(NThreads^2),  …
  • Wait-Free Population Oblivious:O(1), O(ln N), O(N), O(N^2), …

在我们自己的数据结构中,我们正试图遵循这一惯例,并指出每个函数的演进条件的顺序是什么。

http://sourceforge.net/projects/ccfreaks/files/

参考:

[1] 多处理器编程的艺术

原创文章,转载请注明: 转载自并发编程网 – ifeve.com本文链接地址: 无等待是不够的

  • Trackback 关闭
  • 评论 (0)
  1. 暂无评论

return top