Fifo page replacement infinite loop issue

Question

I am trying to do page replacement algorithm in C. I wrote the code below. I have written similar code that had worked below. But now when I try to reproduce the code enters an infinite loop.

I checked the for loop for hit and miss and it becomes stationary while current increments are unlimited. I have been tweaking the program for some time but nothing seems to work.

#include<stdio.h>
#include<stdlib.h>
int n,table[20],fsize,i,j,request[20],arr2[20],current,miss;

void initialize(int arr[],int n){ //set frame entries to -1
    for(i=0;i<n;i++){
        arr[i]=-1;
    }
}

int isavailable(int arg){ //checks if entry is available in frame table (array)
    int present=0;
    for(i=0;i<fsize;i++){
        if(table[i]==arg){
            present=1;
            break;
        }
    }
    return present;
}

void fifo(){ //first in first out
    miss=0;
    current=-1;
    initialize(table,fsize);
    for(i=0;i<n;i++){
        arr2[i]=request[i];
    }
    for(i=0;i<n;i++){
            if(isavailable(arr2[i])==1){ //hit condition
                printf("Hit");
                continue;
            }
            current=(current+1)%fsize; //interates in a cycle during miss
            table[current]=arr2[i]; //places in first entered location
            miss++;
    }
    printf("Total misses: %d",miss);
}

void main(){
    printf("Enter number of requests: ");
    scanf("%d",&n);
    printf("Enter table size: "); //reads frame table size
    scanf("%d",&fsize);
    printf("Enter requests: ");
    for(i=0;i<n;i++){
        scanf("%d",&request[i]); //reads request sequence in array
    }
    printf("FIFO: ");
    fifo();
    printf("LRU: ");
    //lru();
    printf("Optimal: ");
    //optimal();
    
}

Edit:- The input i gave are:-

• no of requests: 7
• sizeoftable: 3
• request: 1,3,0,3,5,6,3

Answer 1

An input of

1,3,0,3,5,6,3

will cause scanf("%d",&request[i]); to fail on the second iteration when it reads an invalid character of ,. This character will be left in the input buffer, and will cause subsequent iterations to also fail.

Only the first element of request is given a user-submitted value, the rest remain zero-initialized (due to static allocation).

You must check the return value of scanf is the expected number of conversions. Here we want to convert one integer (%d), so we check for a return value of 1 (or the inverse to check for error).

if (1 != scanf("%d", &request[i])) {
   /* Handle this problem.
    * A basic way:
    fprintf(stderr, "Invalid input!\n");
    exit(1);
    */
}

%d skips leading whitespace, so the input

1 3 0 3 5 6 3

is more appropriate for the specifier.

---

Using the global variable i as a for the loop condition in both fifo and the nested call to isavailable causes the value to ping-pong between 1 and 0 (with the given input), thus never reaching n.

The solution is to use more locally scoped variables, so that functions do not interfere with each other.

Here is a refactored example.

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>

#define MAX_ALLOC 32

static void panic(const char *fmt, ...)
{
    va_list args;
    va_start(args, fmt);
    vfprintf(stderr, fmt, args);
    va_end(args);
    exit(EXIT_FAILURE);
}

static int contains(int *array, size_t length, int value)
{
    for (size_t i = 0; i < length; i++)
        if (value == array[i])
            return 1;

    return 0;
}

static size_t fifo(size_t tsize, const int *requests, size_t rsize)
{
    int pages[tsize];

    for (size_t i = 0; i < tsize; i++)
        pages[i] = -1;

    size_t miss = 0;

    for (size_t i = 0, offset = 0; i < rsize; i++) {
        if (contains(pages, tsize, requests[i]))
            continue;

        pages[offset++ % tsize] = requests[i];
        miss++;
    }

    return miss;
}

int main(void)
{
    size_t rsize = 0;
    size_t tsize = 0;

    printf("Enter number of requests: ");
    if (1 != scanf("%zu", &rsize))
        panic("Invalid `rsize` format.\n");

    printf("Enter table size: ");
    if (1 != scanf("%zu", &tsize))
        panic("Invalid `tsize` format.\n");

    if (!rsize || rsize > MAX_ALLOC || !tsize || tsize > MAX_ALLOC)
        panic("Bad size(s) (`rsize`: %zu) (`tsize`: %zu) [1, %d]\n",
                rsize, tsize, MAX_ALLOC);

    int requests[rsize];

    printf("Enter requests: ");
    for (size_t i = 0; i < rsize; i++)
        if (1 != scanf("%d", &requests[i]))
            panic("Invalid `request` (%zu)", i + 1);

    printf("FIFO: %zu misses\n", fifo(tsize, requests, rsize));
}

Enter number of requests: 7  
Enter table size: 3
Enter requests: 1 3 0 3 5 6 3
FIFO: 6 misses