Browse Prior Art Database

Wait Free Interprocess Communication Mechanisms

IP.com Disclosure Number: IPCOM000076914D
Original Publication Date: 1972-May-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Collier, WW: AUTHOR [+2]

Abstract

The following series of programmable routines allow one specific process (i.e. program) in a computer system to send an indefinite number of messages to exactly one other process. No message may be lost or received out of order. Once the sender has completed sending a message, the receiver must be able to receive the message (this rules out the case in which the sender tries, but fails, to send a message and so it tries again when it next sends another message). Each process must operate in such a fashion that the other process cannot tell that the first process is active. In particular, neither process can wait for the other to become inactive, such as in a multiprogrammed computer system.

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

Page 1 of 2

Wait Free Interprocess Communication Mechanisms

The following series of programmable routines allow one specific process
(i.e. program) in a computer system to send an indefinite number of messages to exactly one other process. No message may be lost or received out of order. Once the sender has completed sending a message, the receiver must be able to receive the message (this rules out the case in which the sender tries, but fails, to send a message and so it tries again when it next sends another message). Each process must operate in such a fashion that the other process cannot tell that the first process is active. In particular, neither process can wait for the other to become inactive, such as in a multiprogrammed computer system.

In the procedural descriptions which follow (using the PL/1 programming language), certain names possess the same or similar meaning wherever used. The sending process is named ENQUEUE since it passes a message by placing it on a list. For the same reason the receiver is called DEQUEUE. NQELEM is the input parameter to ENQUEUE; it is the address of an element containing the message to be sent plus control information. DQELEM is an output parameter from DEQUEUE; it is zero if DEQUEUE finds no waiting message; otherwise it is the address of the element containing the found message. LNKFLD is the name of the link field used for queuing elements together. MSG is a field containing a message to be passed; it is N characters long. Temporary variables have `TEMP' embedded in their name. An address pointing to the head (tail) of a queue will have a "HEAD" ("TAIL") embedded in its name. The brackets, -1 and 1-, indicate the beginning and end, respectively, of an indivisible operation. A List with Only One Server.

ENQUEUE should both add elements to and delete elements from the queue. DEQUEUE should only scan down the queue for elements containing new messages. The specific action of the two processes is shown below. ENQUEUE: PROC (NQELEM); DCL (NQHEAD,NQTAIL,DQHEAD,NQELEM) PTR(31), 1 ELEM BASED(NQHEAD), 2 LNKFLD PTR(31), 2 MSG CHAR(N); NQTAIL - > LNKFLD = NQELEM; NQTAIL = NQELEM; L5: IF NQHEAD = DQHEAD THEN GO TO L8; NQHEAD = LNKFLD; GO TO L5; L8: IF NQHEAD =0 THEN RETURN; NQHEAD = NQELEM; DQHEAD = NQELEM; RETURN; END ENQUEUE; DEQUEUE: PROC(OUTMSG); DCL DQHEAD PTR(31); 1 ELEM BASED(DQHEAD), 2 LNKFLD PTR(31), 2 MSG CHAR(N), OUTMSG CHAR(N); If DQHEAD=0 THEN RETURN; OUTMSG = MSG; DQTEMP = LNKFLD; DQHEAD = DQTEMP; RETURN; END DEQUBUE;.

Care must be taken that NQTAIL is initialized so that the first time the first statement in ENQUEUE is executed, NQELEM is stored in some innocuous- location (such as NQTAIL).

A failure occurs if LNKFLD is moved to DQTEMP by DEQUEUE, and if the entire ENQUEUE procedure is then executed before DEQUEUE completes (an element is left on the queue which DEQUEUE doesn't find). This bug...