This program tries to simulate FIFO and LRU page replacement. I am trying to implement a simple queue using a dynamically allocated array for the FIFO queue. I want the "page" to be stored in the array.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
/*
* Some compile-time constants.
*/
#define REPLACE_NONE 0
#define REPLACE_FIFO 1
#define REPLACE_LRU 2
#define REPLACE_SECONDCHANCE 3
#define REPLACE_OPTIMAL 4
#define TRUE 1
#define FALSE 0
#define PROGRESS_BAR_WIDTH 60
#define MAX_LINE_LEN 100
/*
* Some function prototypes to keep the compiler happy.
*/
int setup(void);
int teardown(void);
int output_report(void);
long resolve_address(long, int);
void error_resolve_address(long, int);
/*
* Variables used to keep track of the number of memory-system events
* that are simulated.
*/
int page_faults = 0;
int mem_refs = 0;
int swap_outs = 0;
int swap_ins = 0;
/*
* Page-table information. You may want to modify this in order to
* implement schemes such as SECONDCHANCE. However, you are not required
* to do so.
*/
struct page_table_entry *page_table = NULL;
struct page_table_entry {
long page_num;
int dirty;
int free;
};
/*
* These global variables will be set in the main() function. The default
* values here are non-sensical, but it is safer to zero out a variable
* rather than trust to random data that might be stored in it -- this
* helps with debugging (i.e., eliminates a possible source of randomness
* in misbehaving programs).
*/
int size_of_frame = 0; /* power of 2 */
int size_of_memory = 0; /* number of frames */
int page_replacement_scheme = REPLACE_NONE;
long *queue;
void add_end(long page_num){
for(int i=0; i<size_of_memory; i++){
if(queue[i] == NULL){
queue[i] = page_num;
break;
}
}
}
long peek_front(){
return queue[0];
}
void remove_front(){
for(int i=0; i<size_of_memory; i++){
queue[i] = queue[i+1];
}
}
// typedef struct page_in_queue page_in_queue;
// struct page_in_queue {
// long page_num;
// page_in_queue *next;
// };
// page_in_queue *new_page(){
// page_in_queue *new_page;
// new_page = (page_in_queue *) malloc(sizeof(page_in_queue));
// new_page->next = NULL;
// return new_page;
// }
// page_in_queue *add_end(page_in_queue *queue, page_in_queue *page){
// page_in_queue *curr;
// if (queue == NULL) {
// page->next = NULL;
// return page;
// }
// for (curr = queue; curr->next != NULL; curr = curr->next);
// curr->next = page;
// page->next = NULL;
// return queue;
// }
// page_in_queue *peek_front(page_in_queue *queue) {
// return queue;
// }
// page_in_queue *remove_front(page_in_queue *queue){
// if (queue == NULL) {
// return NULL;
// }
// page_in_queue *new_front_page = queue->next;
// free(queue);
// return new_front_page;
// }
long *list;
void add(long page_num){
int i;
for (i=0; i<size_of_memory; i++){
list[i] = list[i+1];
}
list[i] = page_num;
}
long peek_least_used(){
return list[0];
}
/*
* Function to convert a logical address into its corresponding
* physical address. The value returned by this function is the
* physical address (or -1 if no physical address can exist for
* the logical address given the current page-allocation state.
*/
long resolve_address(long logical, int memwrite)
{
int i;
long page, frame;
long offset;
long mask = 0;
long effective;
/* Get the page and offset */
page = (logical >> size_of_frame);
for (i=0; i<size_of_frame; i++) {
mask = mask << 1;
mask |= 1;
}
offset = logical & mask;
if (page_replacement_scheme == 2){
add(page);
}
/* Find page in the inverted page table. */
frame = -1;
for ( i = 0; i < size_of_memory; i++ ) {
if (!page_table[i].free && page_table[i].page_num == page) {
frame = i;
break;
}
}
/* If frame is not -1, then we can successfully resolve the
* address and return the result. */
if (frame != -1) {
effective = (frame << size_of_frame) | offset;
return effective;
}
/* If we reach this point, there was a page fault. Find
* a free frame. */
page_faults++;
for ( i = 0; i < size_of_memory; i++) {
if (page_table[i].free) {
frame = i;
break;
}
}
// page_in_queue *temp_page;
// page_in_queue *queue;
long rem_page;
/* If we found a free frame, then patch up the
* page table entry and compute the effective
* address. Otherwise return -1.
*/
if (frame != -1) {
page_table[frame].page_num = page;
page_table[i].free = FALSE;
swap_ins++;
if (page_replacement_scheme == 1){
// temp_page = new_page();
// temp_page->page_num = page;
add_end(page);
}
effective = (frame << size_of_frame) | offset;
return effective;
}
else {
if (page_replacement_scheme == 1){
rem_page = peek_front();
for ( i = 0; i < size_of_memory; i++){
if(page_table[i].page_num == rem_page){
page_table[i].page_num = page;
page_table[i].free = FALSE;
page_table[i].dirty = memwrite;
swap_ins++;
if(page_table[i].dirty == 1){
swap_outs++;
}
frame = i;
break;
}
}
remove_front();
effective = (frame << size_of_frame) | offset;
return effective;
}
if (page_replacement_scheme == 2){
long temp = peek_least_used();
for ( i = 0; i < size_of_memory; i++){
if(page_table[i].page_num == temp){
page_table[i].page_num = page;
page_table[i].free = FALSE;
page_table[i].dirty = memwrite;
swap_ins++;
if(page_table[i].dirty == 1){
swap_outs++;
}
frame = i;
break;
}
}
effective = (frame << size_of_frame) | offset;
return effective;
}
if (page_replacement_scheme == 3){
}
}
}
/*
* Super-simple progress bar.
*/
void display_progress(int percent)
{
int to_date = PROGRESS_BAR_WIDTH * percent / 100;
static int last_to_date = 0;
int i;
if (last_to_date < to_date) {
last_to_date = to_date;
} else {
return;
}
printf("Progress [");
for (i=0; i<to_date; i++) {
printf(".");
}
for (; i<PROGRESS_BAR_WIDTH; i++) {
printf(" ");
}
printf("] %3d%%", percent);
printf("\r");
fflush(stdout);
}
int setup()
{
int i;
page_table = (struct page_table_entry *)malloc(
sizeof(struct page_table_entry) * size_of_memory
);
if (page_table == NULL) {
fprintf(stderr,
"Simulator error: cannot allocate memory for page table.\n");
exit(1);
}
for (i=0; i<size_of_memory; i++) {
page_table[i].free = TRUE;
}
return -1;
}
int teardown()
{
return -1;
}
void error_resolve_address(long a, int l)
{
fprintf(stderr, "\n");
fprintf(stderr,
"Simulator error: cannot resolve address 0x%lx at line %d\n",
a, l
);
exit(1);
}
int output_report()
{
printf("\n");
printf("Memory references: %d\n", mem_refs);
printf("Page faults: %d\n", page_faults);
printf("Swap ins: %d\n", swap_ins);
printf("Swap outs: %d\n", swap_outs);
return -1;
}
int main(int argc, char **argv)
{
/* For working with command-line arguments. */
int i;
char *s;
/* For working with input file. */
FILE *infile = NULL;
char *infile_name = NULL;
struct stat infile_stat;
int line_num = 0;
int infile_size = 0;
/* For processing each individual line in the input file. */
char buffer[MAX_LINE_LEN];
long addr;
char addr_type;
int is_write;
/* For making visible the work being done by the simulator. */
int show_progress = FALSE;
/* Process the command-line parameters. Note that the
* REPLACE_OPTIMAL scheme is not required for A#3.
*/
for (i=1; i < argc; i++) {
if (strncmp(argv[i], "--replace=", 9) == 0) {
s = strstr(argv[i], "=") + 1;
if (strcmp(s, "fifo") == 0) {
page_replacement_scheme = REPLACE_FIFO;
} else if (strcmp(s, "lru") == 0) {
page_replacement_scheme = REPLACE_LRU;
} else if (strcmp(s, "secondchance") == 0) {
page_replacement_scheme = REPLACE_SECONDCHANCE;
} else if (strcmp(s, "optimal") == 0) {
page_replacement_scheme = REPLACE_OPTIMAL;
} else {
page_replacement_scheme = REPLACE_NONE;
}
} else if (strncmp(argv[i], "--file=", 7) == 0) {
infile_name = strstr(argv[i], "=") + 1;
} else if (strncmp(argv[i], "--framesize=", 12) == 0) {
s = strstr(argv[i], "=") + 1;
size_of_frame = atoi(s);
} else if (strncmp(argv[i], "--numframes=", 12) == 0) {
s = strstr(argv[i], "=") + 1;
size_of_memory = atoi(s);
if (page_replacement_scheme == 1){
queue = (long *)malloc(sizeof(long)*size_of_memory);
}
if (page_replacement_scheme == 2){
list = (long *)malloc(sizeof(long)*size_of_memory);
}
} else if (strcmp(argv[i], "--progress") == 0) {
show_progress = TRUE;
}
}
if (infile_name == NULL) {
infile = stdin;
} else if (stat(infile_name, &infile_stat) == 0) {
infile_size = (int)(infile_stat.st_size);
/* If this fails, infile will be null */
infile = fopen(infile_name, "r");
}
if (page_replacement_scheme == REPLACE_NONE ||
size_of_frame <= 0 ||
size_of_memory <= 0 ||
infile == NULL)
{
fprintf(stderr,
"usage: %s --framesize=<m> --numframes=<n>", argv[0]);
fprintf(stderr,
" --replace={fifo|lru|optimal} [--file=<filename>]\n");
exit(1);
}
setup();
while (fgets(buffer, MAX_LINE_LEN-1, infile)) {
line_num++;
if (strstr(buffer, ":")) {
sscanf(buffer, "%c: %lx", &addr_type, &addr);
if (addr_type == 'W') {
is_write = TRUE;
} else {
is_write = FALSE;
}
if (resolve_address(addr, is_write) == -1) {
error_resolve_address(addr, line_num);
}
mem_refs++;
}
if (show_progress) {
display_progress(ftell(infile) * 100 / infile_size);
}
}
teardown();
output_report();
fclose(infile);
exit(0);
}
The file is saved as virtmem.c. This is the makefile:
#
# "makefile" for the virtual-memory simulation.
#
CC=gcc
CFLAGS=-c -Wall -g
all: virtmem
virtmem.o: virtmem.c
$(CC) $(CFLAGS) virtmem.c
virtmem: virtmem.o
$(CC) virtmem.o -o virtmem
clean:
rm -rf *.o virtmem
After running the "make" command, I run the executable with these inputs
./virtmem --framesize=12 --numframes=100 --replace=fifo --file=traces/ls_out.txt --progress
But it is giving a segmentation fault at the conditional "if(queue[i] == NULL)", saying the memory location cannot be accessed. The gdb output is as follows:
Program received signal SIGSEGV, Segmentation fault.
0x0000555555554bea in add_end (page_num=34158723704) at virtmem.c:80
80 if(queue[i] == (long)0){
(gdb) print queue[i]
Cannot access memory at address 0x0
(gdb)