Cache/disk subsystem with dual aging of cache entries

• US 4,437,155 A
• Filed: 11/14/1980
• Issued: 03/13/1984
• Est. Priority Date: 11/14/1980
• Status: Expired due to Term

• Current Assignee: Sperry Corporation (Unisys Corporation)
• Original Assignee: Sperry Corporation (Unisys Corporation)
• Inventors: Sawyer, Daniel D., Thompson, Marvin J.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Watson, Mark P.
• Application Number:
  US06/207,059
• Time in Patent Office: 1,215 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list

Abstract

When a processor issues a read or write command to read one or more words from a disk, a cache store is checked to see if a copy of the segment(s) containing the word(s) are present therein. If a copy of the segment is not present in the cache store then it is moved from disk to the cache store and sent to the processor. A segment descriptor table is maintained and the entries in the table are linked by forward and backward age links. When a segment is brought into the cache store from a disk because it contains the word or words specified by a command, its segment descriptor is linked in the age chain as the most recently used. Provision is made for reading into the cache store one or more segments in addition to the segment(s) containing the word(s) specified by a command, on speculation that the additional segment(s) contain words most likely to be accessed soon by the processor. The segment descriptor for these additional segments are linked into the age chain at an age which is intermediate the most recently used and the least recently used.

Claims

1. In a data processing system including a host processor for issuing addressing signals specifying data to be accessed, a mass memory, a cache store for storing segments, and a segment descriptor table for storing segment descriptors, there being a segment descriptor associated with each data segment in said cache store and including age information defining, from the most recently accessed to the least recently accessed, the relative lengths of time since each associated data segment has been accessed, the system including means for transferring to said mass memory the least recently accessed segments in said cache store in order to make room for more data segments, the improvement comprising:

means connected to said host processor, said mass memory and said cache store for transferring from said mass memory to said cache store not only a data segment containing data specified by said addressing signals but not resident in said store, but also a number of additional segments; and

,

age modifying means for modifying said age information in said segment descriptors each time data segments are transferred from said mass memory to said cache store to produce modified age information, said modified age information indicating that the data segment containing the data specified by said addressing signals is the most recently accessed data segment, and indicating that said number of additional segments have an age intermediate the most recently accessed and the least recently accessed.

2. The improvement as claimed in claim 1, wherein said age modifying means includes means for storing a value representing the modified age to be assigned to each of said additional segments as said additional segments are transferred from said mass memory to said cache store.

3. The improvement as claimed in claim 1 and further comprising:

means for storing a first value representing a maximum number of segments of data which may be transferred between said mass memory and said cache store;

means for computing a second value representing the number of segments to be transferred from said mass memory to said cache store which contain data specified by said host processor; and

,

difference determining means for determining the difference between said first value and said second value,

said means for transferring data segments from said mass memory to said cache store being responsive to said difference determining means for transferring a number of said additional segments which is equal to said difference.

4. The improvement as claimed in claim 1 wherein said data segments each comprise a plurality of data words.

5. In a data processing system having a host processor, a mass memory for storing segments of data, a cache store for storing copies of segments of data which have been read from, or are to be written to said mass memory, and a store for storing a table of segment descriptors, there being a segment descriptor in said table corresponding to each segment of data resident in said cache store and each of said segment descriptors including a backward age link field and a forward age link field, said age link fields linking said segment descriptors to thereby define an age chain for the segments of data corresponding to said segment descriptors, said backward age link fields defining links in an age chain extending from the most recently accessed data segment in said cache store to the least recently accessed data segment in said cache store and said forward age link fields defining links in an age chain extending from the least recently accessed data segment in said cache store to the most recently accessed data segment in said cache store, a method of assigning ages in said age chain to data segments transferred from said mass memory to said cache store, said method comprising:

assigning to each data segment transferred from said mass memory to said cache store a most recently accessed age if said transfer is made to satisfy a host processor command for access to data in the segment; and

,

assigning to each data segment transferred from said mass memory to said cache store an age which is intermediate said most recently and least recently accessed ages if the transfer is not made to satisfy a host processor command for access to data in the segment.

6. In a system having a host processor, a cache store for storing segments of data, means for linking said segments of data in an age chain according to the relative times at which they were last accessed, a mass memory and means for transferring to said cache store from said mass memory not only segments of data to which access has been required by said host processor but also a number of additional segments to which access has not been required by said host processor, said system being operative to transfer the least recently accessed data segments in said cache store to said mass memory to make room for data segments transferred to said cache store, the method of controlling the aging of segments in said cache store comprising:

assigning to a given segment transferred to said cache store from said mass memory a most recently accessed age if said given segment is transferred because access thereto has been required by said host processor;

assigning to a given segment transferred to said cache store from said mass memory an intermediate age which is intermediate the most recently and least recently accessed ages in said age chain if said given segment is not transferred because access thereto has been required by said host processor.

7. The method as claimed in claim 6 wherein said means for linking said segments of data in an age chain comprises means for storing a segment descriptor table having therein a segment descriptor corresponding to each data segment resident in said cache store, each segment descriptor including a backward age link field pointing to the segment descriptor for the next least recently accessed data segment in the cache store and a forward age link field pointing to the next most recently accessed data segment in said cache store,

said step of assigning an age which is intermediate the most recently and least recently accessed ages comprising adjusting the age links in said chain so as to link the formed segment descriptor in said age chain as the next most recently accessed relative to the last segment descriptor assigned said intermediate age.

8. The improvement as claimed in claim 7 wherein said step of assigning an age which is intermediate the most recently and least recently accessed ages comprises adjusting the age links in the segment descriptors for the next most recently accessed and next least recently accessed data segments, relative to the data segment being assigned said intermediate age, whereby an age field in the segment descriptor for said next most recently accessed and next least recently accessed data segments point to each other and they are adjacent entries in said age chain.