发明授权
US07870344B2 Method and apparatus for emulating linked-load/store-conditional synchronization
有权
用于模拟链接加载/存储条件同步的方法和装置
- 专利标题: Method and apparatus for emulating linked-load/store-conditional synchronization
- 专利标题(中): 用于模拟链接加载/存储条件同步的方法和装置
-
申请号: US11864649申请日: 2007-09-28
-
公开(公告)号: US07870344B2公开(公告)日: 2011-01-11
- 发明人: Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
- 申请人: Nir N. Shavit , Mark S. Moir , Victor M. Luchangco
- 申请人地址: US CA Redwood City
- 专利权人: Oracle America, Inc.
- 当前专利权人: Oracle America, Inc.
- 当前专利权人地址: US CA Redwood City
- 代理机构: Meyertons, Hood, Kivlin, Kowert & Goetzel, P.C.
- 代理商 Robert C. Kowert
- 主分类号: G06F12/00
- IPC分类号: G06F12/00 ; G06F13/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.
公开/授权文献
- US20080077775A1 Efficient Non-Blocking K-Compare-Single-Swap Operation 公开/授权日:2008-03-27