Sequence thrashing avoidance via fall through estimation
One example method includes determining a fall through threshold value for a cache, computing a length ‘s’ of a sequence that is close to LRU eviction, and the length ‘s’ is computed when a current fall through metric value is greater than the fall through threshold value, when the sequence length ‘s’ is greater than a predetermined threshold length ‘k,’ performing a first shift of an LRU position to define a protected queue of the cache, initializing a counter with a value of ‘r’, decrementing the counter each time a requested page is determined to be included in the protected queue, until ‘r’=0, and performing a second shift of the LRU position.
1. A method, comprising:
determining a fall through threshold value for a cache;
computing a length ‘s’ of a sequence that is close to LRU eviction, and the length ‘s’ is computed when a current fall through metric value is greater than the fall through threshold value;
when the sequence length ‘s’ is greater than a predetermined threshold length ‘k,’ performing a first shift of an LRU position to define a protected queue of the cache;
initializing a counter with a value of ‘r’;
decrementing the counter each time a requested page is determined to be included in the protected queue, until ‘r’=0; and
performing a second shift of the LRU position.
2. The method as recited in claim 1 , wherein performing the first shift of the LRU position to define the protected queue of the cache comprises moving the LRU position to a point that is closer to a front of the cache than a start of the protected queue.
3. The method as recited in claim 1 , wherein performing the second shift of the LRU position comprises moving the LRU position to an end of the cache.
4. The method as recited in claim 1 , wherein performing the first shift of the LRU position to define the protected queue of the cache comprises moving the LRU position forward in the cache a number of cache slots, and the number of cache slots by which the LRU is shifted is determined by the length of the sequence ‘s’ and by a number of any skips in the cache.
5. The method as recited in claim 1 , wherein the LRU position is a point of eviction from the cache.
6. The method as recited in claim 1 , wherein the length ‘s’ of the sequence is determined with respect to one or more skips and/or gaps in the cache.
7. The method as recited in claim 1 , wherein the sequence length ‘s’ is determined based in part on a skip in the cache.
8. The method as recited in claim 1 , wherein after the second LRU shift, pages in the protected queue are no longer protected.
9. The method as recited in claim 1 , wherein when ‘r’=0 and a request is received for an unevicted page that was in the protected cache when ‘r’>0, the requested page is promoted to a position closer to a front of the cache than a position of that page just prior to the request.
10. The method as recited in claim 1 , further comprising setting a permissible gap length and/or skip length for use in computing the length ‘s’.
11. A non-transitory storage medium having stored therein instructions that are executable by one or more hardware processors to perform operations comprising:
determining a fall through threshold value for a cache;
computing a length ‘s’ of a sequence that is close to LRU eviction, and the length ‘s’ is computed when a current fall through metric value is greater than the fall through threshold value;
when the sequence length ‘s’ is greater than a predetermined threshold length ‘k,’ performing a first shift of an LRU position to define a protected queue of the cache;
initializing a counter with a value of ‘r’;
decrementing the counter each time a requested page is determined to be included in the protected queue, until ‘r’=0; and
performing a second shift of the LRU position.
12. The non-transitory storage medium as recited in claim 11 , wherein performing the first shift of the LRU position to define the protected queue of the cache comprises moving the LRU position to a point that is closer to a front of the cache than a start of the protected queue.
13. The non-transitory storage medium as recited in claim 11 , wherein performing the second shift of the LRU position comprises moving the LRU position to an end of the cache.
14. The non-transitory storage medium as recited in claim 11 , wherein performing the first shift of the LRU position to define the protected queue of the cache comprises moving the LRU position forward in the cache a number of cache slots, and the number of cache slots by which the LRU is shifted is determined by the length of the sequence ‘s’ and by a number of any skips in the cache.
15. The non-transitory storage medium as recited in claim 11 , wherein the LRU position is a point of eviction from the cache.
16. The non-transitory storage medium as recited in claim 11 , wherein the length ‘s’ of the sequence is determined with respect to one or more skips and/or gaps in the cache.
17. The non-transitory storage medium as recited in claim 11 , wherein the sequence length ‘s’ is determined based in part on a skip in the cache.
18. The non-transitory storage medium as recited in claim 11 , wherein after the second LRU shift, pages in the protected queue are no longer protected.
19. The non-transitory storage medium as recited in claim 11 , wherein when ‘r’=0 and a request is received for an unevicted page that was in the protected cache when ‘r’>0, the requested page is promoted to a position closer to a front of the cache than a position of that page just prior to the request.
20. The non-transitory storage medium as recited in claim 11 , wherein the operations further comprise setting a permissible gap length and/or skip length for use in computing the length ‘s’.