Skip to content

Instantly share code, notes, and snippets.

@zedchance
Created December 6, 2021 18:20
Show Gist options
  • Save zedchance/9d2aae8f4b313acb1664ada51e7f92af to your computer and use it in GitHub Desktop.
Save zedchance/9d2aae8f4b313acb1664ada51e7f92af to your computer and use it in GitHub Desktop.
Page swap algorithm simulator
8 4 12
4
3
4
6
1
6
4
5
2
4
6
1
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
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);
}
@zedchance
Copy link
Author

Output

./vmem input1.txt LRU
Page replacement algorithm: LRU
<  0> page  4 loaded into frame  0
<  1> page  3 loaded into frame  1
<  2> page  4 already in  frame  0
<  3> page  6 loaded into frame  2
<  4> page  1 loaded into frame  3
<  5> page  6 already in  frame  2
<  6> page  4 already in  frame  0
<  7> page  3 unloaded from frame  1, page  5 loaded into frame  1
<  8> page  1 unloaded from frame  3, page  2 loaded into frame  3
<  9> page  4 already in  frame  0
< 10> page  6 already in  frame  2
< 11> page  5 unloaded from frame  1, page  1 loaded into frame  1
7 page faults
./vmem input1.txt CLOCK
Page replacement algorithm: CLOCK
<  0> page  4 loaded into frame  0
<  1> page  3 loaded into frame  1
<  2> page  4 already in  frame  0
<  3> page  6 loaded into frame  2
<  4> page  1 loaded into frame  3
<  5> page  6 already in  frame  2
<  6> page  4 already in  frame  0
<  7> page  3 unloaded from frame  1, page  5 loaded into frame  1
<  8> page  1 unloaded from frame  3, page  2 loaded into frame  3
<  9> page  4 already in  frame  0
< 10> page  6 already in  frame  2
< 11> page  5 unloaded from frame  1, page  1 loaded into frame  1
7 page faults
./vmem input2.txt LRU
Page replacement algorithm: LRU
<  0> page  5 loaded into frame  0
<  1> page  4 loaded into frame  1
<  2> page  4 already in  frame  1
<  3> page  3 loaded into frame  2
<  4> page  2 loaded into frame  3
<  5> page  5 already in  frame  0
<  6> page  4 unloaded from frame  1, page  1 loaded into frame  1
<  7> page  3 unloaded from frame  2, page  6 loaded into frame  2
<  8> page  6 already in  frame  2
<  9> page  5 already in  frame  0
< 10> page  2 already in  frame  3
< 11> page  1 unloaded from frame  1, page  7 loaded into frame  1
< 12> page  6 unloaded from frame  2, page  1 loaded into frame  2
< 13> page  5 unloaded from frame  0, page  6 loaded into frame  0
< 14> page  1 already in  frame  2
< 15> page  2 already in  frame  3
< 16> page  6 already in  frame  0
< 17> page  7 unloaded from frame  1, page  9 loaded into frame  1
< 18> page  6 already in  frame  0
< 19> page  1 unloaded from frame  2, page  0 loaded into frame  2
< 20> page  2 already in  frame  3
< 21> page  9 unloaded from frame  1, page  3 loaded into frame  1
< 22> page  6 already in  frame  0
< 23> page  0 unloaded from frame  2, page  5 loaded into frame  2
< 24> page  3 already in  frame  1
< 25> page  2 already in  frame  3
< 26> page  6 already in  frame  0
< 27> page  5 unloaded from frame  2, page  7 loaded into frame  2
< 28> page  7 already in  frame  2
< 29> page  3 unloaded from frame  1, page  1 loaded into frame  1
15 page faults
./vmem input2.txt CLOCK
Page replacement algorithm: CLOCK
<  0> page  5 loaded into frame  0
<  1> page  4 loaded into frame  1
<  2> page  4 already in  frame  1
<  3> page  3 loaded into frame  2
<  4> page  2 loaded into frame  3
<  5> page  5 already in  frame  0
<  6> page  3 unloaded from frame  2, page  1 loaded into frame  2
<  7> page  2 unloaded from frame  3, page  6 loaded into frame  3
<  8> page  6 already in  frame  3
<  9> page  5 already in  frame  0
< 10> page  4 unloaded from frame  1, page  2 loaded into frame  1
< 11> page  1 unloaded from frame  2, page  7 loaded into frame  2
< 12> page  5 unloaded from frame  0, page  1 loaded into frame  0
< 13> page  6 already in  frame  3
< 14> page  1 already in  frame  0
< 15> page  2 already in  frame  1
< 16> page  6 already in  frame  3
< 17> page  7 unloaded from frame  2, page  9 loaded into frame  2
< 18> page  6 already in  frame  3
< 19> page  2 unloaded from frame  1, page  0 loaded into frame  1
< 20> page  9 unloaded from frame  2, page  2 loaded into frame  2
< 21> page  6 unloaded from frame  3, page  3 loaded into frame  3
< 22> page  1 unloaded from frame  0, page  6 loaded into frame  0
< 23> page  0 unloaded from frame  1, page  5 loaded into frame  1
< 24> page  3 already in  frame  3
< 25> page  2 already in  frame  2
< 26> page  6 already in  frame  0
< 27> page  5 unloaded from frame  1, page  7 loaded into frame  1
< 28> page  7 already in  frame  1
< 29> page  2 unloaded from frame  2, page  1 loaded into frame  2
17 page faults

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment