Browse Prior Art Database

Queuing Functions on 65-Bit Multiprocessors when Requested Queue is Busy

IP.com Disclosure Number: IPCOM000114456D
Original Publication Date: 1994-Dec-01
Included in the Prior Art Database: 2005-Mar-28
Document File: 4 page(s) / 110K

Publishing Venue

IBM

Related People

Corrigan, MJ: AUTHOR [+5]

Abstract

The use of a software lock and a busy list for serializing access to a shared queue on a multitasking system is disclosed. The queue (Fig. 1) consists of a message list, a task list, a software lock bit, and a busy list. The task list contains tasks which are waiting for a message to be added to the queue. The busy list (Fig. 2) contains tasks that are waiting for the software lock and/or messages that couldn't be added to the message list because the software lock was held by a different task. The software lock serializes access to the queue's message and task lists, and access to all but the head pointer of the busy list. The ldarx (load doubleword and reserve) and stdcx (store doubleword conditional) instructions are used to serialize updates to the software lock and the head pointer of the busy list.

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

Queuing Functions on 65-Bit Multiprocessors when Requested Queue
is Busy

      The use of a software lock and a busy list for serializing
access to a shared queue on a multitasking system is disclosed.  The
queue (Fig. 1) consists of a message list, a task list, a software
lock bit, and a busy list.  The task list contains tasks which are
waiting for a message to be added to the queue.  The busy list (Fig.
2) contains tasks that are waiting for the software lock and/or
messages that couldn't be added to the message list because the
software lock was held by a different task.  The software lock
serializes access to the queue's message and task lists, and access
to all but the head pointer of the busy list.  The ldarx (load
doubleword and reserve) and stdcx (store doubleword conditional)
instructions are used to serialize updates to the software lock and
the head pointer of the busy list.

      A conventional software lock is used to serialize normal queue
updates such as adding or removing a message or task from the message
or task list.  The busy list (Fig. 2) is used only when a
serialization conflict arises--a task attempts to access the queue
and finds the software lock is already held by another task.  The
busy list is a linked list containing messages and/or task elements.
The addresses of messages and task elements are 8 bytes in length and
are always quadword aligned, so the 4 low-order address bits are
always 0.  The low-order bits of busy list pointers are used to hold
additional flags (Fig. 3).  These bits must be zeroed before using
the doubleword as a pointer.  The software lock for the queue is one
of the flags in the pointer to the first busy list entry.  The
doubleword containing this pointer and the lock bit will be referred
to as the "lock doubleword".  Ldarx and stdcx are used for all
updates to the lock doubleword.  Because the pointer and the lock bit
are in the same doubleword, they can be updated simultaneously with
the same stdcx instruction.  This prevents orphaned tasks (or
messages) that could otherwise result from one task linking itself
(or a message) onto the busy list while another task simultaneously
unlocks the queue.

      A task attempting to access the queue uses a ldarx to read the
lock doubleword and, if the lock bit is 0, uses stdcx to attempt to
set the lock bit.  This sequence is repeated until either the lock
bit read is 1 or the stdcx is successful:
  AttemptLock:
    temp = lock doubleword                  /* use ldarx */
    If lock bit = 1 goto LockBusy
    lock doubleword = temp + lock flag      /* use stdcx */
    If stdcx fails goto AttemptLock

      If the queue is busy (lock bit = 1), the task can link its own
task element to the front of the busy list.  Another flag bit
(BusyTask) is used to indicate that the pointer points to a task
waiting for the software lock.  If the task succeeds in linking
itself to the busy list,...