I/O Storage controller cache system with prefetch determined by requested record's position within data block

• US 4,490,782 A
• Filed: 06/05/1981
• Issued: 12/25/1984
• Est. Priority Date: 06/05/1981
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dixon, Jerry D., Marazas, Gerald A., Merckel, Gerald U.
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): Williams, Jr., A. E.
• Application Number:
  US06/270,951
• Time in Patent Office: 1,299 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/136
• 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 13/122 where hardware performs an I/O function other than control of data transfer
• CPC Class Codes: G06F 2212/502 using adaptive policy

Abstract

In a data processing system of the type wherein a host processor transfers data to or from a plurality of attachment devices, a cache memory is provided for storing blocks of data which are most likely to be needed by the host processor in the near future. The host processor can then merely retrieve the necessary information from the cache memory without the necessity of accessing the attachment devices. When transferring data to cache from an attachment disk, additional unrequested information can be transferred at the same time if it is likely that this additional data will soon be requested. Further, a directory table is maintained wherein all data in cache is listed at a "home" position and, if more than one block of data in cache have the same home position, a conflict chain is set-up so that checking the contents of the cache can be done simply and quickly.

Claims

1. In a method of operating a data processing system, said method being of the type wherein a host processor requests a record R_m of data stored in at least one memory unit, said memory unit storing a plurality of data blocks each including a sequence of n data records occupying respective positions within said data blocks and consecutively designated R₁ -R_n including said requested data record R_m, where n and m are positive integers and m≦

n, and an I/O controller transfers said requested record from a cache memory to said host processor if said requested record is currently stored in said cache memory and to said cache memory from said memory unit if said requested record is not currently stored in said cache memory, the improvement characterized in that said transferring step comprises;

determining a first block of data in said memory unit containing said requested data record at a position m therein;

determining said position m of said requested data record in said first block of data; and

transferring only said first block of data to said cache memory if m<

T₁, where T₁ is a positive integer, 2≦

T₁ ≦

n; and

transferring both said first and said at least second data blocks to said cache memory if m≦

T₁.

2. The method according to claim 1, wherein said step of transferring data comprises, when said host processor requests a plurality of data records located in said memory unit in different data blocks, transferring said second data block to said cache memory only in accordance with the position of the last requested data record in its respective data block and only if the data block containing said last requested data record is not presently in said cache memory.

3. The method according to claim 2, wherein said transferring step comprises:

transferring only said first data block to said cache memory if said second data block is already stored in said cache memory.

4. A method of operating a data processing system, said system being of the type including a host processor, at least one memory unit for storing a plurality of data units each having a unique file system address and a corresponding hash entry number, a cache memory for storing a portion of the data stored in said memory unit and a controller for transferring data between said host processor and cache memory and between said memory unit and cache memory, said method being of the type wherein said host processor requests a unit of data stored in said memory unit and said controller transfers said requested data from said cache memory to said host processor if said requested data is currently stored in said cache memory, said method further comprising:

maintaining a directory table listing the data units currently stored in said cache memory, said directory table having a plurality of directory table positions each identified by a unique hash entry number and each having at least a file system address portion for indicating the file system address of the data unit listed at said directory table position and forward and backward pointers identifying other positions in said directory table;

examining said directory table to determine if said requested data unit is currently stored in said cache memory;

transferring said data unit from said memory unit to said cache memory if it is not currently stored in said cache memory;

listing said transferred data unit at its home position, i.e, the directory table position identified by the hash entry number corresponding to said transferred data unit, if said home position is not already occupied by a further data unit having the same hash entry number as said transferred data unit, whereby the listing of said transferred data unit comprises a home entry;

listing said transferred data unit at an unused directory table position having a different hash entry number if said home position of said transferred data unit is already occupied by a further data unit having the same hash entry number; and

linking all directory table positions listing data units having the same hash entry number in a conflict chain via said forward and backward pointers.

5. The method of claim 4, wherein said examining step comprises examining the home position of said transferred data unit, and wherein said transferring step comprises transferring said requested data unit to said cache memory if the home position of said transferred data unit is not already occupied by a home entry or if said home position of said transferred data unit is occupied by a home entry but said transferred data unit is not included within said conflict chain.

6. The method according to claim 5, wherein, if said home position of said transferred data unit is currently occupied by data having a different hash entry number, said transferring step comprises:

transferring all information currently at said home position of said transferred data to an unused position of said directory table; and

transferring said requested data unit from said memory unit to said cache memory and listing said transferred data unit at its home position in said directory table.

20. The method according to any one of claims 4-6, further comprising the steps of linking said unused directory, table positions in a free chain via said forward and backward pointers and designating one of said unused directory table positions as a first free entry, and wherein said step of listing said transferred data unit at an unused directory table position having a different hash entry number comprises listing said transferred data unit at said first free entry.

7. A data processing system comprising:

a host processor for requesting a record of data;

at least one memory unit for storing a plurality of blocks of data each including n data records occupying respective positions within said data blocks, where n is a positive integer, each block of data having a unique file system address and a corresponding hash entry number;

a cache memory for storing a portion of the data stored in said memory unit, said cache memory storing a plurality of data blocks at least a first plurality of which have the same corresponding hash entry number and different file system addresses and a second plurality of data blocks all having hash entry numbers different from one another;

a controller for transferring data between said host processor and cache memory and between said memory unit and cache memory, said controller transferring at least a first block of data containing the requested record to said cache memory from said memory unit if said requested record is not already stored in said cache memory; and

directory table means for listing the blocks of data currently stored in said cache memory, said directory table means having a plurality of directory table positions each identified by a unique hash entry number and each having at least a file system address portion for indicating the file system address of the data block listed at said position;

each of said second plurality of data blocks being listed at their home positions in said directory table means, i.e., at the positions identified by their hash entry numbers, the listing of each of said second plurality of data blocks at its home position comprising a home entry;

one of said first plurality of data blocks being listed at a home position identifed by said same corresponding hash entry number and comprising a home entry and the remainder of said first plurality of data blocks being listed at directory table positions which are not home positions for any data block currently stored in said cache memory and thereby comprising conflict entries;

whereby said requested data block is not currently stored in said cache memory if there is no home entry at the home position of said requested data block in said directory table.

8. A data processing system as defined in claim 7, wherein each directory table position includes forward pointer and backward pointer portions pointing to other positions of said directory table, and each of the directory table positions corresponding to said first plurality of data blocks are linked together in a conflict chain via their forward and backward pointers, with said conflict chain beginning at the home position of said one of said first plurality of data blocks, whereby said requested data block is not currently stored in said cache memory if there is currently a home entry at the home position of said requested data block but if said requested data block is not included in a conflict chain beginning at said home position.

9. A data processing system as defined in claim 8, wherein each directory table position includes at least a further portion for indicating if said position is currently occupied by a home entry or if said position is currently occupied by a conflict entry.

10. A data processing system as defined in claim 9, wherein said system further comprises priority table means for listing said directory table entries in a priority order.

12. A data processing system as defined in claim 7, wherein each block of data stored in said memory unit comprises a sequence of n data records consecutively designated R₁ -R_n including said requested data record R_m, where n and m are positive integers and m≦

n, said controller transferring to said cache memory only a first block of data including said requested data record if m<

T₁, where T₁ is a positive integer, 1≦

T₁ <

n and transferring both said first block of data and a second block of data to said cache memory if m≧

T₁.

13. A data processing system as defined in claim 12, said controller comprising means for transferring, when said host processor requests a plurality of data records located in said memory unit in different first data blocks, the first data blocks including those requested records which are not already stored in said cache memory and transferring said second data block to said cache memory only in accordance with the position of the last requested data record in its data block and only if the data block containing said last requested record is not presently stored in said cache memory.

14. A data processing system as defined in claim 12, wherein said controller comprises means for transferring only said first data block to said cache memory if said second data block is already in said cache memory.

18. A data processing system as defined in claim 7, wherein said host processor also requests that data be written into said at least one memory unit and wherein said controller means erases from said cache memory any of said data to be written which is currently stored in said cache memory.

19. A data processing system as defined in claim 8, wherein all unused directory table positions are linked together in a free chain via said forward and backward pointers with one of said unused directory table positions being designated as a first free entry.

11. A data processing system comprising:

a host processor for requesting a record of data;

at least one memory unit for storing a plurality of blocks of data each including a sequence of n data records occupying respective positions in said data blocks and consecutively designated R₁ -R_n including said requested data record R_m, where n and m are positive integers and m≦

n, each block of data having a unique file system address and a corresponding hash entry number;

a cache memory for storing a portion of the data stored in said memory unit, said cache memory storing a plurality of data blocks at least a first plurality of which have the same corresponding hash entry number and different file system addresses and a second plurality of data blocks all having hash entry numbers different from one another;

a controller for transferring data between said host processor and cache memory and between said memory unit and cache memory, said controller transferring a first block of data containing the requested data and a second block of data to said cache memory from said memory unit if said requested data is not already stored in said cache memory, said controller transferring to said cache memory only a first block of data including said requested data record if m<

T₁, where T₁ is a positive integer, 1≦

T₁ <

n and transferring both said first block of data and a second block of data of said cache memory if m≧

T₁.

15. A data processing system as defined in claim 7 or 11, further comprising priority table means for listing the blocks of data stored in said cache memory in a priority order.

16. A data processing system as defined in claim 15, wherein said priority means comprises a Least Recently Used (LRU) table for listing the blocks of data stored in said cache memory in order of their most recent use, with the most recently requested data block in said cache memory being assigned the highest priority and the least recently used data block in said cache memory being assigned a lowest priority.

17. A data processing system as defined in claim 7 or 11, further comprising:

means for determining the number of consecutive memory unit data blocks requested at one time by said host processor and for preventing the transfer of data from said at least one memory unit to said cache memory if said number of consecutive data blocks exceeds a predetermined value.

21. A data processing system as defined in claim 11, said controller comprising means for transferring, when said host processor requests a plurality of data records located in said memory unit in different first data blocks, the first data blocks including those requested records which are not already stored in said cache memory and transferring said second data block to said cache memory only in accordance with the position of the last requested data record in its data block and only if the data block containing said last requested record is not presently stored in said cache memory.

22. A data processing system as defined in claim 21, wherein said controller comprises means for transferring only said first data block to said cache memory if said second data block is already in said cache memory.