원본

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

#define MAX_SIZE 1000

struct Node
{
  int data;
  struct Node *next;
};

struct Queue
{
  struct Node *front;
  struct Node *rear;
  int size;
};

struct Node *newNode(int data)
{
  struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
  temp->data = data;
  temp->next = NULL;
  return temp;
};

struct Queue *createQueue()
{
  struct Queue *q = (struct Queue *)malloc(sizeof(struct Queue));
  q->front = q->rear = NULL;
  q->size = 0;

  return q;
}

int isEmpty(struct Queue *q)
{
  return q->front == NULL;
}

void enqueue(struct Queue *q, int data)
{
  struct Node *temp = newNode(data);
  temp->data = data;
  temp->next = NULL;

  if (isEmpty(q))
  {
    q->front = q->rear = temp;
  }
  else
  {
    q->rear->next = temp;
    q->rear = temp;
  }
  q->size++;
}

int dequeue(struct Queue *q)
{
  if (isEmpty(q))
  {
    return -1;
  }
  struct Node *temp = q->front;
  q->front = q->front->next;
  int data = temp->data;

  if (q->front == NULL)
  {
    q->rear = NULL;
  }
  free(temp);
  q->size--;

  return data;
}

int isPageInMemory(struct Queue *q, int page)
{
  struct Node *temp = q->front;
  while (temp != NULL)
  {
    if (temp->data == page)
    {
      return 1;
    }
    temp = temp->next;
  }
  return 0;
}

void printQueue(struct Queue *q)
{
  struct Node *temp = q->front;
  while (temp != NULL)
  {
    printf("%d ", temp->data);
    temp = temp->next;
  }
  free(temp);
  printf("\n");
}

void simulateFIFO(const char *filename, int node)
{
  FILE *file = fopen(filename, "r");
  if (file == NULL)
  {
    perror("failed");
    exit(EXIT_FAILURE);
  }

  struct Queue *q = createQueue();
  char line[MAX_SIZE];
  int hitCount = 0;
  int totalRequest = 0;

  while (fgets(line, sizeof(line), file))
  {
    char *token = strtok(line, " ");
    while (token != NULL)
    {
      int page = atoi(token);
      totalRequest++;

      if (isPageInMemory(q, page))
      {
        hitCount++;
      }
      else
      {
        if (q->size >= node)
        {
          dequeue(q);
        }
        enqueue(q, page);
      }
      token = strtok(NULL, " ");
    }
  }
  fclose(file);

  double hitRate = (double)hitCount / totalRequest * 100;
  printf("Total request: %d\n", totalRequest);
  printf("Page hit: %d\n", hitCount);
  printf("Hit rate: %.2f%%\n", hitRate);

  while (!isEmpty(q))
  {
    dequeue(q);
  }
  free(q);
}

int main()
{
  const char *filename = "../traces/tr.2c39.txt";

  printf("Result 500 nodes: \n");
  simulateFIFO(filename, 500);

  return 0;
}

수정본

#include <stdio.h>
#include <stdlib.h>
#define MAX_NODE 100

struct Node
{
  int data;
  struct Node *next;
};

struct Queue
{
  struct Node *front;
  struct Node *rear;
  int size;
};

int hitCount = 0;
int request = 0;

int isEmpty(struct Queue *q)
{
  return q->front == NULL;
}

struct Queue *createQueue()
{
  struct Queue *q = (struct Queue *)malloc(sizeof(struct Queue));
  q->front = q->rear = NULL;
  q->size = 0;

  return q;
}

void insert_rear(struct Queue *q, int data)
{
  struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
  temp->data = data;
  temp->next = NULL;

  if (isEmpty(q))
  {
    q->front = q->rear = temp;
  }
  else
  {
    q->rear->next = temp;
    q->rear = temp;
  }
  q->size++;
}

void delete_front(struct Queue *q)
{
  if (isEmpty(q))
  {
    return;
  }

  struct Node *temp = q->front;
  q->front = q->front->next;

  if (q->front == NULL)
  {
    q->rear = NULL;
  }
  free(temp);
  q->size--;
}

struct Node *search(struct Queue *q, int page)
{
  struct Node *temp = q->front;
  while (temp != NULL)
  {
    if (temp->data == page)
    {
      return temp;
    }
    temp = temp->next;
  }
  return NULL;
}

void simulateFIFO(struct Queue *q, int data)
{
  struct Node *temp = q->front;
  request++;

  if (search(q, data))
  {
    hitCount++;
  }

  if (q->size >= MAX_NODE)
  {
    delete_front(q);
  }
  insert_rear(q, data);
}

int main(void)
{
  const char *filename = "../traces/tr.2c39.txt";
  FILE *file = fopen(filename, "r");
  struct Queue *q = createQueue();
  int page;

  if (file == NULL)
  {
    exit(EXIT_FAILURE);
  }

  while (fscanf(file, "%d", &page) != EOF)
  {
    simulateFIFO(q, page);
  }
  fclose(file);

  double hitRate = (double)hitCount / request * 100;
  printf("Total request: %d\n", request);
  printf("Hit count: %d\n", hitCount);
  printf("Hit rate: %.2f%%\n", hitRate);

  return 0;
}