Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Simple Fetch And Add Solution to a Synchronized Signalling Problem

IP.com Disclosure Number: IPCOM000099376D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 6 page(s) / 202K

Publishing Venue

IBM

Related People

Rosenburg, BS: AUTHOR

Abstract

In a multiprocessor operating system, one processor must occasionally signal another to indicate a situation that requires immediate action. We describe a simple fetch&add algorithm for sending such signals under the additional requirement that the signalling processor wait for its signal to be processed.

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

Simple Fetch And Add Solution to a Synchronized Signalling Problem

       In a multiprocessor operating system, one processor must
occasionally signal another to indicate a situation that requires
immediate action.  We describe a simple fetch&add algorithm for
sending such signals under the additional requirement that the
signalling processor wait for its signal to be processed.

      In the course of developing an operating system for the RP3
multiprocessor, we had to solve a synchronized signalling problem
that can be abstracted as follows:
    -  There is one receiving processor.
    -  There are multiple sending processors.
    -  Occasionally a sender signals the receiver.
    -  Signals themselves carry no information.
    -  The receiver must process each signal individually.
    -  After sending a signal, a sender must wait until its
particular signal has been processed.

      Our solution to this problem assumes an underlying hardware
interprocessor interrupt mechanism with the following properties:

      -  One processor may request an interrupt in another processor.

      -  Once an interrupt has been requested, the target processor
will field an interprocessor interrupt as soon as its processor state
allows such interrupts.

      -  Multiple interrupt requests may result in a single
interrupt.

      -  A processor cannot tell when another processor fields an
interrupt.

      A simple solution to this problem is shown in Fig. 1. Its only
drawback is that it requires unbounded integer variables and
unbounded arithmetic.  In this disclosure we develop an algorithm
that is nearly as simple as the algorithm in Fig. 1 but requires only
32-bit integers and arithmetic.  It is probably equivalent to the
unbounded-integer version under some reasonable assumptions about how
far out-of-sync the sender and receivers can get. R,S: shared
unbounded integer Initially, R = S = O. Sender:
    T: private unbounded integer
    T  fetch&add (S, 1)
    Request_interrupt while (R&T) spin Receiver: On_interrupt:
    while (R<S) do
    Process_signal
    R    R + 1
    end Fig. 1.  Unbounded integer solution to the synchronous
signalling problem

      The algorithm in Fig. 1 uses a pair of shared,
unbounded-integer variables, R and S. R counts the number of signals
the receiver has processed, while S counts the number of signals the
senders have generated.  Each sender has a private, unbounded-integer
variable, T, that it uses to remember the particular signal the
sender generated.

      When a sender wishes to signal the receiver, it uses a
fetch&add operation to increment S, the total number of generated
signals.  The fetch&add also records the old value of S in the
private variable T, which therefore holds the number of signals
generated before the current signal.  The sender then requests that
an interprocessor interrupt be generated in the r...