MESSAGE PASSING USING SHARED MEMORY OF A COMPUTER

• US 20030061395A1
• Filed: 06/29/1998
• Published: 03/27/2003
• Est. Priority Date: 06/29/1998
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: MCKENNEY, PAUL E., KINGSBURY, BRENT A., SULMONT, JEAN-MARIE CHRISTIAN
• Granted Patent: US 6,629,152 B2
• Time in Patent Office: Days
• US Class Current: 719/312
• CPC Class Codes: G06F 9/3004 to perform operations on memory
• CPC Class Codes: G06F 9/30087 Synchronisation or serialisation instructions
• CPC Class Codes: G06F 9/544 Buffers; Shared memory; Pipes
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A lock-free mechanism is provided for successfully passing messages between processes even if a process is preempted while sending or receiving a message. Messages are communicated between processes using a mailbox data structure stored in memory shared by the processes, without the use of locks or other mutual exclusion entities that would otherwise limit concurrent delivery and receipt of messages placed in the data structure. The data structure in the illustrative embodiment includes one or more message slots for storing messages placed in the data structure and a number of state variables for inserting messages into and removing messages from the message slots. A process sends or retrieves messages by manipulating the state variables using indivisible atomic operations. This ensures that a process cannot be preempted from message passing until it finishes executing the atomic instruction. The method and mechanism have particular value in distributed shared memory (DSM) and non-uniform memory access (NUMA) machines.

Claims

1. A method for communicating messages between processes via memory of a computer, the method comprising:

providing a mailbox data structure for a second process in memory accessible to a first process and the second process, the data structure having one or more message slots for storing messages sent to the data structure and an availability indicator for indicating if a message slot is available for receiving a message; and

sending a message from the first process to the second process via the mailbox data structure including;

obtaining, in an atomic operation, the present value of the availability indicator and changing the present value to a new value;

determining from the present value of the indicator if a message slot is available for receiving a message; and

sending the message to the data structure if a message slot is available.

2. The method of claim 1 wherein the computer is a distributed shared memory multiprocessor comprised of multiple nodes each with at least one processor and local memory, and the providing step comprises allocating shared memory for the mailbox data structure on a predetermined node associated with the second process.

3. The method of claim 2 wherein the second process is associated with an instance of message-passing software.

4. The method of claim 1 wherein the atomic operation comprises fetching the present value of the indicator, returning the present value, and incrementing the present value to the new value.

5. The method of claim 1 wherein the mailbox data structure includes a location indicator for indicating a location of an available slot, and the sending step includes:

obtaining, in an atomic operation, the present value of the location indicator to identify an available slot and changing the present value to a new value; and

sending the message to the identified slot.

6. The method of claim 5 including making the sending of the message to the identified slot visible to all processors of the computer that execute processes for sending messages.

7. The method of claim 1 wherein the mailbox data structure includes a presence indicator for indicating whether a message is present in a message slot, and the sending step comprises changing, in an atomic operation, the value of the presence indicator to indicate that a message is present in a message slot of the mailbox data structure.

8. The method of claim 7 including:

determining from the presence indicator that a message is present in a message slot;

removing the message from the slot; and

changing, in an atomic operation, the value of the presence indicator to indicate that the message is no longer present in the message slot.

9. The method of claim 8 including changing, in an atomic operation, the value of the availability indicator to indicate that a message slot is available.

10. A computer-readable medium on which is stored instructions of a computer program for executing the steps of claim 1.

11. The method of claim 1 including restoring, in an atomic operation, the value of the availability indicator to the present value if it is determined that a message slot is not available.

12. A mailbox data structure stored in memory of a computer for communicating messages via memory between processes, the data structure comprising:

a set of message slots storing messages sent to the data structure; and

a set of indicators manipulatable by an atomic operation for inserting messages into and removing messages from the message slots.

13. The data structure of claim 12 wherein the set of indicators is a set of state variables comprising:

a first variable indicating if a message slot is available for storing a message;

a second variable indicating a location of an available slot;

a third variable indicating whether a sent message has been received in a message slot; and

a fourth variable indicating a location of a slot containing a received message.

14. A computer-readable medium on which is stored the data structure of claim 12.

15. A multiprocessor computer with distributed shared memory, the computer comprising:

a multiple of nodes each with one or more processors and local memory;

a mailbox data structure stored in a local memory for communicating messages via shared memory between processes, the data structure comprising;

a set of message slots storing messages sent to the data structure; and

an availability indicator for indicating if a message slot is available for receiving a message; and

a set of instructions stored in a computer-readable medium for sending a message to the mailbox data structure including;

obtaining, in an atomic operation, the present value of the availability indicator and changing the present value to a new value;

determining from the present value of the availability indicator if a message slot is available for receiving a message; and

sending the message to the data structure if a message slot is available.

16. A method for communicating messages between processes via memory of a distributed shared memory multiprocessor computer, the computer having a multiple of nodes each with at least one processor and memory, the method comprising:

providing a mailbox data structure for a second process in the memory of a second node, the data structure having one or more message slots for storing messages sent to the data structure and an availability indicator for indicating if a message slot is available for receiving a message; and

sending a message from a first process on a first node to the second process on the second node via the mailbox data structure on the second node including;

in an atomic operation, obtaining the present value of the availability indicator and changing the present value to a new value;

determining from the present value of the indicator if a message slot is available for receiving a message; and

sending the message to the data structure if a message slot is available.

17. A method for communicating messages between processes via memory of a computer, the method comprising:

providing a mailbox data structure for a second process in memory accessible to a first process and the second process, the data structure having one or more message slots for storing messages sent to the data structure and presence indicator for indicating if a message is present in a message slot; and

receiving a message sent from the first process to the second process via the mailbox data structure including;

determining from the presence indicator that a message is present in a message slot;

removing the message from the slot; and

changing, in an atomic operation, the value of the presence indicator to indicate that the message is no longer present in the message slot.

18. The method of claim 17 wherein the mailbox data structure includes a location indicator for indicating the next slot containing a message to be retrieved, and the method includes advancing the location indicator past the message slot containing the message and past succeeding message slots containing messages previously read out of order.

19. The method of claim 17 wherein the mailbox data structure includes an availability indicator for indicating if a message slot is available for receiving a message, and the method includes changing, in an atomic operation, the value of the availability indicator to indicate that the message slot is now available for receiving a message.

20. A computer-readable medium on which is stored instructions of a computer program for executing the steps of claim 17.