FIFO algorithm in C program

Question

what's the error in this code? the program runs but the output seem to have incorrect result.

#include <stdio.h>

int main() {
    int frameno, pageno, pHits = 0, pFaults = 0;

    printf("\nEnter Page Frame: ");
    scanf("%d", &frameno);

    printf("\nEnter Pages: ");
    scanf("%d", &pageno);

    printf("Enter string: ");

    int p, n, i;
    char temp[frameno], pageref[pageno];

    for (p = 0; p < pageno; p++) {
        scanf(" %c", &pageref[p]);
    }

    printf("\nPage Requested \t ");
    for (n = 0; n < frameno; n++) {
        printf("Page Frame %d \t", n + 1);
        temp[n] = '-'; // Initialize with a character that doesn't conflict with pages
    }

    for (p = 0; p < pageno; p++) {
        int pageFound = 0;

        for (i = 0; i < frameno; i++) {
            if (pageref[p] == temp[i]) {
                pHits++;
                pageFound = 1;
                break;
            }
        }

        pFaults++;
        if (!pageFound) {
            if (pFaults <= frameno && pHits == 0) {
                temp[p] = pageref[p];
            } else {
                temp[(pFaults - 1) % frameno] = pageref[p];
            }
        }

        printf("\n%c\t", pageref[p]);
        for (i = 0; i < frameno; i++) {
            if (temp[i] != '-') {
                printf("\t\t %c", temp[i]);
            } else {
                printf(" \t\t");
            }
        }
    }

    printf("\nPage Faults: %d\t", pFaults);
    printf("\nPage Hits: %d\t", pHits);

    return 0;
}

The ouput came out like this, there should be 5 in page frame 1.

Enter Page Frame: 3

Enter Pages: 5
Enter string: 41245

FIFO
Page Requested   Page Frame 1   Page Frame 2    Page Frame 3
4                        4
1                        4               1
2                        4               1               2
4                        4               1               2
5                        4               1               2
Page Faults: 5
Page Hits: 1

Answer 1

I'm assuming that you want to evict the oldest page, the one that came in "first". Not necessarily what is in frame[0], although frame[0] would be the first frame to be ejected since it would contain the first insert. If you only evicted from frame[0], then frames[1] and frames[2] would never change after having something loaded in them.

We'll introduce one additional array:

int insertTimes[frameno] = {0};

Which represents the "time" each page was inserted into your temp array. And then we'll introduce a clock, which is just an integer that increases by 1 each time there's a page fault. You could also just use your pPageFaults counter as well for the time since it's also monotonically increasing.

When we have a page fault, we'll use insertTimes to find the frame with the oldest entry in it by finding the smallest value in it and using the index found to be the indicator of "frame with oldest page"

Also, while we're at it, we'll fix the bug in your code that was also increment pPageFaults by 1 regardless of whether there was one or not.

For your consideration:

void zeroOutArray(char* ptr, size_t numBytes) {
    for (size_t i = 0; i < numBytes; i++) {
        ptr[i] = '\0';
    }
}

int main() {
    int frameno, pageno, pHits = 0, pFaults = 0;

    printf("\nEnter Page Frame: ");
    scanf("%d", &frameno);

    printf("\nEnter Pages: ");
    scanf("%d", &pageno);

    printf("Enter string: ");

    int p, n, i;


    // each array initialized to ={0} which will zero out the entire array
    char temp[frameno];
    char pageref[pageno+1];       // +1 for easier debugging
    int insertionTimes[frameno];  // insertionTimes[i] has the insertion time of the page inside temp[i]

    zeroOutArray(temp, frameno);
    zeroOutArray(pagref, pageno+1);
    zeroOutArray((char*)insertionTimes, sizeof(int)*frameno);


    int inserttime = 1; // our clock

    for (p = 0; p < pageno; p++) {
        scanf(" %c", &pageref[p]);
    }

    printf("\nPage Requested \t ");
    for (n = 0; n < frameno; n++) {
        printf("Page Frame %d \t", n + 1);
        temp[n] = '-'; // Initialize with a character that doesn't conflict with pages
    }

    for (p = 0; p < pageno; p++) {
        int pageFound = 0;

        for (i = 0; i < frameno; i++) {
            if (pageref[p] == temp[i]) {
                pHits++;
                pageFound = 1;
                break;
            }
        }

        if (!pageFound) {
            pFaults++;
            // find the frame with the earliest insert time and replace it with the page requested
            int best = 0;
            for (int i = 0; i < frameno; i++) {
                if (insertionTimes[i] < insertionTimes[best]) {
                    best = i;
                }
            }

            // evict the page at temp[best] and replace it with the one requested
            temp[best] = pageref[p];
            insertionTimes[best] = inserttime++;
        }

        printf("\n%c\t", pageref[p]);
        for (i = 0; i < frameno; i++) {
            if (temp[i] != '-') {
                printf("\t\t %c", temp[i]);
            }
            else {
                printf(" \t\t");
            }
        }
    }

    printf("\nPage Faults: %d\t", pFaults);
    printf("\nPage Hits: %d\t", pHits);

    return 0;
}

Sample run:

Enter Page Frame: 3

Enter Pages: 5
Enter string: 41245

Page Requested   Page Frame 1   Page Frame 2    Page Frame 3
4                        4
1                        4               1
2                        4               1               2
4                        4               1               2
5                        5               1               2
Page Faults: 4
Page Hits: 1

Answer 2

As @JoëlHecht pointed out you probably don't want to count a page fault on hit (or said differently pageno == pFaults + pHits) and once that is fixed you get the expected output. If you want FIFO then you need to track the order of the pages being populated. @selbie provided you input on that so I leave this as a minimal fix for the question asked.

I usually prefer a goto to a flag but here it's easier to just delegate the search to a function (in this case memchr()). Using ' ' instead of - for empty pages so you don't have to special case the output.

Always check the return value on scanf() otherwise you may be operating on uninitialized data.

#include <stdio.h>
#include <string.h>

int main(void) {
    printf("Enter Page Frame: ");
    int frameno;
    scanf("%d", &frameno);

    printf("Enter Pages: ");
    int pageno;
    scanf("%d", &pageno);

    printf("Enter string: ");
    char pageref[pageno];
    for (int p = 0; p < pageno; p++)
        scanf(" %c", &pageref[p]);

    printf("Page Requested");
    char temp[frameno];
    for (int n = 0; n < frameno; n++) {
        printf("\tPage Frame %d", n + 1);
        temp[n] = ' '; // Initialize with a character that doesn't conflict with pages
    }
    printf("\n");
    int pHits = 0;
    int pFaults = 0;
    for (int p = 0; p < pageno; p++) {
        if(memchr(temp, pageref[p], pageno))
            pHits++;
        else {
            pFaults++;
            temp[pFaults <= frameno && pHits == 0 ? p : (pFaults - 1) % frameno] = pageref[p];
        }
        printf("%c", pageref[p]);
        for (int i = 0; i < frameno; i++)
            printf("\t\t%c", temp[i]);
        printf("\n");
    }
    printf(
        "Page Faults: %d\n"
        "Page Hits: %d\n",
        pFaults,
        pHits
    );
    return 0;
}

and you the output is now as you wanted (layout compressed a bit):

Enter Page Frame: 3
Enter Pages: 5
Enter string: 41245
Page Requested  Page Frame 1    Page Frame 2    Page Frame 3
4               4                                
1               4               1                
2               4               1               2
4               4               1               2
5               5               1               2
Page Faults: 4
Page Hits: 1