Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-06-27
2002-05-07
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06385658
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates generally to communications in a computer system and more particularly to performing synchronized message passing in a computer system using shared resources.
As it is known in the art, message passing is one means of communicating between two or more processes. Messages can be sent between two or more processes executing in the same computer system, or between processes executing in different computer systems. Using message passing, a first process wishing to communicate with a second process sends the second process a message. The message is typically a quantity or packet of data sent from the first process to the second process.
One class of techniques for communicating messages between two processes uses a single shared list in which there is always a buffer of one element in the list. A receiving process reads and processes a first message sent from a sending process only when a second message has been added to the list, such as when the sending process sends a second message to the receiving process. In other words, the receiving process does not read, process, and delete a message until the message being accessed by the receiving process is not the same as the one being sent by the sending process. Such a technique only provides for message communication in one direction between two processes.
Another class of techniques for communicating messages between two processes, process A and process B, uses a portion of memory that is shared between processes A and B and contains two shared message lists. The first shared list includes messages sent from process A to process B, and the second shared list includes messages sent from process B to process A. Both shared lists are accessed by each of the processes A and B either to send a message to the other process, or receive its own messages. For example, the first shared list is accessed by process A to send a message to process B by adding the message to the first shared list. The first shared list is also accessed by process B to read messages it receives by removing a message from the first shared list.
Typically, data operations requiring access to one of the shared lists are included in a “critical section” of machine executable code providing exclusive access to a shared resource, such as a list, to an accessing process. Thus, when a process executes an operation in a critical section, it is guaranteed exclusive access to the shared resource.
To provide for synchronization of a shared resource within a critical section, an operating system usually employs a locking mechanism by which a shared resource, such as the foregoing two shared lists included in the portion of memory, is exclusively accessed by one of multiple processes. For example, when one of the two processes, A and B, executes a data operation in a critical section to access the first shared list, a locking mechanism insures that the other process is excluded from also accessing the first shared list. A typical example of such locking mechanisms is the semaphore.
One of the drawbacks of the foregoing technique of a critical section with a locking mechanism is the performance overhead incurred by using the locking mechanism to implement the mutual exclusion. The additional overhead includes requesting, obtaining, and releasing a lock on a shared resource each time a process is accessing the shared resource. This additional overhead adversely impacts system performance, for example, by increasing execution time and requiring computer system resources to instantiate the locking mechanism.
Another drawback of the foregoing technique occurs in the event of an uneven flow of message traffic between processes A and B. If process A sends more messages to process B than process B sends to process A, there is an uneven flow of messages between process A and process B. If processes A and B each allocate their own message buffers, as used for storing data of a message, process A may request additional memory for a message buffer to send a message to process B while process B has unused message buffers. Thus, process A may require an excessive amount of memory for message buffers while process B has message buffers available for use.
To provide for message buffer allocation while minimizing memory requirements in the event of uneven message traffic between process A and process B, a third shared list including “free” or available memory buffers is used. In other words, rather than have process A and process B each individually allocate memory for a message buffer when needed, a third shared list of available message buffers is used by both process A and process B. When process A or process B requires a message buffer to send a message, it first attempts to obtain an available message buffer from the third shared list of free message buffers.
Using this third shared list is an improvement over the previously described technique in that use of the third shared list provides for adaptive message buffer allocation that minimizes memory allocation in the event of uneven message traffic between processes. However, a drawback of the use of a third shared list is that it represents an additional resource that is shared by process A and process B. Thus, a critical section is additionally required for data operations performed to obtain an available message buffer from the shared free list. Generally, using this third shared list further degrades system performance due to the additional use of the locking mechanism.
Thus, there is required an efficient technique for bidirectional message communication between processes which does not require global locking mechanism for synchronization, and which provides adaptive message buffer allocation in the event of uneven message traffic.
SUMMARY OF THE INVENTION
In accordance with principles of the present invention, to facilitate communication between a first and second process, access to shared resources is synchronized through discipline imposed upon updating and accessing the shared resources without requiring a global locking mechanism for synchronization.
In accordance with one aspect of the invention is a method for sending messages from the first process to the second process. The method includes initializing a first message buffer containing message data, and adding the first message buffer to a list of incoming messages to the second process. Initializing the first message buffer includes setting a first flag indicating that the first message buffer contains a message not yet completely processed by the second process, and setting a first link field indicating that the first message buffer is the last message in the list of incoming messages to the second process. The list of incoming messages to the second process includes a second message buffer. The step of adding the first message buffer includes updating a second link field associated with the second message buffer to identify the first message buffer being added.
Further in accordance with another aspect of the invention is an apparatus for sending a message from a first process to a second process. The apparatus includes a first data structure, a second data structure, and a messsage buffer. The first data structure is associated with the first process and includes a remote tail pointer identifying an incoming message associated with the second process. The second data structure is associated with the second process and includes a head pointer to the incoming message list associated with the second process. The message buffer includes a link field identifying a next message in the incoming message list, and a state field indicating whether the message buffer has been processed by the second process.
Further in accordance with yet another aspect of the invention is a method for allocating a message buffer from a free list when sending a message between a first and second process. The method includes determining if the free list includes at least three message buffers and removing a message buffer from one end of the free li
Fraser, Jr. James Ian
Harter, Jr. Paul Karl
Bullock, Jr. Lewis A.
Compaq Information Technologies Group L.P.
Courtenay III St. John
Hamilton Brook Smith & Reynolds P.C.
LandOfFree
Method and apparatus for synchronized message passing using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for synchronized message passing using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for synchronized message passing using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2847080