Browse Prior Art Database

Concurrent Scanning of Dynamically Changing Chains

IP.com Disclosure Number: IPCOM000117943D
Original Publication Date: 1996-Jul-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 2 page(s) / 69K

Publishing Venue

IBM

Related People

Banks, TW: AUTHOR [+2]

Abstract

Concurrent scanning of a chain of data elements (i.e., while elements are being added or removed) normally presents a problem because the scanner risks processing an element which is in the course of being removed and reallocated; this would cause the scanner to pick up invalid data (including an invalid forward chain pointer).

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

Concurrent Scanning of Dynamically Changing Chains

      Concurrent scanning of a chain of data elements (i.e., while
elements are being added or removed) normally presents a problem
because the scanner risks processing an element which is in the
course of being removed and reallocated; this would cause the scanner
to pick up invalid data (including an invalid forward chain pointer).

      The algorithm described below make the assumption that, during
the lifetime of the mechanism, the storage for an element may be
reused only for another element (possibly on a different chain, but
satisfying the algorithms below).

An element has two crucial fields (other than the chain fields):
  o  A 'removed' flag (R)
  o  A timestamp (TEL)

When an element is added to the queue, the following processing is
performed:
  1.  Initialize element, including forward chain (or chains, if
       doubly linked)
  2.  Capture current time and save in TEL.  Capturing the current
       time is done using the STCK instruction on 390 systems or an
       equivalent instruction on other hardware platforms.
  3.  Set R OFF
  4.  Add element to chain (typically at one end, to allow multiple
       concurrent adders, but the algorithm does not rely on this).

When an element is removed from the queue, the following processing
is performed:
  1.  Set R ON (this may need a cpu synchronising instruction to make
       this visible to other cpus)
  2.  Remove element from chain (note - this is not trivial if
multiple
       concurrent removers are allowed, because the predecessor
element
       whose forward itself be in the process of being removed!  The
       intention of this algorithm is to address the problem of
       concurrent scanning, not of multiple concurrent removers).

A scanner does the following:
  1.  Before starting scan, capture...