Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Scheme for Controlling Concurrent Algorithms that Update Linked Data Structures

IP.com Disclosure Number: IPCOM000106299D
Original Publication Date: 1993-Oct-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 4 page(s) / 197K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR [+2]

Abstract

Disclosed is a method for using reservations and traps to enable concurrent routines to traverse linked data-structures while the data structure links are changing. A concern in the area of concurrent programming is the manipulation of links in shared data structures while programs are following those links. A program error occurs if a processor follows a link to a region of memory while a second processor alters the link and reclaims the region of memory that was formerly active. Prior art requires locks on pointers or on data structures that contain those pointers in order to prevent this type of program failure or other similar failures.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 33% of the total text.

Scheme for Controlling Concurrent Algorithms that Update Linked Data Structures

      Disclosed is a method for using reservations and traps to
enable concurrent routines to traverse linked data-structures while
the data structure links are changing.  A concern in the area of
concurrent programming is the manipulation of links in shared data
structures while programs are following those links.  A program error
occurs if a processor follows a link to a region of memory while a
second processor alters the link and reclaims the region of memory
that was formerly active.  Prior art requires locks on pointers or on
data structures that contain those pointers in order to prevent this
type of program failure or other similar failures.

      However, the use of locks is unsatisfactory because of
performance degradation and lack of resiliency in the face of
failures.  If a processor fails while holding a lock on a critical
structure, the entire system becomes blocked, and the system fails.

      Herlihy [1]  and Turek [2]  both considered techniques for
constructing nonblocking data structures.  These techniques assure
that processes are not blocked forever if any process fails or makes
arbitrarily slow progress.  The procedures do not provide for control
of access to storage through obsolete pointers, and it is possible
for return of such storage to be delayed, and for useless work to be
performed in such storage when it is due to be returned.

      Separately, Heidelberger and Stone [3]  described a scheme for
interrupting a process from a remote processor when a shared datum is
changed.  The present work extends that work to produce an efficient
solution to handling shared linked data structures.  The new
contribution is a concurrent lock-free algorithm for inserting and
deleting items in a priority-ordered queue, which we believe to be
the first instance of such an algorithm.

      The problem is to control concurrent algorithms that modify
linked data structures so that a processor can stop and recover
immediately when a remote processor alters one of several possible
designated links in the data structure.  This enables a processor to
make a region of data structure inaccessible, and to guarantee that
no processor is active in that region, so that the region can be
returned to free storage.

The algorithm requires the following apparatus described in [3].

o   a multiprocessor computer system,

o   a reservation registers in each processor, which designates the
    address of a shared variable,

o   READ WITH RESERVATION and WRITE IF RESERVED instructions to set
    the contents of the reservation register and to control the
    updating of shared memory,

o   a field in each reservation reservation that contains an address
    to put into a program counter if the reservation is lost,

o   a means for setting the value of the program counter field to be
    the program address of the READ W...