Cache system adopting an LRU system, and magnetic disk controller incorporating it

• US 4,835,686 A
• Filed: 05/28/1986
• Issued: 05/30/1989
• Est. Priority Date: 05/29/1985
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation), Toshiba Computer Engineering Corporation (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation), Toshiba Computer Engineering Corporation (Toshiba Corporation)
• Inventors: Inoue, Junichi, Furuya, Akihiko, Kanamaru, Kouiti
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US06/867,449
• Time in Patent Office: 1,098 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/136
• CPC Class Codes: G06F 11/1415 at system level
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 2212/312 In storage controller
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0656 Data buffering arrangements

Abstract

A cache system employing an LRU (Least Recently Used) scheme in a replacement algorithm of cache blocks and comprising a directory memory whose entires have LRU counter fields, a host system issuing a read/write command to which an arbitrary LRU setting value is appended, a directory search circuit, and a microprocessor. The directory search circuit searches the directory memory in response to the read/write command issued from the host system. The microprocessor stores the LRU setting value appended to the read/write command in the LRU counter field of the hit entry of the directory memory or of the entry corresponding to the replacement target cache block, in response to the search result of the directory search circuit.

Claims

1. A cache system employing an LRU (Least Recently Used) scheme in a replacement algorithm of cache blocks, comprising:

a cache memory for storing a plurality of cache blocks;

a directory memory having fields storing, in respective entries corresponding to respective cache blocks of said cache memory, block designation information for blocks stored in said cache memory and having LRU counter fields indicating resident status in said cache memory of these blocks;

command issuing means for issuing a read/write command to which an arbitrary LRU setting value and designation information for a read/write target block are appended;

directory search means for searching whether the read/write target block is stored in said cache memory by comparing the stored block designation information of respective entries with the read/write designation information and for indicating a hit when the read/write target block is found to be stored in the cache memory and a cache miss hit when the read/write target block is not found to be stored in the cache memory; and

storing means for storing the arbitrary LRV setting value in the arbitrary LRU counter field of said directory memory corresponding to the cache block which has been hit when a hit occurs, and for storing the arbitrary LRU setting value in the LRU counter field in the directory memory corresponding to the cache block in which the read/write target block is stored by the storing means when a miss hit occurs.

2. A system according to claim 1, further comprising:

a first register for storing a star address of a directory memory entry corresponding to a hit cache block if a cache hit occurs as a result of the directory search, the start address being stored together with a cache hit flag, and said directory search means determining a cache miss hit upon detecting the cache hit flag being off;

a second register for storing a start address of a directory memory field entry having a largest LRU value; and

wherein the storing means stores the read/write target block in the cache block corresponding to the entry specified by the start address stored in said second register when a cache miss hit is indicated and no empty space is available in said cache memory.

3. A system according to claim 2, wherein said storing means checks said first register, initializes an LRU value of the directory memory field entry accessed in response to the start address in said first register, into the arbitrary LRU value when a cache hit is detected, and initializes any one of an LRU value of an unstored entry of said directory memory, and an LRU value of the directory memory entry accessed by an address of said second register, into the arbitrary LRU value appended to the read/write command when a cache miss hit is indicated in a read mode.

4. A cache system attached to a host system, said cache system having a cache memory in a disk controller, said cache memory being adapted to store part of a copy of the data of a disk unit in a plurality of cache blocks, the cache system comprising:

a directory memory including, in an entry corresponding to each of the cache blocks in the cache memory, a field for storing specified data of a disk block stored in the cache memory, and a field for storing data representing incompletion of write data specified by the host system on said disk unit;

directory search means for searching whether a write target disk block is stored in said cache memory by comparing the stored disk block specified data in each entry of said directory memory with the write target disk block specifying data, in response to a disk write instruction having data specifying the write target disk block from the host system and for indicating a hit when the write target disk block is determined to be stored in the cache memory and for indicating a miss hit when the write target disk block is determined to not be stored in the cache memory; and

write instruction execution control means for, if a cache hit is indicated and an instructed from said host system is the specified disk write instruction, accessing said directory memory to determine if the number of entries whose incompletion of write data storing fields are set exceeds a predetermine number, and when the number of entries is smaller than the predetermined number, inhibiting writing of the write data in said disk unit, writing the write data specified by the write instruction in a corresponding block in said cache memory, and setting the incompletion of write data storing field of the entry in said directory memory.

5. A system according to claim 4, wherein, when the number of entries in which the incompletion of write data storing fields are set exceeds the predetermined number, said write instruction execution control means writes the write data in the corresponding block in said cache memory and in said disk unit, writes in said disk unit at least the contents of said cache memory which are accessed by entries whose number exceeds the predetermined number, and resets the incompletion of write data storing field.

6. A system according to claim 4, further comprising means for searching, upon power failure,

incompletion of write data in respective entries of said directory memory, and for writing data stored in the cache block of said cache memory corresponding to the entry in which the incompletion of write data field is set, into the corresponding disk block of said disk unit.

7. A system according to claim 4, wherein the number of entries in which incompletion of write data storing fields are a set is established to be a maximum for allowing writing in said disk unit in a backup operation upon power failure.

8. A system according to claim 5, wherein the number of entries in which incompletion of write data fields are set is established to be a maximum for allowing writing in said disk unit in a backup operation upon power failure.

9. A disk cache system having a cache memory with a plurality of cache blocks in a disk controller, said cache memory being adapted to store part of a copy of the data of a disk, comprising:

a directory memory including, in an entry corresponding to each of the cache blocks in said cache memory, a field for storing specified data of a disk data block stored in said cache memory, a field for storing data representing incompletion of write data specified by a host system on said disk unit, and a field for storing data for inhibiting replacement of a disk data block specified by a host system;

directory search means for searching whether a read target disk block is stored in said cache memory by comparing the stored disk block specified data in each entry of said directory memory with the write target disk block specifying data, in response to a disk read instruction having data specifying the read target disk block from said host system, and for indicating a hit when the read target disk block is determined to be stored in the cache memory and for indicating a miss hit when the read target disk block is determined to not be stored in the cache memory; and

read instruction execution control means for, if a cache miss hit is indicated by said directory search means and an instruction from said host system is a disk read instruction, accessing said directory memory to determine an entry to be replaced among the entries whose replacement inhibiting data storing fields are reset, writing, if the incompletion of write data storing field of said entry to be replaced is set, data of the corresponding block in said cache memory in said disk unit and thereafter writing the read data in the corresponding block and transferring the read data to said host system, resetting the incompletion of write data storing field of the entry to be replaced, and setting/resetting the replacement inhibiting data storing field in response to the read instruction.

10. A system according to claim 9, wherein the disk read instruction includes control data for setting/resetting the replacement inhibiting data storing field of the entry to be replaced when a cache miss hit is indicated during a disk read request.

11. A disk cache system having a cache memory in a disk controller, said cache memory being adapted to store part of a copy of the disk data blocks of a disk unit in a plurality of cache blocks, comprising:

a directory memory including, in an entry corresponding to each of the cache blocks in said cache memory, a field for storing specified data of a disk block stored in said cache memory, a field for storing data representing incompletion of write data specified by a host system on said disk unit, and a field for storing data for inhibiting replacement of a disk data block specified by a host system;

directory search means for searching whether a read/write target disk block is stored in said cache memory by comparing the stored disk data block specified data in each entry of said directory memory with the read/write target disk block specifying data, in response to a disk write instruction or a disk read instruction from said host system, and for indicating a hit when the read/write target disk block is determined to be stored in the cache memory and for indicating a miss hit when the read/write target disk block is determined to not be stored in the cache memory; and

write instruction execution control means for, if the cache hit is indicated and an instruction from said host system is an instruction for specifying withholding of writing data into said disk, accessing said directory memory to determine if the number of entries whose incompletion of write data storing fields are set exceeds a predetermined number, and when the number of entries is smaller than the predetermined number, withholding writing of the write data in said disk unit, writing the write data specified by the write instruction in a corresponding block in said cache memory, and setting the incompletion of write data storing field of the entry in said directory memory; and

read instruction execution control means for, if a cache miss hit is indicated by said directory search means and an instruction from said host system is a disk read instruction, accessing said directory memory to determine an entry to be replaced among the entries whose replacement inhibiting data storing fields are reset, writing, if the incompletion of write data storing field of said entry to be replaced is set, data of the corresponding block in said cache memory in said disk unit and thereafter writing the read data in the corresponding block and transferring the read data to said host system, resetting the incompletion of write data storing field, and setting/resetting the replacement inhibiting data storing field in response to the read instruction.

12. A system according to claim 11, wherein, when the number of entries in which the incompletion of write data storing fields are set exceeds the predetermined number, said write instruction execution control means wires the write data in the corresponding block in said cache memory and said disk unit, writes in said disk unit at least the contents of said cache memory which are accessed by entries, whose number exceeds the predetermined number, and resets the incompletion of write data storing fields.

13. A system according to claim 11, wherein the number of entries whose incompletion of write data storing fields are set is established to be a maximum number of entries for allowing writing in said disk unit in a backup operation upon power failure.

14. A system according to claim 12 wherein the number of entries whose incompletion of write data storing fields are set is established to be a maximum number of entries for allowing writing in said disk unit in a backup operation upon power failure.

15. A system according to claim 11, wherein the disk read instruction includes control data for setting/resetting the replacement inhibiting data storing field of the entry to be replaced when a cache miss hit is indicated in the disk read request mode.