MESSAGE PASSING USING SHARED MEMORY OF A COMPUTER
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14)
-
-
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. - View Dependent Claims (18, 19, 20)
-
Specification