Browse Prior Art Database

Enqueue Top for Recovery

IP.com Disclosure Number: IPCOM000052478D
Original Publication Date: 1981-Jun-01
Included in the Prior Art Database: 2005-Feb-11
Document File: 2 page(s) / 63K

Publishing Venue

IBM

Related People

Goldstein, BC: AUTHOR

Abstract

If a process dequeues an item off a FIFO (first in, first out)-double threaded queue for processing and then aborts, then a mechanism is provided to place the item back onto the queue (as part of recovery) so that it can be selected as the first candidate.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 100% of the total text.

Page 1 of 2

Enqueue Top for Recovery

If a process dequeues an item off a FIFO (first in, first out)-double threaded queue for processing and then aborts, then a mechanism is provided to place the item back onto the queue (as part of recovery) so that it can be selected as the first candidate.

When a failure occurs and a dequeued item has not been successfully processed, it needs to be placed back on the queue (as the next likely candidate for selection - so as not to violate the FIFO nature of the queue).

The following provides such a solution without serialization to normal enqueues of items onto the queue.

Before describing this, the following definitions and assumptions are given for the double threaded queue: 1) Assumes FIFO discipline

2) Each item on queue has a forward (FWD) and backward (BKWD)

pointer.

3) The queue anchor has a

- HEAD pointer (points to oldest item on queue)

- TAIL pointer (points to latest item on queue).

A pictorial representation of a double threaded queue including a queue anchor is shown in Fig. 1, where the high-order bit of TAIL is the ENQ-LOCK and the high-order bit of head is the DEQ-LOCK.

The algorithm for enqueue-top is presented in the flow chart of Fig. 2, where QI = item to be placed on queue and TAIL is initialized to point to itself.

1

Page 2 of 2

2

[This page contains 7 pictures or other non-text objects]