Patent ID: 8112589

Claim:
A storage device for caching data read from a main memory and data to be written in the main memory, comprising: a cache memory having a plurality of cache segments, one or more cache segments holding data matching with data in the main memory being set in a protected state to protect the cache segments from a rewrite state, an upper limit of a number of the one or more cache segments being set in a protected state being a predetermined reference number; and a cache controller that, in accordance with a write cache miss, allocates a selected cache segment selected from those cache segments which are not in the protected state to cache write data and writes the write data in the selected selected cache segment; wherein each of the cache segments is in any one of a plurality of states including at least an invalid state where valid data is not included, the protected state, a shared state where data matches with data in the main memory but can be replaced with respect to data writing, and an update state where data to be written in the main memory is included, and in accordance with the write cache miss, the cache controller selects as the selected cache segment: a first cache segment if the first cache segment is in the invalid state; else a second cache segment if the second cache segment is in the shared state; else a third cache segment if the third cache segment is in the update state after writing data in the cache segment in the update state back in the main memory; and then allocates the selected cache segment to cache write data; wherein in accordance with the write cache miss, if the selected cache segment is the second cache segment, the cache controller selects, as the second cache segment, from the cache segments in the shared state, a cache segment whose LRU value which is an index value indicating an unused period indicates a longest unused period, and if the selected cache segment is the third cache segment, the cache controller writes data in at least one of those cache segments in the update state whose LRU values indicate a longest unused period back in the main memory, and selects, as the third cache segment, one of the cache segments whose data was written back to main memory; wherein under a condition that the third cache segment in the update state is allocated to cache write data, the cache controller resets the LRU value of the allocated third cache segment and updates each of the LRU values of other cache segments in the update state to a value indicating a longer unused period; and wherein the main memory can write data block by block, a block corresponding to a plurality of cache segments, and under a condition that the third cache segment in the update state is allocated to cache write data, the cache controller resets the LRU value of the allocated third cache segment and resets the LRU value of a fourth cache segment in the update state which stores data in a same block as the allocated fourth cache segment belongs.