Almost non-blocking linked stack implementation

Details Almost non-blocking linked stack implementation Almost non-blocking linked stack implementation

2004-06-30

2008-11-11

Vo, Tim (Department: 2168)

Data processing: database and file management or data structures

Database design

Data structure types

C712S009000, C710S020000, C710S021000, C714S011000, C718S106000

Reexamination Certificate

active

07451146

ABSTRACT:
A method and computer system for implementing, in a multithreaded environment, an almost non-blocking linked list allow a lock-free access provided that certain conditions are met. The approach involves: associating a pointer and an auxiliary data structure with each linked list, using a compare-and-swap (CAS) operation, and making a slight modification of values associated with nodes under certain conditions. The CAS operation guards against setting the pointers incorrectly during insertion and removal operations. The auxiliary data structure, also referred to as the ‘black list,’ holds a dynamic list of values, typically pointer values, associated with nodes that are in the process of being removed by a thread.

REFERENCES:
patent: 5111411 (1992-05-01), Browne
patent: 5295262 (1994-03-01), Seigh, II
patent: 5867649 (1999-02-01), Larson
patent: 5867660 (1999-02-01), Schmidt et al.
patent: 5924098 (1999-07-01), Kluge
patent: 6173373 (2001-01-01), Bonola
patent: 6178473 (2001-01-01), Bonola
patent: 6374286 (2002-04-01), Gee et al.
patent: 6826757 (2004-11-01), Steele et al.
patent: 7017160 (2006-03-01), Martin et al.
patent: 7111293 (2006-09-01), Hersh et al.
patent: 7117502 (2006-10-01), Harris
patent: 7194495 (2007-03-01), Moir et al.
patent: 7254597 (2007-08-01), Moir et al.
patent: 7299242 (2007-11-01), Moir et al.
patent: 7389291 (2008-06-01), Shavit et al.
patent: 2003/0140085 (2003-07-01), Moir et al.
patent: 2003/0174572 (2003-09-01), Moir et al.
patent: 2003/0182462 (2003-09-01), Moir et al.
patent: 2003/0182465 (2003-09-01), Moir et al.
patent: 2004/0165610 (2004-08-01), Chasin
patent: 2005/0071335 (2005-03-01), Kadatch
Boehm, “An Almost Non-Blocking Stack”, Jun. 25, 2004, HP Labs Technical Reports, Hewlett-Packard Development Company, HPL-2004-105.
OED.com, Oxford English Dictionary Online, Entry for “almost”, Dec. 31, 1989, 2nd Ed.
Boehm, “An Almost Non-Blocking Stack”, Jul. 25, 2004, PODC'04, ACM Press, p. 40-49.

Affiliated with

Also associated with

Rating

Almost non-blocking linked stack implementation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Almost non-blocking linked stack implementation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Almost non-blocking linked stack implementation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4027843