Invention Grant
- Patent Title: Obstruction-free data structures and mechanisms with separable and/or substitutable contention management mechanisms
-
Application No.: US14733908Application Date: 2015-06-08
-
Publication No.: US09323586B2Publication Date: 2016-04-26
- Inventor: Mark S. Moir , Victor M. Luchangco , Maurice Herlihy
- Applicant: Oracle International Corporation
- Applicant Address: US CA Redwood City
- Assignee: Oracle International Corporation
- Current Assignee: Oracle International Corporation
- Current Assignee Address: US CA Redwood City
- Agency: Meyertons, Hood, Kivlin, Kowert & Goetzel, P.C.
- Agent Robert C. Kowert
- Main IPC: G06F12/00
- IPC: G06F12/00 ; G06F13/00 ; G06F13/28 ; G06F9/52 ; G06F9/46 ; G06F12/14

Abstract:
We teach a powerful approach that greatly simplifies the design of non-blocking mechanisms and data structures, in part by, largely separate the issues of correctness and progress. At a high level, our methodology includes designing an “obstruction-free” implementation of the desired mechanism or data structure, which may then be combined with a contention management mechanism whose role is to facilitate the conditions under which progress of the obstruction-free implementation is assured. In general, the contention management mechanism is separable semantically from an obstruction-free concurrent shared/sharable object implementation to which it is/may be applied. In some cases, the contention management mechanism may actually be coded separately from the obstruction-free implementation. We elaborate herein on the notions of obstruction-freedom and contention management, and various possibilities for combining the two. In addition, we include description of some exemplary applications to particular concurrent software mechanisms and data structure implementations.
Public/Granted literature
Information query