zedchance/Makefile

## input1.txt
8 4 12
4
3
4
6
1
6
4
5
2
4
6
1


## input2.txt
10 4 30
5
4
4
3
2
5
1
6
6
5
2
7
1
6
1
2
6
9
6
0
2
3
6
5
3
2
6
7
7
1


## Makefile
all: vmem

vmem: vmem.c
	clang vmem.c -o vmem

test: vmem input1.txt
	./vmem input1.txt LRU
	./vmem input1.txt CLOCK

test2: vmem input2.txt
	./vmem input2.txt LRU
	./vmem input2.txt CLOCK

clean:
	rm -rf vmem


## vmem.c
// virtual memory simulator

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

typedef int page;
typedef int frame;

frame * memory;
int pcount = 0, fcount = 0, rcount = 0;
int faults = 0;

void set(page item, int index)
{
    memory[index] = item;
}

frame replace(page item, int item_to_replace)
{
    // look for item to replace
    for (int i = 0; i < fcount; i++)
    {
        if (memory[i] == item_to_replace)
        {
            memory[i] = item;
            return i;
        }
    }

    // can't find
    return 42;
}

page retrieve(page item)
{
    // search for page
    for (int i = 0; i < fcount; i++)
    {
        if (memory[i] == item)
        {
            return i;
        }
    }

    // can't retrieve
    return -1;
}

void lru(page * incoming)
{
    int last_used[pcount];
    for (int i = 0; i < pcount; i++)
    {
        // -1 indicates that page hasn't been used
        last_used[i] = -1;
    }

    // process requests
    for (int i = 0; i < rcount; i++)
    {
        printf("<%3d> ", i);
        page current = incoming[i];

        // check if page is already in memory
        if (retrieve(current) != -1)
        {
            printf("page %2d already in  frame %2d\n", current, retrieve(current));
            last_used[current] = i;
        }
        // page fault, swap page into memory
        else
        {
            // find which page to unload
            page oldest = (i - 1 < 0) ? -1 : incoming[i - 1];
            for (int j = 0; j < fcount; j++)
            {
                if (last_used[memory[j]] < last_used[oldest])
                {
                    oldest = memory[j];
                }
            }

            // swap in new page at index of oldest resident page
            frame new = replace(current, oldest);
            if (oldest != -1)
            {
                printf("page %2d unloaded from frame %2d, ", oldest, new);
            }
            printf("page %2d loaded into frame %2d\n", current, new);
            last_used[current] = i;
            faults++;
        }
    }
}

void clock(page * incoming)
{
    // 0 indicates no second chance
    // 1 indicates the page gets a second chance
    int second_chance[pcount];
    for (int i = 0; i < pcount; i++)
    {
        second_chance[i] = 0;
    }

    // process requests
    int pointer = 0;
    for (int i = 0; i < rcount; i++)
    {
        printf("<%3d> ", i);
        page current = incoming[i];

        // check if already in memory
        if (retrieve(current) != -1)
        {
            printf("page %2d already in  frame %2d\n", current, retrieve(current));
            second_chance[retrieve(current)] = 1;
        }

        // swap in page
        else
        {
            // move forward, using up second chances until we find one that doesn't have one
            while (second_chance[pointer] == 1)
            {
                second_chance[pointer] = 0;
                pointer = (pointer + 1) % fcount;
            }

            // -1 indicates the frame is empty
            if (memory[pointer] != -1)
            {
                printf("page %2d unloaded from frame %2d, ", memory[pointer], pointer);
            }
            printf("page %2d loaded into frame %2d\n", current, pointer);
            set(current, pointer);
            pointer = (pointer + 1) % fcount;
            faults++;
        }
    }
}

int main(int argc, char ** argv)
{
    // check args
    if (argc < 3)
    {
        fprintf(stderr, "Not enough arguments\n");
        fprintf(stderr, "Usage: %s input_file LRU|CLOCK\n", argv[0]);
        exit(1);
    }

    // open input file
    FILE * in = fopen(argv[1], "r");
    if (!in)
    {
        fprintf(stderr, "Can't open '%s' for reading\n", argv[1]);
        exit(1);
    }

    // setup
    char line[1000];
    fgets(line, 1000, in);
    sscanf(line, "%d %d %d", &pcount, &fcount, &rcount);

    // read incoming page order
    page incoming[rcount];
    int p = 0;
    while (fgets(line, 1000, in) != NULL)
    {
        if (sscanf(line, "%d", incoming + p) == 1) p++;
    }
    fclose(in);

    // create "memory"
    frame f[fcount];
    memory = f;
    for (int i = 0; i < fcount; i++)
    {
        // -1 represents an empty frame
        memory[i] = -1;
    }

    // get mode and run simulation
    if (strcmp(argv[2], "LRU") == 0)
    {
        printf("Page replacement algorithm: LRU\n");
        lru(incoming);
    }
    else if (strcmp(argv[2], "CLOCK") == 0)
    {
        printf("Page replacement algorithm: CLOCK\n");
        clock(incoming);
    }
    else
    {
        fprintf(stderr, "I don't know the '%s' page replacement algorithm\n", argv[2]);
        fprintf(stderr, "Usage: %s input_file LRU|CLOCK\n", argv[0]);
    }
    printf("%d page faults\n", faults);
}
	all: vmem

	vmem: vmem.c
	clang vmem.c -o vmem

	test: vmem input1.txt
	./vmem input1.txt LRU
	./vmem input1.txt CLOCK

	test2: vmem input2.txt
	./vmem input2.txt LRU
	./vmem input2.txt CLOCK

	clean:
	rm -rf vmem
	// virtual memory simulator

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

	typedef int page;
	typedef int frame;

	frame * memory;
	int pcount = 0, fcount = 0, rcount = 0;
	int faults = 0;

	void set(page item, int index)
	{
	memory[index] = item;
	}

	frame replace(page item, int item_to_replace)
	{
	// look for item to replace
	for (int i = 0; i < fcount; i++)
	{
	if (memory[i] == item_to_replace)
	{
	memory[i] = item;
	return i;
	}
	}

	// can't find
	return 42;
	}

	page retrieve(page item)
	{
	// search for page
	for (int i = 0; i < fcount; i++)
	{
	if (memory[i] == item)
	{
	return i;
	}
	}

	// can't retrieve
	return -1;
	}

	void lru(page * incoming)
	{
	int last_used[pcount];
	for (int i = 0; i < pcount; i++)
	{
	// -1 indicates that page hasn't been used
	last_used[i] = -1;
	}

	// process requests
	for (int i = 0; i < rcount; i++)
	{
	printf("<%3d> ", i);
	page current = incoming[i];

	// check if page is already in memory
	if (retrieve(current) != -1)
	{
	printf("page %2d already in frame %2d\n", current, retrieve(current));
	last_used[current] = i;
	}
	// page fault, swap page into memory
	else
	{
	// find which page to unload
	page oldest = (i - 1 < 0) ? -1 : incoming[i - 1];
	for (int j = 0; j < fcount; j++)
	{
	if (last_used[memory[j]] < last_used[oldest])
	{
	oldest = memory[j];
	}
	}

	// swap in new page at index of oldest resident page
	frame new = replace(current, oldest);
	if (oldest != -1)
	{
	printf("page %2d unloaded from frame %2d, ", oldest, new);
	}
	printf("page %2d loaded into frame %2d\n", current, new);
	last_used[current] = i;
	faults++;
	}
	}
	}

	void clock(page * incoming)
	{
	// 0 indicates no second chance
	// 1 indicates the page gets a second chance
	int second_chance[pcount];
	for (int i = 0; i < pcount; i++)
	{
	second_chance[i] = 0;
	}

	// process requests
	int pointer = 0;
	for (int i = 0; i < rcount; i++)
	{
	printf("<%3d> ", i);
	page current = incoming[i];

	// check if already in memory
	if (retrieve(current) != -1)
	{
	printf("page %2d already in frame %2d\n", current, retrieve(current));
	second_chance[retrieve(current)] = 1;
	}

	// swap in page
	else
	{
	// move forward, using up second chances until we find one that doesn't have one
	while (second_chance[pointer] == 1)
	{
	second_chance[pointer] = 0;
	pointer = (pointer + 1) % fcount;
	}

	// -1 indicates the frame is empty
	if (memory[pointer] != -1)
	{
	printf("page %2d unloaded from frame %2d, ", memory[pointer], pointer);
	}
	printf("page %2d loaded into frame %2d\n", current, pointer);
	set(current, pointer);
	pointer = (pointer + 1) % fcount;
	faults++;
	}
	}
	}

	int main(int argc, char ** argv)
	{
	// check args
	if (argc < 3)
	{
	fprintf(stderr, "Not enough arguments\n");
	fprintf(stderr, "Usage: %s input_file LRU\|CLOCK\n", argv[0]);
	exit(1);
	}

	// open input file
	FILE * in = fopen(argv[1], "r");
	if (!in)
	{
	fprintf(stderr, "Can't open '%s' for reading\n", argv[1]);
	exit(1);
	}

	// setup
	char line[1000];
	fgets(line, 1000, in);
	sscanf(line, "%d %d %d", &pcount, &fcount, &rcount);

	// read incoming page order
	page incoming[rcount];
	int p = 0;
	while (fgets(line, 1000, in) != NULL)
	{
	if (sscanf(line, "%d", incoming + p) == 1) p++;
	}
	fclose(in);

	// create "memory"
	frame f[fcount];
	memory = f;
	for (int i = 0; i < fcount; i++)
	{
	// -1 represents an empty frame
	memory[i] = -1;
	}

	// get mode and run simulation
	if (strcmp(argv[2], "LRU") == 0)
	{
	printf("Page replacement algorithm: LRU\n");
	lru(incoming);
	}
	else if (strcmp(argv[2], "CLOCK") == 0)
	{
	printf("Page replacement algorithm: CLOCK\n");
	clock(incoming);
	}
	else
	{
	fprintf(stderr, "I don't know the '%s' page replacement algorithm\n", argv[2]);
	fprintf(stderr, "Usage: %s input_file LRU\|CLOCK\n", argv[0]);
	}
	printf("%d page faults\n", faults);
	}