Browse Prior Art Database

Mutual Exclusion Algorithm for a Distributed Environment

IP.com Disclosure Number: IPCOM000105427D
Original Publication Date: 1993-Jul-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 2 page(s) / 64K

Publishing Venue

IBM

Related People

Schwendemann, W: AUTHOR [+2]

Abstract

Disclosed is a basic technique to serialize use of a shared resource in a "distributed environment". The algorithm goes as follows:

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

Mutual Exclusion Algorithm for a Distributed Environment

      Disclosed is a basic technique to serialize use of a shared
resource in a "distributed environment".  The algorithm goes as
follows:

o   there exists central controller whose job it is to grant
    exclusive of a "shared resource" to only one process in the
    "network".  It maintains a queue of "outstanding" requests to use
    the resource.

o     before a "process" uses a shared resource, it first sends a
    request to the central controller.

o   the central controller sends a message to the processes telling
    it that it can use the resource.

o   when a process is finished with the "shared resource", it sends a
    "completed" message back to the central controller.

o   Upon receipt of a completed message, the central controller sends
    a message to the next process in the queue informing it that it
    can now use the resource.

      The problem with this approach is that it requires 3 messages
to be sent - urequest, permission to use, and completion messages.

      The algorithm described in this disclosure has the advantage of
reducing the number of "completion messages" that need to be sent.
This algorithm still makes use of a "central controller".

Below is the Central Controller Logic

o   Initial State

    -   request queue is empty
    -   set flag to indicate resource is not in use (i.e., off)

o   Runtime State

    -   listen for incoming "request to use resource" or "completed"
        message.
    -   if the message received is a "request to use" message, then
        --  if "resource in use" flag is set off

o   send "permission to use" message to requestor

o   turn "resource in use" flag on

    -   else add requestor to the "waiting" queue
        --  else a "completed" message must have been received
    -   if "waiting" queue is empty, turn "resource in use" flag off
        flag to off
    -   else

o   turn "resource in use" flag to on

o   send "pe...