1 定義
使用這個ppt的定義:
- wait free
Every operation is bounded on the number of steps before completion.
或者定義為:
A method is wait-free if it guarantees that every call finishes its execution
in a finite number of steps.
- lock-free
- At least one thread must be able to make progress at any given time
- Eventually, all threads must make progress
- Given infinite time, infinitely many threads will progress
- obstruction-free
A single thread, with all other threads paused, may complete its work.
說明: The Art of Multiprocessor Programming 對于lock-free 的定義有點模糊，內(nèi)容如下，但是表達的意思是類似的，一個函數(shù)有可能在有限步驟內(nèi)無法返回。
例子就是，無鎖通用構(gòu)造(多處理器編程藝術(shù)ch6)中間某一個線程的apply函數(shù)由于其他線程競爭成功始終失敗，將其轉(zhuǎn)變?yōu)闊o等待通用構(gòu)造的方法則是利用"助人為樂"，保證所有線程調(diào)用apply總是可以有限步返回。
A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.
2 性質(zhì)
- 所有wait free 都是 lock free，所有的lock free 都是 obstruction free。
- 是否能舉一個是obstruction-free 但是不是 lock free 的例子 ?
存在，詳細的內(nèi)容請查看鏈接，此處簡單描述。如果對于一個stack 兩個線程分別進行push和pop，而且push 和 pop 由于某些需要兩步完成，那么這兩個操作會因為各自執(zhí)行了第一個操作而導(dǎo)致對方的第二步操作無法進行。但是當(dāng)系統(tǒng)中間只有一個進程的時候，該線程可以完成工作。
3 為什么要使用wait free
利用cas構(gòu)成各種wait free 算法中間其實還是含有大量的循環(huán)（失敗的線程需要不反復(fù)嘗試，直到成功），這和spin lock 的循環(huán)似乎沒有什么區(qū)別，即不能帶來性能提升，而且wait free 算法似乎更加難以設(shè)計，所以為什么還是要使用wait free 呢？
參考，我的想法是:
- 性能取決于wait free具體算法的實現(xiàn)，運行的程序，可能高，可能低。
There are so many variants... tagged pointers, epoch based reclamation, RCU/quiescent state, hazard pointers, general process-wide garbage collection, etc. All these strategies have performance implications, and some also place restrictions on how your application in general can be designed.
If preemption in the middle of a critical section is sufficiently rare, then dependent blocking progress conditions are effectively indistinguishable from their nonblocking counterparts. If preemp?tion is common enough to cause concern, or if the cost of preemption-based delay is sufficiently high, then it is sensible to consider nonblocking progress con?ditions.
- wait free 的核心是:防止出現(xiàn)死鎖，即為當(dāng)持有鎖的thread不釋放鎖，其他的線程只能干看著。但是wait free 不會出現(xiàn)，所有的線程只會不停的執(zhí)行CAS指令，如果失敗重新嘗試。
not all threads can be blocked by a sudden delay of one or more other threads.
The absolute wait-free and lock-free progress properties have good
theoretical properties, they work on just about any platform, and they provide
real-time guarantees useful to applications such as music, electronic games, and
other interactive applications. The dependent obstruction-free, deadlock-free,
and starvation-free properties rely on guarantees provided by the underlying
platform. Given those guarantees, however, the dependent properties often admit
simpler and more efficient implementations
4 例子
- queue 的wait free 是如何處理 deque 但是queue is empty 的情況的 ? (返回null 吧!
