Patent ID: 7533239
Filing Date: 2009-05-12
Classification: G06F

Abstract:
1. A data system using a least recently used (LRU) caching scheme using synchronous and asynchronous prefetch of data from a data storage device, the system avoiding violation of stack property substantially without incurring additional sequential misses from cache at least in part by determining a marginal utility of adding space to a sequential list to be equal to a number between s/L and 2s/L, inclusive, wherein L represents the length of the sequential list and “s” is a rate of sequential misses, wherein the system executes logic including: empirically determining a marginal utility of adding space to a random list; and based on the determining and Empirically determining acts, dynamically establishing a desired size of the sequential list, wherein the logic executes the empirically determining act by determining the rate “s” of sequential misses as the number of se sequential misses during a time period defined by two successive cache hits in a bottom portion ΔL of the random list, and further wherein the system executes logic comprising: moving at least one newly prefetched group of units of data along with an asynchronous trigger unit of data in the group of units of data to a most recently used (MRU) portion of a sequential data list; and moving at least some unaccessed units of data in the group of units of data to the MRU portion of the sequential data list.