# US 2014/0156940 A1 · Mechanism for Page Replacement in Cache Memory > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0156940 A1 - Document ID: US20140156940A1 - Status: Published application - Kind: A1 - Application number: 13/690,191 - Filed: 2012-11-30 - Published: 2014-06-05 - Earliest claimed: 2012-11-30 - Assignees: Red Hat, Inc. - Applicants: Red Hat, Inc. - Inventors: Johannes Weiner - Web page: https://patentgrep.com/patent/US20140156940A1 ## CPC - G06F 12/122: of the least frequently used [LFU] type, e.g. with individual count value - G06F 11/3452: {Performance evaluation by statistical analysis} - G06F 12/0802: Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches - G06F 12/121: using replacement algorithms - G06F 12/123: with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list - G06F 2201/885: Monitoring specific for caches - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A mechanism for page replacement for cache memory is disclosed. A method of the disclosure includes referencing an entry of a data structure of a cache in memory to identify a stored value of an eviction counter, the stored value of the eviction counter placed in the entry when a page of a file previously stored in the cache was evicted from the cache, determining a refault distance of the page of the file based on a difference between the stored value of the eviction counter and a current value of the eviction counter, and adjusting a ratio of cache lists maintained by the processing device to track pages in the cache, the adjusting based on the determined refault distance. ## Claims ### Claim 1 A computer-implemented method, comprising: referencing, by a processing device, an entry of a data structure of a cache in memory to identify a stored value of an eviction counter, the stored value of the eviction counter placed in the entry when a page of a file previously stored in the cache was evicted from the cache; determining, by the processing device, a refault distance of the page of the file based on a difference between the stored value of the eviction counter and a current value of the eviction counter; and adjusting, by the processing device, a ratio of cache lists maintained by the processing device to track pages in the cache, the adjusting based on the determined refault distance. ### Claim 2 (depends on 1) The method of claim 1, wherein the refault distance indicates a number of pages that were evicted from the cache in between the eviction of the page and a faulting of the page back into the cache. ### Claim 3 (depends on 1) The method of claim 1, wherein the cache lists comprise a protected list and a probationary list. ### Claim 4 (depends on 3) The method of claim 3, further comprising: determining whether the refault distance of the page is smaller than or equal to the number of pages that a size of the probationary list can increase, wherein the number of pages that the size of the probationary list can increase is equal to a size of the protected list; and when the refault distance is smaller than or equal to the number of pages that the size of the probationary list can increase, performing the adjusting the ratio. ### Claim 5 (depends on 3) The method of claim 3, wherein when the refault distance is greater than the number of pages that the size of the probationary list can increase, leaving the ratio of the protected list and the probationary list in a current state of the ratio. ### Claim 6 (depends on 1) The method of claim 1, wherein the data structure of the cache is a tree data structure, and wherein an offset of the page in the file is used as an index into the tree data structure to reference the entry for the page. ### Claim 7 (depends on 3) The method of claim 3, wherein the adjusting the ratio further comprising increasing the probationary list by at least one entry by moving at least one entry at a tail of the protected list to a head of the probationary list. ### Claim 8 (depends on 6) The method of claim 6, further comprising adding an entry for the page to the head of the probationary list. ### Claim 9 (depends on 1) The method of claim 1, wherein the eviction counter is incremented each time a page is evicted from the cache. ### Claim 10 A system, comprising: a plurality of nodes each comprising: a memory comprising a cache; and a processing device communicably coupled to the memory; and a memory management module executable from the plurality of nodes, the memory management module to: reference an entry of a data structure of a first cache of a first node of the plurality of nodes to identify a stored value of a global eviction counter, the stored value of the global eviction counter stored in the entry when a page of a file previously stored in the first cache was evicted from the first cache, wherein the first node originates a request for the page from a processing device of the first node; and calculating a first local refault distance of the page of the file based on the stored value, a current value of the global eviction counter, and a current value of a first local eviction counter associated with the first node. ### Claim 11 (depends on 10) The system of claim 10, wherein the memory management module further to, when the first local refault distance is smaller than or equal to a number of pages that a size of a probationary list of the first cache can increase, adjust a ratio of a protected list of the first cache and the probationary list of the first cache based on the determined first local refault distance, wherein the number of pages that the size of the probationary list of the first cache can increase is equal to a size of the protected list of the first cache. ### Claim 12 (depends on 11) The system of claim 11, wherein the memory management module further to: increase the probationary list of the first cache by at least one entry by moving at least one entry at a tail of the protected list of the first cache to a head of the probationary list of the first cache; and adding an entry for the page to the head of the probationary list of the first cache. ### Claim 13 (depends on 11) The system of claim 11, wherein the memory management module further to: when the first local refault distance is greater than the number of pages that the size of the probationary list of the first cache can increase, calculating a second local refault distance of the page of the file based on the value of the stored value, the current value of the global eviction counter, and a current value of a second local eviction counter associated with a second node of the plurality of nodes, wherein the second node is a neighboring node to the first node that originated the request for the page; and when the second local refault distance is smaller than a number of pages that a size of a probationary list of a second cache of the second node can increase, adjust a ratio of a protected list of the second cache and the probationary list of the second cache based on the determined second local refault distance, wherein the number of pages that the size of the probationary list of the second cache can increase is equal to a size of the protected list of the second cache. ### Claim 14 (depends on 13) The system of claim 13, wherein the memory management module further to: increase the probationary list of the second cache by at least one entry by moving at least one entry at a tail of the protected list of the second cache to a head of the probationary list of the second cache; and adding an entry for the page to the head of the probationary list of the second cache. ### Claim 15 (depends on 10) The system of claim 10, wherein the first local refault distance indicates a number of pages that were evicted from the first cache in between the eviction of the page and a faulting of the page back into the first cache. ### Claim 16 (depends on 10) The system of claim 10, wherein the memory management module further to decay the first local eviction counter at a rate that results in a higher weight placed on recent evictions from the first cache of the first node and a lower weight placed on older evictions from the first cache of the first node. ### Claim 17 A non-transitory machine-readable storage medium including data that, when accessed by a machine, cause the machine to perform operations comprising: referencing, by a processing device of the machine, an entry of a data structure of a cache in memory to identify a stored value of an eviction counter, the stored value of the eviction counter stored in the entry when a page of a file previously stored in the cache was evicted from the cache; determining, by the processing device, a refault distance of the page of the file based on a difference between the stored value and a current value of the eviction counter; when the refault distance is smaller than or equal to a number of pages that a size of a probationary list of the cache can increase, increasing, by the processing device, a size of the probationary list by at least one entry by moving at least one entry at a tail of a protected list of the cache to a head of the probationary list; and adding, by the processing device, an entry for the page to the head of the probationary list. ### Claim 18 (depends on 17) The non-transitory machine-readable storage medium of claim 17, wherein the refault distance indicates a number of pages that were evicted from the cache in between the eviction of the page and a faulting of the page back into the cache. ### Claim 19 (depends on 17) The non-transitory machine-readable storage medium of claim 17, wherein when the refault distance is greater than the number of pages that the size of the probationary list can increase, leaving the ratio of the protected list and the probationary list at a current state. ### Claim 20 (depends on 17) The non-transitory machine-readable storage medium of claim 17, wherein the data structure of the cache is a tree data structure, and wherein an offset of the page in the file is used as an index into the tree data structure to reference the entry for the page.