Adaptive read-ahead disk cache

• US 5,809,560 A
• Filed: 10/13/1995
• Issued: 09/15/1998
• Est. Priority Date: 10/13/1995
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Compaq Computer Corporation (HP Inc.)
• Inventors: Schneider, Randy D.
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): TZENG, FRED
• Application Number:
  US08/543,067
• Time in Patent Office: 1,068 Days
• Field of Search: 395/440, 395/471, 395/417, 395/823, 711/6, 711/203, 711/204, 711/202, 711/213
• US Class Current: 711/204
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

An adaptive read ahead cache is provided with a real cache and a virtual cache. The real cache has a data buffer, an address buffer, and a status buffer. The virtual cache contains only an address buffer and a status buffer. Upon receiving an address associated with the consumer'"'"'s request, the cache stores the address in the virtual cache address buffer if the address is not found in the real cache address buffer and the virtual cache address buffer. Further, the cache fills the real cache data buffer with data responsive to the address from said memory if the address is found only in the virtual cache address buffer. The invention thus loads data into the cache only when sequential accesses are occurring and minimizes the overhead of unnecessarily filling the real cache when the host is accessing data in a random access mode.

Claims

1. A method for buffering read requests from a bus master to a data storage device using a cache system, said bus master having a bus master address output for requesting data and a bus master data input for receiving data corresponding to said bus master address output, said data storage device having a data storage device address input for receiving a data storage device address and a data storage device data output for providing data corresponding to said data storage device address input, said cache system having a bus master address input coupled to said bus master address output, a bus master data output coupled to said bus master data input, a data storage device address output coupled to said data storage address input, and a data storage device data input coupled to said data storage device data output, said cache system having a real cache with a real cache data buffer, a real cache address buffer and a real cache status buffer, the read cache address buffer having a plurality of entries for storing real cache addresses, said cache system having a virtual cache with only a virtual cache address buffer and a virtual cache status buffer, said cache system buffering data associated with said bus master address, said method comprising the steps of:

storing said bus master address output in only said virtual cache address buffer if said bus master address output is not found in either of said real cache address buffer and said virtual cache address buffer;

filling said real cache data buffer with data responsive to said bus master address from said data storage device if said bus master address is found only in said virtual cache address buffer;

providing data responsive to sad bus master address directly from said bus master to said data storage device without placing said data in said real cache data buffer if said address is not found in said real cache address buffer or said virtual cache address buffer;

updating said real cache address buffer and said real cache status buffer if said bus master address is found only in said virtual cache address buffer;

detecting a hit in one of sad real cache address buffer entres if said bus master address output matches a real cache address; and

providing data from said real cache data buffer associated with said bit to said bus master.

2. The method of claim 1, wherein said real cache status buffer stores cache invalidation information, further comprising the step of updating said real cache status buffer with cache invalidation bits.

3. The method of claim 1, wherein each of said real cache status buffer and virtual cache status buffer stores usage history information, further comprising the step of updating each of said real cache status buffer and said virtual cache status buffer with usage history statistics.

4. The method of claim 1, wherein said real cache address buffer has a plurality of address entries and said real cache data buffer has a plurality of buffer entries, one buffer entry corresponding to each of said address entries, said filling step flier comprises the steps of:

identifying one of said address entries in said real cache address buffer as a replacement entry;

copying said bus master address output into said replacement entry; and

copying said data responsive to said address into said real cache data buffer entry associated with said replacement entry.

5. The method of claim 4, wherein said identifying step further comprises the step of selecting a least recently used entry from said real cache address buffer.

6. The method of claim 4, further comprising the step of moving the address stored in said replacement entry to said virtual cache address buffer before copying said address from said bus master into said replacement entry.

7. The method of claim 6, wherein said moving step further comprises the step of identifying a most recently used entry from said virtual cache address buffer to store said replacement entry.

8. The method of claim 4, wherein said real cache status buffer has a plurality of entries corresponding to said real cache address buffer entries, said method further comprising the step of marking said real cache status buffer entry corresponding to said hit as a most recently used entry.

9. The method of claim 1, further comprising the step of providing data responsive to said address from said real cache data buffer to said bus master if said address is found in said real cache address buffer.

10. The method of claim 1, further comprising the step of adding one or more read ahead addresses to said read requests from said bus master if said bus master address output is not found in either of said real cache address buffer and said virtual cache address buffer.

11. The method of claim 1, wherein said virtual cache address buffer has a plurality of entries, said storing step further comprises the steps of:

identifying one of said entries as a replacement entry; and

copying said bus master address into said replacement entry.

12. The method of claim 11, wherein said identifying step further comprises the step of searching said virtual cache status buffer for a replacement entry.

13. The method of claim 11, wherein said identifying step selects said replacement entry using a least recently used replacement algorithm.

14. The method of claim 13, wherein said replacement entry is marked as the most recently used entry to update said virtual cast status buffer.

15. The method of claim 13, wherein said least recently used replacement algorithm uses a queue.

16. The method of claim 1, further comprising the step of adding one or more read ahead addresses to said read requests from said bus master if said bus master address output is not found in either of said real cache address buffer and said virual cache address buffer.

17. The method of claim 16, wherein said adding step adds a small number of said read ahead addresses to said read requests.

18. A disk caching system for buffering read requests comprising:

a bus master having a bus master address output for requesting data and a bus master data input for receiving data corresponding to said bus master address;

a data storage device having a data storage device address input for receiving a data storage device address and a data storage device data output for providing data corresponding to said data storage device address; and

a cache having a bus master address input coupled to said bus master address output, a bus master data output coupled to said bus master data input, a data storage device address output coupled to said data storage device address input, and a data storage device data input coupled to said data storage device data output, said cache system having a real cache with a real cache data buffer, a real cache address buffer and a real cache status buffer, the real cache address buffer having a plurality of entries for storing real cache addresses, said cache system having a virtul cache with only a virtual cache address buffer and a virtual cache status buffer, said cache system buffering data associated with said bus master address, said cache system including;

means for storing said bus master address in only said virtual cache address buffer if said bus master address is not found in either of said real cache address buffer and said virtual cache address buffer;

means for filling said real cache data buffer with data responsive to said bus master address from said data storage device if said bus master address is found only in said virtual cache address buffer;

a means for providing data responsive to said address from said real cache data buffer to said data storage device if said address is found in said real cache address buffer; and

a means for updating said real cache address buffer and said real cache status buffer if said bus master address is found only in said virtual cache address buffer;

a means for providing data responsive to said address directly from said bus master to said data storage device without placing said data in said real cache buffer if said address is not found in said real cache buffer or said virtual cache address buffer;

a means for detecting a hit in one of said real cache buffer entries if said bus master address matches a real cache address; and

a means for providing data from said real cache data buffer associated with said hit to said bus mater.

19. The disk caching system of claim 18, wherein said real cache status buffer stores cache invalidation information, further comprising a means for updating said real cache status buffer with cache invalidation bits.

20. The disk caching system of claim 18, wherein each of said real cache status buffer and virtual cache status buffer stores usage history information, further comprising a means for updating each of said real cache status buffer and said virtual cache status buffer with usage history statistics.

21. The disk caching system of claim 18, wherein said real cache address buffer has a plurality of address entries and said real cache data buffer has a plurality of buffer entries, one buffer entry corresponding to each of said address entries, said means for filling further comprising:

means for identifying one of said address entries in said real cache address buffer as a replacement entry;

means for copying said bus master address into said replacement entry; and

means for copying said data responsive to said address into said real cache data buffer entry associated with said replacement entry.

22. The disk caching system of claim 21, wherein said identifying means further comprises a means for selecting a least recently used entry from said real cache address buffer.

23. The disk caching system of claim 21, further comprising a means for moving the address stored in said replacement entry to said virtual cache address buffer before copying said address from said bus master into said replacement entry.

24. The disk caching system of claim 23, wherein said moving means further comprises a means for identifying a most recently used entry from said virtual cache address buffer to store said replacement entry.

25. The disk caching system of claim 21, wherein said real cache status buffer has a plurality of entries corresponding to said real cache address buffer entries, said disk caching system further comprising a means for marking said real cache status buffer entry corresponding to said hit as a most recently used entry.

26. The disk caching system of claim 18, further comprising a means for providing data responsive to said address from said real cache data buffer to said bus master if said address is found in said real cache address buffer.

27. The disk caching system of claim 18, further comprising a means for adding one or more read ahead addresses to said read requests from said bus master if said bus master address output is not found in either of said real cache address buffer and said virtual cache address buffer.

28. The disk caching system of claim 18, wherein said virtual cache address buffer has a plurality of entries, said storing means further comprises:

means for identifying one of said entries as a replacement entry; and

means for copying said bus master address into said replacement entry.

29. The disk caching system of claim 28, wherein said identifying means further comprises a means for searching said virtual cache status buffer for a replacement entry.

30. The disk caching system of claim 28, wherein said identifying means selects said replacement entry using a least recently used replacement algorithm.

31. The disk caching system of claim 30, wherein said replacement entry is marked as the most recently used entry to update said virtual cache status buffer.

32. The disk caching system of claim 30, wherein said least recently used replacement algorithm uses a queue.

33. The disk caching system of claim 18, further comprising a means for adding one or more read ahead addresses to said read requests from said bus master if said bus master address output is not found in either of said real cache address buffer and said virtual cache address buffer.

34. The disk caching system of claim 33, wherein said adding means adds a small number of said read ahead addresses to said read requests.

35. A computer system for buffering read requests comprising:

a bus master having a bus master address output for requesting data and a bus master data input for receiving data corresponding to said bus master address;

a data storage device having a data storage device address input for receiving a data storage device address and a data storage device data output for providing data corresponding to said data storage device address; and

a cache system having a bus master address input coupled to said bus master address output, a bus master data output coupled to said bus master data input, a data storage device address output coupled to said data storage device address input, and a data storage device data input coupled to said data storage device data output, said cache system having a real cache with a real cache data buffer, a real cache address buffer and a real cache status buffer, said cache system having a virtual cache with only a virtual cache address buffer and a virtual cache status buffer, said cache system buffering data associated with said bus master address, said cache system including;

means for storing said bus master address in only said virtual cache address buffer if said bus master address is not found in either of said real cache address buffer and said virtual cache address buffer;

means for filling said real cache data buffer with data responsive to said bus master address from said data store device if said bus master address is found only in said virtual cache address buffer;

means for providing data responsive to said bus master address directly from said bus master to said data storage device without placing said data in said real cache data buffer if said address is not found in said real cache address buffer or said virtual cache address buffer; and

means for updating said real cache address buffer and said real cache status buffer if said address is found only in said virtual cache address buffer,

means for detecting a hit in one of said real cache address buffer entries if said bus master address output matches a real cache address; and

means for providing data from said real cache data buffer associated with said hit to said bus master.

36. The computer system of claim 35, wherein said real cache status buffer stores cache invalidation information, further comprising a means for updating said real cache status buffer with cache invalidation bits.

37. The computer system of claim 35, wherein each of said real cache status buffer and virtual cache status buffer stores usage history information, further comprising a means for updating each of said real cache status buffer and said virtual cache status buffer with usage history statistics.

38. The computer system of claim 35, wherein said real cache address buffer has a plurality of address entries and said real cache data buffer has a plurality of buffer entries, one buffer entry corresponding to each of said address entries, said means for filling further comprising:

means for identifying one of said address entries in said real cache address buffer as a replacement entry;

means for copying said consumer address into said replacement entry; and

means for copying said data responsive to said address into said real cache data buffer entry associated with said replacement entry.

39. The computer system of claim 38, wherein said identifying means further comprises a means for selecting a least recently used entry from said real cache address buffer.

40. The computer system of claim 38, further comprising a means for moving the address stored in said replacement entry to said virtual cache address buffer before copying said address from said bus master into said replacement entry.

41. The computer system of claim 40, wherein said moving means further comprises a means for identifying a most recently used entry from said virtual cache address buffer to store said replacement entry.

42. The computer system of claim 38, wherein said real cache status buffer has a plurality of entries corresponding to said real cache address buffer entries, said computer system further comprising a means for marking said real cache status buffer entry corresponding to said hit as a most recently used entry.

43. The computer system of claim 35, further comprising a means for providing data responsive to said address from said real cache data buffer to said bus master if said address is found in said real cache address buffer.

44. The computer system of claim 35, further comprising a means for adding one or more read ahead addresses to said read requests from said bus master if said bus master address output is not found in either of said real cache address buffer and said virtual cache address buffer.

45. The computer system of claim 35, wherein said virtual cache address buffer has a plurality of entries, said storing means further comprises:

means for identifying one of said entries as a replacement entry; and

means for copying said bus master address into said replacement entry.

46. The computer system of claim 45, wherein said identifying means further comprises a means for searching said virtual cache status buffer for a replacement entry.

47. The computer system of claim 45, wherein said identifying means selects said replacement entry using a least recently used replacement algorithm.

48. The computer system of claim 47, wherein said replacement entry is marked as the most recently used entry to update said virtual status buffer.

49. The computer system of claim 47, wherein said least recently used replacement algorithm uses a queue.

50. The computer system of claim 35, further comprising a means for adding one or more read ahead addresses to said read requests from said bus mater if said bus master address output is not found in either of said real cache address buffer and said virtual cache address buffer.

51. The computer system of claim 50, wherein said adding means adds a small number of said read ahead addresses to said read requests.

52. A method for buffering read requests from a bus master to a data storage device using a cache system, said bus master having a bus master address output for requesting data and a bus master data input for receiving data corresponding to said bus master address output, said data storage device having a data storage device address input for receiving a data storage device address and a data storage device data output for providing data corresponding to said data storage device address input, said cache system having a bus master address input coupled to said bus master address output, a bus master data output coupled to said bus master data input, a data storage device address output coupled to said data storage device address input, and a data storage device data input coupled to said data storage device data output, said cache system having a real cache with a real cache data buffer, a real cache address buffer and a real cache status buffer, said cache system having a virtual cache with only a virtual cache address buffer and a virtual cache status buffer, said cache system buffering data associated with said bus master address, said method comprising the steps of:

buffering said bus master data in said real cache data buffer and storing said bus master address output in only said virtual cache address buffer if said bus master address output is not found in either of said real cache address buffer and said virtual cache address buffer; and

filling said real cache data buffer with data responsive to said bus master address output from said data storage device if said bus master address output is found only in said virtual cache address buffer.

53. A method for buffering requests from a bus master to a data storage device using a cache system, said cache system including a virtual cache and a real cache, said method comprising the steps of:

predicting a read request is a sequential access if a request generates a hit to the real cache;

predicting a read request is a random access if a request generates a miss to the virtual cache and a miss to the real cache; and

predicting a read request is a sequential access if the request generates a miss to the real cache and a hit to the virtual cache.

54. The method of claim 53, further comprising the step of:

providing data directly from the real cache to the data storage device if a sequential access is predicted.

55. The method of claim 53, further comprising the step of:

providing data directly from the bus master to the data storage device if a random access is predicted.

56. The method of claim 55, the virtual cache including a virtual cache address buffer, further comprising the step of:

updating the virtual cache address buffer with the address of the request to enable sequential accesses to be checked for sequential operation.

57. The method of claim 55, the virtual cache including a virtual status buffer, further comprising the step of:

marking the virtual cache status buffer corresponding to the request of a most recently used line to update said virtual cache.

58. The method of claim 53, further comprising the step of:

enlarging the request to include a plurality of read-ahead requests if the request is small and if a sequential access is predicted.

59. The method of claim 53, the virtual cache including a virtual cache buffer, further comprising the step of:

detecting if the address corresponding to the address is found in the virtual cache address buffer to determine if there is a hit to the virtual cache.

60. The method of claim 53, the real cache including a real cache address buffer, and further comprising the step of:

detecting if the address corresponding to the request is found in the real cache address buffer to determine if there is a hit to the real cache.

61. The method of claim 53, wherein the data storage device is a disk drive.