Asynchronous read-ahead disk caching using multiple disk I/O processes and dynamically variable prefetch length
First Claim
1. A method for operating a data cache that is coupled to a data store, comprising the steps of:
- receiving, from a requestor, a Demand for a unit of data, the unit of data being a constituent unit of data of a file comprised of a plurality of logically sequential units of data;
determining from one or more data cache entries if the Demanded unit of data is resident in said data cache; and
if the Demanded unit of data is determined to be resident in the data cache, returning the Demanded unit of data from the data cache to the requestor, wherein the step of determining includes the steps of,determining from a predetermined one of the data cache entries if the Demanded unit of data is a unit of data that was most recently prefetched into the data cache from the data store, and, if so,prefetching up to L further units of data from the data store to the data cache, wherein L represents a content of a Prefetch Block Length Counter;
wherein,if the step of determining from one or more data cache entries if the Demanded unit of data is resident in the data cache indicates that the Demanded unit of data is not resident in the data cache, the method executes instead the steps of;
decreasing the value of L by a decrease increment; and
fetching the Demanded unit of data into the data cache while also prefetching up to L further units of data from the data store to the data cache.
3 Assignments
0 Petitions
Accused Products
Abstract
A file-based Read-ahead method employs asynchronous I/O processes to fetch Demand and Read-ahead data blocks from a disk (4), depending on their physical and logical sequentialities. When a file system (10) issues an I/O address to obtain data blocks from a file, it also determines the disk location of data blocks that are logically consecutive with the demanded data. The number of such data blocks to be determined in this process is accomplished in accordance with a dynamic Read-ahead method. If the data blocks are physically consecutive, a single I/O request is sent to a disk driver to obtain both the Demand data block and to Prefetch the Read-Ahead data block(s). If, instead, the data blocks are found not to be physically consecutive, a plurality of asynchronous disk I/O requests are issued so as to separately obtain the Demand and the Read-Ahead data blocks.
-
Citations
11 Claims
-
1. A method for operating a data cache that is coupled to a data store, comprising the steps of:
-
receiving, from a requestor, a Demand for a unit of data, the unit of data being a constituent unit of data of a file comprised of a plurality of logically sequential units of data; determining from one or more data cache entries if the Demanded unit of data is resident in said data cache; and if the Demanded unit of data is determined to be resident in the data cache, returning the Demanded unit of data from the data cache to the requestor, wherein the step of determining includes the steps of, determining from a predetermined one of the data cache entries if the Demanded unit of data is a unit of data that was most recently prefetched into the data cache from the data store, and, if so, prefetching up to L further units of data from the data store to the data cache, wherein L represents a content of a Prefetch Block Length Counter;
wherein,if the step of determining from one or more data cache entries if the Demanded unit of data is resident in the data cache indicates that the Demanded unit of data is not resident in the data cache, the method executes instead the steps of; decreasing the value of L by a decrease increment; and fetching the Demanded unit of data into the data cache while also prefetching up to L further units of data from the data store to the data cache. - View Dependent Claims (2, 3, 4, 5, 7, 8, 9)
-
-
6. A method for operating a data cache that is coupled to a data store, comprising the steps of:
-
receiving, from a requestor, a Demand for a unit of data; determining from one or more data cache entries if the Demanded unit of data is resident in said data cache; and if the Demanded unit of data is determined to be resident in the data cache, returning the Demanded unit of data from the data cache to the requestor, wherein the step of determining includes the steps of, determining from a predetermined one of the data cache entries if the Demanded unit of data is a unit of data that was most recently prefetched into the data cache from the data store, and, if so, increasing a value L of a prefetch unit counter; determining if a previously Demanded unit of data was also a unit of data that was most recently prefetched into the data cache from the data store; and
, if not,prefetching up to L units of data from the data store to the data cache, the up to L prefetched units of data being logically contiguous to a last prefetched unit of data; and updating the predetermined one of the data cache entries to indicate the identities of the prefetched units of data;
otherwiseif the step of determining from one or more data cache entries if the Demanded unit of data is resident in a data cache indicates that the Demanded unit of data is not resident in the data cache, the method executes instead the steps of; decreasing the value of L; fetching the Demanded unit of data into the data cache while also prefetching up to L units of data from the data store to the data cache, the up to L units of data being logically contiguous to the Demanded unit of data; and updating the predetermined one of the data cache entries to indicate the identities of the prefetched units of data.
-
-
10. A digital data processor comprised of a data cache that is coupled to a data store, said data processor further comprising:
-
means, coupled to said data cache and to said data store, for prefetching units of data from the data store to the data cache; means for receiving a Demand for a unit of data; first means for determining from one or more data cache entries if the Demanded unit of data is resident in said data cache; means, responsive to the Demanded unit of data being determined to be resident in the data cache, for returning the Demanded unit of data from the data cache; second means for determining from a predetermined one of the data cache entries if the Demanded unit of data is a unit of data that was most recently prefetched into the data cache from the data store, and, if so, for increasing a value L of a prefetch unit counter means; third means for determining if a previously Demanded unit of data was also a unit of data that was most recently prefetched into the data cache from the data store; and
, if not, causing said prefetching means to prefetch up to L units of data from the data store to the data cache;means for updating the predetermined one of the data cache entries to indicate the identities of the prefetched units of data;
whereinthe digital data processor further comprises means, responsive to the operation of the first determining means indicating that the Demanded unit of data is not resident in the data cache, for decreasing the value of L;
for fetching the Demanded unit of data into the data cache and for causing said prefetching means to prefetch up to L units of data from the data store to the data cache; and
for updating the predetermined one of the data cache entries to indicate the identities of the prefetched units of data; andmeans, responsive to the second determining means indicating that the Demanded unit of data is a unit of data that is resident in the data cache but is not a unit most recently prefetched into the data cache from the data store, for maintaining the value of L at a current value. - View Dependent Claims (11)
-
Specification