cpsc3655-assignment-3/a3.c

/*
 * Author: Tait Hoyem
 * License: Creative Commons 4.0: CC-BY-SA-NC
 *
 * Although the program works for part #1 (i.e., the fixed string)
 * it does not appear to work properly for section 2 (i.e., the random string).
 * My assumption is that this is not an error in the algorithm, but rather in
 * how to interpret the seed, or how to generate the numbers. If this can be
 * resolved by chaning the method of generation, or by interpreting the seed
 * differently, then I'd appreciate not being marked down for it, since the
 * algorithms are correct.
 *
 * The STRATEGY_faults(...) functions could not be simplified (abstracted) due
 * to opt_faults(...) requiring different parameters. I would have liked to make
 * this a little bit more generic like cache_missed(strategy_func, ...).
 */

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

#define PAGE_LENGTH 100

// headings
static char *FORMAT_STRING = "%-15s%-15s\n";
// strategies
static char *FORMAT_STRING_INT = "%-15s%-15d\n";

// Exit codes:
//
// 1: memory error
// 2: not enough command-line arguments
enum ErrorCodes {
  MEM_ERR = 1,
  CMD_ARGS_ERR,
};

// taken from assignment #2 for handling allocation errors
void malloc_err(void) {
  switch (errno) {
  case ENOMEM:
    fprintf(stderr, "Fatal error: out of memory!\n");
    break;
  default:
    fprintf(stderr, "Fatal malloc error code: %d\n", errno);
    break;
  }
  exit(MEM_ERR);
}

void help() { printf("Usage: a3 <number of frames> [seed for random]\n"); }

int find(int *frames, int num_frames, int value) {
  for (int i = 0; i < num_frames; i++) {
    if (frames[i] == value) {
      return i;
    }
  }
  return -1;
}

// reorders the cache frames based on LRU method
// returns true if there was a page fault; otherwise, false
int lru_reorder(int *frames, int num_frames, int new_frame) {
  int found_idx = find(frames, num_frames, new_frame);
  // if the value is not found in the frame list
  if (found_idx == -1) {
    // move all frame values forwards
    for (int i = num_frames - 1; i > 0; i--) {
      frames[i] = frames[i - 1];
    }
    // the newest frame is the latest requested
    frames[0] = new_frame;
    // cache miss
    return 1;
  }
  // if there the requestes frame is in the cache and is not the first item
  if (found_idx > 0) {
    // bubble up the element to the back
    for (int i = found_idx; i > 0; i--) {
      int temp = frames[i];
      frames[i] = frames[i - 1];
      frames[i - 1] = temp;
    }
  }
  // no cache miss
  return 0;
}

int lru_faults(int pages[PAGE_LENGTH], int *frames, int num_frames) {
  int faults = 0;
  for (int i = 0; i < PAGE_LENGTH; i++) {
    faults += lru_reorder(frames, num_frames, pages[i]);
  }
  return faults;
}

int fifo_reorder(int *frames, int num_frames, int new_frame) {
  int is_cache_miss = 0;
  int is_already_in = find(frames, num_frames, new_frame);
  // found, then not a cache miss
  if (is_already_in != -1) {
    return 0;
    // otherwise make sure to return the cache miss at the end of the function
  } else {
    is_cache_miss = 1;
  }
  // move all frames
  for (int i = num_frames - 1; i > 0; i--) {
    frames[i] = frames[i - 1];
  }
  // set first as new frame
  frames[0] = new_frame;
  return is_cache_miss;
}

int fifo_faults(int pages[PAGE_LENGTH], int *frames, int num_frames) {
  int faults = 0;
  for (int i = 0; i < PAGE_LENGTH; i++) {
    faults += fifo_reorder(frames, num_frames, pages[i]);
  }
  return faults;
}

int opt_reorder(int *frames, int num_frames, int page_idx,
                int pages[PAGE_LENGTH]) {
  // if alrady found, cache hit
  if (find(frames, num_frames, pages[page_idx]) != -1) {
    return 0;
  }
  // find the frame which is longest unused from now
  int lng_frame_val = 0;
  int frame_idx = 0;
  for (int i = 0; i < num_frames; i++) {
    int frame_val = 0;
    for (int j = page_idx; j < PAGE_LENGTH; j++) {
      if (pages[j] != frames[i]) {
        frame_val++;
      } else {
        break;
      }
    }
    if (frame_val > lng_frame_val) {
      lng_frame_val = frame_val;
      frame_idx = i;
    }
  }
  // repalce the frame that will be used farthest in the future
  frames[frame_idx] = pages[page_idx];
  // cache miss
  return 1;
}

int opt_faults(int pages[PAGE_LENGTH], int *frames, int num_frames) {
  int faults = 0;
  for (int i = 0; i < PAGE_LENGTH; i++) {
    faults += opt_reorder(frames, num_frames, i, pages);
  }
  return faults;
}

void clear_frames(int *frames, int num_frames) {
  for (int i = 0; i < num_frames; i++) {
    frames[i] = -1;
  }
}

int main(int argc, char **argv) {
  int pages[PAGE_LENGTH] = {2, 8, 7, 2, 0, 3, 1, 7, 3, 1, 9, 3, 6, 1, 8, 4, 5,
                            1, 8, 8, 3, 4, 4, 3, 4, 2, 0, 6, 6, 7, 0, 1, 0, 9,
                            3, 6, 4, 6, 8, 0, 4, 6, 2, 3, 5, 7, 8, 0, 3, 2, 0,
                            0, 0, 4, 6, 9, 1, 4, 3, 8, 8, 0, 0, 9, 7, 0, 7, 0,
                            9, 7, 7, 3, 8, 8, 9, 2, 7, 2, 1, 2, 0, 9, 1, 1, 1,
                            5, 0, 7, 1, 4, 9, 1, 9, 5, 8, 4, 4, 7, 9, 6};
  int num_frames = 0;
  int *frames = NULL;

  if (argc < 2) {
    help();
    exit(CMD_ARGS_ERR);
  } else if (argc >= 2) {
    num_frames = atoi(argv[1]);
    frames = malloc(sizeof(int) * num_frames);
    if (frames == NULL) {
      malloc_err();
    }
    clear_frames(frames, num_frames);
  }
  if (argc >= 3) {
    srand(atoi(argv[2]));
    for (int i = 0; i < PAGE_LENGTH; i++) {
      pages[i] = rand() % 10;
    }
  }
  printf(FORMAT_STRING, "Algorithm", "# Page faults");
  printf(FORMAT_STRING_INT, "FIFO", fifo_faults(pages, frames, num_frames));
  clear_frames(frames, num_frames);
  printf(FORMAT_STRING_INT, "LRU", lru_faults(pages, frames, num_frames));
  clear_frames(frames, num_frames);
  printf(FORMAT_STRING_INT, "OPT", opt_faults(pages, frames, num_frames));
  free(frames);
  return 0;
}