50 lines
2.1 KiB
C
50 lines
2.1 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
|
|
// Page Replacement: FIFO & Optimal (Minimal Code for Paper)
|
|
int main() {
|
|
int nf, np, i, j, k, pf, hit, idx, max_f, vic; // nf=frames, np=pages, pf=faults, idx=fifo_idx, max_f=max_future, vic=victim
|
|
int *rs, *f; // rs=ref_string, f=frames
|
|
|
|
printf("F N:"); scanf("%d%d", &nf, &np); // Frames, NumPages
|
|
rs = malloc(np * sizeof(int));
|
|
f = malloc(nf * sizeof(int));
|
|
if(!rs || !f) return 1; // Basic alloc check
|
|
printf("RS:"); for(i=0; i<np; i++) scanf("%d", &rs[i]); // Ref String
|
|
|
|
// FIFO
|
|
puts("FIFO"); pf=0; idx=0;
|
|
for(k=0; k<nf; k++) f[k]=-1; // Init frames
|
|
for(i=0; i<np; i++){ // Iterate ref string
|
|
hit=0; for(k=0; k<nf; k++) if(f[k]==rs[i]) {hit=1; break;} // Check hit
|
|
if(!hit){ // Page Fault
|
|
pf++; f[idx]=rs[i]; idx=(idx+1)%nf; // Replace using FIFO index
|
|
}
|
|
}
|
|
printf("F:%d\n", pf); // Print Faults
|
|
|
|
// Optimal
|
|
puts("OPT"); pf=0;
|
|
for(k=0; k<nf; k++) f[k]=-1; // Re-init frames
|
|
for(i=0; i<np; i++){ // Iterate ref string
|
|
hit=0; for(k=0; k<nf; k++) if(f[k]==rs[i]) {hit=1; break;} // Check hit
|
|
if(!hit){ // Page Fault
|
|
pf++; int empty=-1; for(k=0; k<nf; k++) if(f[k]==-1) {empty=k; break;} // Find empty frame
|
|
if(empty!=-1) f[empty]=rs[i]; // Use empty frame if available
|
|
else { // No empty frames, find victim
|
|
vic=0; max_f=-1; // Victim index, max future distance
|
|
for(k=0; k<nf; k++){ // Check each current frame 'f[k]'
|
|
int fut=-1; // Index of next use for f[k]
|
|
for(j=i+1; j<np; j++) if(f[k]==rs[j]) {fut=j; break;} // Look ahead
|
|
if(fut==-1) {vic=k; break;} // f[k] not used again? Best victim. Stop search.
|
|
if(fut>max_f) {max_f=fut; vic=k;} // f[k] used later than current max? Update victim.
|
|
}
|
|
f[vic]=rs[i]; // Replace victim frame
|
|
}
|
|
}
|
|
}
|
|
printf("F:%d\n", pf); // Print Faults
|
|
|
|
free(rs); free(f); // Free memory
|
|
return 0;
|
|
}
|