System and method for updating from a read-only to a read-write entry and concurrently invalidating stale cache copies from head-to-tail and tail-to-head directions

This Application is related to co-pending U.S. patent application Ser. No. 09/235,588, entitled “System and Method for Deleting Read-Only Head Entries in Multi-Processor Computer Systems Supporting Cache Coherence with Mixed Protocols,” filed on Jan. 22, 1999, now U.S. Pat. No. 6,321,304 which is hereby incorporated by reference.

1. Field of the Invention

This invention relates generally to cache coherence in computer systems having multiple processors with caches, and more particularly to a system and method for updating a cache entry from read-only to read-write.

2. Description of the Background Art

Multiple-processor computer systems involve various processors which at the same time may each work on a separate portion of a problem or work on a different problem. FIG. 1 shows a multi-processor system, including a plurality of Central Processing Units (CPUs) or processors 102 A, 102 B . . . 102 N, communicating with memory 104 via interconnect 106 , which could be, for example, a bus or a collection of point-to-point links. Processors 102 access data from memory 104 for a read or a write. In a read operation, processor 102 receives data from memory 104 without modifying the data, while in a write operation processor 102 modifies the data transmitted to memory 104 .

Each processor 102 generally has a respective cache unit 108 A, 108 B, . . . 108 N, which is a relatively small group of high speed memory cells dedicated to that processor. A processor 102 's cache 108 is usually on the processor chip itself or may be on separate chips, but is local to processor 102 . Cache 108 for each processor 102 is used to hold data that was accessed recently by that processor. Since a processor 102 does not have to go through the interconnecting bus 106 and wait for the bus 106 traffic, the processor 102 can generally access data in its cache 108 faster than it can access data in the main memory 104 . In a normal operation, a processor 102 N first reads data from memory 104 and copies that data to the processor's own cache 108 N. During subsequent accesses for the same data the processor 102 N fetches the data from its own cache 108 N. In effect, after the first read, data in cache 108 N is the same copy of data in memory 104 except that the data is now in a high-speed local storage. Typically, cache 108 N can be accessed in one or two cycles of CPU time while it takes a processor 102 15 to 50 cycles to access memory 104 . A typical processor 102 runs at about 333 Mhz or 3 ns (nanoseconds) per cycle, but it takes at least 60 ns or 20 cycles to access memory 104 .

A measure of data, typically 32, 64, 128, or 2 n bytes, brought from memory 104 to cache 108 is usually called a “cache line.” The data of which a copy was brought to cache 108 and which remains in memory 104 is called a “memory line.” The size of a cache line or a memory line is determined by a balance of the overhead per read/write operation versus the usual amount of data transferred from memory and cache. An efficient size for a cache line results in transfers spending about 25% of their time on overhead and 75% of their time on actual data transfer.

A particular problem with using caches is that data becomes “stale.” A first processor 102 A may access data in the main memory 104 and copy the data into its cache 108 A. If the first processor 102 A then modifies the cache line of data in its cache 108 A, then at that instant the corresponding memory line becomes stale. If a second processor, 102 B for example, subsequently accesses the original data in the main memory 104 , the second processor 102 B will not find the most current version of the data because the most current version is in the cache 108 A. For each cache-line address, cache coherence guarantees that only one copy of data in cache 108 can be modified. Identical copies of a cache line may be present in multiple caches 108 , and thus be read by multiple processors 102 at the same time, but only one processor 102 is allowed to write, i.e., modify, the data. After a processor 102 writes to its cache 108 that processor 102 must “invalidate” any copies of that data in other caches to notify other processors 102 that their cache lines are no longer current.

FIG. 2A shows valid cache lines D 0 for caches 108 A to 108 N whereas FIG. 2B shows cache 108 B with an updated cache line D 1 and other caches 108 A, 108 C, and 108 N with invalidated cache lines D 0 . The processors 102 A, 102 C, and 102 N with invalidated cache data D 0 in their respective caches 108 must fetch the updated version of cache line D 1 if they want to access that data line again.

Normally and for illustrative purposes in the following discussion, cache coherence protocols are executed by processors 102 associated with their related caches. However, in other embodiments these protocols may be executed by one or more specialized and dedicated cache controllers.

There are different cache coherence management methods for permitting a processor 102 to modify its cache line in cache 108 and invalidate other cache lines. One method (related to the present invention) utilizes, for each cache line, a respective “shared list” representing cache-line correspondences by “double-links” where each cache has a forward pointer pointing to the next cache entry in the list and a backward pointer pointing to the previous cache entry in the list. Memory 104 has a pointer which always points to the head of the list.

FIG. 3 shows a linked list 300 of caches 108 A . . . 108 N with the associated memory 104 . Memory 104 has a pointer which always points to the head (cache 108 A) of the list while the forward pointers Af, Bf, and Cf of caches 108 A, 108 B, and 108 C respectively point forward to the succeeding caches 108 B, 108 C, and 108 D (not shown). Similarly, backward pointers Nb, Cb, and Bb of caches 108 N, 108 C, and 108 B respectively point backward to the preceding caches. Because each cache unit 108 is associated with a respective processor 102 , a linked list representation of cache 108 is also understood as a linked list representation of processors 102 .

There are typically two types of cache sharing list. The first type list is the read-only (sometimes called “fresh”) list of caches for which none of the processors 102 has permission to modify the data. The second type list is a read-write (sometimes called “owned”) list of caches for which the head-of-list processor 102 may have permission to write to its cache 108 . A list is considered “stable” after an entry has been completely entered into or completely deleted from the list. Each of the stable list states is defined by the state of the memory and the states of the entries in the shared list. Relevant states of memory include HOME, FRESH, and STALE. HOME indicates no shared list exists, FRESH indicates a read-only shared list, and STALE indicates the shared list is a read-write list and data in the list can be modified. A processor 102 must get authorization to write to or read from memory. A list entry always enters the list as the list head, and the action of entering is referred to as “prepending” to the list. If a list is FRESH (the data is the same as in memory), the entry that becomes the newly created head receives data from memory; otherwise it receives data from the previous list head. In a read-write list, only the head is allowed to modify (or write to) its own cache line and, after the head has written the data, the head must invalidate the other stale copies of the shared list. In one embodiment, invalidation is done by purging the pending invalidated entries of the shared list.

FIGS. 4A-4F illustrate how the two types of list are created and grown. Each of the FIG. 4 includes a before and an after list with states of the list and memory 104 . In FIG. 4A, initially memory 104 is in the HOME state, indicating there is no cache shared list. Processor 102 A requests permission to read a cache line. Since this is a read request, memory 104 changes from the HOME state to the FRESH state, and the resulting after list 402 AR is a read-only list with one entry 108 A. Cache 108 A receives data from memory 104 because cache 108 A accesses data that was previously uncached. This starts the read-only list 402 AR.

In FIG. 4B processor 102 B requests a read permission to enter the read-only list 402 B, which is the same list as 402 AR of FIG. 4 A. Cache 108 B then becomes the head of the list 402 BR receiving data line from head 108 A. The list 402 BR is still a read-only list since both entries of the list have asked for read-only permission, and therefore the memory state remains FRESH.

In FIG. 4C, memory 104 is initially in the HOME state and processor 102 A requests a read-write permission. Cache 108 A then becomes the head of the list 402 CR. Because a read-write permission was requested, list 402 CR is a read-write list. As soon as memory 104 grants a read-write permission, memory 104 changes from the HOME state to the STALE state.

In FIG. 4D processor 102 B requests a read permission to enter a read-write list 402 D. Cache 108 B becomes the head of the list 402 DR. Since memory 104 is initially in the STALE state, the resulting list 402 DR is a read-write list and memory 104 remains in the STALE state.

In FIG. 4E, the initial list 402 E is read-only with memory 104 in the FRESH state, and processor 102 B requests a write permission. Cache 108 B then becomes the head of the list 402 ER. Since processor 102 B asked for a write permission, memory 104 changes state from FRESH to STALE, and list 402 ER is a read-write list.

In FIG. 4F the list 402 F is a read-write list and processor 102 B requests a write permission. Since list 402 F is read-write, list 402 FR is also read-write, and memory 104 remains in the STALE state. In a read-write list, only the head is allowed to modify (or write to) its own cache line, and, after the head has written the data, the head must invalidate stale copies of the shared list.

In one prior art embodiment, invalidation is done by purging the stale entries of the shared list. Consequently, this invalidation-by-deletion results in a stable read-write list having only one read-write entry.

FIG. 4G shows the original list 402 G and the resulting list 402 GR in which only the head 108 N remains while other list entries have been deleted after an invalidation-by-deletion.

FIG. 4H illustrates an invalidation-by-deletion. In FIG. 4H list 402 H is, for example, a read-write list having one cache entry 108 A. Cache 108 B enters list 402 H as a read-write entry, and after writing, cache 108 A is deleted, resulting in list 402 HR 1 with only one cache 108 B. And in another example, cache 108 C enters list 402 HR 1 with a read-write request. After cache 108 C is modified, cache 108 B is deleted, resulting in the read-write list 402 HR 2 with only one entry 108 C. Thus, a read-write entry entering a one-entry read-write list always results in a one-entry read-write list.

FIG. 4I illustrates how a list having a read-write entry at the tail, and that tail may be the only entry in the list. In FIG. 4I cache 108 B enters read-write list 402 I as a read-only entry, and the resulting list 402 IR 1 has two cache entries 108 A and 108 B with cache 108 A being at the tail in the read-write state and cache 108 B at the head in the read-only state. As long as a read-only cache 108 enters the list, the list keeps growing as list 402 IR 2 and the read-write cache 108 A remains at the tail in the read-write state. In list 402 IR 2 , caches 102 N, 102 C, and 102 B are in the read-only state. However, when a cache 108 enters the list as a read-write, the resulting list becomes a one entry list, like list 402 IR 3 because processor 102 M has invalidated stale cache entries ( 108 A- 108 N) by deleting them.

The deleting scheme illustrated in FIGS. 4G-4I is inherently inefficient because sequentially deleting every entry from the head to the tail to result in list 402 IR 3 takes a long time. Long lists with entries being deleted can seriously degrade system performance. Another inefficiency also arises, for example, in list 402 IR 2 when processor 102 A seeks to write to its cache 108 A. In one prior art embodiment, cache 108 A leaves list 402 IR 2 and re-enters the list as a new entry. Leaving the list poses inefficiency as the list needs to keep track of members entering and leaving. Entering the list as a new entry also suffers the inefficiency of sequential deletion because the processor 102 A has to invalidate or delete other stale entries of the list.

In light of the deficiencies of the prior art, there is a need for a system that can minimize the time to invalidate stale cache copies.

The present invention, advantageous over prior art solutions, improves invalidation times by a factor of nearly two or four as compared to the SCI Standard's sequential invalidation.

The present invention provides a system and a method for updating a cache-sharing list from read-only to read-write in accordance with standard cache coherence protocols. In one embodiment, an updating request is associated with a tail cache entry, and the processor associated with the cache requests the main memory to update the processor's cache line. In response to the request, a copy of the cache line is created and made the head of the list. Thus, there are two cache entry copies in two places in the list. The processor then updates its cache and allows concurrent invalidation of stale cache entries in both directions from head-to-tail (forward) and from tail-to-head (backward).

Two preferred forward-invalidation methods are implemented. In the first (slow) method the list head informs the next-list entry that the next-list entry is to be invalidated. In response the next-list entry informs the head of the identity of the next-list entry's successor, which in turn needs to be invalidated. The next-list entry is then invalidated and the next-list entry's successor becomes the next-list entry (with respect to the list head) and is subjected to the same invalidation process as the previous next-list entry. The process continues until all entries in the list have been invalidated.

In the second (fast) method of forward invalidation, the head first informs the next-list entry that every stale entry in the list is to be invalidated. In response the next-list entry informs the head that a validate completion signal will be returned to the head. The next-list entry is then invalidated and the invalidation signal is forwarded towards the tail where the last invalidated entry sends to the head a confirmation signal that all invalidations have been completed.

In backward invalidation the tail informs the preceding entry that the preceding entry is about to become a tail, and that upon becoming the tail the preceding entry itself needs to be invalidated. The tail is then invalidated and the preceding entry becomes the tail and is subjected to the invalidation process, and so on until all invalidations have been completed.

Because the fast forward invalidation poses a potential deadlock, this invalidation method is used only when deadlock is free; otherwise when potential deadlock is detected the slow method is used even though the slow method takes about twice as long to complete. By having fast forward invalidation and concurrent backward invalidation the overall invalidation time is improved by about four times as compared to slow forward invalidation alone.

FIG. 1 shows a conventional multi-processor system with a cache memory for each processor;

FIG. 2A illustrates all processors' cache lines being valid;

FIG. 2B shows one cache line being valid while others are invalidated;

FIG. 3 shows a cache-sharing double-linked list;

FIG. 4A illustrates creation of a read-only shared list;

FIG. 4B illustrates a cache entry entering a shared read-only list;

FIG. 4C illustrates creation of a read-write shared list;

FIG. 4D shows a read-permission entry entering a read-write list;

FIG. 4E shows a write-permission entry entering a read-only list;

FIG. 4F shows a write-permission entry entering a read-write list;

FIG. 4G shows invalidated entries being deleted;

FIG. 4H illustrates a read-write entry joining a read-write list, resulting in a one-member list;

FIG. 4I illustrates a growing list and a one-member list after invalidation by deletion;

FIG. 5 shows an operation of the invention in which a list 502 requests that its tail cache entry be updated;

FIG. 6A shows two copies of a cache in two places in the list;

FIG. 6B shows a method in accordance with the present invention to update an entry;

FIG. 6 C. is a flowchart showing steps of a first embodiment to invalidate a list of FIG. 6A;

FIG. 6D is a flowchart showing steps of a second embodiment to invalidate a list of FIG. 6A;

FIG. 6E is a flowchart showing steps of invalidating stale entries from tail-to-head;

FIG. 7 shows a cache in accordance with the present invention;

FIG. 8 shows a state-transition table of a cache requester in FIG. 5;

FIG. 9 shows a state-transition table of a memory responder in FIG. 5; and

FIG. 10 shows a state-transition table of a cache responder in FIG. 5 .

The present invention provides a system and method for updating a cache list entry from the read-only type to the read-write type. After the entry is updated, invalidation of stale cache entries starts concurrently from both ends of the list, i.e., in the directions from head-to-tail and from tail-to-head. The invention is applicable for example when the processor associated with a tail cache entry in a read-only list has obtained read-write permission and seeks to update its cache.

FIG. 5 shows an example of read-only list 502 having cache entries 108 A, 108 B, 108 C, 108 D, and 108 E, and processor 102 E seeks to update its cache 108 E. In accordance with the invention, when processor 102 E is about to update its cache 108 E, cache 108 E remains in the list, and a second copy of cache 108 E is created and made the head of the list. The invention is advantageous over prior art solutions in which cache 108 E would be deleted from, then reenter, list 502 .

FIG. 6A shows a list 600 A with two copies 108 E_ 1 and 108 E_ 2 of cache 108 E. Cache 108 E_ 2 is the head, while cache 108 E_ 1 is the tail, of the list.

FIG. 6B shows a method of the present invention used to transform list 502 of FIG. 5 to list 600 A of FIG. 6 A. At step 600 B, processor 102 E informs memory 104 that processor 102 E seeks to update its cache 108 E. At step 608 B a second copy of cache 108 is created. Cache 108 E, or now 108 E_l, remains as the tail of the list while the second copy, or cache 108 E_ 2 , is made the head of the list. At step 612 B cache 108 E_ 2 is updated and at step 616 B invalidation of stale entries (cache 108 B, 108 C, 108 D, and 108 E_ 1 ) starts concurrently from head to tail and from tail to head.

FIG. 6C illustrates a first method for invalidating list 600 A of FIG. 6A in the direction from head to tail. At step 600 C cache 108 A is informed that it is about to be invalidated. At step 604 C cache 108 A informs the head 102 E_ 1 that cache 108 B (successor of cache 108 A) is the next to be invalidated, and at step 608 C cache 108 A is invalidated. In the invalidation by deletion, cache 108 A is deleted from the list. Step 612 C repeats steps 600 C- 608 C to other stale cache entries (caches 108 B, 108 C, 108 D, and 108 E_ 1 in the list chain) until all invalidation is complete.

FIG. 6D illustrates a second method for invalidating the list 600 A of FIG. 6A, also in the direction from head to tail. At step 600 D next list entry 108 A is informed that all stale cache entries are to be invalidated. At step 604 D cache 108 A responds to cache 108 E_ 2 that once all stale cache entries are invalidated a completion signal will be returned to cache 108 E_ 2 . At step 608 D cache entry 108 A is invalidated, and invalidation is forwarded to cache 108 B, 108 C, and eventually to the tail 108 E_ 1 at step 612 D. At step 616 D the last invalidated copy (cache 108 E_ 1 ) sends a completion signal to head 108 E_ 2 indicating that all entries have been invalidated.

FIG. 6E shows an invalidation method in the direction from tail to head. At step 600 E the tail (cache 108 E_ 1 of list 600 A in FIG. 6A) informs its preceding entry (cache 108 D) that cache 108 D is about to become a tail and that after becoming the tail, cache 108 D as in turn needs to be invalidated. At step 604 E the tail 108 E_ 1 is invalidated and leaves cache 108 D as the tail. The method then returns to step 600 E with cache 108 D as a tail, and continues until all stale entries ( 108 C, 108 B, and 108 A) have been invalidated.

The head-to-tail invalidation method of FIG. 6D poses a potential deadlock because an incoming invalidation request completion (from cache 108 B to cache 108 C, or cache 108 C to cache 108 D, etc.) is dependent on outgoing invalidate request completions (from cache 108 E_ 1 to cache 108 E_ 2 ). However, the possible deadlock is detectable. Therefore, when deadlock is clear the head-to-tail deletion method of FIG. 6D is implemented, but when deadlock potential is detected the invalidation method of FIG. 6C is implemented even though this method takes twice as long to complete compared to the method of FIG. 6 D.

FIG. 7 shows, in relevant parts, a cache 108 in accordance with the invention that includes a requester 702 and a responder 704 . Requester 702 , via a Request on line 7003 , initiates an action desired by a processor 102 to another processor 102 or to memory 104 , and receives a Response on line 7005 . Responder 704 receives either from a processor 102 or memory 104 a Request on line 7007 , and, via a Response on line 7009 , responds to the action requested by a requester 702 . In the preferred embodiment memory 104 includes a responder 704 , but does not include a requester 702 . Row la shows an action taken by cache requester 702 when memory 104 was in the fresh (“F”) state while row 1 b shows the same action taken by cache requester 702 when memory 104 was in a stale state. The suffixes “F” and “S” correspond to the fresh state and

FIG. 8 shows a state-transition table of cache requester 702 of cache 108 E in FIG. 5 . In row 1 a requester 702 , associated with a tail cache 108 E, has a “TAIL” old state. Cache 108 E then generates an “mReadOwned” request, that is, cache 108 E requests memory (“m”) 104 for a read-write (“Owned”) permission. Cache 108 E then receives a “DONE 13 F” response and the identification of the next (“IDnext”) cache entry (cache 108 A) for cache 108 E to point to. “DONE” indicates that cache 108 E is granted the request, and “F” indicates that memory 104 was in the read-only state. Cache 108 E then changes state to “ENDS_TAIL_F,” i.e., cache 108 E now has two copies 108 E_ 1 and 108 E_ 2 , and copy 108 E_ 1 remains as a tail (“TAIL”), but both copies 108 E_ 1 and 108 E_ 2 are at both ends (“ENDS”), the tail end and the head end, of the list.

Row 1 b is the same as row 1 a , except that row 1 b deals with the situation in which memory 104 was in the read-write state (“S”).

In rows 2 a and 2 b requester 702 , in response to an action taken in row 1 a , has an “ENDS_TAIL_F” old state and generates a “cMarkPost” request. A “c” indicates that requester 702 asks the next cache entry 108 (cache 108 A) to become the tail and then delete itself (“MarkPost”);

In row 2 a requester 702 receives a “DONE” response and changes state to “HEADd_INVAL_F,” indicating that cache 108 E_ 2 is the only copy of cache 108 E and is the head (“HEAD”) of a read-write (“d”) list. Consequently, invalidation (“INVAL”) of stale cache copies occurs as appropriate.

In row 2 b requester 702 receives a “BUSY” response as the next cache entry is busy and cannot perform the request, that is, it cannot invalidate itself. Requester 702 thus changes state to “ENDS_INVAL_F,” that is, requester 702 is still at the end and needs to be invalidated.

Rows 3 a and 3 b are the same as rows 2 a and 2 b respectively, except that rows 3 a and 3 b deal with the situations in which memory 104 was previously in the read-write state.

In rows 4 a , 4 b , and 4 c requester 702 , in response to an action taken in rows 2 b , 4 a , and 4 c , has an “ENDS_INVAL_F” state. Requester 702 then generates a “cMarkInval_F” request to ask the next cache (“c”) entry 108 to invalidate (“MarkInval”) itself. An “F” indicates that memory 104 was previously in the read-only state.

In rows 4 a , requester 702 receives a “MORE” response when there is at least one other cache entry 108 to be invalidated and when the next cache entry 108 is not the second copy (cache 108 E_ 1 ) of cache 108 E. Requester 702 remains the “ENDS_INVAL_F” state, but continues with a revised next-cached identifier provided by a cache that has been invalidated.

In row 4 b , where the next cache entry 108 is the second copy (cache 108 E_ 1 ) of cache 108 E (“IDreq”), requester 702 also returns a “MORE” response, but changes state to “ONLYd,” which indicates that, after cache 108 E_ 1 is invalidated, cache 108 E_ 2 is the only (“ONLY”) copy of cache 108 E in a read-write (“d”) list.

In row 4 c , requester 702 receives a “BUSY” response, and thus remains the “ENDS_INVAL_S” state and will continue to retry the “cMarkInval_F” request.

Rows 5 a , 5 b , and 5 c are the same as rows 4 a , 4 b , and 4 c , respectively, except that rows 5 a - 5 c deal with the situations in which memory 104 was previously in the read-write state (“S”).

In rows 6 a , 6 b , and 6 c requester 702 , in response to an action taken in rows 2 a , 6 a , and 6 c , has a “HEADd_INVAL_F” old state. Requester 702 associated with cache 108 E (or 108 E_ 2 in FIG. 6) which is the head (“HEAD”) of a read-write (“d”) list. Cache 108 E then generates a “cMarkInval_F” request to ask the next cache (“c”) entry to invalidate (“MarkInval”) itself. An “F” indicates memory 104 was previously in a read-only state.

In row 6 a cache requester 702 receives a “MORE” response and the identification of the successor of the next (“IDnext”) cache entry. Requester 702 thus remains the “HEADd_INVAL_F” state and continues to invalidate other cache entries in the list.

In row 6 b cache requester 702 receives a “DONE” response, and changes state to “ONLYd.”

In row 6 c cache requester 702 receives a “BUSY” response, and remains the “HEADd_INVAL_F” state.

Rows 7 a , 7 b , and 7 c are the same as rows 6 a , 6 b , and 6 c , respectively, except that rows 7 a - 7 c deal with the situations in which memory 104 was previously in the read-write state.

Rows 8 a and 8 b shows requester 702 associated with a cache 108 that was initially in the middle of the list, has become a tail, then generates an “mMarkPost” request to memory (“m”) 104 to delete the cache 108 itself. In row 8 a memory 104 acknowledges the request by generating a “DONE” response which cache 108 receives. Cache 108 then changes state to “INVAL.” In row 8 b cache 108 receives a “BUSY” response, and thus remains the “LAST_TAIL” state.

Row 9 shows requester 702 , in response to an action taken in rows 4 b , 5 b , 6 b , and 7 b , has an “ONLYd” old state, which, being a stable state, generates no further request.

FIG. 9 shows a state-transition table of a memory responder 704 M of memory 104 . States of responder 704 M during the creation of list 500 A are not shown. In row 1 memory 104 points to the head (“IDhead”) of the list, and responder 704 M has a “FRESH” state for a read-only list. Responder 704 M then receives an “mReadOwned” request; thus changes state to “STALE,” points to the requesting (“IDreq”) cache entry (cache 108 E_ 2 of FIG. 600 A), and returns a “DONE_F” response.

Row 2 is the same as row 1 except that the list, instead of being a read-only list, is a read-write list. Memory 104 thus has a “STALE” old state and returns a “DONE_S” response.

FIG. 10 shows a state-transition table of a cache responder 704 of a cache entry 108 in FIGS. 5 and 6A.

Rows 1 a and 1 b show that responder 704 receives a “cMarkedPost” request from a tail entry requesting that responder 704 become a tail entry and then invalidate itself. In row la responder 704 becomes a tail, returns a “DONE” response, and changes state to “LAST_TAIL.”

In row 1 b responder 704 cannot become a tail, ignores the request, returns a “BUSY” response, and therefore remains the same state.

In row 2 a responder 704 having an “ENDS_INVAL_F” old state, that is, responder 704 is associated with a cache being at both ends of the list (cache 108 E_ 1 and 108 E_ 2 ). An “F” indicates that memory 104 was previously in a read-only state. Responder 704 then receives a “cMarkInval_F” request to invalidate itself. An “F” in “cMarkInval_F” indicates that responder 704 is associated with the tail, i.e, cache copy 108 E_ 1 . Consequently, request “cMarkInval_F” comes from a preceding entry of tail 108 E_ 1 , or cache 108 D. Copy 108 E_ 1 , after invalidating itself, is deleted from the list. Responder 704 is now associated with only cache copy 108 E_ 2 , which is the head of the list. Therefore, responder 704 changes state to “HEADd_INVAL_F” and returns a “DONE” response.

Row 2 b is the same as row 2 a , except that rows 2 b deals with the situations in which memory 104 was previously in a read-write (“S”) state.

In row 3 a responder 704 also has an “ENDS_INVAL_F” old state, but receives a “cMarkInval_S” request to delete itself. An “S” in “cMarkInval_S” indicates that responder 704 is associated with the head copy 108 E_ 2 . In this case responder 704 ignores the invalidation request until after all stale cache copies 108 A, 108 B, 108 C, 108 D, and 108 E_ 1 have been invalidated.

Row 3 b is the same as row 3 a except that row 3 b deals with the situations in which memory 104 was previously in the read-write (“S”) state.

In row 4 a responder 704 has a “CORE,” state, i.e., it is in the middle of the list. Responder 704 then receives a “cMarkInval_F” request to invalidate itself. Responder 704 changes state to “INVAL,” i.e., invalidates itself, and returns a “DONE” response together with the identification of the next list entry (“IDnext”) to be invalidated.

Row 4 b is the same as row 4 a except that row 4 b deals with the situations in which memory 104 was in the read-write (“S”) state.

In row 5 a responder 704 is associated with the head copy 108 E_ 2 and copy 108 E_ 1 has been deleted from the list. Responder 704 then receives a “cMarkInval_S” to delete itself. Responder 704 returns a “BUSY” response to ignore the request until after stale cache copies 108 A, 108 B, 108 C, and 108 D have been invalidated. Responder 704 thus remains the same state “HEAD_INVAL_F.”

Row 6 a is the same as row 6 b except that row 6 b deals with the situations in which memory 104 was previously in the read-write state.

The present invention has been explained with reference to various preferred embodiments. Other embodiments will be apparent to those skilled in the art after reading this disclosure. For example, the present invention may be implemented in either software or hardware and any implementation of lists can utilize the invention. Additionally, the invention may effectively be used in combination with multi-processor systems other than those described in accordance with the preferred embodiments. Therefore, these and other variations upon the preferred embodiment are intended to be covered by the following claims.