Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1994-12-22
2001-06-12
Bonnokhah, Majid (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06247064
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to multiprocessing digital computer systems and particularly to instruction set architecture support for passing messages between concurrently executing processes and for synchronizing concurrently executing processes.
2. Background Information
The application of Merwin H. Alferness, et. al., Docket Number RA-3317, discloses a system architecture for providing improved message passing and process synchronization capabilities. Critical enhancements are made to operating system functions to permit processes executing within this system architecture to pass large messages between them without incurring large performance penalties associated with multiple copy operations on the message data. High level language support is provided in this system to enable an applications programmer to easily use the added functionality of the system. Hardware instruction set architecture support is also provided by the system to ensure that transfers of data and synchronization of communicating processes take place at machine speeds, rather than through multiple software layers of process control in the operating system.
The system architecture, known as the “Queuing Architecture,” uses queues as a mechanism for message passing and process synchronization. A queue client process places entries or events on a queue. A queue server process receives entries or events from a queue. An entry contains a message passed between a client process and a server process over the queue. The message consists of data or control information. An event is an indication that a condition known to both the client process and server process has occurred, but which contains no message. Thus, an event works as a synchronization mechanism between processes. Each entry on a queue is represented in a unit of storage called a queue bank. The queue bank has a control area and a text area. The control area contains control information and pointers to other entries on a queue. The text area contains the message data. In the preferred embodiment of the present invention, the text area of a queue bank is limited in size to 262,144 36-bit words. A queue bank may be a queue header or a queue entry. A queue is made up of one queue header and zero or more queue entries. The queue header holds control information for the queue. Queue entries hold the message data being passed between processes. To pass a message from one process to another process in the Queuing Architecture, the sending process inserts the message data into a queue entry and then enqueues it to a queue. The receiving process, which may be waiting on entries being placed on the queue, dequeues the queue entry and processes the message data.
The implementation of the enqueue operation is of crucial importance for this system architecture. If the act of placing a queue entry on a queue is too slow, overall performance of the system suffers because of the frequency of use of the enqueue operation. Furthermore, the enqueue operation should be performed without copying the message data contained in the queue entry in order to maximize system throughput. Existing message passing systems usually copy the message data from the sending process's virtual space into the system memory used to represent a mailbox. The data is then copied from the mailbox into the receiving process's virtual space. Ideally, the processing time required to perform this copying of the message data should be eliminated. It would be more efficient if a mechanism was provided in the architecture of the system such that the message data could be transferred between processes via a shared queue structure without the need for copying. If this enqueue operation could be performed by the hardware of the system, rather than by the operating system kernel, system performance could be greatly improved.
SUMMARY OF THE INVENTION
An object of this invention is to efficiently add message data to be transferred from a sending process to a receiving process to a shared queue without copying the message data.
Another object of this invention is to enqueue a queue entry to a queue shared by multiple communicating processes in one instruction.
Still another object of this invention is to provide an application programmer with instruction set architecture support for improved message passing and process synchronization capabilities.
Yet another object of this invention is to provide a specialized instruction, which is part of the instruction set architecture of a computer system, to enqueue message data or an event indicator to a queue structure shared by multiple communicating processes.
A further object of this invention is to provide an enqueue instruction for enqueuing a queue entry containing message data to be passed between communicating processes to a shared queue in a minimum amount of system processing time.
Another object of this invention is to provide an enqueue instruction for enqueuing a queue entry containing message data to the front of a shared queue.
Another object of this invention is to provide a new instruction to efficiently pass an event indicator from one process to another process.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the Drawings and Description of the Preferred Embodiment, with the scope and aspects of the invention defined in the appended Claims.
According to the present invention, the foregoing and other objects and advantages are attained by a new instruction which adds a queue entry containing message data to be transferred from a sending process to a receiving process to a queue shared by the processes. If desired by the programmer, in lieu of adding a queue entry containing message data, the new instruction inserts an event indicator into the shared queue structure, thereby providing synchronization capabilities between the two communicating processes.
In accordance with an aspect of this invention, a computer system, executing multiple processes controlled by an operating system, has at least one processor for executing instructions and a main storage unit accessible by the processes. The main storage unit has units of data storage called queue banks, wherein each queue bank represents a queue header element or a queue entry element of a queue. The queue, which is a linked list of one queue header and zero or more queue entries, is shared by communicating processes. Each queue entry contains a group of data signals (i.e., the message data) to be communicated from one process to another. The queue header contains control information and an event indicator, which is used for process synchronization. The system supports interprocess communication by executing an enqueue instruction, which is part of the instruction set architecture of the system. The implementation details of the enqueue instruction include mechanisms for accessing a queue and a new queue entry, and for linking the new queue entry to the selected queue.
In accordance with another aspect of the invention, a method of executing a single instruction to add a new queue entry to a queue shared by multiple communicating processes comprises the steps of calculating the address of the queue header of a queue selected by the operands of the instruction, calculating the address of the new queue entry selected by the operands of the instruction, and updating the links in the queue header and queue entries to add the new queue entry to the queue.
Still other objects 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
Alferness Merwin H.
Caldarale Charles R.
Johnson David C.
Johnson David R.
McBreen James R.
Bonnokhah Majid
Caldwell P G
Johnson Charles A.
McMahon Beth L.
Starr Mark T.
LandOfFree
Enqueue instruction in a system architecture for improved... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enqueue instruction in a system architecture for improved..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enqueue instruction in a system architecture for improved... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2518286