Method and apparatus for grouping asynchronous recording operations

• US 4,636,946 A
• Filed: 02/24/1982
• Issued: 01/13/1987
• Est. Priority Date: 02/24/1982
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hartung, Michael H., Tayler, Gerald E.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Eakman, Christina M.
• Application Number:
  US06/351,835
• Time in Patent Office: 1,784 Days
• Field of Search: 364/200, 364/900
• US Class Current: 711/136
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/312 In storage controller

Abstract

The disclosure relates to demotion of data to a backing store (disk storage apparatus--DASD) from a random access cache in a peripheral data storage system. A cache replacement control list, such as a least recently used (LRU) list is scanned in a soon-to-be replaced first portion (portion closest to LRU entry) to identify first data to be demoted. Then the control list is scanned in first and second portions to identify further data to be demoted with the first data as a single group of data. In DASD, such data is all storable in the same cylinder of the DASD.

Claims

1. In a peripheral data storage system having host connection means for connecting the data storage system to a host processor and having a cache and a backing store, means for transferring data signals between said cache store and said backing store, said cache and backing store each having a plurality of addressable data storage areas for storing data, directory means connected to the cache store for enabling the addressing of the cache store areas using backing store addresses;

the improvement comprising;

first means for maintaining a control list having an entry for each allocated one of said addressable data storage areas in said cache storing data allocated from said backing store, each said entry including a first indicator indicating that data stored in said area associated with said entry has been modified from the corresponding data stored in said backing store, and a second indicator, indicating a relationship of data stored in said area associated with said entry to other data stored in said cache;

first scan means coupled to said first means for scanning a first portion of said control list to identify a first one of said addressable data storage areas in said cache store storing modified data;

second scan means coupled to said first means and to said first scan means for scanning said control list from said first one of said addressable data storage areas in said first portion of said control list through a second portion of said control list to identify further ones of said addressable data storage areas in said cache having a predetermined relationship to data stored in said first one of said addressable data storage areas; and

means coupled to said means for transferring data signals between said cache and said backing store and to said first and second scan means to link addressable data storage areas in cache identified as having said predetermined relationship as data to be transferred as a group of data blocks from said cache to said backing store.

2. The system according to claim 1 wherein said backing store includes a plurality of data-storage areas each constituting a cylinder of addressable data-storage registers, and further including means limiting said second scan means to identifying only said allocated cache-store addressable data-storage areas that are associable within the cylinder containing said first-identified one addressable data storage area.

3. The system according to claim 2, further including:

said second scan means further having means for receiving peripheral commands from said host connection means for addressing said backing store addressable data-storage registers;

said peripheral commands indicating an addressed register; and

logical device means coupled to said transferring means for storing said peripheral commands and for identifying a cylinder of said backing store containing said addressed registers.

4. The system according to claim 1, further including:

second list means for identifying addressable data-storage areas in said cache store that are storing data discarded from the cache store and to be coupled to said means for linking, third scan means for scanning said second list means prior to said first and second scan means scanning said first list means such that said cache-store addressable data-storage areas identified in said second list means are available for allocation prior to the cache-store addressable data-storage areas of said cache store that are identified in said first means; and

said means for linking including means for freeing said cache-store addressable data-storage areas for allocation without transferring any data from said cache store to said backing store.

5. The peripheral data storage system set forth in claim 1 or 4, further including:

cache control means coupled to said cache store and to said host connection means for receiving requests for data access from a connected host processor via said host connection means, the cache control means including a directory means, said control list means and a directory inquiring means connected to said directory means for determining if a given received request for data access relates to an allocated addressable data-storage area in said cache store for evaluating a cache hit for enabling access to said cache store for completing a data access requested by said received data-access request and when received request for data access does not relate to allocated addressable data-storage area in the cache store for indicating a cache miss;

means coupled to said host connection means and to said cache control means for reporting said indicated cache miss to said host connection means as a request to retry said received request for data access and having logical-device means indicating said indicated cache miss and logical association with said received request for data access and including means for initiating scanning said first list means for identifying a one of said addressable data-storage areas in said cache store as being available for allocation; and

means in said cache control means responsive to said indicated cache miss in said logical-device means into a free indicated one of said addressable data-storage areas in said cache store to allocate said free addressable data-storage area to said received data request and signalling said host connection means that said given received data access request can be retried.

6. The machine-implemented method of managing data storage space allocations for a cache having a plurality of data storage spaces attached to a host and to a backing store having a plurality of addressable data storage elements, a directory of said data storage spaces for indicating said space allocations with respect to addresses of said data storage elements and whether or not such allocated data storage spaces respectably are storing data which is modified from data stored in related ones of said data storage elements, control list means for indicating and listing accesses to said data storage elements in an order of priority for replacement of data stored in said cache data storage spaces in accordance to predetermined usage characteristics of said stored data;

comprising the steps of;

establishing a first threshold in said control list means representing a first predetermined number of data storage space allocations listed in said control list means for replacement from a data storage space indicated in said control list means as the data storage space containing data most likely to be replaced;

establishing a second threshold in said control list means representing a second predetermined number of indicated data storage space allocations listed in said control list means, said second predetermined number being larger than said first predetermined number;

scanning said control list means beginning at said given most likely to be replaced indicated data storage space and proceeding towards that established first threshold;

identifying during said scan a data storage space storing modified data;

said modified data having predetermined data storage characteristics;

listing data storage spaces identified as storing modified data with a first encountered one of said indicated data storage spaces during said scan of data storage space, storing modified data defined as a first identified one of said data storage spaces;

continuing said scan from said first identified one of said spaces storing nodified data to said second threshold for further identifying additional ones of said data storage spaces storing nodified data having said predetermined data storage characteristics;

adding said additional ones of said indicated data storage spaces to said list; and

transferring data stored in said data storage spaces in said list from said cache to said backing store as a serial stream of data.

7. The machine implemented method set forth in claim 6, further including the steps of:

maintaining a second list in said control list means of data storage spaces storing data which meets predetermined criteria for removal from said cache; and

adjusting said control list means by deleting identification of said data-storage spaces storing data to be discarded from said control list means before scanning said control list means.

8. The machine-implemented method set forth in claim 6 or 7, further including maintaining a free list of free data-storage spaces which are immediately available for allocation to receive data;

and

examining said free list and initiating freeing ones of said data-storage spaces when the number of entries in said free list are less than a given number.

9. The machine-implemented method set forth in claim 6 or 7, further including the machine-executable steps of:

receiving from said host a request for a data access;

examining said directory to determine if a data-storage space allocation is made in said cache that relates to said received request for data access, if said directory indicates a space is allocated then performing the data access, otherwise initiating a request for allocation of a data-storage space allocation; and

establishing a free list of said spaces indicating which of said spaces are immediately available for allocation in response to said request for allocation, then first examining said free list and allocating any data-storage space identified on said free list for said received request for data access, otherwise initiating freeing a one of said data-storage spaces.

10. A peripheral data-storage system having a plurality of addressable direct-access data-storage devices (DASD), each of said DASDs having a plurality of addressable cylinders wherein each cylinder has a plurality of addressable data-storing memory segments, high-speed buffer store having a plurality of buffer segments, each said buffer segment having a data-storing capacity equal to the data-storing capacity of said memory segments, connection means for attaching the system to a host;

the improvement including in combination;

receiving means for receiving peripheral commands from host connection means for fetching data from said DASDs;

a digital processor connected to said connection means and to said receiving means and having a control store for storing programs of instructions for operating the data-storage system;

signal means connected to said connection means, digital processor, said DASDs and said buffer for transferring signals between said DASDs, said buffer and said host connection means;

first program means in said control store for enabling said processor to operate the storage system to transfer one segment of data from said DASDs to said high-speed buffer store in response to a one of said received peripheral commands;

second program means in said control store for enabling said processor via said first program means to maintain a control list of said buffer segments in an order reflecting host connection means accesses to data stored in the respective buffer segments and to maintain a list of said buffer segments free for allocation for data storage; and

third program means in said control store for enabling said processor to first scan said control list for data stored in one of said buffer segments to be transferred from said buffer store to one of said DASDs and secondly to scan said control list for additional data stored in said buffer store having a predetermined DASD address relationship to said one buffer segment DASD address for grouping said one buffer segment DASD address and additional data for transfer to one of said DASDs under control of said first program means and including means to activate said first program means upon completion of said second scan wherein said third program means is coupled to said second program means to transfer identification signals for said one and additional buffer store segments from said control list to said free list.

11. The peripheral storage system set forth in claim 10 wherein each of said DASDs has a plurality of cylinders of record tracks, all record tracks in each cylinder having a given radial address, respectively, each of said memory segments being in respective ones of said record tracks, further including:

fourth program means in said control store for enabling the processor to operate the storage system to limit said one buffer segment DASD address and additional data stored in said buffer store to that data storable in a given cylinder of one of said DASDs.

12. A hierarchical data-storage system having connection means for connecting the data-storage system to a host processor, the system including a high-speed data cache and a relatively slow-speed backing store, data-transfer paths coupled to said cache and backing store for transferring data between addressable storage locations in said data cache and said backing store, cache replacement control means coupled to said data-transfer paths and said cache for being responsive to the contents of the storage locations in said cache to select particular items of data for replacement in accordance with predetermined replacement criteria, and data-transfer control means coupled to said data-transfer paths and said backing store for identifying locations in said backing store to receive data items so selected;

characterized in that;

said data-transfer control means grouping said selected data items with that data accessable through one of said data-transfer paths and to activating such data-transfer paths on a group-by-group basis, each group consisting of data items whose transfer involves the one said data-transfer path.

13. A system according to claim 12 wherein said backing store includes a plurality of cylinders each cylinder including one or more storage registers, wherein read or write access to registers in different ones of said cylinders is subject to access delays, each of said cylinders being in a different one of said data-transfer paths.

14. A system as claimed in claim 12 in which said backing store comprises a plurality of addressable direct-access magnetic disk data-storage devices, each device having a plurality of addressable data-storing cylinders and each cylinder having a plurality of said addressable memory segments, said cache comprises a high-speed buffer store having a plurality of said buffer segments constituting said cache storage locations, each buffer segment having a data-storing capacity equal to the data-storing capacity of said memory segments, further characterized by a command register for receiving peripheral commands from said host connection means to fetch data from said data-storage devices;

a digital processor having a control store for storing programs of instructions for operating the storage system;

first program means in said control store for enabling said digital processor to operate the storage system to transfer one segment of data from said backing store to said cache for each of said requests for a segment of data received from said host connection means;

second program means activated via said first program means and stored in said control store for enabling said digital processor to maintain a control list of identifications of said buffer segments in an order reflecting host connection means accesses to data stored in the respective buffer segments and to maintain a list of identifications of said buffer segments free for allocation for receiving data for storage;

third program means in said control store for enabling said processor to first scan said control list for data stored in a one of said buffer store segments to be transferred from said buffer store to a one of said storage devices and secondly to scan said control list for additional data stored in said buffer store having an identification located in a predetermined position in said control list with respect to said one buffer store segment identification in the control list for grouping said one and additional data for transfer to one of said storage devices under control of said first program means and including means for enabling the processor to activate said first program means upon completion of said second scan and coupled to said second program means to transfer said identifications for said one and additional buffer store segments from said control list to said free list.

15. A system as claimed in claim 14 wherein each of said data-storage devices has a plurality records tracks, all record tracks in each cylinder having a same radial address, further characterized by fourth program means in said control store for enabling the processor to operate the storage system to limit data stored in said buffer store to that data storable in a given cylinder of one of said storage devices.