Method and apparatus for adaptive circular predictive buffer management

• US 5,623,608 A
• Filed: 11/14/1994
• Issued: 04/22/1997
• Est. Priority Date: 11/14/1994
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ng, Spencer W.-F.
• Primary Examiner(s): Eng, David Y.
• Application Number:
  US08/338,919
• Time in Patent Office: 890 Days
• Field of Search: 395/775, 395/375, 395/800, 395/250
• US Class Current: 711/137
• 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 12/127 using additional replacement algorithms
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

A system for adaptively managing predictive buffer memory prefetching operations to optimize buffer memory hits in a data storage system. The arriving data access request (DAR) stream is monitored for a particular data access pattern and, when a sequential access pattern (SAP) is detected, the buffer memory prefetching storage rule is switched to a circular overwrite mode (COM) to achieve the best sequential access performance. When the sequential access pattern disappears, a nonsequential access pattern (NAP) is detected and the buffer memory prefetching storage rule is responsively switched to a non-sequential or block overwrite mode (BOM) to maximize data block "re-use" hits in the data buffer. Sequential access pattern detection is achieved using a threshold that may be adapted to the size of incoming DARs. The buffer memory may be organized in many smaller segments, each operated independently according to the system of this invention, to provide simultaneous optimal predictive buffering for multiple processing threads.

Claims

1. A method for adaptively operating a buffer memory by adjusting management of said buffer memory to optimize buffer memory hits in a data storage system having a primary storage means for storing a sequence of data blocks coupled to said buffer memory through a controller means for reading and storing in said buffer memory each of one or more said data blocks requested by a data access request (DAR) from a processor input/output (I/O) means wherein said DAR is the latest of an uninterruptedly consecutive DAR sequence having an acccss pattern, said controller means having means for prefetching a consecutive plurality of said data blocks stored in said primary storage means subsequently to said one or more requested data blocks and having means for storing said consecutive data block plurality in said buffer memory in either a block overwrite mode (BOM) or a circular overwrite mode (COM), said method comprising the steps of:

(a) detecting either a sequential said access pattern (SAP) or a nonsequential said access pattern (NAP) in said DAR sequence;

(b) switching said buffer memory storing means to said circular overwrite mode (COM) responsive to a detection of said SAP; and

(c) switching said buffer memory storing means to said block overwrite mode (BOM) responsive to a detection of said NAP.

2. The method of claim 1 wherein said buffer memory includes a plurality of memory segments each independently operated such that an active said buffer memory segment is switched to said COM responsive to said SAP detection and is switched to said BOM responsive to said NAP detection.

3. The method of claim 2 wherein said detecting step (a) comprises the steps of:

(a.1) selecting a predetermined threshold for consecutive DARs;

(a.2) counting the number of said consecutive DARs received in said uninterruptedly consecutive DAR sequence; and

(a.3) producing said SAP detection when said consecutive DAR number exceeds said predetermined threshold, otherwise producing said NAP detection.

4. The method of claim 3 wherein said selecting step (a.1) comprises the step of:

(a.1.1) changing said predetermined threshold responsive to the number of data blocks requested by said DAR.

5. A buffer memory controller coupled to a buffer memory in a data storage system having a primary storage means for storing a sequence of data blocks coupled to said buffer memory through said buffer memory controller and having means for accepting a plurality of data access requests (DARs) from a processor I/O controller, wherein said each DAR is the latest of an uninterruptedly consecutive DAR sequence having an access pattern, said buffer memory controller comprising:

fetching means coupled to said primary storage means and said buffer memory for reading and storing in said buffer memory each of one or more said data blocks requested by said each DAR;

prefetching means in said fetching means for reading and storing in said buffer memory a consecutive plurality of said data blocks stored in said primary storage means subsequently to said one or more data blocks requested by said each DAR, wherein said prefetching means stores said consecutive data block plurality in said buffer memory in either a block overwrite mode (BOM) or a circular overwrite mode (COM);

detecting means coupled to said fetching means for detecting either a sequential access pattern (SAP) or a non-sequential access pattern (NAP) in each said uninterruptedly consecutive DAR sequence; and

switching means coupled to said prefetching means for switching said prefetching means storage mode to said COM responsive to said SAP detection and for switching said prefetching storing means to said BOM responsive to said NAP detection.

6. The buffer memory controller of claim 5 wherein said buffer memory comprises:

a plurality of memory segments each independently operated in said COM responsive to said SAP detection and in said BOM responsive to said NAP detection.

7. The buffer memory controller of claim 7 wherein said detecting means comprises:

selecting means for selecting a predetermined threshold for consecutive DARs;

counting means for counting the number of consecutive said DARs received in said each uninterruptedly consecutive DAR sequence; and

comparing means coupled to said selecting means and said counting means for producing said SAP detection when said consecutive DAR number exceeds said predetermined threshold and for producing said NAP detection otherwise.

8. The buffer memory controller of claim 7 wherein said selecting means comprises:

means for changing said predetermined threshold responsive to the number of said data blocks requested by said each DAR.

9. The buffer memory controller of claim 8 wherein said prefetching means comprises:

minimum prefetching means for completing the prefetch of a minimum number of said data blocks before interruption.

10. A direct access storage device (DASD) having a rotating magnetic medium for storing a sequence of data blocks coupled to a buffer memory through a buffer memory controller comprising:

input means for accepting a plurality of DARs from a processor I/O controller, wherein each said DAR is the latest of an uninterruptedly consecutive DAR sequence having an access pattern;

fetching means coupled to said rotating magnetic medium and said buffer memory for reading and storing in said buffer memory each of one or more said data blocks requested by said each DAR;

prefetching means in said fetching means for reading and storing in said buffer memory a consecutive plurality of data blocks stored in said rotating magnetic medium subsequently to said one or more data blocks requested by said each DAR, wherein said prefetching means stores said consecutive data block plurality in said buffer memory in either a BOM or a COM;

detecting means coupled to said fetching means for detecting either a SAP or a NAP in said each uninterruptedly consecutive DAR sequence; and

switching means coupled to said prefetching means for switching said prefetching storing means to said COM responsive to said SAP detection and for switching said prefetching storing means to said BOM responsive to said NAP detection.

11. The DASD of claim 10 wherein said buffer memory comprises:

a plurality of memory segments each independently operated in said COM responsive to said SAP detection and in said BOM responsive to said NAP detection.

12. The DASD of claim 11 wherein said detecting means comprises:

selecting means for selecting a predetermined threshold for consecutive DARs;

counting means for counting the number of consecutive said DARs received in said each uninterruptedly consecutive DAR sequence; and

comparing means coupled to said selecting means and said counting means for producing said SAP detection when said consecutive DAR number exceeds said predetermined threshold and for producing said NAP detection otherwise.

13. The DASD of claim 12 wherein said selecting means comprises:

means for changing said predetermined threshold responsive to the number of said data blocks requested by said each DAR.

14. The DASD of claim 13 wherein said prefetching means comprises:

minimum prefetching means for completing the prefetch of a minimum number of said data blocks before interruption.

15. An optical data storage system having an optical storage medium for storing a sequence of data blocks coupled to a buffer memory through a buffer memory controller comprising:

input means for accepting a plurality of DARs from a processor I/O controller, wherein each said DAR is the latest of an uninterruptedly consecutive DAR sequence having an access pattern;

fetching means coupled to said optical storage medium and said buffer memory for reading and storing in said buffer memory each of said one or more said data blocks requested by said each DAR;

prefetching means in said fetching means for reading and storing in said buffer memory a consecutive plurality of data blocks stored in said optical storage medium subsequently to said one or more data blocks requested by said each DAR, wherein said prefetching means stores said consecutive data block plurality in said buffer memory in either a BOM or a COM;

detecting means coupled to said fetching means for detecting either a SAP or a NAP in said each uninterruptedly consecutive DAR sequence; and

switching means coupled to said prefetching means for switching said prefetching storing means to said COM responsive to said SAP detection and for switching said prefetching storing means to said BOM responsive to said NAP detection.

16. The optical data storage system of claim 15 wherein said buffer memory comprises:

a plurality of memory segments each independently operated in said COM responsive to said SAP detection and in said BOM responsive to said NAP detection.

17. The optical data storage system of claim 16 wherein said detecting means comprises:

selecting means for selecting a predetermined threshold for consecutive DARs;

counting means for counting the number of consecutive said DARs received in said each uninterruptedly consecutive DAR sequence; and

comparing means coupled to said selecting means and said counting means for producing said SAP detection when said consecutive DAR number exceeds said predetermined threshold and for producing said NAP detection otherwise.

18. The optical data storage system of claim 17 wherein said selecting means comprises:

means for changing said predetermined threshold responsive to the number of said data blocks requested by said each DAR.

19. The optical data storage system of claim 18 wherein said prefetching means comprises:

minimum prefetching means for completing the prefetch of a minimum number of said data blocks before interruption.