CS480 Notes

Explore

Project files

Project #4

Last edited 276 days ago by System Writer

Name

Priority

Status

Button

Open up Project 5 files

000

🚀 Done

Done

Pseudo Code

000

🚀 Done

Done

Demonstrate functionality

000

🚀 Done

Done

Get started on Project 5

000

🚀 Done

Done

Problem set 4

000

🔨 Working on it

Done

There are no rows in this table

⁠

Project parameters:

PURPOSE

This assignment is to simulate two different page replacement algorithms: First-in First-out(FIFO) and Least Recently Used(LRU). This comparison will give you a better understanding of these two page replacement algorithms.

DESCRIPTION A program needs to have its code and data reside in memory before it is executed. But sometimes the memory size cannot fit all the code and data of running programs. The solution is to slice both memory and programs into equal-sized pages. An OS can easily swap in the needed page of a program from disk to memory. Paging happens when a page fault occurs. A page fault happens when a needed page is not resident in memory and needs to be swapped in, possibly overwriting another page in memory. A page replacement algorithm decides which memory page must be paged out (swap out, write to disk) to make room for the requested page. To design a good page replacement algorithm, we don't want to frequently swap the same memory page in and out. So to evaluate a page replacement algorithm, we can run it on a particular pattern of memory references and determine the number of page faults that occur, the fewer the better. In this assignment, you need to implement the FIFO and LRU page-replacement algorithms presented in this chapter.

ASSIGNMENT Please download four.zip, which includes the following files:

vmalgorithm.h // header file defines Marcos and global variables

vmalgorithm.c // implementation of LRU and FIFO algorithms

testvm.c // test program Makefile

Readme // Design Documentation: you need to explain how you implement the LRU and FIFO algorithm.

Your assignment is to fill the FIFO and LRU functions in vmalgorithm.c to simulate FIFO and LRU page replacement algorithm, respectively. Feel free to add helper functions, global variables and etc if needed.

The testvm.c is the test program, so DO NOT modify it unless for test purpose (You may need to comment/uncomment a few lines during your test, will elaborate later).

There are several global variables defined vmalgorithm.h should be used in your code, please understand each of them before coding: #define AccessPatternLength 20 // total number of memory access

typedef struct { int *PageFrameList; // The dynamically-allocated array representing memory frames int nextToReplaced; // point to the next frame to be replaced }PageFrame;

int *accessPattern; // point to an dynamic-allocated array indicating page access pattern. For example, int accessPattern[5] = [4,2,2,0,1] means page 4,2,2,0,1 will be accessed one by one in order

int ReferenceSZ; // range of pages to be accessed, if this number is 4, which indicates the maximum page index to be accessed is 4. int FrameNR; // the number of page frames in memory PageFrame memory; // representing the simulated memory

You need to understand the differences between page (virtual memory) and page frame (physical memory). For example, if ReferenceSZ = 7 and FrameNR = 3, then the program has 7 virtual pages but the physical memory only has 3 page frames, so paging is mandatory.

Suppose the access pattern accessPattern = [5 2 2 0 4], initially, the memory is empty, so PageFrameList: -1, -1, -1.

By following the access pattern, if page fault, the page will be loaded into memory, so PageFrameList should be changed in the following order:

5 -1 -1 //access page 5, page fault 5 2 -1 //access page 2, page fault 5 2 -1 //access page 2, hit 5 2 0 //access page 0, page fault 4 2 0 //access page 4, since the page 5 is LRU, evict it and load in Page 4.

TESTING The code will take two arguments: one is the page range (virtual memory), the other is the number of page frames in memory.

The command Format:

./testvm [reference page range] [number of frames]

For example: ./testvm 7 3 The displayed information should look as below: The Access Pattern: 5 2 2 0 4 6 4 4 1 3 4 5 0 4 5 6 2 0 0 1 Running program using FIFO algorithm ... ... 5 -1 -1 5 2 -1 5 2 -1 5 2 0 4 2 0 . . . 0 6 2 1 6 2 page fault of FIFO: 13

The Same Access Pattern: 5 2 2 0 4 6 4 4 1 3 4 5 0 4 5 6 2 0 0 1 Running program using LRU algorithm ... ... 5 -1 -1 5 2 -1 5 2 -1 5 2 0 4 2 0 . . . 2 6 0 2 1 0 page fault of LRU: 13

Note: We strongly recommend you follow the instructions to change testvm.c to further verify your code (You only need to comment/uncomment a few lines there).

REQUIREMENTS: 1. Your program should work for any random value of accessPattern, ReferenceSZ and FrameNR;

2. You should utilize the Structure PageFrame in implementing FIFO and LRU algorithms. To be more specific, PageFrameList is to store the loaded pages in memory frames and nextToReplaced is to indicate the next memory frame to be replaced. 3. The screen output should be similar as the example shown above, you must print out PageFrameList after each memory access; 4. The total number of page fault must be calculated and printed out.

Directions to complete your assignment

Download the provided source code from

four.zip⁠

⁠

Download four.zip⁠

to your computer. (Note: would recommend using a computer installed with Ubuntu 22.04, you also can use Edoras server if you don't have the computer)

Unzip the zip file on your using the commands:

unzip four.zip

so you will have a new folder: four (source files).

3. Modify source files under folder four to complete this assignment (Note: you should add appropriate level of comments in your code).

Test your program to make sure it works correctly.

Re-test your program following the commands provided above and record the terminal session to Test.log

Answer the questions included in README file.

How to submit your assignment

Please submit all your source code including README and Test.log to Gradescope (Required), submission to Edoras server is NOT required. Note: You can develop and test your program on Edoras if you want, but MUST submit your Code to Gradescope.

Note: You MUST follow all of the assignment specifications. Even if you get a 70/70 Autograding on the Gradescope, we will be manually checking for the requirements and deducting points if you break them.

Please finish your coding by 11:59pm Aug 6st . Your grading may be started immediately after the deadline unless noticed otherwise, so please make your files ready by the deadline.

Excuses of “but it worked on my machine” will not be accepted, so if you develop elsewhere, plan to leave time for any migration problems that might arise.

vmalgorithm.c - Implementation of LRU and FIFO algorithms

FIFO()

The First-In, First-Out (FIFO) algorithm is a type of paging algorithm in which the page that is first brought into the memory will be the first one to be removed upon needing a replacement. In this case, we will maintain a pointer to the next frame due to be replaced.

Implementation Steps for FIFO:

Initialize a variable pageFaults to count the number of page faults.

Iterate through the access pattern (i.e., the sequence of pages to be accessed).

For each page, check if it is already in the page frame list (memory).

If the page is found in memory, continue to the next page.

If the page is not found in memory, replace the page frame pointed to by memory.nextToReplaced with the current page.

Increment memory.nextToReplaced in a circular manner using the modulo operator.

Increment the page fault count.

Print the current state of the page frames.

Return the total number of page faults.

function FIFO(accessPattern, frameCount): pageFrameList = array of size frameCount initialized to -1 nextToReplace = 0 pageFaults = 0

for page in accessPattern: if page not in pageFrameList: pageFrameList[nextToReplace] = page nextToReplace = (nextToReplace + 1) % frameCount pageFaults += 1

return pageFaults

LRU()

The Least Recently Used (LRU) algorithm is another type of paging algorithm which works on the principle of replacing the page that has not been used for the longest duration of time. For this algorithm, we can use an additional array 'lastUsed' that tracks the last use of a page.

Iterate over 'accessPattern' and for each access, update the corresponding index in 'lastUsed' to the iteration number.

When a page fault occurs, find the page with the smallest 'lastUsed' value and replace that page.

function LRU(accessPattern, frameCount): pageFrameList = array of size frameCount initialized to -1 lastUsed = array of size frameCount to keep track of last access time pageFaults = 0 time = 0

for page in accessPattern: if page not in pageFrameList: replaceIndex = index of the minimum value in lastUsed pageFrameList[replaceIndex] = page lastUsed[replaceIndex] = time pageFaults += 1 else: index = index of page in pageFrameList lastUsed[index] = time

time += 1

return pageFaults

OUTPUT:

eddie@eddie-pcmasterrace:~/workplace/cs480/programming/four$ ls Makefile Readme testvm.c vmalgorithm.c vmalgorithm.h eddie@eddie-pcmasterrace:~/workplace/cs480/programming/four$ make cc -c -o testvm.o testvm.c testvm.c: In function ‘main’: testvm.c:35:4: warning: implicit declaration of function ‘initializePageFrame’ [-Wimplicit-function-declaration] 35 | initializePageFrame(); | ^~~~~~~~~~~~~~~~~~~ testvm.c:44:4: warning: implicit declaration of function ‘printAccessPattern’ [-Wimplicit-function-declaration] 44 | printAccessPattern(); // print the access pattern again ... | ^~~~~~~~~~~~~~~~~~ cc -c -o vmalgorithm.o vmalgorithm.c vmalgorithm.c: In function ‘generateAccessPattern’: vmalgorithm.c:18:11: warning: implicit declaration of function ‘time’ [-Wimplicit-function-declaration] 18 | srand(time(0)); | ^~~~ gcc testvm.o vmalgorithm.o -o testvm eddie@eddie-pcmasterrace:~/workplace/cs480/programming/four$ ./testvm 7 3 Running program using FIFO algorithm ... ... 5 -1 -1 5 2 -1 5 2 -1 5 2 0 4 2 0 4 6 0 4 6 0 4 6 0 4 6 1 3 6 1 3 4 1 3 4 5 0 4 5 0 4 5 0 4 5 0 6 5 0 6 2 0 6 2 0 6 2 1 6 2 Page Faults of FIFO: 13 page fault of FIFO: 13

The Same Access Pattern: 5 2 2 0 4 6 4 4 1 3 4 5 0 4 5 6 2 0 0 1 Running program using LRU algorithm ... ... 5 -1 -1 5 2 -1 5 2 -1 0 2 -1 0 4 -1 0 4 6 0 4 6 0 4 6 0 4 1 3 4 1 3 4 1 3 4 5 0 4 5 0 4 5 0 4 5 6 4 5 6 2 5 6 2 0 6 2 0 6 1 0 Page Faults of LRU: 13 page fault of LRU: 13 eddie@eddie-pcmasterrace:~/workplace/cs480/programming/four$

Cheat Sheet

Terminal Commands Reference

To Connect, and pull from Edoras:

YKRw973o

ssh cssc 1710@edoras.sdsu.edu

ssh in with your account

Passwd:

After you login you can run finger $USER to check

check ls

Go to shared folder, find the folder labeled in the project requirements & copy the project files over to your programming file.

$: cd /home/cs/zhengli/cs480-02

$: ls

data.zip zero.zip

$: cp *.zip /home/cs/zhengli/cssc1710/programming

$: cd /home/cs/zhengli/cssc1710/programming

$: ls

data.zip zero.zip

For local pull of the project files:

$: scp cssc1710@edoras.sdsu.edu:/home/cs/zhengli/cssc1710/localpull/project.tar.gz ./

$: tar -xzvf project.tar.gz

$: unzip data.zip, zero.zip

$: rm project.tar.gz

Submission of project back to edoras:

$: zip -r project.zip programming

$: scp /home/eddie/workplace/cs480/prelimproj.zip cssc1710@edoras.sdsu.edu:~/programming

⁠

make testalphabet

Generate testalphabet executable

make testspecial

Generate testspecial executable

./testalphabet

./testspecial

script test.log

record test log to test.log file

exit

exit the recording to the log file

⁠

Want to print your doc?
This is not the way.

Try clicking the ⋯ next to your doc name or using a keyboard shortcut (

CtrlP

) instead.