Browse Prior Art Database

Spin Queues

IP.com Disclosure Number: IPCOM000084515D
Original Publication Date: 1975-Nov-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 2 page(s) / 13K

Publishing Venue

IBM

Related People

Collier, WW: AUTHOR [+2]

Abstract

The following multiprocess contention problems are resolved by access serialization procedures and system constructs described below. Problem 1.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Spin Queues

The following multiprocess contention problems are resolved by access serialization procedures and system constructs described below. Problem 1.

In the course of contention for a shared resource, multiple processors may be required to examine a common flag in order to wait for the flag to be reset by another processor. In some computing systems the examining processors may lock out the resetting processor and prevent resetting of the flag. Problem 2.

In some multiprogrammed systems low-level processes in a control program may have to contend for a shared resource and be able to individually suspend execution, when the resource is already in use, without having to call upon suspension facilities which service higher level processes. Therefore a separate, low-level contend and suspend function may be needed.

Solution of these problems is predicated on the following assumptions. Assume that there are available within the computing system two instructions named Enqueue and Dequeue defined functionally as follows. Enqueue adds a specified element to a specified queue and indicates whether or not the queue was empty prior to its execution. Dequeue deletes a first element from a specified queue and indicates whether or not the queue is empty at the completion of its execution. Both instructions are atomic; that is, the execution of each is made by the system to appear indivisible. Solution to Problem 1.

Each processor, instead of spinning on the common flag, adds an element uniquely associated with that processor to a queue known as a Spin Queue which is shared by and addressable by all processors. The Spin Queue usage is such that one and only one processor at a time receives indication that its associated element occupies the first position on the queue. The processor having the first element in effect gains access to a shared resource associated with the queue, while all other processors spin on indivi...