Memory subsystem command input queue having status locations for resolving conflicts

• US 5,388,222 A
• Filed: 03/28/1994
• Issued: 02/07/1995
• Est. Priority Date: 07/06/1989
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Chisvin, Lawrence A. P., Hartwell, David W., Rantala, Joseph F., Grooms, John K.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Shin, Christopher B.
• Application Number:
  US08/219,807
• Time in Patent Office: 316 Days
• Field of Search: 395/200, 395/900, 395/425, 395/278, 364/200, 364/900
• US Class Current: 711/154
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Methodology and circuitry for managing read and write commands from nodes to a shared memory resource on a common data bus, including nodes with write-back caches, nodes with write-through caches and nodes without caches.

Claims

1. A method of resolving conflicts between execution of commands from a plurality of nodes to a shared memory resource by use of a memory input queue, said commands each being directed to a specific address in said shared memory resource, said memory input queue having a plurality of storage locations that are available for storage of said commands, each of said plurality of storage locations having a "free" state, a "new" state, a "wait" state and a "match" state, at least one of said plurality of nodes having a write-back cache and at least one of said plurality of nodes not having a write-back cache, said commands comprising "ownership read" type and "disown write" type commands from said at least one of said plurality of nodes with a write-back cache, and "read" type and "write" type commands from said at least one of said plurality of nodes without a write-back cache, said memory input queue being connected between said plurality of nodes to receive said commands therefrom and said shared memory resource to access said shared memory resource, said method comprising the steps of:

receiving any of said commands in said memory input queue as received commands;

setting each of said plurality of storage locations in said memory input queue that is available for storage of said commands into said "free" state;

storing each of said received commands in one of said storage locations as stored commands in said memory input queue and changing the state of said one of said storage locations from said "free" state to said "new" state to indicate that said stored commands are to be processed;

creating mask data corresponding to each of said stored commands of said "disown write" type and said "write" type;

selecting each of said stored commands from said storage locations in said memory input queue;

changing, from said "new" state to said "wait" state, the state of each of said storage location that stores one of said stored commands if said one of said stored commands is directed to the same specific address in said shared memory resource as another one of said stored commands of the "ownership read" type or "disown write" type;

deferring the execution of each of said stored commands of the "read" type in said "wait" state until at least one of said stored commands of the "ownership read" type or "disown write" type is executed;

merging and storing said mask data that corresponds to each of said stored commands of the "write" type to create merged mask data;

for each of said stored commands of the "disown write" type changing, from said "wait" state to said "match" state, the state of each of said storage locations in said memory input queue that stores one of said stored commands that is directed to the same address in said shared memory resource as any of said stored commands of the "disown write" type and using said mask data of said stored commands of the "write" type from said storage locations in said "match" state to inhibit said mask data of each of said stored commands of the "disown write" type during execution and executing each of said stored commands of the "read" type from said storage locations in said "match" state after execution of said stored commands of the "disown write" type;

after execution of any of said stored commands that are not directed to the same address in said shared memory resource as any other of said stored commands of the "ownership read" or "disown write" type, changing the storage location that stores said any one of said stored commands from said "new" state to said "free" state to indicate that said storage location that stores said any one of said stored commands is available to receive a new one of said commands; and

after execution of one of said stored commands from one of said storage locations in said "match" state, changing said one of said storage locations in said "match" state from said "match" state to said "free" state to indicate that said storage location that was changed from said "new" state to said "free" sate is available to store a new one of said commands.

2. Circuitry for resolving conflicts between execution of commands from a plurality of nodes to a shared memory resource by use of a memory input queue, said commands each being directed to a specific address in said shared memory resource, said memory input queue having a plurality of storage locations that are available for storage of said commands, each of said plurality of storage locations being in a "free" state, a "new" state, a "wait" state or a "match" state, at least one of said plurality of nodes having a write-back cache and at least one of said plurality of nodes not having a write-back cache, said commands comprising "ownership read" type and "disown write" type commands from each of said plurality of nodes with a write-back cache, and "read" type and "write" type commands from each of said plurality of nodes without write-back caches, said memory input queue being connected between said plurality of nodes to receive said commands therefrom and said shared memory resource to access said shared memory resource, said circuitry for resolving conflicts comprising:

means for executing said commands;

means for receiving any of said commands in said memory input queue as received commands;

means for setting each of said plurality of storage locations in said memory input queue that is available for storage of said commands to said "free" state;

means for storing each of said received commands in one of said storage locations as stored commands and changing the state of each of said storage locations that stores one of said stored commands from said "free" state to said "new" state to indicate that said stored command is to be processed;

means for determining said specific address for each of said stored commands;

means for selecting each of said stored commands;

means for changing from said "new" state to said "wait" state the state of each of said storage locations that stores one of said stored commands if said one of said stored commands is directed to the same specific address in said shared memory resource as another one of said stored commands of the "ownership read" or "disown write" type;

means for deferring the execution of each of said stored commands of the "read" type in said "wait" state until at least one of said stored commands of the "ownership read" or "disown write" type is executed;

means for creating mask data corresponding to each of said stored commands of said "disown write" type and said "write" type;

means for merging and storing said mask data to create merged mask data corresponding to each of said stored commands of the "write" type in said "wait" state;

means responsive to one of said stored commands of the "disown write" type for changing from said "wait" state to said "match" state the state of each of said storage locations that stores one of said stored commands of the "write" type or the "read" type that is directed to the same specific address in said shared memory resource as said one of said stored commands of the "disown write" type and using said merged mask data of said stored commands of the "write" type that are directed to the same specific address to inhibit said mask data of said one of said stored commands of the "disown write" type during execution and executing said stored commands of the "read" type that are directed to the same specific address after execution of said one of said stored commands of the "disown write" type;

means for changing each storage location that stores one of said stored commands that is not directed to the same specific address in said shared memory resource as any of said stored commands of the "ownership read" type or disown write" type from said "new" state to said "free" state after the execution of said one of said stored commands that is not directed to the same specific address in said shared memory resource as any of said stored commands of the "ownership read" type or "disown write" type to indicate that said storage location that was changed from said "new" state to said "free" state is available to store a new one of said commands; and

means for changing each storage location that stores one of said stored commands in said "match" state after the execution of said one of said stored commands in said "match" state from said "match" state to said "free" state to indicate that said storage location that was changed from said "match" state to said "free" state is available to store a new one of said commands.