Cache coherency protocol for multi processor computer system

A cache coherency protocol for a multi-processor system which provides for read/write, read-only and transitional data states and for an indication of these states to be stored in a memory directory in main memory. The transitional data state occurs when a processor requests from main memory a data block in another processor's cache and the request is pending completion. All subsequent read requests for the data block during the pendency of the first request are inhibited until completion of the first request. Also provided in the memory directory for each data block is a field for identifying the processor which owns the data block in question. Data block ownership information is used to determine where requested owned data is located.

FIELD OF THE INVENTION 
The invention is directed to the field of multi-processor computer systems 
and, more particularly, to multi-processor computer systems wherein each 
of the central processing units in a system has a write-back cache memory 
and is coupled by a point-to-point connection to a cross bar switch unit 
that is, in turn, coupled, point-to-point, to several main memory modules. 
BACKGROUND OF THE INVENTION 
Modern day computer systems frequently comprise a central processing unit 
and a memory hierarchy including a relatively large, but relatively slow 
main memory module and a relatively fast, but relatively small cache 
memory coupled between the central processing unit and the main memory 
module. The data and instructions being processed at any one time by the 
central processing unit are temporarily stored in the cache memory to take 
advantage of the high speed of operation of the cache memory to thereby 
increase the overall speed of operation of the computer system. The use of 
a cache memory is based upon the principles of temporal locality and 
spatial locality. More specifically, when a central processing unit is 
accessing data and instructions from a particular space within physical 
memory, it will most probably access the data and instructions from that 
space and, in addition, access data and instructions from contiguous 
space, for a certain period of time. Accordingly, data blocks, including 
the contiguous space of physical memory where data being utilized by the 
central processing unit resides, are placed in the cache memory to greatly 
decrease the time required to fetch data and instructions from those 
frequently referred to data blocks. 
A cache memory scheme may be either a write-through cache or a write-back 
cache. In a write-through cache, a central processing unit writes through 
to main memory whenever it writes to an address in cache memory. In a 
write-back cache, the central processing unit does not update the main 
memory at the time of writing to its cache memory but updates the memory 
at a later time. For example, when the central processing unit is changing 
the contents of its cache memory, it will send the latest copy of 
written-to data to the main memory before it refills the space within the 
cache occupied by the written-to data. In this manner, the speed of 
operation of the central processing unit is not slowed down by the time 
that would be required to update the main memory after each write 
operation. Instead, the main memory is updated at the completion of the 
operations relating to the data block contained in the cache memory. 
Many computer systems operate on the basis of the concept of a single, 
simple copy of data. In a multi-processor system including several central 
processing units, each with its own write-back cache, incoherencies within 
the data arise when one of the central processing units writes to a data 
block in its cache memory. In other words, when a particular central 
processing unit writes to its cache, the main memory will not have a 
correct copy of the data until the central processing unit updates the 
main memory. 
If a particular central processing unit requests a data block currently in 
the cache of another central processing unit of the multi-processor system 
and that data block has been written to by such other central processing 
unit on a write-back basis, as described above, a coherency scheme must be 
utilized to insure that the latest correct copy of the data is sent to the 
requesting central processing unit. Typically, heretofore known 
multi-processor systems have implemented a so-called "snoopy" protocol in 
a shared bus configuration for the several central processing units of the 
system to assure that the latest copy of a data block is sent to a 
requesting central processing unit. 
Pursuant to the snoopy protocol, all of the central processing units of the 
multi-processor system are coupled to the main memory through a single, 
shared bus. Each of the caches of the several central processing units and 
any other devices coupled to the shared bus "snoop" on (i.e. watch or 
monitor) all transactions with main memory by all of the other caches. 
Thus, each of the caches is aware of all data blocks transferred from main 
memory to the several other caches throughout the multi-processor system. 
Inasmuch as the caches are coupled to the main memory by a single, shared 
bus, it is necessary to implement an arbitration mechanism to grant access 
to the shared bus to one of possibly several devices requesting access at 
any particular time. The arbitration mechanism will effectively serialize 
transactions with the main memory and the snoopy protocol utilizes the 
serialization to impose a rule that only one cache at a time has 
permission to modify a data block. 
After modification of the data block in the one cache, the main memory does 
not contain a valid copy of the data until it is updated by the cache 
having the written to block, as described above. In accordance with the 
snoopy protocol, the copy of the written to data block in the one cache is 
substituted for the main memory copy whenever another cache requests that 
data block prior to the update of the main memory. 
An ownership model of the snoopy protocol includes the concept of 
"ownership" of a data block. A device must first request and obtain 
ownership of a data block in its cache before it can write to that data 
block. At most one device can own a data block at any one time and the 
owner always has the valid copy of that data block. Moreover, the owner 
must update the main memory before it relinquishes ownership of the block 
to assure coherency of the data throughout the multi-processor system. 
By definition, ownership means the right to modify a data block. When no 
device of the system owns a data block it is said to be owned by the main 
memory and copies of the data block may be "shared" by any of the devices 
of the system. A shared mode means the device has read only access to a 
shared copy of a data block residing in its cache. Since the main memory 
owns the data block in the shared mode, all shared copies exactly match 
the main memory and are, hence, correct copies. Once any one device other 
than main memory obtains ownership of a data block, no other device may 
share the block and all copies of the data block which are shared are 
invalidated at the time ownership is obtained by the one device. 
It is implicit above that a single request is made and acted upon at a time 
on the shared bus. Hence all bus requests are ordered and all caches and 
the memory see them in the same order. It is also implicit above that the 
memory does not respond to a request if some cache owns the data; instead 
the owning cache supplies the data. This is typically done by having each 
cache search itself for the data with each bus request. If a cache finds 
that it owns the data, it suppresses memory (which could otherwise 
respond), typically with a signal wire for this purpose, and applies the 
data to the bus itself. 
In a variation of the ownership model, the main memory includes a directory 
of all main memory lines to ensure that data coherency is maintained 
throughout the multi-processor system. The directory contains an entry for 
each data block in the main memory and each entry comprises a bit mask of 
k+1 bits. The number k equals the number of caches in the system with each 
one of the k bits of the mask corresponding to one of the caches. The 
extra bit of the k+1 bits provides the ownership status of the 
corresponding data block. Thus, if the (k+1) bit is on, then one and only 
one of the remaining bits can also be on since only one cache at a time 
can have write privileges to a data item. 
The main memory utilizes the directory to provide a centralized cache 
coherency system. The main memory queries the directory for each read or 
write request that it receives from the various central processing units 
in the multi-processor system to determine the current state of the 
requested data item, i.e. owned or shared, depending upon the state of the 
(k+1) bit, and the location of copies of the data item, as indicated by 
the remaining bits of the bit mask. 
The information obtained from the directory enables the main memory to 
enforce the coherency scheme. For example, if a data block is not owned 
and a read only copy is present in several of the caches, the (k+1) bit 
will be off and the bits corresponding to the caches that have a copy of 
the data block will each be on. If another central processing unit, which 
does not have a copy of the data block wants to write to the data block, 
it sends a request to the main memory for the data block with write 
privileges. The main memory will query the directory to determine that the 
data block is not presently owned and that copies reside in several of the 
caches. The main memory will send an invalidate signal to all of the 
caches where a copy of the data block resides, as indicated by the bits of 
the bit mask and then set the k+1 bit to now indicate the owned state. 
The main memory further sets the bit corresponding to the requesting cache. 
The main memory can perform similar operations upon each read or write 
request to determine the state and location of any data block and to reset 
the bit mask and send control signals as required to maintain data 
coherency. 
The above-described coherency protocols provide a highly effective scheme 
for maintaining data coherency throughout a multi-processor system 
including devices having write-back caches. However, a major drawback of 
the scheme is that only one device at a time may access main memory due to 
the single shared bus coupling all of the devices to the main memory and 
the necessity of serializing all transactions with the main memory. Thus, 
the maximum speed of operation theoretically possible in a system having 
parallel central processing units is diminished in practical applications 
since only one central processing unit at a time can complete a 
transaction with the main memory through the shared bus. Moreover, each 
device coupled to the shared bus must devote certain resources to an 
active and continuous monitoring of the shared bus in accordance with the 
snoopy protocol. 
SUMMARY OF THE INVENTION 
The present invention provides a multi-node system. The nodes may be, for 
example, several central processing units, each being connected to one or 
more memories by a memory/node coupling mechanism. The memory/node 
coupling mechanism may be a cross bar switch unit coupled point-to-point 
to one or more main memory modules and nodes and wherein each node 
(central processing unit or other devices) of the system has a write-back 
cache. In accordance with the invention, cache coherency throughout the 
system is maintained by each main memory module through a novel memory 
directory resident on the module. 
The point-to-point connections through the cross bar switch increase the 
speed of operation of the system by permitting several connections between 
central processing units and the main memory modules to be made 
simultaneously. The memory directory of each main memory module contains 
several coherency state fields for each data block stored in the module to 
indicate the coherency state of the data block. Each main memory module 
enforces coherency throughout the multi-processor system for data block 
stored within the module by making a query to its memory directory upon 
each data transfer operation which affects or may be affected by the 
coherency state of a data block and issuing appropriate commands to 
implement data transfers while maintaining coherency in the system. 
Pursuant to the invention, the coherency state fields provide the memory 
module with complete information on the coherency state of each data block 
including ownership status of the block, an owner ID to uniquely identify 
a particular cache which owns a modified data block, a copy mask to 
indicate which caches have a copy of a shared data block and a lock-status 
bit to indicate that an interlock instruction is being executed. In this 
manner, the memory module can enforce a cache coherency policy in a highly 
efficient and speedy operation. For example, the owner-ID information 
enables the memory module to immediately identify and forward commands to 
a current owner during a transfer of ownership operation. 
In addition, in accordance with a feature of the invention, the ownership 
status information includes transitional states to indicate outstanding 
data and ownership transfer operations. Thus, the processing of read and 
write requests can be expedited, as for example, through efficient use of 
the cross-bar switch and a pipelined operation, so that subsequent read 
and write operations can be initiated prior to the completion of a current 
read or write operation. The transitional states tell the main memory 
module whether an outstanding data transfer operation regarding a 
particular data block is being executed so that the memory module can 
block or inhibit a subsequent read request for that data block until the 
already commenced operation has been completed. The transitional states 
therefor provide an automatic conflict check mechanism during accelerated 
cache operations.

DETAILED DESCRIPTION 
Referring now to the drawings and initially to FIG. 1, there is illustrated 
a multi-processor computer system in accordance with an exemplary 
embodiment of the present invention. Each one of several nodes, for 
example, four central processing units (CPU's) 10, 11, 12 and 13 includes 
a write back cache memory 30, as known in the art, and is coupled by a 
channel 14, 15, 16 and 17, respectively, to a cross bar switch unit 18. An 
I/O adapter 19 is also coupled by a channel 20 to the cross bar switch 
unit 18. The I/O adapter is, in turn, coupled to one or more peripheral 
devices (not illustrated). Moreover, each of several (for example, four) 
main memory modules 22, 23, 24, 25 is coupled by channels 26, 27, 28 and 
29, respectively, to the cross bar switch unit. 
Each of the main memory modules 22-25 stores a preselected portion of the 
data and instructions currently comprising the main memory of the system. 
Preselected subsets of the main memory that are fetched from one or more 
of the main memory modules 22-25 reside in the various cache memories 30 
to facilitate high speed operation of the system. When a particular CPU 
10-13 seeks to access data, it first looks for the data in its cache 
memory 30. If the data is present in the cache memory 30, a "cache hit" is 
said to occur and the CPU 10-13 receives the data from the cache memory 
30. When the data is not present in the cache memory 30, a "cache miss" 
signal is asserted and the CPU 10-13 must then fetch the data from the 
main memory module 22-25 where the data resides. 
In the event of a cache miss, the CPU 10-13 must issue a request command to 
the main memory module 22-25. This command provides address information to 
the cross bar switch 18 which operates to create a path via the 
appropriate channels 14-17 and 26-29 between the requesting CPU 10-13 and 
the particular main memory module 26-29 where the data identified by the 
address information resides. The data may then be communicated back to the 
requesting CPU 10-13 by the main memory module 26-29 for storage in the 
cache memory 30 associated with the requesting CPU 10-13. 
As discussed above in the Background of the Invention section, if the 
requesting CPU 10-13 then writes to the data, the copy of the data 
residing in the main memory module 22-25 or in any other cache memory 30 
in the system will no longer be valid. The multi-processor data coherency 
protocol of the present invention operates to invalidate all other copies 
of the data and make certain that the latest copy in the requesting CPU 
10-13 is used for subsequent requests for that data. 
Pursuant to the invention, the main memory modules 22-25 are provided with 
a memory directory 31. Preferably, there is one memory directory per 
memory module. The memory directory maintains coherency state information 
on each of a multiplicity of data blocks within the corresponding main 
memory module 22-25. A data block refers to a preselected amount of 
addressable data, for example, 64 bytes, which is transferred to a cache 
memory upon each CPU 10-13 request for data. The memory directory 31 
enables each one of the main memory modules 22-25 to ascertain coherency 
state information which affects or is affected by any data transfer 
operations between the main memory module 22-25 and any of the cache 
memories 30 in the system. The main memory module utilizes the coherency 
state information in its directory to issue commands which implement data 
transfers while maintaining coherency throughout the multi-processor 
system for all data blocks which reside in the main memory module 22-25. 
Referring now to FIG. 2, there is illustrated the details of a memory 
directory 31 in accordance with an exemplary embodiment of the invention. 
The memory directory 31 has an entry 32 for each data block in the 
corresponding main memory module 22-25. Each entry includes a block ID 
field 33 to uniquely identify a particular data block residing in the main 
memory module 22-25. Next to each block ID field are four coherency state 
fields for that block: a Memory-State field 34, a Block-Owner ID field 35, 
a Copy-Mask field 36, and a Lock-Status field 37. Theses fields are 
defined, as follows: 
1. Memory-State field 34--The current ownership state of the block in the 
main memory module 22-25, either SHARED-UNMODIFIED, EXCLUSIVE-MODIFIED, 
FORWARD-EXCLUSIVE, FORWARD-SHARED, or UNOWNED. This field requires two 
bits per block. 
SHARED-UNMODIFIED: The data block is present in zero or more cache memories 
30 and is not modified. The main memory module 22-25 has a valid copy and 
all cache copies are READ-ONLY. 
EXCLUSIVE-MODIFIED: The data block is present in exactly one cache memory 
30 that owns the data block and the data is modified, i.e., the data in 
the data block has been written by the CPU 10-13 associated with the cache 
memory that owns the data and is inconsistent with the copy in the main 
memory module 22-25. The one owner CPU 10-13 has READ/WRITE access to the 
data block. 
FORWARD-EXCLUSIVE: The data block is present in exactly one cache memory 30 
and is modified. In addition, there is an outstanding Read Exclusive 
command (see below) to the block from another cache memory 30. Any 
additional read commands to this block force the main memory module 22-25 
to stop processing all new read commands until the outstanding Read 
Exclusive is completed. This is a transitional state for the memory. There 
is no corresponding state for the cache. 
FORWARD-SHARED: The data block is present in exactly one cache memory 30 
and is modified. In addition, there is an outstanding READ SHARED command 
(see below) to the block from another cache memory 30. Any additional read 
commands to this data block force the main memory module 22-25 to stop 
processing all new read commands until the outstanding READ SHARED command 
is completed. 
UNOWNED: The data block is not present in any cache memory 30. This state 
is implemented with a Memory-State of SHARED-UNMODIFIED and a Copy-Mask 
(see below) of all zeros. 
2. Block-owner field 35--A six bit field containing a unique Owner-ID of 
the CPU 10-13 with a cache memory 30 containing a modified copy of the 
data. Changes to this field occur upon the issuance of a Read Exclusive 
(see below) command. 
For either of the FORWARD states, the Block-Owner field contains the 
Owner-ID of the CPU 10-13 for the read command being processed. 
3. Copy-Mask field 36--A bit field used in conjunction with an Invalidate 
command (see below) to assist the memory module 22-25 in determining if it 
is required to invalidate copies the data block identified by the block ID 
of the entry field 36. The Copy-Mask field 36 contains a bit corresponding 
to each of the cache memories 30. The bit is set when a copy of the data 
block is in the cache corresponding to the bit. 
4. Lock-Status bit 37--A single bit data field per data block in the 
system. This bit is used to implement the interlock mechanism. 
CPU Coherency Information 
Each CPU 10-13 must maintain local state information for each data block in 
its cache memory 30. 
Thus, each CPU 10-13 is provided with a data block state directory 38 as 
illustrated in FIG. 3. The data block state directory has an entry 39 for 
each data block-sized location in the cache memory 30. Each entry contains 
a block ID field 40 to identify the specific data block residing in the 
corresponding location in the cache memory 30 and a block coherency state 
field 41 to indicate the coherency state of the data block. 
Each data block in each cache memory 30 can be in one of three possible 
states: 
1. INVALID: The data block does not contain valid data. 
2. SHARED-UNMODIFIED: The data block is valid, and some other cache memory 
30 may have this block. The main memory module 22-25 is the owner. The CPU 
10-13 has READ-ONLY access to the data block. 
3. EXCLUSIVE-MODIFIED: The data block is valid, and no other cache memory 
30 has this block. The data in the data block has been modified by the CPU 
10-13 associated with the cache memory 30, and is therefore inconsistent 
with main memory. The CPU 10-13 has READ/WRITE access to the data block. 
A data block in the EXCLUSIVE-MODIFIED state is written back to its main 
memory module 22-25 when evicted on a cache miss or when a Read Shared 
command to the block is received, as explained in more detail below. 
Coherency Commands 
Data coherency is maintained through the use of the memory directories and 
the node block state directories in conjunction with the following 
commands issued by the main memory modules 22-25 and the CPU's 10-13. The 
commands issued by the CPUs 10-13 are as follows: 
Read Shared (Rd-Shr)--requests one of the main memory modules 22-25 to send 
a read-only copy of a data block. 
Read Exclusive (Rd-Ex)--requests one of the main memory modules 22-25 to 
send a writable copy of a data block. 
Write Unowned (Wrt-Un)--writes modified data back to a main memory module 
22-25 and clears the data block location for new data. This command is 
issued when a modified data block is evicted on a cache miss. This occurs 
when the location occupied by the modified data block is needed to store a 
new data block needed due to the cache miss. 
Write Shared (Wrt-Shr)--write modified data back to a main memory module 
22-25 but keeps a read-only copy; generated when a forwarded Read Shared 
is asserted by another CPU 10-13 and the data requested by the other CPU 
10-13 is owned by the CPU 10-13 which asserts the Write Shared command. 
Read Data Response (RDAT)--sends read data to another CPU 10-13; generated 
by a Read Shared or a Read Exclusive that hits in the cache. 
Forward Acknowledge (FACK)--notifies the appropriate main memory module 
22-23 that a forwarded Read Exclusive command has been processed. 
The commands issued by a main memory module 22-25 to the CPU's 10-13 are as 
follows: 
Read Data Response (RDAT)--read data 
Forward Read Shared (Fwd-Shr)--requests a cache memory 30 to write a 
modified block back to main memory module 22-23 and forward a copy to 
another CPU 10-13. 
Forward Read Exclusive (Fwd-Ex)--requests a cache memory 30 to forward a 
modified block to another CPU 10-13 and return a Forward Acknowledge 
command to the main memory module 22-23. 
Invalidate (INVAL)--tells all cache memories 30 having a copy of a 
particular data block to set the invalid state 41 for the block in the 
state directory 38 associated with the cache memory 30, this command is 
ignored in a cache memory 30 with the block marked EXCLUSIVE-MODIFIED in 
its state directory 38. 
General Description of Coherency Operations 
A general description of the operation of the multi-processor system as 
related to cache coherency is written in terms of a CPU 10-13 reference to 
its cache memory 30, of which there are four possible outcomes, Read Hit, 
Read Miss, Write Hit, and Write Miss. In addition, either Miss case may 
result in an Eviction. 
READ HIT--The data block is in the cache memory in the either 
SHARED-UNMODIFIED or the EXCLUSIVE-MODIFIED state and is returned to the 
CPU 10-13 with no coherency protocol overhead. 
READ MISS--The data block is either invalid or not in the cache memory 30 
and the CPU 10-13 or its cache memory 30 sends a Read Shared command to 
the appropriate main memory module 22-25. Whenever a CPU 10-13 or its 
cache memory 30 issues a Read Shared command, the data block state 
directory shall indicate the state of the needed data block as 
SHARED-UNMODIFIED PENDING. The SHARED-UNMODIFIED PENDING state is 
transitional and shall be changed to the SHARED-UNMODIFIED state upon 
receipt by the CPU 10-13 or its cache memory 30 of a Read Data response 
command containing the needed data block. When a Read Shared command is 
received by the main memory module 22-25, main memory checks the ownership 
state of the block in its memory director 31 and performs the following: 
1. If the ownership state is of the SHARED-UNMODIFIED, the block may be 
sent immediately and the memory ownership state remains SHARED-UNMODIFIED. 
2. If the ownership state is EXCLUSIVE-MODIFIED, the state is changed to 
FORWARD-SHARED, and a Forward Read Shared command is sent to the CPU 10-13 
which owns the data block. When the owner receives the Forward Read Shared 
it sets the state in its state directory 38 to SHARED-UNMODIFIED, sends 
the data block with a Read Data Response to the CPU 10-13 that requested 
the data block and finally sends a Write Shared command containing the 
modified block of data to update the main memory module 22-25. Should the 
owner CPU 10-13 voluntarily replace the data block before the Forward Read 
Shared arrives, the CPU 10-13 ignores the Forward Read Shared command. In 
this case, the main memory module 22-25 will forward the requested data to 
the requesting CPU 10-13 as a side effect of the Write Unowned command 
asserted by the owner CPU 10-13. When the main memory module 22-23 
receives either the Write Shared or the Write Unowned (voluntary eviction 
case) command, it changes the ownership state to SHARED-UNMODIFIED. 
3. If the ownership state is FORWARD-SHARED, the main memory module 22-23 
blocks the Read Shared, and blocks all further requests for that data 
block. When the Forward Read Shared associated with the FORWARD-SHARED 
state completes, the ownership state changes to SHARED-UNMODIFIED. The 
main memory module 22-25 then restarts the blocked Read Shared, and 
completes the actions described above under SHARED-UNMODIFIED. 
4. If the ownership state is FORWARD-EXCLUSIVE, the main memory module 
22-25 blocks the Read Shared, and blocks all further read requests for 
that data block. When the Forward Read Exclusive associated with the 
FORWARD-EXCLUSIVE state completes, the ownership state will be changed to 
EXCLUSIVE-MODIFIED. The main memory module 22-25 then restarts the blocked 
Read Shared, and completes the actions described above under 
EXCLUSIVE-MODIFIED 
WRITE HIT--If the coherency state for the data block in the state directory 
38 associated with the CPU 10-13 is EXCLUSIVE-MODIFIED the write may 
proceed without any additional overhead. The SHARED-UNMODIFIED state 
(implies READ-ONLY access) in the state directory 38 is treated as Write 
Miss. 
WRITE MISS--The data block is not in the cache memory 30 or the state in 
the state directory 38 is either invalid or SHARED-UNMODIFIED, the CPU 
10-13 or its cache memory 30 sends a Read-Exclusive command to the 
appropriate memory module 22-25. Whenever a CPU 10-13 or its cache memory 
30 issues a Read-Exclusive command, the data block state directory shall 
indicate the state of the needed block as EXCLUSIVE-MODIFIED PENDING. The 
EXCLUSIVE-MODIFIED PENDING state is transitional and will be changed to 
EXCLUSIVE-MODIFIED upon receipt by the CPU 10-13 or its cache memory 30 of 
a Read Data Response command containing the needed data block. When a 
Read-Exclusive command is received by the main memory module 22-25, main 
memory checks the ownership state of the block in its memory directory 31, 
and performs the following. 
1. If the ownership state is SHARED-UNMODIFIED and the Copy-Mask is all 
zeros (no possible Read-Only copies, i.e. UNOWNED state), the data block 
is sent immediately and the ownership state is set to EXCLUSIVE-MODIFIED. 
If the Copy-Mask is non-zero, an Invalidate command is broadcast to all 
CPU's 10-13 (ignored by the CPU 10-13 which requested the data block since 
its local state is EXCLUSIVE-MODIFIED), and then the data block is sent 
and the ownership state is set to EXCLUSIVE-MODIFIED. 
2. If the ownership state is EXCLUSIVE-MODIFIED, the state is changed to 
FORWARD-EXCLUSIVE, and a Forward Read Exclusive command is sent to the 
owner CPU 10-13. When the owner CPU 10-13 receives the Forward Read 
Exclusive it sets its local state to INVALID, sends the data block with a 
Read Data Response to the requesting CPU 10-13, and finally sends a 
Forward Acknowledge command to the main memory module 22-25. 
Should the owner CPU 10-13 voluntarily replace the block before the Forward 
Read Exclusive arrives, the CPU 10-13 ignores the Forward Read Exclusive. 
In this case, the main memory module 22-23 will forward the requested data 
to the requesting CPU 10-13 as a side effect of the Write Unowned command 
executed by the owner CPU 10-13. 
When the main memory module 22-25 receives either the Forward 
Acknowledgement or the Write Unowned (voluntary eviction case) command, it 
changes the ownership state to EXCLUSIVE-MODIFIED. 
3. If the ownership state is FORWARD-SHARED, the main memory module 22-25 
blocks the Read Exclusive, and blocks all further requests for that data 
block. When the Forward Read Shared associated with the FORWARD-SHARED 
state completes, the ownership state is changed to SHARED-UNMODIFIED. The 
main memory module 22-23 then restarts the blocked Read Exclusive, and 
completes the actions described above under SHARED-UNMODIFIED. 
4. If the ownership state is FORWARD-EXCLUSIVE, the main memory module 
22-25 blocks the Read Exclusive, and blocks all further read requests for 
that data block. When the Forward Read Exclusive associated with the 
FORWARD-EXCLUSIVE state completes, the ownership state is changed to 
EXCLUSIVE-MODIFIED. The memory then restarts the blocked Read Exclusive, 
and completes the actions described above under EXCLUSIVE-MODIFIED. 
REPLACEMENT--Action is required only when an EXCLUSIVE-MODIFIED block is 
replaced in a cache memory 30. The CPU 10-13 or its cache 30 sends a Write 
Unowned to the appropriate main memory module 22-25, which changes the 
ownership state from EXCLUSIVE-MODIFIED to UNOWNED. If the ownership state 
is FORWARD-SHARED when the write unowned command is received, the main 
memory module forwards the modified data block to the CPU 10-13 with the 
outstanding read command, and sets the ownership state to 
SHARED-UNMODIFIED. If the ownership state if FORWARD-EXCLUSIVE when the 
write unowned command is received, the main memory module 22-25 forwards 
the modified data to the CPU 10-13 with the outstanding read, and sets the 
ownership state to EXCLUSIVE-MODIFIED. 
Graphical representations of the coherency operations described above for 
both a cache and for main memory are depicted in FIGS. 4 and 5, 
respectively. These figures depict cache and memory states as enclosed in 
labeled circles or squares and commands driving the transition between 
such states as labeled connecting arrows. 
The coherency protocol of the present invention supports the use of 
hardware interlocks through an "interlock protocol." The interlock 
protocol provides a "lock status" bit that follows the data wherever it 
travels in the computer system and is stored with the data whenever it is 
owned. More specifically, lock status is transmitted with every write data 
and read data transfer, and stored in cache whenever the cache maintains 
the data in the EXCLUSIVE-MODIFIED state. Also, lock status is stored in 
the memory directory of main memory. 
The interlock protocol is summarized as follows: 
1. For each Write Unowned and Write Shared command issued by a processor, 
lock status is transmitted along with the command to main memory. 
2. For each Read Response command issued by a processor or main memory, 
lock status is transmitted along with the data. 
3. Each data block in a cache in the EXCLUSIVE-MODIFIED state has lock 
status bit encoded in the field representing the state. This creates two 
variants of the state: EXCLUSIVE-MODIFIED (when the data block is 
unlocked) and EXCLUSIVE-MODIFIED-LOCKED (when the interlock is set). 
4. Each block in memory has a lock status bit in its associated entry in 
the memory directory. This bit indicates the last interlock status in the 
system recorded in main memory for the data block. 
At initialization, main memory clears all lock status bits in the memory 
directory, and all data blocks are indicated as being in the UNOWNED 
state. 
When a processor issues a Read Exclusive command, it will receive a Read 
Response with the lock status bit set or clear, depending upon the value 
of the lock status of the data block in the responding processor's cache. 
If the lock status bit is set, the cache state for the data block is 
updated to EXCLUSIVE-MODIFIED-LOCKED; otherwise the data block's state 
remains EXCLUSIVE-MODIFIED. 
When a processor receives a Forward Read Exclusive or Forward Read Shared 
command, it supplies the requested data with a Read Response command with 
the lock status bit set or cleared, depending on the value of the lock 
status of the data block in the responding processor's cache. The lock 
status bit would be set if the block is in the EXCLUSIVE-MODIFIED-LOCKED 
state. 
When a processor receives a Forward Read Shared command and if a data block 
is in the EXCLUSIVE-MODIFIED state, the data block is written back to main 
memory with a Write Shared command with the lock status bit cleared. If 
the data block is in the EXCLUSIVE-MODIFIED-LOCKED state, the write 
transaction is made with the lock status bit set. 
When a processor needs to evict a data block which is in the 
EXCLUSIVE-MODIFIED state, the block is written back to main memory with a 
Write Unowned transfer with the lock status bit cleared. If the block is 
in the EXCLUSIVE-MODIFIED-LOCKED state, the write transaction is made with 
the lock status bit set.