Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
DOUBLE-ENDED QUEUE WITH CONCURRENT NON-BLOCKING INSERT AND REMOVE OPERATIONS
Document Type and Number:
WIPO Patent Application WO2001053942
Kind Code:
A3
Abstract:
An array-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 array-based algorithm allows uninterrupted concurrent access to both ends of the deque, while returning appropriate exceptions in the boundary cases when the deque is empty or full. An interesting characteristic of the concurrent deque implementation is that a processor can detect these boundary cases, e.g., determine whether the array is empty or full, without checking the relative locations of the two end pointers in an atomic operation.

Inventors:
SHAVIT NIR N
AGESEN OLE
DETLEFS DAVID L
FLOOD CHRISTINE H
GARTHWAITE ALEXANDER T
MARTIN PAUL A
STEELE GUY L JR
Application Number:
PCT/US2001/000042
Publication Date:
May 30, 2002
Filing Date:
January 02, 2001
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
SUN MICROSYSTEMS INC (US)
International Classes:
G06F5/14; G06F7/78; G06F9/46; (IPC1-7): G06F9/46
Domestic Patent References:
WO1986000434A11986-01-16
Foreign References:
EP0366585A21990-05-02
EP0466339A21992-01-15
Other References:
AGESEN O ET AL: "DCAS-BASED CONCURRENT DEQUES", SPAA 2000. 12TH. ANNUAL ACM SYMPOSIUM ON PARALLEL ALGORITHMS AND ARCHITECTURES. BAR HARBOR, ME, JULY 9 - 12, 2000, ANNUAL ACM SYMPOSIUM ON PARALLEL ALGORITHMS AND ARCHITECTURES, NEW YORK, NY: ACM, US, 9 July 2000 (2000-07-09), pages 137 - 146, XP002172095, ISBN: 1-58113-185-2
DETLEFS D L ET AL: "EVEN BETTER DCAS-BASED CONCURRENT DEQUES", DISTRIBUTED COMPUTING. 14TH INTERNATIONAL CONFERENCE, 4 October 2000 (2000-10-04), pages 59 - 73, XP002172096
ARORA N S ET AL: "THREAD SCHEDULING FOR MULTIPROGRAMMED MULTIPROCESSORS", SPAA '97. 10TH. ANNUAL ACM SYMPOSIUM ON PARALLEL ALGORITHMS AND ARCHITECTURES. PUERTO VALLARTA, MEXICO, JUNE 28 - JULY 2, 1998, ANNUAL ACM SYMPOSIUM ON PARALLEL ALGORITHMS AND ARCHITECTURES, NEW YORK, NY: ACM, US, 28 June 1998 (1998-06-28), pages 119 - 129, XP002172092, ISBN: 0-89791-989-0
Download PDF:
View/Download PDF      PDF Help



 
Previous Patent: METHOD AND SYSTEM FOR RENDERING ADDITIONAL INFORMATION BASED ON EITHER EXTERNAL OR INTERNAL INPUT

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