A program uses pages in the order given (the reference string). Memory has f frames, all empty at the start. Each reference to a page that is not in a frame is a page fault; the page is loaded into a free frame if there is one. When every frame is full, LRU removes the page that was used least recently. A hit counts as a use.
Input
The first line has f and n (1 ≤ f ≤ 10, 1 ≤ n ≤ 100). The second line has the n page numbers (0 to 99).
Output
Two lines: faults: F and hits: H.
Examples
Example 1 · Input
3 20 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
Expected output
faults: 12 hits: 8
Example 2 · Input
4 12 1 2 3 4 1 2 5 1 2 3 4 5
Expected output
faults: 8 hits: 4
Hints
Hint 1
For each frame, remember when its page was last used (the reference's position).
Hint 2
On a hit, update that time.
Hint 3
On a fault with full frames, replace the frame with the smallest time.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int frames, n, frame[10], last_used[10], used = 0, faults = 0;
scanf("%d %d", &frames, &n);
for (int i = 0; i < n; i++) {
int page, found = -1;
scanf("%d", &page);
for (int f = 0; f < used; f++)
if (frame[f] == page) found = f;
if (found >= 0) {
last_used[found] = i;
continue;
}
faults++;
int slot = used;
if (used < frames) {
used++;
} else {
slot = 0;
for (int f = 1; f < frames; f++)
if (last_used[f] < last_used[slot]) slot = f;
}
frame[slot] = page;
last_used[slot] = i;
}
printf("faults: %d\nhits: %d\n", faults, n - faults);
return 0;
}