Memory is full — who goes?
When a page fault happens and every frame is in use, the kernel must evict a page to disk. Evict one that's needed again soon and you get another fault. FIFO throws out the oldest page; LRU throws out the one *used* longest ago — usually much better, because programs reuse recent data (locality, again).
Two policies
function fifo(refs, frames) {
const memory = [];
let faults = 0;
for (const page of refs) {
if (memory.includes(page)) continue; // hit
faults++;
if (memory.length === frames) memory.shift(); // evict the oldest arrival
memory.push(page);
}
return faults;
}
function lru(refs, frames) {
const memory = []; // least recently used first
let faults = 0;
for (const page of refs) {
const i = memory.indexOf(page);
if (i >= 0) {
memory.splice(i, 1); // hit: move to "most recent"
memory.push(page);
continue;
}
faults++;
if (memory.length === frames) memory.shift(); // evict the least recently used
memory.push(page);
}
return faults;
}