Enhanced least recently used round robin cache management method and apparatus for allocation and destaging of cache segments

Claim 2

In a cache system having a plurality of allocable segments for storing cached data, wherein the cache system searches the plurality of allocable segments for data referenced by cache commands and provides access to the referenced data if the referenced data is present in the cache, a method for managing allocation of the plurality of allocable segments comprising the steps of: (a) establishing a replacement candidate segment, wherein said replacement candidate segment is the first one of the plurality of allocable segments to be considered for allocation if the referenced data is not present in the plurality of allocable segments; (b) establishing a recently used zone ahead of said replacement candidate segment, wherein said recently used zone encompasses a predetermined number of the plurality of allocable segments, said predetermined number being less than the plurality of allocable segments; (c) designating a segment as recently used if reference is made to data and the data resides in a segment within said recently used zone; (d) allocating said replacement candidate segment if the referenced data is not present in the plurality of allocable segments and said replacement candidate segment has not been designated recently used; (e) designating said replacement candidate segment as not recently used if the referenced data is not present in the plurality of allocable segments and said replacement candidate segment is presently designated as recently used; (f) selecting a succeeding segment for use as said replacement candidate segment; (g) advancing said recently used zone; and (h) repeating steps (d) through (g) until said replacement candidate segment is allocated.

Claim 3

The method of claim 1, wherein said recently used zone begins at said replacement candidate segment.

Claim 4

The method of claim 2, wherein said predetermined number of is less than or equal to three-fourths the number of allocable segments in the cache.

Claim 5

The method of claim 1, wherein said selecting step (f) selects the next addressable segment for use as said replacement candidate segment.

Claim 6

In a post-store cache system having a plurality of allocable segments for storing cached data, wherein the cached data is accessible by a plurality of hosts and each of the hosts is coupled and has access to one or more disks from which data is cached, and selected ones of the disks are exclusively accessible by selected ones of the hosts wherein the cache system searches the plurality of allocable segments for data referenced by cache commands issued by the plurality of hosts and provides access to the referenced data if the referenced data is present in the cache, a method for managing allocation of the plurality of allocable segments, comprising the steps of: establishing a replacement segment, wherein said replacement segment is one of the plurality of allocable segments to be allocated if the referenced data is not present in the plurality of allocable segments; establishing a destage zone ahead of said replacement segment, wherein said destage zone encompasses a predetermined number of the plurality of allocable segments, said predetermined numbering being less than the plurality of allocable segments; destaging one or more written segments from said destage zone if data referenced by a cache command is not present in the plurality of allocable segments and said one or more written segments have not been recently referenced; allocating the replacement segment if the data referenced in the cache command is not present in the plurality of allocable segments; selecting a succeeding segment for use as said replacement segment when said replacement segment is allocated; and advancing said destage zone when said succeeding segment is selected.

Claim 7

In a post-store cache system having a plurality of allocable segments for storing cached data, wherein the cached data is accessible by a plurality of hosts and each of the hosts is coupled and has access to one or more disks from which data is cached, and selected ones of the disks are exclusively accessible by selected ones of the hosts wherein the cache system searches the plurality of allocable segments for data referenced by cache commands issued by the plurality of hosts and provides access to the referenced data if the referenced data is present in the cache, a method for managing allocation of the plurality of allocable segments, comprising the steps of: establishing a replacement segment, wherein said replacement segment is one of the plurality of allocable segments to be allocated if the referenced data is not present in the plurality of allocable segments; establishing a destage zone ahead of said replacement segment, wherein said destage zone encompasses a predetermined number of the plurality of allocable segments, said predetermined numbering being less than the plurality of allocable segments; destaging one or more written segments from said destage zone if data referenced by a cache command is not present in the plurality of allocable segments and said one or more written segments have not been recently referenced; allocating the replacement segment if the data referenced in the cache command is not present in the plurality of allocable segments; selecting a succeeding segment for use as said replacement segment when said replacement segment is allocated; and advancing said destage zone when said succeeding segment is selected.

Claim 8

The method of claim 5, wherein said destage zone leads said replacement segment by approximately one-half the number of the plurality of allocable segments.

Claim 9

The method of claim 5, wherein said destaging step further includes the steps of: selecting for destaging one or more segments in said destage zone which are to be destaged to a disk to which the host which issued the cache command has access; and reporting to the host which issued the cache command said one or more segments from said selecting for destaging step.

Claim 10

The method of claim 7, further comprising the step of searching the plurality of allocable segments for segments that have disk addresses that are contiguous to disk addresses of said one or more segments from said selecting for destaging step, wherein said reporting step further includes reporting the segments found in said searching step.

Claim 11

In a post-store cache system having a plurality of allocable segments for storing cached data, wherein the cached data is accessible by a plurality of hosts and each of the hosts is coupled and has access to one or more disks from which data is cached, and selected ones of the disks are exclusively accessible by selected ones of the hosts wherein the cache system searches the plurality of allocable segments for data referenced by cache commands issued by the plurality of hosts and provides access to the referenced data if the referenced data is present in the cache, a method for managing allocation of the plurality of allocable segments, comprising the steps of: (a) establishing a replacement candidate segment, wherein said replacement candidate segment is the first one of the plurality of allocable segments to be examined for allocation if a referenced segment is not present in the plurality of allocable segments; (b) establishing a recently used zone ahead of said replacement candidate segment, wherein said recently used zone encompasses a predetermined number of the plurality of allocable segments, said predetermined number being less than the plurality of allocable segments; (c) establishing a destage zone ahead of said replacement candidate segment, wherein said destage zone encompasses one or more of the plurality of allocable segments; (d) destaging one or more written segments from said destage zone if data referenced by a cache command is not present in the plurality of allocable segments and said one or more written segments have not been recently referenced; (e) designating a segment as recently used if reference is made to the segment and the segment is within said recently used zone; (f) allocating said replacement candidate segment if the referenced data is not present in the plurality of allocable segments and said replacement candidate segment has not been designated recently used; (g) designating said replacement candidate segment as not recently used if the referenced data is not present in the plurality of allocable segments and said replacement candidate segment is presently designated as recently used; (h) selecting a succeeding segment for use as said replacement candidate segment; (i) advancing said recently used zone; (j) advancing said destage zone; and (k) repeating steps (f) through (j) until said replacement candidate is allocated.

Claim 12

In a post-store cache system having a plurality of allocable segments for storing cached data, wherein the cached data is accessible by a plurality of hosts and each of the hosts is coupled and has access to one or more disks from which data is cached, and selected ones of the disks are exclusively accessible by selected ones of the hosts wherein the cache system searches the plurality of allocable segments for data referenced by cache commands issued by the plurality of hosts and provides access to the referenced data if the referenced data is present in the cache, a method for managing allocation of the plurality of allocable segments, comprising the steps of: (a) establishing a replacement candidate segment, wherein said replacement candidate segment is the first one of the plurality of allocable segments to be examined for allocation if a referenced segment is not present in the plurality of allocable segments; (b) establishing a recently used zone ahead of said replacement candidate segment, wherein said recently used zone encompasses a predetermined number of the plurality of allocable segments, said predetermined number being less than the plurality of allocable segments; (c) establishing a destage zone ahead of said replacement candidate segment, wherein said destage zone encompasses one or more of the plurality of allocable segments; (d) destaging one or more written segments from said destage zone if data referenced by a cache command is not present in the plurality of allocable segments and said one or more written segments have not been recently referenced; (e) designating a segment as recently used if reference is made to the segment and the segment is within said recently used zone; (f) allocating said replacement candidate segment if the referenced data is not present in the plurality of allocable segments and said replacement candidate segment has not been designated recently used; (g) designating said replacement candidate segment as not recently used if the referenced data is not present in the plurality of allocable segments and said replacement candidate segment is presently designated as recently used; (h) selecting a succeeding segment for use as said replacement candidate segment; (i) advancing said recently used zone; (j) advancing said destage zone; and (k) repeating steps (f) through (j) until said replacement candidate is allocated.

Claim 13

The method of claim 9, wherein said destaging step includes the steps of: selecting for destaging one or more segments in said destage zone which are to be destaged to a disk to which the host which issued the cache command has access; searching the plurality of allocable segments for segments that have disk addresses that are contiguous to disk addresses of said one or more segments from said selecting for destaging step; and reporting to the host which issued the cache command said one or more segments from said selecting for destaging step and the segments from said searching step.

Claim 14

In a post-store cache system having a plurality of allocable segments for storing cached data, wherein the cached data is accessible by a plurality of hosts and each of the hosts is coupled and has access to one or more disks from which data is cached, and selected ones of the disks are exclusively accessible by selected ones of the hosts wherein the cache system searches the plurality of allocable segments for data referenced by cache commands issued by the plurality of hosts and provides access to the referenced data if the referenced data is present in the cache, a apparatus for managing allocation of the plurality of allocable segments, comprising: a plurality of recently used indicators, wherein each of the plurality of allocable segments is associated with one of said plurality of recently used indicators and each of said plurality of recently used indicators signifies whether a segment has been recently referenced; a replacement pointer which references a replacement segment, wherein said replacement segment is a first one of the plurality of allocable segments and is the first segment to be considered for allocation; a recently used zone pointer which references a second one of the plurality of allocable segments, wherein segments ahead of said replacement pointer and behind said recently used zone pointer form a recently used zone; cache detection means, responsive to the cache commands and interfaced with the plurality of allocable segments, for detecting whether the data referenced by a cache command is present in the plurality of allocable segments, for generating a hit signal if the data referenced by a cache command is present in the plurality of allocable segments, and for generating a miss signal if the data referenced by a cache command is not present in the plurality of allocable segments; designation means responsive to said hit-signal and interfaced with said plurality of recently used indicators, said replacement pointer, and said recently used zone pointer for setting one of said plurality of recently used indicators to signify that a segment was recently referenced if the segment referenced by a cache command is within the range of addresses formed by said replacement pointer and said replacement zone pointer; and allocation means responsive to said miss signal and interfaced with said replacement pointer, said plurality of recently used indicators, and said recently used zone pointer for allocating said replacement segment if said one of said plurality of recently used indicators which is associated with said replacement segment indicates that said replacement segment has not been recently referenced, and for advancing said replacement pointer and said recently used zone pointer if said one of said plurality of recently used indicators which is associated with said replacement segment indicates that said replacement segment has been recently referenced.

Claim 15

In a post-store cache system having a plurality of allocable segments for storing cached data, wherein the cached data is accessible by a plurality of hosts and each of the hosts is coupled and has access to one or more disks from which data is cached, and selected ones of the disks are exclusively accessible by selected ones of the hosts wherein the cache system searches the plurality of allocable segments for data referenced by cache commands issued by the plurality of hosts and provides access to the referenced data if the referenced data is present in the cache, a apparatus for managing allocation of the plurality of allocable segments, comprising: a plurality of recently used indicators, wherein each of the plurality of allocable segments is associated with one of said plurality of recently used indicators and each of said plurality of recently used indicators signifies whether a segment has been recently referenced; a replacement pointer which references a replacement segment, wherein said replacement segment is a first one of the plurality of allocable segments and is the first segment to be considered for allocation; a recently used zone pointer which references a second one of the plurality of allocable segments, wherein segments ahead of said replacement pointer and behind said recently used zone pointer form a recently used zone; cache detection means, responsive to the cache commands and interfaced with the plurality of allocable segments, for detecting whether the data referenced by a cache command is present in the plurality of allocable segments, for generating a hit signal if the data referenced by a cache command is present in the plurality of allocable segments, and for generating a miss signal if the data referenced by a cache command is not present in the plurality of allocable segments; designation means responsive to said hit-signal and interfaced with said plurality of recently used indicators, said replacement pointer, and said recently used zone pointer for setting one of said plurality of recently used indicators to signify that a segment was recently referenced if the segment referenced by a cache command is within the range of addresses formed by said replacement pointer and said replacement zone pointer; and allocation means responsive to said miss signal and interfaced with said replacement pointer, said plurality of recently used indicators, and said recently used zone pointer for allocating said replacement segment if said one of said plurality of recently used indicators which is associated with said replacement segment indicates that said replacement segment has not been recently referenced, and for advancing said replacement pointer and said recently used zone pointer if said one of said plurality of recently used indicators which is associated with said replacement segment indicates that said replacement segment has been recently referenced.

Claim 16

The apparatus of claim 11, further comprising: a lower-bound pointer which references a lower-bound-segment, wherein said lower-bound-segment is a third one of the plurality of allocable segments; an upper-bound pointer which references an upper-bound-segment, wherein said upper-bound-segment is a fourth one of the plurality of allocable segments, whereby segments within the range of segment addresses of said lower-bound pointer and said upper-bound pointer for a destage zone; destage means responsive to said miss signal and interfaced with said lower-bound pointer and said upper-bound pointer for destaging selected segments from said destage zone when said miss signal is active.

Claim 17

The apparatus of claim 12, wherein said selected segments are segments to be destaged to a disk to which the host which issued the cache command has access.