Browse Prior Art Database

Scheme for Low-Overhead High-Concurrency Update

IP.com Disclosure Number: IPCOM000118247D
Original Publication Date: 1996-Nov-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 6 page(s) / 283K

Publishing Venue

IBM

Related People

Lumby, JE: AUTHOR

Abstract

System software often deals with lists of control blocks, each item on the list representing one instance of some general concept or resource - for example, a list of device control blocks, one per device, or a list of application control blocks, one per current application. Usually, the system needs to be able to add and delete entries to/from the list dynamically, as the related thing (device, application, etc.) enters and leaves the system. In a multi-user or multi-processing system, many such add/delete requests could occur close together, raising the possibility that the list could be corrupted if two separate processes are both adding or deleting at the same point in the list.

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

Scheme for Low-Overhead High-Concurrency Update

      System software often deals with lists of control blocks, each
item on the list representing one instance of some general concept or
resource - for example, a list of device control blocks, one per
device, or a list of application control blocks, one per current
application.  Usually, the system needs to be able to add and delete
entries to/from the list dynamically, as the related thing (device,
application, etc.) enters and leaves the system.  In a multi-user or
multi-processing system, many such add/delete requests could occur
close together, raising the possibility that the list could be
corrupted if two separate processes are both adding or deleting at
the same point  in the list.  The traditional and simple solution to
this corruption problem is to serialize the adding and deleting -
that is, only one process is allowed to add or delete an entry
to/from the list at a time.  This can slow the system down.

      The solution is to allow concurrent updates and to extend the
add and delete routines to ensure integrity of the list and also to
provide a safe way of restoring the list.  The extension to the
add/delete routines is twofold:
  1.  Break the routine into stages, each of which updates
       only one field.
  2.  Define a scheme which is followed by each stage of each
       update routine, and which consists of three primary steps:
        a.  Before updating the field, check whether any
             conflicting update is in progress at this particular
             point in the list.
        b.  Update the field using an "atomic"  and "serializing"
             instruction, for example, Compare and Swap.  This
             stage of the overall add or delete is serialized with
             other routines attempting to update the same field;
             thus, the serialization is at a much finer granularity
             than in the traditional solution.
        c.  If the Compare and Swap instruction returns "failure,"
             a conflict, and the update is performed, then perform
             "UNDO" operations to restore the list back to the state
             of the locality of this particular update, and then
             re-try the whole add or delete.

      A system is considered as consisting of:  (a) a set of data
objects or fields organized in some way; (b) a set of algorithms each
of which modifies some of the fields in a particular way and may also
add or delete fields; and (c) tasks which can execute the algorithms
concurrently.

      The complete set of fields is referred to as the "datanet",
the execution of one of the algorithms as an "update", and "modify"
to mean a change in value of a field.  The datanet must be kept
"self-consistent", i.e., its fields must al...