DOUBLE-ENDED QUEUE WITH CONCURRENT NON-BLOCKING INSERT AND REMOVE OPERATIONS

WIPO Patent Application WO2001053943

A3

A linked-list-based concurrent shared object implementation has been developed that provides non-blocking and linearizable access to the concurrent shared object. In an application of the underlying techniques to a deque, the linked-list-based algorithm allows non-blocking completion of access operations without restricting concurrency in accessing the deque's two ends. The new implementation is based at least in part on a new technique for splitting a pop operation into two steps, marking that a node is about to be deleted, and then deleting it. Once marked, the node logically deleted, and the actual deletion from the list can be deferred. In one realization, actual deletion is performed as part of a next push or pop operation performed at the corresponding end of the deque. An important aspect of the overall technique is synchronization of delete operations when processors detect that there are only marked nodes in the list and attempt to delete one or more of these nodes concurrently from both ends of the deque.

SHAVIT NIR N
MARTIN PAUL A
STEELE GUY L JR

PCT/US2001/000043

April 18, 2002

January 02, 2001

Click for automatic bibliography generation  

SUN MICROSYSTEMS INC (US)

G06F5/10; G06F7/78; G06F9/46; (IPC1-7): G06F9/46

EP0466339A2

1992-01-15

MASSALIN H.: "SYNTHESIS: AN EFFICIENT IMPLEMENTATION OF FUNDAMENTAL OPERATING SYSTEM SERVICES", DISSERTATION SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY IN THE GRADUATE SCHOOL OF ARTS AND SCIENCES, COLUMBIA UNIVERSITY, NEW YORK, NY, US, 1992, pages 1 - 142, XP002172093, Retrieved from the Internet [retrieved on 20010713]
MASSALIN H., PU C.: "A LOCK-FREE MULTIPROCESSOR OS KERNEL", TECHNICAL REPORT NO. CUCS-005-91, DEPARTMENT OF COMPUTER SCIENCE, COLUMBIA UNIVERSITY, NEW YORK, NY, US, 19 June 1991 (1991-06-19), pages 1 - 19, XP002172094, Retrieved from the Internet [retrieved on 20010713]
ARORA N. S., BLUMOFE R. D., PLAXTON C. G.: "THREAD SCHEDULING FOR MULTIPROGRAMMED MULTIPROCESSORS", PROCEEDINGS OF THE TENTH ANNUAL ACM SYMPOSIUM ON PARALLEL ALGORITHMS AND ARCHITECTURES (SPAA98), PUERTO VALLARTA, MEXICO, 28 June 1998 (1998-06-28) - 2 July 1998 (1998-07-02), ASSOCIATION FOR COMPUTING MACHINERY, ACM, NEW YORK, NY, US, pages 119 - 129, XP002172092, ISBN: 0-89791-989-0, Retrieved from the Internet [retrieved on 20010713]
AGESEN O., DETLEFS D. L., FLOOD C. H., GARTHWAITE A. T., MARTIN P. A., SHAVIT N. N., STEELE JR. G. L.: "DCAS-BASED CONCURRENT DEQUES", PROCEEDINGS OF THE TWELFTH ANNUAL ACM SYMPOSIUM ON PARALLEL ALGORITHMS AND ARCHITECTURES (SPAA2000), BAR ARBOR, MAINE, US, 9 July 2000 (2000-07-09) - 12 July 2000 (2000-07-12), ASSOCIATION FOR COMPUTING MACHINERY, ACM, NEW YORK, NY, US, pages 137 - 146, XP002172095, Retrieved from the Internet [retrieved on 20010713]

View/Download PDF      PDF Help

Previous Patent: DOUBLE-ENDED QUEUE WITH CONCURRENT NON-BLOCKING INSERT AND REMOVE OPERATIONS

Next Patent: REDUNDANT DATA MEMORY