Description

Lab assignment 8: Memory Management
Objectives
1. To simulate two kinds of basic page replacement algorithms
2. To evaluate the performance, in terms of miss/hit rate, of these algorithms

Guidelines
The goal of this assignment is to gain experience with page replacement (and to a lesser extent, caching) algorithms. In this assignment, your goal is to write programs that simulate page replacement algorithms. Your initial program is to accept at least one numeric command-line parameter, which it will use as the number of available page frames. In this case: int main(int argc, char *argv[]){
int cacheSize = atoi(argv[1]); // Size of Cache passed by user

A simulation of a page replacement algorithm will then use cacheSize as a number of pages/blocks of memory/cache size. This value can be read for example using “lru” as follows:

$lru 27 or $simulate -lru 7

Your program should expect page requests to arrive on standard input (stdin), so a basic fgets(), or scanf() call cab be used to read in the unsigned integer page numbers being requested. Assuming you have a sequence of page numbers in a text file called “testInput.txt” you should be able to run your simulator by typing:

$cat testInput.txt| lru 42

Generate testInput.txt file

int main(int argc, char *argv[]) { FILE *fp; char buffer [sizeof(int)];
int i;
fp = fopen(“testInput.txt”, “w”); for (i=0; i<someNumber; i++){ sprintf(buffer, “%d “, rand()%capNumber); fputs(buffer, fp);
}
fclose(fp); return 0;
}

Step 2. Define the following data types in your page replacement code: typedef struct { int pageno;
. . .
} ref_page;

ref_page cache[cacheSize]; // Cache that stores pages char pageCache[100]; // Cache that holds the input from test file int totalFaults = 0; // keeps track of the total page faults

Read page requests iteratively
Step 3. Write a C program to read iteratively the output of $cat testInput.txtpipelined as a standard input to the executable page replacement program. This can be implemented using
char *fgets(char *str, int n, FILE *stream)

while (fgets(pageCache, 100, stdin)) {
int page_num = atoi(pageCache); // Stores number read from file as an int

In this case, your program will accept page requests on stdin as individual numbers, one per line, where each number indicates the requested page number. Each program is to further ignore any trailing text on the input lines, or any lines that do not start with a number. Your program terminates its simulation when it encounters an end-of-file.

Test for memory sizes of between 10 and 500 pages.

Page replacement algorithm
Step 4. Write a program for each of the following replacement algorithms: FIFO, LRU, and Second Chance Page Replacement.

FIFO (First In First Out): is the simplest page replacement algorithm that keeps track of all the pages in the memory in a queue with the oldest page at the front of the queue. On a page fault, it replaces the oldest page that has been present in memory for the longest time. The following code snippet is provided as a guidance. A similar code can be implemented for the LRU and 2nd chance:

bool foundInCache = false;
for (i=0; i<cacheSize; i++){ if (cache[i].pageno == page_num){ foundInCache = true; break; //break out loop because found page_num in cache
}
}
if (foundInCache == false){
}
Check pseudo code

Expected Output
Step 5. The output of a page replacement program will be every page number that was not found to be in the cache. In other words, the output will be a sequence of page numbers that represents all the incoming requests that resulted in a page fault. Using your program, you should be able to get two numbers from the Unix command line (by counting the number of lines read from the input file, and the number of lines produced by your simulator). The first of these numbers is the total number of page/block requests your simulator program has received (you get this by counting the number of valid lines in your input file), and the second number is how many of these page requests did result in a page fault (you get this by counting the number of lines produced as output by your program – which is faithfully reproducing the page replacement algorithm’s behavior).

Once again, the size of the memory being managed by your program (the number of page frames, or the size of the cache if you treat this as a caching algorithm) is to be accepted as a command-line argument to your program. Any status output (e.g., messages you wish to print for debugging/user) should be sent to stderr (standard error, in other words, it should be possible to use your program and see nothing in standard output other than the page-faults/cache-misses, by redirecting only stdout).

Test your Page Replacement Algorithms using a series of commands in a shell script
Step 6. In lab 1, you learned about shell scripting as a tool that allows you to execute a series of commands by running a shell program that contains them instead of typing all commands. Create a .sh file to generate different test cases, e.g.
#!/bin/bash make;
echo “———-FIFO———-” cat testInput.txt | ./fifo 10 echo “———-End FIFO———-” echo
echo “———-LRU———-” cat testInput.txt | ./lru 10 echo “———-End LRU———-” echo echo “———-Second Chance———-” cat testInput.txt | ./sec_chance 10 echo “———-End Second Chance———-”

echo “FIFO 10K Test with cache size = 10, 50, 100, 250, 500” cat testInput10k.txt | ./fifo 10 | wc -l cat testInput10k.txt | ./fifo 50 | wc -l cat testInput10k.txt | ./fifo 100 | wc -l cat testInput10k.txt | ./fifo 250 | wc -l cat testInput10k.txt | ./fifo 500 | wc -l echo echo “LRU 10K Test with cache size = 10, 50, 100, 250, 500” cat testInput10k.txt | ./lru 10 | wc -l cat testInput10k.txt | ./lru 50 | wc -l cat testInput10k.txt | ./lru 100 | wc -l cat testInput10k.txt | ./lru 250 | wc -l cat testInput10k.txt | ./lru 500 | wc -l echo
echo “Second Chance 10K Test with cache size = 10, 50, 100, 250, 500” cat testInput10k.txt | ./sec_chance 10 | wc -l cat testInput10k.txt | ./sec_chance 50 | wc -l cat testInput10k.txt | ./sec_chance 100 | wc -l cat testInput10k.txt | ./sec_chance 250 | wc -l cat testInput10k.txt | ./sec_chance 500 | wc -l echo make clean;
echo

all: fifo.c lru.c sec_chance.c gcc -o lru lru.c gcc -o fifo fifo.c
gcc -o sec_chance sec_chance.c

clean:; rm -f *.out lru fifo sec_chance
Requirements to complete the lab
2. Write up a description of your implementations and sample miss-rate (page fault rate) results, and submit it alongside your code. This portion of the assignment is as critical, if not more so, than the actual implementation of your solution.
3. Provide a complete write-up that will include a test of your solutions and a comparison of the hit rates for the different algorithms you have implemented. Create a table and plot a graph to represent your findings.

Note: Your tests use random numbers but be aware that assignments are tested against a test file, so it’s a good idea to study your results carefully and to pay particular attention to verifying the correct behavior of your replacement algorithms.