发明申请
- 专利标题: Efficient Non-Blocking K-Compare-Single-Swap Operation
- 专利标题(中): 高效的非阻塞K比较单互换操作
-
申请号: US11864624申请日: 2007-09-28
-
公开(公告)号: US20080077748A1公开(公告)日: 2008-03-27
- 发明人: Nir Shavit , Mark Moir , Victor Luchangco
- 申请人: Nir Shavit , Mark Moir , Victor Luchangco
- 主分类号: G06F12/00
- IPC分类号: G06F12/00
摘要:
The design of nonblocking linked data structures using single-location synchronization primitives such as compare-and-swap (CAS) is a complex affair that often requires severe restrictions on the way pointers are used. One way to address this problem is to provide stronger synchronization operations, for example, ones that atomically modify one memory location while simultaneously verifying the contents of others. We provide a simple and highly efficient nonblocking implementation of such an operation: an atomic k-word-compare single-swap operation (KCSS). Our implementation is obstruction-free. As a result, it is highly efficient in the uncontended case and relies on contention management mechanisms in the contended cases. It allows linked data structure manipulation without the complexity and restrictions of other solutions. Additionally, as a building block of some implementations of our techniques, we have developed the first nonblocking software implementation of load-linked/store-conditional that does not severely restrict word size.
公开/授权文献
- US07865671B2 Efficient non-blocking K-compare-single-swap operation 公开/授权日:2011-01-04