Hierarchical queuing in a system architecture for improved message passing and process synchronization

• US 5,555,396 A
• Filed: 12/22/1994
• Issued: 09/10/1996
• Est. Priority Date: 12/22/1994
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: Johnson, David R., McBreen, James R., Caldarale, Charles R., Kerzman, Joseph P., Alferness, Merwin H.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): CHOW, CHRISTOPHER S
• Application Number:
  US08/362,034
• Time in Patent Office: 628 Days
• Field of Search: 395/872, 395/874, 395/876, 395/200.14, 395/474, 395/480, 395/492, 395/200.17, 395/200.18, 364/514 C
• US Class Current: 711/147
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A system and method for interprocess communication between concurrently executing, cooperating sequential processes in a digital computer system uses a shared memory queue as a mechanism for message passing and process synchronization. Data to be transferred from a sending process to a receiving process is stored in a queue entry on the shared memory queue. Hierarchical queuing allows a sending process to collect multiple message segments as entries in a local sub-queue, which is enqueued as a single entity to the shared memory queue when all message segments are present. The receiving process dequeues the sub-queue in one operation, thereby increasing the efficiency of message transfer while preventing the erroneous dequeuing of message segments when multiple receiving processes are waiting on the same shared memory queue. In this manner, the logical maximum size of a message being passed between processes is expanded.

Claims

1. In a system having a plurality of processes controlled by a computer operating system, the system including at least one instruction processor coupled to a main storage unit, units of data storage residing in the main storage unit called queue banks, each queue bank being capable of representing a queue header element or a queue entry element of a queue, each queue including one queue header and zero or more queue entries, a queue being the mechanism by which processes can communicate with each other and containing attributes describing its use, a queue entry being used for storing message data, the computer operating system having a function for creating a primary queue in response to a request from a first process, a system for providing inter-process communication without copying message data or requiring computer operating system action comprising:

(a) local queue creation means for creating a local queue in the main storage unit, said local queue being accessible only to the first process creating said local queue, said local queue having a queue header and at least one queue entry, and for storing a plurality of multi-word messages to be transferred from the first process to a second process into said at least one queue entry;

(b) enqueue means for adding said queue header of said local queue as a queue entry to a primary queue without performing a data copy of said plurality of multi-word messages and without requiring actions to be taken by the computer operating system, in response to an enqueue request from the first process; and

(c) dequeue means for removing said queue header of said local queue from said primary queue in response m a dequeue request from said second process, whereby access is provided to said plurality of multi-word messages stored in said at least one queue entry of said local queue to said second process, without performing a data copy of said plurality of multi-word messages and without requiring actions to be taken by the computer operating system, and wherein said second process gains concurrent access to said plurality of multi-word messages.

2. In a system having at least first and second processes being controlled by a computer operating system, the system including at least one instruction processor coupled to a main storage unit, units of data storage residing in the main storage unit called queue banks, each queue bank being capable of representing a queue header element or a queue entry element of a queue, each queue including one queue header and zero or more queue entries, a queue being the mechanism by which processes can communicate with each other and containing attributes describing its use, a queue entry being used for storing message data, a method of interprocess communication without copying message data or requiring computer operating system action comprising the steps of:

(a) creating a primary queue in the main storage unit, said primary queue having a queue header and zero or more queue entries, wherein each of said queue entries stores message data to be transferred from the first process to the second process;

(b) creating a local queue in the main storage unit, said local queue having a queue header and at least one queue entry;

(c) storing a plurality of multi-word messages to be transferred from the first process to the second process in said at least one queue entry of said local queue;

(d) adding said local queue to said primary queue by enqueuing said queue header of said local queue as a queue entry in said primary queue without performing a data copy of said plurality of multi-word messages and without requiring actions to be taken by the computer operating system; and

(e) removing said local queue from said primary queue by dequeuing said queue header of said local queue, thereby providing access to said plurality of multi-word messages stored in said at least one queue entry of said local queue for the second process, without performing a data copy of said plurality of multi-word messages and without requiring actions to be taken by the computer operating system.

3. In a computer system having a queuing architecture to support interprocess communication between at least first and second processes being executed by at least one processor coupled to a main storage unit and controlled by a computer operating system, units of data storage residing in the main storage unit called queue banks, each queue bank being capable of representing a queue header element or a queue entry element of a queue, each queue including one queue header and zero or more queue entries, a queue being the mechanism by which princesses can communicate with each other and containing attributes describing its use, a queue entry being used for storing a multi-word message segment, a method of interprocess communication without copying message segments comprising the steps of:

(a) creating a primary queue in the main storage unit;

(b) creating a local queue in the main storage unit;

(c) storing a multi-word message segment into a queue bank;

(d) adding said queue bank as a queue entry to said local queue by enqueuing said queue bank to said local queue without performing a data copy of said multi-word message segment and without requiring actions to be taken by the computer operating system;

(e) repeating steps (c) and (d) for all said message segments to be sent from the first process to the second process that must be processed by the second process together as a complete message;

(f) adding said local queue to said primary queue by enqueuing said queue header of said local queue as a queue entry in said primary queue without performing a data copy of said multi-word message segment and without requiring actions to be taken by the computer operating system, and;

(g) removing said local queue from said primary queue by dequeuing said queue header of said local queue without performing a data copy of said multi-word message segment and without requiring actions to be taken by the computer operating system, thereby providing access to said complete message for the second process.

4. A method as in claim 3, wherein said adding local queue to said primary queue step adds said local queue to the front of said primary queue.