Motivation

...

We can try one of the modifications of LRU as well (for example, "segmented LRU" seems suitable for Ignite) or CLOCK algorithm (or one of its modifications).

Random-LRU algorithm

Random-LRU algorithm. Every time page is accessed, its timestamp gets updated. When a page fault occurs and it's required to replace some pages, the algorithm randomly chooses 5 pages from the page memory and evicts a page with the latest timestamp.

Segmented-LRU algorithm

Segmented-LRU algorithm is a scan-resistant variation of the Least Recently Used (LRU) algorithm. Segmented-LRU pages list is divided into two segments, a probationary segment, and a protected segment. Pages in each segment are ordered from the least to the most recently accessed. New pages are added to the most recently accessed end (tail) of the probationary segment. Existing pages are removed from wherever they currently reside and added to the most recently accessed end of the protected segment. Pages in the protected segment have thus been accessed at least twice. The protected segment is finite, so migration of a page from the probationary segment to the protected segment may force the migration of the LRU page in the protected segment to the most recently used end of the probationary segment, giving this page another chance to be accessed before being replaced. Page to replace is polled from the least recently accessed end (head) of the probationary segment.

...