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, FIFO removes the page that was loaded first.
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: 15 hits: 5
Example 2 · Input
4 12 1 2 3 4 1 2 5 1 2 3 4 5
Expected output
faults: 10 hits: 2
Hints
Hint 1
Keep the frames in an array, and the index of the frame FIFO will replace next.
Hint 2
A hit changes nothing for FIFO.
Hint 3
On a fault, put the page in that frame and move the index on, wrapping round with %.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int frames, n, frame[10], oldest = 0, faults = 0;
scanf("%d %d", &frames, &n);
for (int f = 0; f < frames; f++) frame[f] = -1;
for (int i = 0; i < n; i++) {
int page, hit = 0;
scanf("%d", &page);
for (int f = 0; f < frames; f++)
if (frame[f] == page) hit = 1;
if (!hit) {
frame[oldest] = page;
oldest = (oldest + 1) % frames;
faults++;
}
}
printf("faults: %d\nhits: %d\n", faults, n - faults);
return 0;
}