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

Portable Recovery of Linked Lists

IP.com Disclosure Number: IPCOM000113563D
Original Publication Date: 1994-Sep-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 128K

Publishing Venue

IBM

Related People

Washer, A: AUTHOR

Abstract

Disclosed is a method of protecting recoverable resources against failure of a resource-updating process. Linked lists are manipulated so that failures do not irretrievably corrupt the list. The present method is well suited to dealing with failure of the task during updates to linked lists, and the method is portable across operating systems.

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

Portable Recovery of Linked Lists

      Disclosed is a method of protecting recoverable resources
against failure of a resource-updating process.  Linked lists are
manipulated so that failures do not irretrievably corrupt the list.
The present method is well suited to dealing with failure of the task
during updates to linked lists, and the method is portable across
operating systems.

      Many operating systems do not provide guaranteed exit routines
on process failure or abort.  This causes difficulties in maintaining
the integrity of data that is shared between processes, since a
process failure which occurs during a data update will often leave
the shared data in a corrupt state.  A portable, operating system
independent, method to ensure data integrity is required.

This method assumes that an operating system is capable of providing
the following features.
  1.  Some form of storage that can be shared between processes.
  2.  Mutual Exclusion (Mutex) Semaphores.

      No further assumptions are made about the operating system, and
no privileges are assumed, other than the capability of using the
above features.

      All data operations are performed under protection of a Mutex
semaphore, and the Mutex holder is required to build an audit trail
of updates to the data, before updating the data.  This audit trail
must be built in order to define the failure path, and must be
recorded in such a way that the backout operation can be performed by
another process.

      If a lock owner is unable to complete a data operation while
holding the mutex (perhaps because it has been killed by the
operator), then the operation must be backed out by the next process
that obtains the lock prior to accessing the data that is protected
by the mutex.

      This method was originally produced to resolve problems with
the integrity of doubly linked lists.  The method was later
considerably extended in scope to cover all data in a Resource
Manager.  To simplify the description, the original linked list
problem is used as an example.

      The requirement is to preserve the integrity of a shared
doubly-linked list, such that both directions of linkage would always
be valid.  This is complicated by the fact that one must have
indirection in linkages, since pointers are not generally valid in
more than one process.  There is no way to guarantee an atomic copy
of a structure (without assuming operating system privileges), and it
must be assumed that a failure during a linkage update leaves a
corrupt linked list .

      Each element in the linked list is referred to as a QuickCell.
Each QuickCell in a list is assumed to have the same structure, such
that the list is homogenous.  QuickCells reside in shared memory, and
are always identified by handles (HQC).  This handle is valid system
wide, whereas pointers will normally have process-scope.  A pointer
to the quick cell can be derived from the HQC.  Each Quic...