Browse Prior Art Database

Protected Shared Latch

IP.com Disclosure Number: IPCOM000111315D
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 119K

Publishing Venue

IBM

Related People

Brown, DD: AUTHOR [+4]

Abstract

Disclosed is an algorithm that provides concurrent processes with the ability to add and delete elements from a linked list, which provides better recovery and storage management capability over the original shared latch algorithm as applied to linked lists.

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

Protected Shared Latch

      Disclosed is an algorithm that provides concurrent processes
with the ability to add and delete elements from a linked list, which
provides better recovery and storage management capability over the
original shared latch algorithm as applied to linked lists.

A linked list serialized by a shared latch contains the following
structures:

o   A fullword anchor containing the address of the first element on
    the list or 0.

o   A doubleword, where the first word contains a counter containing
    the number of processes iterating over elements on the list and
    the second word contains the address of a list of elements that
    are pending unchained/pending deletion.

o   Linked list elements where each element contains a word which
    contains the address of the next element ("next" field) on the
    list.

      The basic shared latch algorithm, as applied to linked lists,
allows adding elements to the front of the list and removal of an
element anywhere in the list.  To add an element, the process stores
the address contained in the anchor in the element being added and
uses compare and swap logic to modify the anchor.  To traverse the
list, the process must first increment the latch count by 1.  While
traversing the list, the process may logically delete an element by
marking it pending unchained and adding it to the list of pending
unchained/pending deleted elements; the the actual removal of the
element from the list and subsequent deletion are deferred.  When the
process is ready to release the latch, the following is performed:

o   If the latch count is 1, then

    -   the process "steals" the list of pending unchained/pending
        deleted elements and replaces its anchor with 0 (this is
        accomplished atomically via compare double and swap).

    -   The stolen list is traversed, and every element that is
        pending unchained is unchained and every element that is
        pending deletion is purged from the list.

    -   If after the first pass through the list the latch count is
        still 1, then

        --  traverse the stolen pending unchained/pending deleted
            list a second time and delete all of the elements.

    -   Else,

        --  add the stolen pending unchained/pending deleted list to
            the real pending unchained/pending deleted list via
            compare and swap.

      Despite its benefits, the shared latch algorithm is subject to
the following reliability issues:

o   no means to recover a corrupted latch count

    Since shared latch depends on the latch count returning to zero
    to trigger a purge of the pending unchained/pending deletion
    list, a corrupted latch count could cause storage exhaustion.

o   no means to control the size of the pending unchained/pending
    deletion list

   ...