Message queue processing among cooperative processors having significant speed differences

• US 5,224,215 A
• Filed: 07/13/1990
• Issued: 06/29/1993
• Est. Priority Date: 07/13/1990
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Disbrow, John R.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US07/553,203
• Time in Patent Office: 1,082 Days
• Field of Search: 395/250, 395/275, 395/325, 395/500, 395/650, 395/425, 395/600
• US Class Current: 709/234
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

Processors communicatively attaching a storage sub-system and which place a message on a queue no longer have to wait on a queue lock set by another processor or sub-system dequeuing a message. This is realized by use of a double ended linked list or queue of messages having an isolation/reference point wherein an enqueuing end of the list is lockable and accessible independently from the dequeuing end of the list. The locking primitive may be of the multi-processor lock synchronizing atomic type such as TEST AND SET.

Claims

1. A method for passing task oriented messages between a plurality of high speed processors and an external storage sub-system communicatively coupled over a shared memory, comprising the steps of:

(a) defining first and second dense linked linear lists in the shared memory, each list having independently lockable first and second ends thereof;

(b) obtaining a first lock by a processor on the first end of the first list when available, inserting messages between the first end and any last message so linked, and releasing said first lock;

(c) obtaining another lock by the sub-system on the second end of the first list when available, removing messages anywhere on the list, and releasing said other lock; and

(d) repeating steps (b) and (c) on the first and second ends of the second list by the storage sub-system and a processor respectively, concurrent access to non-overlapping sets of messages by the storage sub-system and a processor to the same list occurring either to the first and second ends of the second list or the second and first ends of the first list respectively.

4. The method according to any one of the claims 1, or 2, wherein the processors originate messages in the form of a sub-system control blocks (DCB'"'"'s), each DCB specifying one or more access operations to be executed by said sub-system, and further wherein said DCB'"'"'s being enqueued on the first list by the originating processors, said sub-system dequeuing and processing each DCB from said first list according to either an external discipline (LIFO, FILO, FIFO) or to a priority reordering of said first list or portion thereof.

5. The method according to claim 4, wherein each DCB assumes either a waiting, active, or completed status, the waiting DCB'"'"'s constituting the first list, active DCB'"'"'s being currently processed, and completed DCB'"'"'s constituting the second list.

6. The method according to any one of claims 1 or 2, wherein said sub-system includes at least a first synchronous DASD array and at least a first controller means for accessing said array and for sending and receiving messages to and from the shared memory.

2. A method for passing task oriented messages in a system having a plurality of high speed processors, an external storage subsystem, shared internal memory, and means utilizing the shared internal memory for enqueuing messages by the processors and for dequeuing messages by the storage subsystem in a first direction, and, for enqueuing messages by the storage subsystem and for dequeuing messages by the processors in a second direction, each processor accessing a lock primitive (Test and Set), accessing a lock including comparison matching a resultant from executing a lock primitive with a lockword, comprising the steps of:

(a) defining first and second linked linear lists in the shared internal memory, reference points and operator sets over the lists, each operator set including a top of list (TOQ) and bottom of list (BOQ) pointers, top of list (TOQL) and bottom of list (BOQL) lockwords, each list having a top of the list end and a bottom of the list end;

(b) obtaining a first lock by one of the processors on the BOQ end of the first list upon comparison matching the BOQL with the resultant of executing the lock primitive by said one processor, embedding messages between a reference point and any last message including a null message so connected in the list, and releasing said first lock;

(c) obtaining another lock by the sub-system on the TOQ end of the first list only upon comparison matching the TOQL with the resultant of executing the lock primitive by the subsystem, removing one or more messages from said list, and releasing said other lock;

(d) repeating steps (b) and (c) on the BOQ and TOQ ends of the second list by the storage sub-system and a processor respectively, concurrent access to non-overlapping sets of messages by the storage sub-system and a processor to the same list occurring either to the BOQ and TOQ ends of the second list or the TOQ and BOQ of the first list respectively; and

(e) reordering the list of messages by obtaining another lock by the sub-system on the TOQ of the first list when available, removing messages anywhere on the list, linking at least some of the dequeued messages together in one or more fragmentary chains, and then reinserting the fragmentary chains back into the queue, and releasing said other lock.

3. The method according to claim 2, wherein only the processor holding said other lock (TOQL) may alter any pointer to the TOQ end of the list or any of the messages at the BOQ end of the list, and further wherein only the processor holding the first lock (BOQL) may alter any pointer designating the BOQ end on the list.

7. A system having a plurality of fast processors communicatively coupling an external storage sub-system by way of a shared memory, said system comprising:

means responsive to messages originating from selected processors for writing the messages into the shared memory, linking said messages into a wait queue, and signaling the storage sub-system;

means at the storage sub-system aperiodically responsive to said signaling for dequeing the messages from the wait queue, actively processing the dequeued messages, enqueuing the processed messages onto a completion queue in said shared memory, and signaling the system; and

means aperiodically responsive to the sub-system signals for dequeing the processed messages form the completion queue;

wherein said system further comprises;

means for defining a pair of linked lists in the shared memory with separately lockable ends; and

means for operating said lists as oppositely poled queues (processor to subsystem direction, and subsystem to processor direction) supporting message passing between high and low speed processors by enqueing messages on each list by a processor or the sub-system lockably independent from

(i) the dequeuing of messages by the sub-system if the processor enqueues the messages, or,

(ii) the dequeuing of messages by the processor if the sub-system enqueues the messages on the sample list,

said means for operating said lists include

means for managing concurrent access to non-overlapping sets of messages by the storage sub-system and a processor to the same list occurring either to the first and second ends of the second list or the second and first ends of the first list respectively; and

means for reordering the list of messages by obtaining another lock by the sub-system on the second end of the queue poled in the processor to subsystem direction when available, removing messages anywhere on the list, linking at least some of the dequeued messages together in one or more fragmentary chains, and then reinserting the fragmentary chains back into the queue, and releasing said other lock.

8. The system according to claim 7, wherein the external storage sub-system further comprises at least a first synchronous DASD array, and at least a first controller means coupling said first array to the shared memory via the enqueuing/dequeuing means at said sub-system.