Cache evictions from data cache based on content of address translation table cache and address translation table

Abstract

A storage device includes a non-volatile memory, a cache memory and a memory controller. The non-volatile memory stores a logical-to-physical address translation table for managing partitioned data and storage locations thereof. The cache memory stores a data cache and a logical-to-physical address translation table cache which holds a portion of the logical-to-physical address translation table. When the memory controller receives a data read-out request from outside, in the case no empty entry is found in the data cache, among the partitioned data in the data cache, it creates an empty entry to read out the data thereto by evacuating partitioned data of which entries in the logical-to-physical address translation table exist in the logical-to-physical address translation table cache into the non-volatile memory prior to other partitioned data.