 |
Claims  |
|
|
What is claimed is:
1. A method for coalescing a working set of data from a cache prior to destaging the data from the cache to a storage device having a plurality of addressable locations,
comprising the steps of:
locating least recently accessed data awaiting destage from the cache,
selecting a root item of data to be included in the working set, the root item of data having a lower storage address on the storage device than the least recently accessed data,
identifying additional data in the cache that will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data,
including the additional data in the working set, and
completing the working set without including therein said least recently accessed data awaiting destage from the cache.
2. The method of claim 1 wherein an additional data item is identified and included in the working set only if the additional data item is within a predetermined range of storage locations that includes the root item.
3. The method of claim 1 wherein data written into the cache is entered at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue.
4. The method of claim 3 wherein identifying additional data in the cache comprises analyzing a data item adjacent to the root item in the LRU queue, to determine whether the adjacent data item will be destaged to locations in the storage device
with addresses substantially adjacent to the address of the root item of data, and if so, including the adjacent item in the working set.
5. The method of claim 4 wherein the next least recently accessed data item in the LRU queue is analyzed.
6. The method of claim 4 wherein identifying additional data in the cache further comprises analyzing a data item adjacent to any data item included in the working set, to determine whether the adjacent data item will be destaged to locations in
the storage device with addresses substantially adjacent to the address of the root item of data, and if so, including the adjacent item in the working set.
7. The method of claim 1 wherein identifying additional data in the cache comprises searching the data items in the cache to locate any data item not already include d in the working set, that will be destaged to locations in the storage device
with addresses substantially adjacent to the address of the root item of data.
8. The method of claim 7 wherein data written into the cache is entered at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue, and
wherein identifying additional data in the cache further comprises analyzing a data item adjacent to the root item in the LRU queue, to determine whether the adjacent data item will be destaged to locations in the storage device with addresses
substantially adjacent to the address of the root item of data, and if so, including the adjacent item in the working set.
9. The method of claim 8 wherein identifying additional data in the cache further comprises analyzing a data item adjacent to any data item included in the working set, to determine whether the adjacent data item will be destaged to locations in
the storage device with addresses substantially adjacent to the address of the root item of data, and if so, including the adjacent item in the working set.
10. The method of claim 1 wherein the root data item is identified by the steps of:
initially selecting the least recently accessed data item in the cache,
searching for a data item at a lower storage address than the currently selected data item that is within a predetermined range of addresses including the currently selected data item, and if such a data item is located, making the located data
item the currently selected data item,
repeating the searching step until a data item at a lower storage location address within a predetermined address range of the currently selected item cannot be found, and then
making the currently selected data item the root data item.
11. A method for coalescing a working set of data from a cache prior to destaging the data from the cache to a storage device having a plurality of addressable locations, comprising the steps of:
selecting on data item to be a root item of data to be included in the work in g set,
identifying additional data in the cache that will be destaged to locations in the storage device with addresses substantially adjacent to the root item of data,
including the additional data in the working set, and
completing the working set without including least recently accessed data awaiting destage from the cache.
12. The method of claim 11 further comprising identifying a larger than average group of data items that were stored together into the cache, wherein a first data item of the group is selected to be the root data item.
13. The method of claim 11 wherein an additional data item is identified and included in the working set only if the additional data item is within a predetermined range of storage locations that includes the root item.
14. The method of claim 11 wherein data written into the cache is entered at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue.
15. The method of claim 14 wherein identifying additional data in the cache comprises analyzing a data item adjacent to the root item in the LRU queue, to determine whether the adjacent data item will be destaged to locations in the storage
device with addresses substantially adjacent to the address of the root item of data, and if so, including the adjacent item in the working set.
16. The method of claim 15 wherein the next least recently accessed data item in the LRU queue is analyzed.
17. The method of claim 15 wherein identifying additional data in the cache further comprises analyzing a data item adjacent to any data item included in the working set, to determine whether the adjacent data item will be destaged to locations
in the storage device with addresses substantially adjacent to the address of the root item of data, and if so, including the adjacent item in the working set.
18. The method of claim 11 wherein identifying additional data in the cache comprises searching the data items in the cache to locate any data item not already included in the working set, that will be destaged to locations in the storage device
with addresses substantially adjacent to the address of the root item of data.
19. The method of claim 18 wherein data written into the cache is entered at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue, and
wherein identifying additional data in the cache further comprises analyzing a data item adjacent to the root item in the LRU queue, to determine whether the adjacent data item will be destaged to locations in the storage device with addresses
substantially adjacent to the address of the root item of data, and if so, including the adjacent item in the working set.
20. The method of claim 19 wherein identifying additional data in the cache further comprises analyzing a data item adjacent to any data item included in the working set, to determine whether the adjacent data item will be destaged to locations
in the storage device with addresses substantially adjacent to the address of the root item of data, and if so, including the adjacent item in the working set.
21. A cache control circuit for coalescing a working set of data from a cache prior to destaging the data from the cache to a storage device having a plurality of addressable locations, the control circuit configured to:
locate least recently accessed data awaiting destage from the cache,
select a root item of data to be included in the working set, the root item of data having a lower storage address on the storage device than the least recently accessed data,
identify additional data in the cache that will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data,
include the additional data in the working set, and
complete the working set without including said least recently accessed data awaiting destage from the cache.
22. The cache control circuit of claim 21 wherein the cache control circuit is configured to identify an additional data item and include the additional data item in the working set only if the additional data item is within a predetermined
range of storage locations that includes the root item.
23. The cache control circuit of claim 21 wherein the cache control circuit is configured to enter data written into the cache at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue.
24. The cache control circuit of claim 23 wherein the cache control circuit is configured to identify additional data in the cache by analyzing a data item adjacent to the root item in the LRU queue, to determine whether the adjacent data item
will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data, and if so, include the adjacent item in the working set.
25. The cache control circuit of claim 24 wherein the cache control circuit is further configured to analyze the next least recently accessed data item in the LRU queue.
26. The cache control circuit of claim 24 wherein the cache control circuit is configured to identify additional data in the cache by analyzing a data item adjacent to any data item included in the working set, to determine whether the adjacent
data item will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data, and if so, include the adjacent item in the working set.
27. The cache control circuit of claim 21 wherein the cache control circuit is configured to identify additional data in the cache by searching the data items in the cache to locate any data item not already included in the working set, that
will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data.
28. The cache control circuit of claim 27 wherein the cache control circuit is configured to enter data written into the cache at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue, and
the cache control circuit identifies additional data in the cache by analyzing a data item adjacent to the root item in the LRU queue, to determine whether the adjacent data item will be destaged to locations in the storage device with addresses
substantially adjacent to the address of the root item of data, and if so, includes the adjacent item in the working set.
29. The cache control circuit of claim 28 wherein the cache control circuit is configured to identify additional data in the cache by analyzing a data item adjacent to any data item included in the working set, to determine whether the adjacent
data item will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data, and if so, include the adjacent item in the working set.
30. The cache control circuit of claim 21 wherein the cache control circuit is configured to identify the root data item by the steps of:
initially selecting the least recently accessed data item in the cache,
searching for a data item at a lower storage address than the currently selected data item that is within a predetermined range of addresses including the currently selected data item, and if such a data item is located, making the located data
item the currently selected data item,
repeating the searching step until a data item at a lower storage location address within a predetermined address range of the currently selected item cannot be found, and then
making the currently selected data item the root data item.
31. A cache control circuit for coalescing a working set of data from a cache prior to destaging the data from the cache to a storage device having a plurality of addressable locations, the cache control circuit configured to:
select one data item to be a root item of data to be included in the working set,
identify additional data in the cache that will be destaged to locations in the storage device with addresses substantially adjacent to the root item of data,
include the additional data in the working set, and
complete the working set without including least recently accessed data awaiting destage from the cache.
32. The cache control circuit of claim 31 wherein said control circuit is further configured to identify a larger than average group of data items that were stored together into the cache, and wherein the cache control circuit is configured to
select a first data item of the group to be the root data item.
33. The cache control circuit of claim 31 wherein the cache control circuit is configured to identify and include an additional data item in the working set only if the additional data item is within a predetermined range of storage locations
that includes the root item.
34. The cache control circuit of claim 31 wherein the cache control circuit is configured to enter data written into the cache at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue.
35. The cache control circuit of claim 34 wherein the cache control circuit is configured to identify additional data in the cache by analyzing a data item adjacent to the root item in the LRU queue, to determine whether the adjacent data item
will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data, and if so, include the adjacent item in the working set.
36. The cache control circuit of claim 35 wherein the cache control circuit is configured to analyze the next least recently accessed data item in the LRU queue.
37. The cache control circuit of claim 35 wherein the cache control circuit is configured to identify additional data in the cache by analyzing a data item adjacent to any data item included in the working set, to determine whether the adjacent
data item will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data, and if so, include the adjacent item in the working set.
38. The cache control circuit of claim 31 wherein the cache control circuit is configured to identify additional data in the cache by searching the data items in the cache to locate any data item not already included in the working set, that
will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data.
39. The cache control circuit of claim 38 wherein the cache control circuit is configured to enter data written into the cache at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue, and
the cache control circuit is configured to identify additional data in the cache by analyzing a data item adjacent to the root item in the LRU queue, to determine whether the adjacent data item will be destaged to locations in the storage device
with addresses substantially adjacent to the address of the root item of data, and if so, include the adjacent item in the working set.
40. The cache control circuit of claim 39 wherein the cache control circuit is configured to identify additional data in the cache by analyzing a data item adjacent to any data item included in the working set, to determine whether the adjacent
data item will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data, and if so, include the adjacent item in the working set.
41. A program product, comprising:
(a) a program configured to perform a method of coalescing a working set of data from a cache prior to destaging the data from the cache to a storage device having a plurality of addressable locations, the method comprising:
locating least recently accessed data awaiting destage from the cache,
selecting a root item of data to be included in the working set, the root item of data having a lower storage address on the storage device than the least recently accessed data,
identifying additional data in the cache that will be destaged to locations in the storage device with addresses substantially adjacent to the address of the root item of data,
including the additional data in the working set, and
completing the working set without including said least recently accessed data awaiting destage from the cache; and
(b) a signal bearing media bearing the program.
42. The program product of claim 41, wherein the signal bearing media is a transmission type media.
43. The program product of claim 41, wherein the signal bearing media is a recordable media.
44. A program product, comprising:
(a) a program configured to perform a method of coalescing a working set of data from a cache prior to destaging the data from the cache to a storage device having a plurality of addressable locations, the method comprising:
selecting one data item to be a root item of data to be included in the working set,
identifying additional data in the cache that will be destaged to locations in the storage device with addresses substantially adjacent to the root item of data,
including the additional data in the working set, and
completing the working set without including least recently accessed data awaiting destage from the cache; and
(b) a signal bearing media bearing the program.
45. The program product of claim 44, wherein the signal bearing media is a transmission type media.
46. The program product of claim 44, wherein the signal bearing media is a recordable media. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
FIELD OF THE INVENTION
The invention relates to destage of data from a write cache to a storage device, and methods for managing destage to improve efficiency thereof.
BACKGROUND OF THE INVENTION
In a data processing system, instructions and associated data are transferred from storage devices to one or more processors for processing, and then resulting data generated by the processor is returned to storage devices. Thus, typical
processing operations involve frequent and repetitive reading and writing from/to storage devices. As a result, storage access delays are often a primary limitation in the performance of a data processing system. Preferably, therefore, storage access
speed should be maximized to maximize performance. However, often cost and other constraints require that the storage devices be comprised of relatively long access time circuitry, e.g., hard disk rives. To overcome the resulting performance rawbacks,
caches are typically used.
A cache typically includes a relatively small, but relatively high speed, bank of memory, that can be more rapidly accessed by the processor(s) than the storage device that the cache services. A write cache is used to temporarily store data
being written by the processor to a storage device. The processor writes data into the write cache, and thereafter the data is transferred or destaged from the write cache to the appropriate storage device. A read cache duplicates memory locations in
the storage device, so that when a particular storage location being accessed by the processor is duplicated in the read cache, the processor may rapidly access the read cache instead of waiting for access to the storage device.
Typically, a cache is associated with a cache directory, which stores an indication of those memory locations currently stored in the cache. Thus, when a processor requests access to a particular memory location, the cache directory is accessed
to determine whether that memory location is in the cache. If so, the requested memory location may be accessed in the cache, if appropriate. If the memory location is not in the cache, the accessed memory location may be established in the cache, if
appropriate.
Typically, sequential locations on a storage device can be read or written rapidly. For example, a disk drive may be arranged into tracks and sectors, so that sequential data in sequential tracks and sectors can be rapidly read or written.
However, it is also typical to incur long access delays when reading or writing data at disparate locations. For example, a disk drive typically incurs a substantial delay to transfer from one track and sector to another, non-adjacent track and sector.
In light of the rapid access that can be made to sequential locations on a storage device, caches are typically organized into "lines", which are relatively long sequences of sequential storage locations. Typically, when storage locations are
written into a write cache, the data written into the cache is arranged into cache lines, and then sequential locations from one or more sequential cache lines are destaged to the storage device at one time. Similarly, when memory locations are
duplicated into a read cache, typically the needed memory location as well as neighboring memory locations, are brought into a line of the cache.
Data is typically destaged from a write cache in the order in which it is written to the cache, i.e., first-in, first-out. This approach, however, can lead to various difficulties.
For example, while sequential storage locations are often written sequentially in time, this is not always the case. Consider, for example, a processing thread that writes to sequential storage locations in a first range of storage location on a
storage device, and then writes to sequential storage locations in a second range of storage locations which is adjacent to the first range. If the second range is located at higher storage addresses than the first range of storage locations, then the
first range should be destaged before the second range, and in this case a destage algorithm which destages memory locations in the order in which they were written to the cache, can operate efficiently. However, if the second range of storage locations
is at lower storage addresses than the first range, then the second range should be destaged before the first range, and in this case a destage algorithm which destages memory locations in the order in which they were written in the cache will operate
inefficiently, because the first range will be destaged first.
As a further example, when an exceptionally large amount of data is written to the cache in one operation, a sizeable percentage of the cache will be consumed. A large block of data of this kind should be destaged as soon as possible to free
space in the cache. Unfortunately, if a first-in, first-out strategy is used in destaging the data, this large percentage of the cache will remain consumed until all previously written data has been destaged. The resulting delay can cause the cache to
become full, preventing additional write operations and delaying processing.
SUMMARY OF THE INVENTION
The invention addresses these and other difficulties inherent in destage of data on a first-in, first-out basis, by coalescing as much data together as possible prior to each destage operation. This results in higher performance by destaging a
large quantity of data from the cache with each destage operation.
Specifically, in one aspect of the present invention, a working set of data items stored in a write cache is coalesced for destage to a storage device, by locating the least recently accessed data in the cache that will be destaged to the storage
device, and then selecting a root item of data at a lower storage address than the least recently accessed data. The working set is then completed by identifying additional data in the cache that will be destaged to locations in the storage device
substantially adjacent to the root item of data.
In another aspect, a working set of data items stored in a write cache is coalesced for destage to a storage device, by identifying a larger than average group of data items that were stored together into the cache, and selecting one of the data
items in the group, e.g., the first item in the group, as a root item of data to be included in the working set. The working set is then completed by identifying additional data in the cache that will be destaged to locations in the storage device
substantially adjacent to the root item of data.
In the particular disclosed embodiment described below, if the cache does not include a larger than average group of data items, the root data item is identified by initially selecting the least recently accessed destagable data item in the
cache. Then, a search is conducted for a destagable data item at a lower storage device address that is within a predetermined range of storage locations of the currently selected data item. If such a data item is found, then this data item becomes the
currently selected data item, and the search is repeated. When the search fails to find a data item at a lower storage device address within a predetermined range of the currently selected item, the process terminates and the currently selected data
item becomes the root data item. This approach ensures that adjacent, later-written data items at lower storage device addresses, such as the second address range described in the preceding example, will be included in the destage operation.
In the disclosed embodiment, data items are included in the working set only if those data items are within a predetermined range of storage locations that includes the root item. Data items outside of this range are not adjacent to the root
item of data and not included in the working set.
In the disclosed embodiment, data written into the cache is entered at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue. Once the root item of data or any other item of data is included in the
working set, then a data item substantially adjacent to the included item in the LRU queue (e.g., the next more recently accessed data item) is analyzed, to determine whether the adjacent data item will be destaged to locations in the storage device
which are adjacent to the storage locations of the root item of data. If this criterion is met by a data item, and the data item is in a destageable state then the data item is included in the working set, and further data items are sought by reviewing
adjacent data items in the LRU queue. This is a significant advantage, because adjacent data items can be readily identified through a review of the LRU queue.
In the disclosed embodiment, additional adjacent data items are also located by searching the data items in the cache to locate any data item not already included in the working set, that will be destaged to locations in the storage device which
are also substantially adjacent to the root item of data. If a data item is found, it is included in the working set, and further data items are sought by reviewing adjacent data items in the LRU queue. This approach further ensures that adjacent,
later-written data items at higher storage device addresses, such as the second address range described in the preceding example, will be included in the destage operation.
In still another aspect, the invention features a program product configured to coalesce a working set of data for destage to a storage device in accordance with the approach described above, and a signal bearing media bearing the program, which
may be a transmission type media or a recordable media.
These and other advantages and features, which characterize the invention, are set forth in the claims annexed hereto and forming a further part hereof. However, for a better understanding of the invention, and the advantages and objectives
attained by its use, reference should be made to the Drawing, and to the accompanying descriptive matter, in which there is described embodiments of the invention.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a block diagram of a computer system consistent with the invention.
FIG. 2 is a data structure diagram showing the contents of the cache directory illustrated in FIG. 1.
FIG. 3 is a data structure diagram showing the organization of the contents of the cache directory into lists and queues using pointers included in the data structures.
FIG. 4 is a flow chart of specific operations performed as part of selecting a working set and writing data to the cache.
FIG. 5 is a flow chart of specific operations performed as part of reading data from the cache.
FIG. 6 is a flow chart of specific operations performed as part of selecting a working set of data for destage from the cache, and destaging data from the cache.
FIG. 6A is a flow chart of specific operations performed as part of selecting a root CL for building a working set of data for destage from the cache.
DETAILED DESCRIPTION
Prior to discussing the operation of embodiments of the invention, a brief overview of a computer system in which the invention may be used is provided.
Turning to the Drawing, wherein like numbers denote like parts throughout the several views, FIG. 1 shows a block diagram of a computer system 20 consistent with the invention. Those skilled in the art will appreciate that the mechanisms and
apparatus consistent with the invention apply equally to any computer system, regardless of whether the computer system is a complicated multi-user computing apparatus or a single user device such as a personal computer or workstation. As shown in FIG.
1, computer system 20 includes a main or central processing unit (CPU) 22 connected through a system bus 21 to a main memory 30, a memory controller 24, an auxiliary storage interface 26, and a terminal interface 28.
Memory controller 24, through use of a processor separate from CPU 22, moves information between main memory 30, auxiliary storage interface 26, and CPU 22. While for the purposes of explanation, memory controller 24 is shown as a separate
entity, those skilled in the art understand that, in practice, portions of the function provided by memory controller 24 may actually reside in the circuitry associated with CPU 22 and main memory 30. Further, while memory controller 24 of the
embodiment is described as having responsibility for moving requested information between main memory 30, auxiliary storage interface 26 and CPU 22, those skilled in the art will appreciate that the mechanisms of the present invention apply equally to
any storage configuration, regardless of the number and type of the storage entities involved.
Auxiliary storage interface 26, which operates under the control of software or firmware in a controller 31, allows computer system 20 to store and retrieve information from an auxiliary storage device 28, such as a magnetic disk, magnetic tape
or optical storage device. Included within auxiliary storage interface 26 is a cache memory 32 of volatile or non-volatile memory for storing lines of storage locations read from or written to the auxiliary storage device 28. Also included is a cache
directory memory 34, which is a volatile or non-volatile memory storing an indication of which memory locations are within the cache memory 32, as discussed above. In addition, auxiliary storage interface 26 includes a backup cache directory memory 36,
which is a self-contained non-volatile memory module, such as a battery backed SRAM. Backup cache directory memory 36 stores information regarding the memory locations stored in the cache memory 32, so that in the event of a failure in the auxiliary
storage interface 26, leading to a loss of the contents of the cache memory 32 and/or cache directory memory 34, reconstruction or invalidation can be performed. Backup cache directory memory 36 is stored in one or more socketed circuits, so that when a
defective auxiliary storage interface 26 is replaced, memory 36 may be moved from the defective auxiliary storage interface 26 to the replacement auxiliary storage interface without loss of the information in the backup cache directory memory.
Terminal interface 28 allows system administrators and computer programmers to communicate with computer system 20, normally through one or more programmable workstations 38.
Although the system depicted in FIG. 1 contains only a single main CPU and a single system bus, it will be understood that the invention also applies to computer systems having multiple CPUs and buses.
It will be appreciated that computer system 20 is merely an example of one system upon which the routines in accord with principles of the present invention may execute. Further, as innumerable alternative system designs may be used, principles
of the present invention are not limited to any particular configuration shown herein.
In general, the routines executed to implement the illustrated embodiments of the invention, whether implemented as part of an operating system or a specific application, program, object, module or sequence of instructions will be referred to
herein as "computer programs". The computer programs typically comprise instructions which, when read and executed by one or more processors in the devices or systems in a computer system consistent with the invention, cause those devices or systems to
perform the steps necessary to execute steps or generate elements embodying the various aspects of the present invention. Moreover, while the invention has and hereinafter will be described in the context of fully functioning computer systems, those
skilled in the art will appreciate that the various embodiments of the invention are capable of being distributed as a program product in a variety of forms, and that the invention applies equally regardless of the particular type of signal bearing media
used to actually carry out the distribution. Examples of signal bearing media include but are not limited to recordable type media such as volatile and non-volatile memory devices, floppy disks, hard disk drives, CD-ROM's, DVD's, magnetic tape, etc.,
and transmission type media such as digital and analog communications links.
Referring now to FIG. 2, the contents of the cache directory memory 34 can be more clearly understood. Within cache directory memory 34 are a number of records 40, which for the purposes of the following disclosure will be known as cache line or
CL records. Each CL record consumes 64 bytes of storage in cache directory memory 34. Each CL record, when in use, identifies the location of from one to eight contiguous blocks of data for a storage device stored in the cache. Each block stores a
number of bytes of data awaiting destage from the cache to a storage device, e.g., 512, 520 or some other number of bytes. As illustrated in FIG. 2, the cache directory includes a number, x, of CL records. The size of the cache memory and the number of
CL records available for managing the cache memory can be arbitrarily chosen based on performance.
In addition to the CL records, the cache directory memory 34 includes a hash table 42, used as an index to locate a CL record for a particular storage location as discussed below. Memory 34 also includes a number of pointers. Specifically,
there are a plurality of LRU queue pointers 44, including one "head" and one "tail" pointer for each storage device connected to the auxiliary storage interface 26, which are used in managing queues of CL records. Furthermore, there are a plurality of
priority CL pointers 46, including one pointer for each storage device connected to the auxiliary storage interface 26, which are used in identifying the first CL record of a large group of such records which is to be destaged prior to other CL records.
Also, there are a plurality of working set queue pointers 48, one for each of several destage, read or write operations that may operate on the write cache, used in identifying a working set of CL records that are included in a working set for the
associated operation. Finally, there is a free CL list pointer 50, used in identifying free CL records. The use of these pointers will be discussed below with reference to FIG. 3.
The detailed internal structure of a CL record is also illustrated in FIG. 2. The CL record is divided into 16 four-byte fields, each of which stores data needed for management of the cache directory. A first four-byte field 52 stores a logical
block base address for the one to eight blocks of cache data being managed by the CL record. The logical block base address indicates the starting address on a storage device of the first block of the eight blocks that may be managed by the CL record.
A CL record manages up to eight blocks of data, specifically, a CL record manages any or all of the eight sequential blocks of storage locations on a storage device starting at the logical block base address identified in field 42 and continuing for the
following eight blocks of locations.
The second four-byte field 54 in a CL record stores additional address information for the blocks being managed by the CL record, as well as information regarding the state of those blocks in the cache. Specifically, the second four byte field
stores the logical device number for the storage device in which the data blocks managed by the CL record are to be stored. Multiple logical storage devices may be managed by the auxiliary storage interface 26 illustrated in FIG. 1 using the write
cache; the logical device number identified in field 54 indicates which of these storage devices that data will be stored in.
Field 54 further includes a byte of "valid block" bits, i.e., eight bits, one for each of the eight blocks managed by the CL record 40. Because a CL record may manage from one to eight blocks, it is necessary for the CL record to identify which
of the eight sequential blocks following the logical block base address identified in field 52, are being managed by the CL record. The eight "valid block" bits correspond to the eight sequential blocks which follow the logical block base address. If a
"valid block" bit is set, this indicates that the corresponding block in the storage device is being managed by the CL record. If a "valid block" bit is not set, this indicates that the corresponding block in the storage device is not being managed by
the CL record.
Field 54 further includes state information regarding the use of the CL record. Specifically, a CL record may have one of five states:
Avail--which indicates that the CL record is not presently being used to manage data in the write cache.
WIP--which indicates that the CL record is managing data for which a write to the cache from the processor is in progress.
Idle--which indicates that the CL record is managing data in the cache, but that data is not being written, read or destaged at the present time.
RIP--which indicates that the CL record is managing data which is presently being read from the cache by the processor.
DIP--which indicates that the CL record is managing data which is presently being destaged from the cache.
As will be noted below in detail, a CL progresses through these states in a controlled manner, moving from one state to another as respective write, read, and destage operations are performed upon the CL record. As is described below, as an
operation is performed on a working set of CL records, the state of each CL record that is involved in the operation, is updated to the appropriate state. Furthermore, when an operation builds a working set for an operation, the state of each CL record
in the working set is evaluated, and if the state of the CL record is inconsistent with the operation to be performed, the operation is not performed on the CL record, thus preventing collisions between operations, i.e., attempts to use the same CL
record and associated data for inconsistent purposes at the same time.
For example, read operations are only permitted if all of the CL records in the working set for the read operation are in the Idle state. If this is not the case, for example, if particular data is being written to the cache, and thus the
associated CL record is in the WIP state, as part of identifying a working set, the read operation will detect that a CL record needed for the read operation is in the WIP state. As a result, the read operation will be suspended. A similar sequence of
events will occur if any of the CL records needed for a read operation is in the process of being destaged from the cache and thus is in the DIP state. Only if all CL records included in the working set are in the Idle state, will the read operation
proceed; and only in this case, will the state of all CL records be reset to the RIP state to indicate that a read is in progress for the CL record.
In the event of a collision, a flag in the CL record is set to indicate the occurrence of a collision. This flag, which is known as a collision bit, is included in field 54 of each CL record 40. When a collision is detected and an operation is
suspended, the collision bit in the CL record which caused the collision is set. As discussed below, when an operation which uses a CL record terminates, that operation reviews the CL record to determine whether the collision bit is set, and if so, the
previously suspended operation which experienced the collision is restarted.
The first two fields 52 and 54 of a CL record thus include complete information on the locations in the storage device of blocks being managed by the cache, and the state of those blocks in the operation of the cache. These two fields,
therefore, include all information needed to identify, at any moment in time, which blocks on the storage device are storing invalid data, i.e., data which the processor has requested that the auxiliary storage interface overwrite, and for which there is
new data stored in the cache waiting to be destaged to the storage device.
Fields 52 and 54 are known as a CL-subset, and are duplicated in the backup cache directory memory 36. Specifically, backup cache directory memory 36 includes the number x, of eight byte CL-subset records 56, one CL-subset record in memory 36
corresponding to each CL record 40 in cache directory memory 34.
As described below, when write, purge or destage operations are performed, the contents and state of CL records will change. When the state of a CL record transitions due to (a.) the initial writing of data into the cache, (b.) purging of data
from the cache due to writing of newer data for the same storage locations, or (c.) destage of data from the cache, fields 52 and 54 (the CL-subset) of the CL record are stored into the associated CL-subset record 56 in backup cache directory memory 36.
This ensures that a completely current CL-subset record is always stored in the backup cache directory memory 36. Specifically, the CL-subset record associated with a CL record is updated when the CL record transitions from the WIP state to the Idle
state--in | | |
