# US 2016/0253265 A1 · Using access-frequency hierarchy for selection of eviction destination

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0253265 A1
- Document ID: US20160253265A1
- Status: Published application
- Kind: A1
- Application number: 15/017,687
- Filed: 2016-02-08
- Published: 2016-09-01
- Earliest claimed: 2015-02-26
- Assignees: Strato Scale Ltd.
- Applicants: Strato Scale Ltd.
- Inventors: Mike Rapoport; Abel Gordon; Ariel Maislos
- Web page: https://patentgrep.com/patent/US20160253265A1

## CPC

- G06F 12/0891: using clearing, invalidating or resetting means
- G06F 3/0604: {Improving or facilitating administration, e.g. storage management}
- G06F 3/0605: {by facilitating the interaction with a user or administrator}
- G06F 3/061: {Improving I/O performance}
- G06F 3/0631: {by allocating resources to storage systems}
- G06F 3/0649: {Lifecycle management}
- G06F 3/0673: {Single storage device}
- G06F 3/0685: {Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays}
- G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
- G06F 12/128: adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
- G06F 12/08: in hierarchically structured memory systems, e.g. virtual memory systems
- G06F 2212/604: Details relating to cache allocation
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method includes, in a computing system in which one or more workloads access memory pages in a memory, defining multiple memory-page lists, and specifying for each memory-page list a respective different scanning period. Access frequencies, with which the memory pages are accessed, are estimated continually by periodically checking the memory pages on each memory-page list in accordance with the scanning period specified for that memory-page list, and re-assigning the memory pages to the memory-page lists based on the estimated access frequencies. One or more of the memory pages are evicted from the memory based on a history of assignments of the memory pages to the memory-page lists.

## Claims

### Claim 1

A method, comprising:
in a computing system in which one or more workloads access memory pages in a memory, defining multiple memory-page lists, and specifying for each memory-page list a respective different scanning period;
continually estimating access frequencies with which the memory pages are accessed, by periodically checking the memory pages on each memory-page list in accordance with the scanning period specified for that memory-page list, and re-assigning the memory pages to the memory-page lists based on the estimated access frequencies; and
evicting one or more of the memory pages from the memory based on a history of assignments of the memory pages to the memory-page lists.

### Claim 2 (depends on 1)

The method according to claim 1, wherein checking and re-assigning the memory pages comprise, in response to identifying that a memory page, which is currently assigned to a first memory-page list having a first scanning period, has been accessed since it was previously checked, re-assigning the memory page to a second memory-page list having a second scanning period larger than the first scanning period.

### Claim 3 (depends on 1)

The method according to claim 1, wherein checking and re-assigning the memory pages comprise, in response to identifying that a memory page, which is currently assigned to a first memory-page list having a first scanning period, has not been accessed since it was previously checked, re-assigning the memory page to a second memory-page list having a second scanning period smaller than the first scanning period.

### Claim 4 (depends on 3)

The method according to claim 3, wherein the second scanning period is a smallest scanning period among the specified scanning periods.

### Claim 5 (depends on 1)

The method according to claim 1, wherein evicting the memory pages comprises evicting a memory page in response to identifying that the memory page is assigned to a memory-page list having a smallest scanning period among the specified scanning periods, and was not accessed for more than a predefined time period.

### Claim 6 (depends on 1)

The method according to claim 1, wherein evicting the memory pages comprises selecting a storage tier for evicting a memory page, from among multiple storage tiers, based on the history of the assignments of the memory page.

### Claim 7 (depends on 6)

The method according to claim 6, wherein selecting the storage tier comprises calculating a weighted average of numbers of times that the memory page was assigned to the respective memory-page lists, and selecting the storage tier based on the weighted average.

### Claim 8 (depends on 6)

The method according to claim 6, wherein selecting the storage tier comprises applying a mapping that chooses the storage tier as a function of the history of the assignments, and comprising evaluating a quality of previous selections of the storage tiers, and adapting the mapping based on the evaluated quality.

### Claim 9

A computing system, comprising:
a memory for storing memory pages; and
a processor, which is configured to run one or more workloads that access the memory pages in the memory, to define multiple memory-page lists and specify for each memory-page list a respective different scanning period, to continually estimate access frequencies with which the memory pages are accessed, by periodically checking the memory pages on each memory-page list in accordance with the scanning period specified for that memory-page list, to re-assign the memory pages to the memory-page lists based on the estimated access frequencies, and to evict one or more of the memory pages from the memory based on a history of assignments of the memory pages to the memory-page lists.

### Claim 10 (depends on 9)

The computing system according to claim 9, wherein, in response to identifying that a memory page, which is currently assigned to a first memory-page list having a first scanning period, has been accessed since it was previously checked, the processor is configured to re-assign the memory page to a second memory-page list having a second scanning period larger than the first scanning period.

### Claim 11 (depends on 9)

The computing system according to claim 9, wherein, in response to identifying that a memory page, which is currently assigned to a first memory-page list having a first scanning period, has not been accessed since it was previously checked, the processor is configured to re-assign the memory page to a second memory-page list having a second scanning period smaller than the first scanning period.

### Claim 12 (depends on 11)

The computing system according to claim 11, wherein the second scanning period is a smallest scanning period among the specified scanning periods.

### Claim 13 (depends on 9)

The computing system according to claim 9, wherein the processor is configured to evict a memory page in response to identifying that the memory page is assigned to a memory-page list having a smallest scanning period among the specified scanning periods, and was not accessed for more than a predefined time period.

### Claim 14 (depends on 9)

The computing system according to claim 9, wherein the processor is configured to select a storage tier for evicting a memory page, from among multiple storage tiers, based on the history of the assignments of the memory page.

### Claim 15 (depends on 14)

The computing system according to claim 14, wherein the processor is configured to calculate a weighted average of numbers of times that the memory page was assigned to the respective memory-page lists, and to select the storage tier based on the weighted average.

### Claim 16 (depends on 14)

The computing system according to claim 14, wherein the processor is configured to select the storage tier by applying a mapping that chooses the storage tier as a function of the history of the assignments, to evaluate a quality of previous selections of the storage tiers, and to adapt the mapping based on the evaluated quality.

### Claim 17

A computer software product, the product comprising a tangible non-transitory computer-readable medium in which program instructions are stored, which instructions, when read by a processor that runs one or more workloads that access memory pages in a memory, cause the processor to define multiple memory-page lists, to specify for each memory-page list a respective different scanning period, to continually estimate access frequencies with which the memory pages are accessed, by periodically checking the memory pages on each memory-page list in accordance with the scanning period specified for that memory-page list, to re-assign the memory pages to the memory-page lists based on the estimated access frequencies, and to evict one or more of the memory pages from the memory based on a history of assignments of the memory pages to the memory-page lists.
