Browse Prior Art Database

Enumeration of Hierarchical Data Structures

IP.com Disclosure Number: IPCOM000123514D
Original Publication Date: 1998-Dec-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 2 page(s) / 101K

Publishing Venue

IBM

Related People

Dean, A: AUTHOR [+4]

Abstract

Hierarchical data structures such as those encountered in transactional processing systems such as CICS* are ideally accessed simultaneously using multiple threads of execution. In order to preserve the integrity of the data it is usual to restrict access to one thread at a time. This can produce a bottle-neck in a program, particularly when threads are searching the data structure using an Enumeration (sometimes referred to as an Iterator or Cursor). Searching requires the whole structure to be locked to all but one thread whilst that thread runs through potentially all the elements in the structure.

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

Enumeration of Hierarchical Data Structures

   Hierarchical data structures such as those encountered in
transactional processing systems such as CICS* are ideally accessed
simultaneously using multiple threads of execution.  In order to
preserve the integrity of the data it is usual to restrict access to
one thread at a time.  This can produce a bottle-neck in a program,
particularly when threads are searching the data structure using an
Enumeration (sometimes referred to as an Iterator or Cursor).
Searching requires the whole structure to be locked to all but one
thread whilst that thread runs through potentially all the elements
in the structure.

   The improved approach described here uses optimistic
Enumeration, where multiple threads are permitted to Enumerate the
data structure simultaneously.  They assume that the structure has
not been changed by another thread, and are only aware of changes
when they attempt to access the next element.  This is done by the
structure being Enumerated keeping a count of the number of times the
structure has been changed.  A copy of this count is taken by each
Enumeration object.  If the copy of the count differs from that held
in the data structure then the Enumeration knows that it is now
invalid.  Thus, multiple threads can access the same data structure
and only cause each other problems when they change that structure.
These problems can now be dealt with in a controlled manner.

   Optimistic Enumeration only reduces the bottle-neck
slightly, as it is likely that multiple threads will wish to update
the structure frequently, and will thus interfere often.  To overcome
this problem the improved system breaks down the data structure into
a hierarchy of sub-structures.  At each level of the hierarchy an
Enumeration class is implemented.  For every Enumeration type, the
object returned by a call for the next element is of the type being
held in the whole collection (i.e. the Enumerations return the same
type of objects at all levels of the hierarchy).  The imp...