Protected Shared Latch
Original Publication Date: 1994-Feb-01
Included in the Prior Art Database: 2005-Mar-26
Brown, DD: AUTHOR [+4]
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.
Protected Shared Latch
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
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
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
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
list a second time and delete all of the elements.
-- add the stolen pending unchained/pending
deleted list to
the real pending unchained/pending deleted list via
compare and swap.
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