JavaScript: LRU replacement with a Map
When memory is full, a cache or an operating system must evict something. Least-recently-used (LRU) evicts the item that has gone unused the longest, on the assumption that recent use predicts future use. Each access either hits a resident page or causes a page fault.
JavaScript
class LruMemory {
constructor(frames) {
this.frames = frames;
this.pages = new Map();
this.faults = 0;
}
access(page) {
if (this.pages.has(page)) {
this.pages.delete(page);
} else {
this.faults++;
if (this.pages.size === this.frames) {
const oldest = this.pages.keys().next().value;
this.pages.delete(oldest);
}
}
this.pages.set(page, true);
}
}
const refs = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1];
const memory = new LruMemory(3);
for (const page of refs) {
memory.access(page);
}
console.log("faults: " + memory.faults);
console.log("resident, oldest first: " + [...memory.pages.keys()].join(" "));