無等待是不够的

杜老師說 2022-01-07 13:36:46 阅读数:156

等待 不够

原文地址譯文鏈接,譯者:許巧輝,校對:周可人

無等待是不够的

以目前針對演進條件(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本文鏈接地址: 無等待是不够的

FavoriteLoading添加本文到我的收藏
版权声明:本文为[杜老師說]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201071336460926.html