Poor Man’s LRU
The kernel uses the following idea several times over, once for each of several sorts of kernel data structure.
For such a sort there is a fixed size array of frames for that sort of structure.
Within each structure there is a field of 1, 2 or 3 bits usually called aging.
Each time the structure is used, aging is set to a constant K which depends on which array.
When some frame in the array must be allocated for a new structure, the scavenge index for the array is retrieved.
This index circularly traverses the array decrementing the aging field of each structure it passes and stopping when such a field is already 0.
That frame is vacated and allocated to the new structure.
The scavenge index is preserved to continue the scan for the next frame allocation in this array.
After the scan cycle has passed over a frame K times without having been required, the frame will be selected for reallocation.
For large aging fields this approaches true LRU.
For some of these arrays there is also a free list of unoccupied frames which is consulted first.
I am sure that this has been invented many times but I have not seen it described.
This paper describes a similar scheme called ‘reuse replacement’ where the counter is incremented, instead of set to K, each time it is required.
I don’t have numbers but we considered and abandoned that variation.
The use case that convinced us was a variable that is referenced three times in quick succession.
It should get no better cache service than another that was referenced just once at about the same time.
The Keykos kernel scheme is a better approximation to LRU.
Cache lines may well contain unrelated data and higher use count might foretell sooner future use.
This logic does not apply to the kernel structures.
See ‘xvalid’ here for aging mapping tables and pages.