Summary: Implement a program that simulates maintaining a page table using three di?erent page replacement algorithms.
In this assignment you will write a program that simulates the contents of page table as memory requests are made. This starts with loading a reference string (a sequence of page numbers) which represents the pages being requested by a speci?c program. Whenever the program requests a page not already in a frame (i.e., not in physical memory), we say that a page fault occurs as the system must load the piece of data into a frame. Typically, there are many more pages (virtual memory) than frames (physical memory), meaning not every page can being loaded physical memory at the same time. At some point, the program will have a page fault but all frames are being used. This requires us to select a particular page for eviction to make space for a new page, and the selection is performed according to some page replacement algorithm.
This document is separated into four sections: Background, Requirements, Data File, and Submission. You have almost ?nished reading the Background section already. In Requirements, we will discuss what is expected of you in this homework. In Data File, we discuss the format of the simulation data.
Our goal is to write a program that simulates a page table. The page table is e?ectively an array of page entries, where each entry includes a frame number and some other metadata. The metadata includes a so-called valid/invalid bit, which indicates if a particular page is loaded into physical memory (i.e., it exists in some frame). Whenever a program tries to access a particular page (see Simulator.c which loads and uses a speci?c reference string), it informs the page table. The page table's job is to make sure pages are loaded when needed. Initially all pages have their valid bit set to zero to represent the fact that nothing is loaded. When a page is accessed, it is brought into memory. For our limited simulation, bringing something into memory only means setting it's valid bit to one to represent that it is loaded (we won't actually do anything). When there are unused frames, the page table will select the ?rst unused frame to use rather than use a page replacement algorithm. A page replacement algorithm is used to select which of the existing pages should be evicted from memory (i.e., have it's valid bit set to zero) when all frames are in use, so that a new page can be made to use the frame that the evicted page previously occupied. Your program must support three page replacement algorithms: First-in First-Out (FIFO), Least Recently Used (LRU), Most Frequently Used (MFU). Tie breaking for LRU and MFU should always select the lowest page number (e.g., for MFU, if both page 1 and 2 have the same frequency, replace page 1). Header ?les are provided.
Your job is implement a page table and these three page replacement algorithms. Requirements:
1. DataLoader.c: A ?le containing a set of functions to load a data ?le. (This is not a class.)
2. PageTable.c: A ?le containing a set of functions to simulate a page table.
You may add other helper functions as needed. The output for the sample data ?le is given below: see image.
2.1 Verbose Output
This should not be displayed, we only give it as a suggestion for how to do debugging. For the purposes of troubleshoting, we implemented a more complete output for the program when the verbose option is enabled (see below). This output shows the various pieces of data that each page entry contains. see image.
Your program is required to read in a text ?le which contains a description of a reference string that will be simulated. The ?rst line gives the number of pages for the system, the second gives the number of frames, and the third line lists the number of page requests (aka entries) in the reference string. After that, reference string entries are listed in sequence from 0 to the number indicated. All numbers are positive integers. A sample data ?le is attached to this assignment (not the one we will grade with) and an annotated version is shown below. You may assume that a reference string contains at most 512 entries.
4; number of pages. see canvas for the version of this file you need to support
3; number of frames
7; number of entries in reference string
0;0th page in reference string
1;1th page in reference string
2;...
3
3
1
0;6th page in reference string
DataLoader.h
#ifndef FILELOADER_H
#define FILELOADER_H
#include < stdio.h>
#include < stdlib.h>
//structs
struct test_scenario {
int refstr_len;
int refstr[512];
int page_count;
int frame_count;
};
/**
* Loads a test_scenario strut from a textfile.
*
* @param filename The name of the file to load.
* @return A struct containing the loaded file.
*/
struct test_scenario* load_test_data(char* filename);
#endif
PageTable.h
#ifndef PAGETABLE_H
#define PAGETABLE_H
#include < stdio.h>
#include < stdlib.h>
//enumeration to represent replacement algorithms.
enum replacement_algorithm {
FIFO=0,
LRU,
MFU
};
//forward declarations for structs
struct page_table_entry;
struct page_table;
/**
* Creates a new page table object. Returns a pointer to created page table.
*
* @param page_count Number of pages.
* @param frame_count Numbers of frames.
* @param algorithm Page replacement algorithm
* @param verbose Enables showing verbose table contents.
* @return A page table object.
*/
struct page_table* page_table_create(int page_count, int frame_count, enum replacement_algorithm algorithm, int verbose);
/**
* Destorys an existing page table object. Sets outside variable to NULL.
*
* @param pt A page table object.
*/
void page_table_destroy(struct page_table** pt);
/**
* Simulates an instruction accessing a particular page in the page table.
*
* @param pt A page table object.
* @param page The page being accessed.
*/
void page_table_access_page(struct page_table *pt, int page);
/**
* Displays page table replacement algorithm, number of page faults, and the
* current contents of the page table.
*
* @param pt A page table object.
*/
void page_table_display(struct page_table* pt);
/**
* Displays the current contents of the page table.
*
* @param pt A page table object.
*/
void page_table_display_contents(struct page_table *pt);
#endif
Simulator.c
#include < stdio.h>
#include < string.h>
#include "DataLoader.h"
#include "PageTable.h"
int main(int argc, char* argv[]) {
char* filename = argv[1];
struct test_scenario* data = load_test_data(filename);
struct page_table* pt_fifo = page_table_create(data->page_count, data->frame_count, FIFO, 0);
struct page_table* pt_lru = page_table_create(data->page_count, data->frame_count, LRU, 0);
struct page_table* pt_mfu = page_table_create(data->page_count, data->frame_count, MFU, 0);
//simulate page requests: fifo
for (int i = 0; i < data->refstr_len; i++) {
page_table_access_page(pt_fifo, data->refstr[i]);
//page_table_display_contents(pt_fifo);
}
page_table_display(pt_fifo);
//simulate page requests: lru
for (int i = 0; i < data->refstr_len; i++) {
page_table_access_page(pt_lru, data->refstr[i]);
//page_table_display_contents(pt_lru);
}
page_table_display(pt_lru);
//simulate page requests: mfu
for (int i = 0; i < data->refstr_len; i++) {
page_table_access_page(pt_mfu, data->refstr[i]);
//page_table_display_contents(pt_mfu);
}
page_table_display(pt_mfu);
page_table_destroy(&pt_fifo);
page_table_destroy(&pt_lru);
page_table_destroy(&pt_mfu);
free(data);
}
data1.txt
4
3
7
0
1
2
3
3
1
0