When virtual memory systems decide to evict a memory page out to disk, it’s sometimes mentioned that the last time of access of that memory page is used to help decide which page is evicted. But what mechanism is used to track the last time of access of a memory page?
I believe the TLB only stores information on its current set of pages not all of them. Or is it simply that anything not present in the TLB is game for eviction under that criteria?
Advertisement
Answer
The page frame reclaiming algorithm(PFRA) in Linux kernel is acutally quite complex and it uses several heuristics to decide which page to evict. The actual decision is based on many factors, but following two stand out.
1. The Least Recently Used (LRU) Lists
Linux divides memory into different memory zones, each zone has a zone descriptor and this descriptor along with other things stores references to two very important lists namely active and inactive.
The active list includes the pages that have been accessed recently, while the inactive list includes the pages that have not been accessed for some time. Different page frames move from one list to another and out of lists depending on the access patterns.
2. Page descriptor flags
following two flags in the page descriptor allows kernel to identify if a given page is included in one of the above lists.
PG_lru – The page is in the active or inactive page list
PG_active -The page is in the active page list
Understanding the Linux Kernel states the following when it describes how PFRA actually uses above information.
The main idea behind the LRU algorithm is to associate a counter storing the age of the page with each page in RAM—that is, the interval of time elapsed since the last access to the page. This counter allows the PFRA to reclaim only the oldest page of any process. Some computer platforms provide sophisticated support for LRU algorithms;† unfortunately, 80 × 86 processors do not offer such a hardware feature, thus the Linux kernel cannot rely on a page counter that keeps track of the age of every page. To cope with this restriction, Linux takes advantage of the Accessed bit included in each Page Table entry, which is automatically set by the hardware when the page is accessed; moreover, the age of a page is represented by the position of the page descriptor in one of two different “The Least Recently Used (LRU) Lists”.