Enqueue instruction in a system architecture for improved message passing and process synchronization

• US 6,247,064 B1
• Filed: 12/22/1994
• Issued: 06/12/2001
• Est. Priority Date: 12/22/1994
• Status: Expired due to Term

• Current Assignee: Unisys Corporation
• Original Assignee: Unisys Corporation
• Inventors: McBreen, James R., Caldarale, Charles R., Johnson, David C., Johnson, David R., Ward, Wayne D., Alferness, Merwin H.
• Primary Examiner(s): Bonnokhah, Majid
• Assistant Examiner(s): CALDWELL, PATRICIA G
• Application Number:
  US08/361,626
• Time in Patent Office: 2,364 Days
• Field of Search: 395/100, 395/375, 395/200.13, 395/250, 364/244.3, 709/310-332, 709/100-108, 709/200, 709/237, 709/223, 709/215, 710/54, 711/169, 713/502
• US Class Current: 719/312
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A system and method for adding a queue entry containing message data to a queue shared by communicating, sequential processes includes an enqueue instruction. The enqueue instruction attaches a queue entry to either the tail or the head of the shared queue, as specified by an application programmer. Execution of the enqueue instruction includes blocking access to the queue by other processes, updating queue linkages, activating processes waiting on entries being made to the queue, monitoring interrupts, and validating the appropriate queue data structures. If desired, in lieu of adding a queue entry containing message data to the queue, the enqueue instruction inserts an event indicator into the shared queue structure, thereby providing synchronization capabilities between communicating processes.

Claims

1. In a computer system executing a plurality of processes controlled by a computer operating system, the computer system having at least one processor for executing instructions and a main storage unit directly accessible by the plurality of processes, units of data storage residing in the main storage unit called queue banks, each of the queue banks being capable of representing a queue header element or a queue entry element, the computer system further having one or more queues, each of the one or more queues including a linked list of one queue header and zero or more queue entries, a queue entry being used for storing a group of data signals to be communicated between selectable sending ones and selectable receiving ones of the plurality of processes, the queue header being used to store queue control information including queue links and an event indicator, an enqueue system supporting interprocess communication by one of the selectable sending ones of the plurality of processes executing an enqueue instruction available as part of the instruction set architecture of the computer system, the enqueue system supporting interprocess communication comprising:

queue access means for allowing the one of the selectable sending ones of the plurality of processes to directly read from, and to directly write to, a selected queue selected by the enqueue instruction;

queue entry access means for reading from and writing to a new queue entry selected by the enqueue instruction; and

queue updating means for modifying the queue links connecting the queue header and the queue entries of said selected queue to add said new queue entry to said selected queue and to remove said new queue entry from the visibility of the one of the selectable sending ones of the plurality of processes.

2. The enqueue system supporting interprocess communication of claim 1, wherein said queue updating means performs an enqueue to front operation to modify said queue links connecting said queue header and said queue entries of said selected queue to add said new queue entry to said selected queue following said queue header of said selected queue, if said enqueue to front operation is allowed by said queue header of said selected queue.

3. The enqueue system supporting interprocess communication of claim 1, further including means for modifying the event indicator in said queue header of said selected queue to communicate that an event has occurred.

4. The enqueue system supporting interprocess communication of claim 1, further including means for activating a previously suspended one of the plurality of processes in response to said new queue entry being added to said selected queue if said selected queue had no queue entries or in response to the event indicator in said queue header of said selected queue being changed to indicate that an event has occurred.

5. A computer system for executing a plurality of processes controlled by a computer operating system having at least one processor for executing instructions and a main storage unit directly accessible by the plurality of processes wherein the main storage unit is capable of storing one or more queues, each of the one or more queues being a linked list of one queue header linked through queue links to zero or more queue entries, an interprocess communication supporting system, comprising:

a plurality of queue banks residing in the main storage unit, each of said queue banks to represent a queue header or a queue entry, each queue entry to store control signals and message data received from an identified one of the plurality of processes, each said queue header to include control signals and an event indicator;

instruction processing circuitry included in the processor and directly coupled to the main storage unit to execute, within said identified one of the plurality of processes, an enqueue instruction to add a new queue entry to a selected one of the one or more queues, said enqueue instruction having operands to select said new queue entry and said selected one of the one or more queues, said enqueue instruction processing circuitry including;

queue access circuitry to read from and write to said selected one of the one or more queues;

queue entry access circuitry to read from and write to said new queue entry; and

queue updating circuitry to update the control signals included in said selected one of the one or more queues and to update the control signals included in said new queue entry to add said new queue entry to said selected one of the one or more queues and to remove said new queue entry from the visibility of said identified one of the plurality of processes.

6. The interprocess communication supporting system of claim 5, wherein said queue updating circuitry modifies the queue links connecting the queue header and the queue entries of said selected one of the one or more queues to add said new queue entry to the head of said selected one of the one or more queues, if enqueuing to the head of said selected one of the one or more queues is allowed by said queue header.

7. The interprocess communication supporting system of claim 5, further including a modifying circuit to modify the event indicator in said queue header of said selected one of the one or more queues to communicate that an event has occurred.

8. The interprocess communication supporting system of claim 5, further including an activating circuit to activate a previously suspended one of the plurality of processes in response to said new queue entry being added to said selected one of the one or more queues if said selected one of the one or more queues had no queue entries or in response to said event indicator in said queue header of said selected one of the one or more queues being changed to indicate that an event has occurred.

9. In a computer system having at least one processor for executing instructions, including an enqueue instruction which is part of the instruction set architecture of the computer system, the computer system further having units of data storage called queue banks, the at least one processor for executing a plurality of processes, each of the queue banks being capable of representing a queue header element or a queue entry element, each of the queue banks containing a control area for holding control information and a text area for holding message data words, the computer system further having a plurality of queues, each of the plurality of queues being a linked list of one queue header connected through links to zero or more queue entries, the links being stored in the control area of the queue banks representing the queue header and queue entries, each queue bank being accessed using a pointer stored in a queue bank descriptor data structure, queue bank descriptor data structures not currently in use being saved in an inactive queue bank descriptor list, and a queue being accessed via the queue bank descriptor data structure of its queue header, a system for executing an enqueue instruction by a sending one of the plurality of processes, the enqueue instruction to send message data words from the sending one of the plurality of processes to a receiving one of the plurality of processes by adding a new queue entry to a shared queue that is directly accessible to both the sending one of the plurality of processes and to the receiving one of the plurality of processes, an interprocess communication support system comprising:

first address calculation means for calculating the address of the queue bank descriptor data structure of the queue header of a selected shared queue selected by the operands of the enqueue instruction;

queue access means for providing read and write access to said queue header and queue entries of said selected shared queue using the pointer stored in said queue bank descriptor data structure of said queue header of said selected shared queue;

second address calculation means for calculating the address of the queue bank descriptor data structure of a new queue entry selected by said operands of the enqueue instruction;

queue entry access means for allowing said sending one of the plurality of processes to directly read from and to directly write to said new queue entry using the pointer stored in the queue bank descriptor of said new queue entry;

storage means for storing the number of message data words being stored in the text area of said new queue entry into the control area of said new queue entry;

queue update means for updating the links in the control area of said queue header and in the control area of the last queue entry of said selected shared queue to point to said new queue entry, thereby adding said new queue entry to the end of said selected shared queue; and

queue bank descriptor maintenance means for returning said queue bank descriptor data structure of said new queue entry to the inactive queue bank descriptor list for preventing said sending one of the plurality of processes from further writing to said new queue entry.

10. The an interprocess communication support system of claim 9, further including means for activating a previously suspended one of the plurality of processes in response to said new queue entry being added to said selected shared queue if said selected shared queue had no queue entries or in response to the event indicator in said queue header of said selected shared queue being changed to indicate that an event has occurred.

11. In a computer system having at least one processor for executing instructions which are included in the instruction set of the computer system, the computer system further having units of data storage called queue banks, each queue bank being capable of representing a queue header or a queue entry, each queue bank containing a control area for holding control information and a text area for holding message data words, the computer system further having one or more queues, each of the one or more queues being a linked list of one queue header and zero or more queue entries wherein the one queue header and zero or more queue entries are interconnected via links, the links being stored in the control area of the queue banks representing the queue header and queue entries, the computer system having at least one client process and at least one server process, the at least one client process being capable of directly accessing the queue, and the at least one server process being capable of directly accessing the queue, executing a single instruction by the processor within said client process to add a new queue entry to a queue to support interprocess communication, the method comprising the steps of:

(a) calculating the address of the queue header of a selected one of the one or more queues selected by the operands of the instruction;

(b) calculating the address of a new queue entry selected by said operands of the instruction; and

(c) directly writing to the links in the control area of said queue header and of the last queue entry of said selected one of the one or more queues to point to said new queue entry to add said new queue entry to said selected one of the one or more queues and to deny the at least one client process from further read and write access to said new queue entry.

12. The method of claim 11, wherein said updating step updates said links in said control area of said queue header of said selected one of the one or more queues and the control area of said new queue entry, thereby adding said new queue entry to the front of said selected one of the one or more queues.

13. In a computer system having at least one processor for executing hardware instructions and units of data storage called queue banks, each queue bank being capable of representing a queue header element or a queue entry element, each queue bank containing a control area for holding control information and an event indicator, the computer system further having data structures called queues, each of the queues being a linked list of one queue header and zero or more queue entries, the computer system having at least one client process and at least one server process, the at least one client process and the at least one server process each being capable of directly accessing selectable ones of the queues, a method of executing a single one of the hardware instructions including specified operands by a selectable one of the at least one client process running on the processor to add a new event indicator to one of the queues comprising the steps of:

(a) calculating the address of the queue header of a selected one of the queues selected by the operands of the single one of the hardware instructions; and

(b) updating the event indicator in the control area of said queue header of said selected one of the queues, the selectable one of the at least one client process thereby communicating to a selectable one of the at least one server process that an event related to said selected one of the queues has occurred.

14. In a computer system for executing multiple processes having at least one processor for executing hardware instructions and units of data storage called queue banks directly accessible by the at least one processor, each of the queue banks being capable of representing a queue header element or a queue entry element, each of the queue banks containing a control area for holding control information and a text area for holding message data words, the computer system further having a queue being a linked list of one queue header linked through links to zero or more queue entries, the links being stored in the control area of the queue banks representing the queue header and queue entries, a queue bank being accessed via a queue bank descriptor data structure, queue bank descriptor data structures not currently in use being saved in an inactive queue bank descriptor list, and a queue being accessed using a pointer stored in the queue bank descriptor data structure of its queue header, a method of executing a single hardware instruction, including specified operands, by an identified one of the multiple processes running on one of the at least one processor to add a new queue entry to a queue comprising the steps of:

(a) calculating the address of the queue bank descriptor data structure of the queue header of a selected queue selected by the operands of the single hardware instruction;

(b) accessing said queue header and the queue entries of said selected queue by using the pointer stored in the queue bank descriptor data structure of said queue header of said selected queue;

(c) calculating the address of the queue bank descriptor data structure of a new queue entry selected by said operands of the single hardware instruction;

(d) accessing said new queue entry by using the pointer stored in the queue bank descriptor data structure of said new queue entry;

(e) directly storing the number of message data words being used in the text area of said new queue entry into the control area of said new queue entry; and

(f) updating the links in the control area of said queue header and the last queue entry of said selected queue to point to said new queue entry, thereby adding said new queue entry to the end of said selected queue and preventing the identified one of the multiple processes from further accessing said new queue entry.

15. The method of claim 14, further including the step of:

(g) returning said queue bank descriptor data structure of said new queue entry to the inactive queue bank descriptor list.

16. The method of claim 14, wherein said updating step updates the links in said control area of said queue header of said selected queue and said control area of said new queue entry, thereby adding said new queue entry to the front of said selected queue, if enqueuing to said front of said selected queue is allowed by said queue header.

17. In a computer system having multiple processes executed by at least one processor for executing instructions which are part of the instruction set of the computer system and units of data storage called queue banks, each queue bank being capable of representing a queue header element or a queue entry element of a queue, each queue bank containing a control area for holding control information and an event indicator, and a text area for holding message data words, the computer system having a queue being a linked list of one queue header and zero or more queue entries, the computer system storing data structures called queue bank descriptors, each of the queue bank descriptors storing a pointer to a queue bank, and a queue being accessed via the queue bank descriptor of its queue header, executing a single enqueue instruction within one of the multiple processes to add a new event indicator to a queue, the enqueue instruction having a plurality of operands, the method steps comprising:

(a) calculating the address of the queue bank descriptor of the queue header of a selected queue selected by the plurality of operands of the enqueue instruction;

(b) directly accessing the queue header of said selected queue by referencing the queue bank descriptor of the queue header of said selected queue; and

(c) updating the event indicator in the control area of the queue header of said selected queue, thereby communicating to a different one of the multiple processes that an event relating to said selected queue has occurred.

18. In a computer system having a processor for executing multiple processes, the computer system having a machine instruction set including instructions to be executed by the processor, the computer system further having a memory having units of data storage called queue banks which are directly accessible to the processor, the computer system further having a plurality of queues, each of the queues consisting of a header and a linked list of entries, wherein each of the entries in the linked list of entries consists of a queue bank containing control signals and message data signals and wherein the header contains control signals, the method of interprocess communication performed by an identified one of the multiple processes executing an enqueue instruction which is part of the machine instruction set, comprising:

identifying one of the plurality of queues as the selected queue;

identifying a selected one of the queue banks to be added to said selected queue wherein said selected one of the queue banks contains message data signals directly written into said selected one of the queue banks by the identified one of the multiple processes and which are to be communicated to a different one of the multiple processes;

modifying the control signals in predetermined ones of the linked list of entries of said selected queue and modifying the control signals in said selected one of the queue banks to indicate that said selected one of the queue banks is one of said linked list of entries of said selected queue; and

preventing the identified one of the multiple processes from further reading to or writing from said selected one of the queue banks, thereby protecting said message data provided by the identified one of the multiple processes from further modification by the identified one of the multiple processes.

19. The method of claim 18 wherein said modifying step modifies the control signals in predetermined ones of the linked list of entries of said selected queue and modifies the control signals in said selected one of the queue banks to indicate that said selected one of the queue banks is the first entry in said linked list of entries of said selected queue.

20. The method of claim 18, and further including the step of activating a previously suspended one of the multiple processes after said modifying step if said selected one of the queue banks is the only entry in said linked list of entries of said selected queue.

21. The method of claim 18, and further including the step of modifying the control signals in the header of said selected queue to communicate that an event occurred.

22. The method of claim 21, and further including the step of activating a previously suspended process in response to said step of modifying said control signals in said header of said selected queue.