Electrical computers and digital processing systems: interprogra – Interprogram communication using shared memory
Reexamination Certificate
1999-07-22
2004-10-05
Follansbee, John (Department: 2154)
Electrical computers and digital processing systems: interprogra
Interprogram communication using shared memory
Reexamination Certificate
active
06802066
ABSTRACT:
A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all copyright rights whatsoever.
FIELD OF THE INVENTION
The subject invention relates generally to computer systems and more particularly to a software implemented lockless circular buffer.
BACKGROUND OF THE INVENTION AND RELATED ART
In the past, emulation software has been employed together with a number of microprocessor chips to emulate mainframe hardware. Such emulation software is comprised of many processes, each of which emulates a piece of prior art hardware, such as a central processor, an I/O processor or a task control unit. The processes request actions from each other by sending messages. Each message is 4 (64-bit) words long. For the system to function properly, the receiving process must receive messages in the order they are sent. Message ordering is critical. For example, a first of two messages might indicate a first value to be written in a disk storage space and the second message an update of that value. If the messages are reversed, the incorrect value will be stored on disk.
The emulator implements message ordering by establishing a circular buffer for each process—a fixed length area where messages are placed when they are sent to the process. Sending processes put messages in each successive slot in the buffer, and the receiving process retrieves them in the same order, according to a first-in, first-out (FIFO) protocol. Thus, each process can have at most a fixed number of messages waiting to be processed.
Several processes can be simultaneously attempting to send a message to a particular process. To prevent the loss of messages, the implementation must ensure that each process uses a unique slot in the buffer. In the prior art, locking mechanisms such as Mutexes, Semaphores, or Critical Regions have been employed to control and order access to the buffer. Such “locking” approaches are notoriously slow since one process must wait while another process has a lock on the buffer.
SUMMARY OF THE INVENTION
The invention provides a lockless circular buffer. Slots in the buffer are assigned using a counter which is incremented atomically. In this manner, a process can fetch the counter from memory, increment it by 1, and store it back into memory without the possibility of interruption by another process. This “atomic” operation assures that a unique slot number will be assigned to each process request, even though such requests occur simultaneously. Two counters are kept for each buffer: one contains the number of messages inserted and the other contains the number of messages removed. The number of the last message removed is used to resolve overflow situations where the buffer fills up, resulting in two processes being assigned the same slot number.
Still other objects, features and advantages of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein is shown and described only the preferred embodiment of the invention, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive, and what is intended to be protected by Letters Patent is set forth in the appended claims. The present invention will become apparent when taken in conjunction with the following description and attached drawings, wherein like characters indicate like parts, and which drawings form a part of this application.
REFERENCES:
patent: 4623997 (1986-11-01), Tulpule
patent: 4635254 (1987-01-01), Tulpule et al.
patent: 5339418 (1994-08-01), East et al.
patent: 5797035 (1998-08-01), Birrittella et al.
patent: 5920719 (1999-07-01), Sutton et al.
patent: 6557056 (2003-04-01), Lanteigne et al.
Carden, IV Robert Clinton
Irving Michael James
Cass Nathan
Follansbee John
Patel Haresh
Rode Lise A.
Starr Mark T.
LandOfFree
Method and system to share circular buffer without 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 system to share circular buffer without using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system to share circular buffer without using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3304352