Question

Write a program that implements the FIFO and LRU page-replacement algorithms learned in class. First, generate a random page reference string where page numbers range from 0 to 9. Then, apply the random page-reference string to each algorithm, and record the number of page faults incurred by each algorithm. Implement the replacement algorithms so that the number of page frames can vary from 1 to 7. Assume demand paging is used.

Answer 1

Code implemented using C++ below

Step-by-step explanation:

sambswas

answered this

#include<iostream>

#include<cstdlib>

#define CYCLES 100

using namespace std;

struct page_table_entry {

int page_num;

int last_access_time;

int first_access_time;

};

int num_of_frames;

int sequence;

struct page_table_entry *page_table;

void init() {

page_table = new page_table_entry[num_of_frames];

for (int i = 0; i < num_of_frames; i++) {

page_table[i].page_num = -1;

page_table[i].first_access_time = -1;

page_table[i].last_access_time = -1;

}

sequence = 0;

}

int get_random_page() {

sequence++;

return rand() % 10;

}

int request_frame_LRU() {

for (int i = 0; i < num_of_frames; i++)

if (page_table[i].page_num == -1) {

cout << "Empty frame found at location " << i << endl;

return i;

}

int target = 0;

for (int i = 1; i < num_of_frames; i++)

if (page_table[i].last_access_time < page_table[target].last_access_time)

target = i;

cout << "target frame is " << target << ", containing page " << page_table[target].page_num << endl;

return target;

}

int request_frame_FIFO() {

for (int i = 0; i < num_of_frames; i++)

if (page_table[i].page_num == -1){

cout << "Empty frame found at location " << i << endl;

return i;

}

int target = 0;

for (int i = 1; i < num_of_frames; i++)

if (page_table[i].first_access_time < page_table[target].first_access_time)

target = i;

cout << "target frame is " << target << ", containing page " << page_table[target].page_num << endl;

return target;

}

int search_page(int page) {

for (int i = 0; i < num_of_frames; i++) {

if (page_table[i].page_num == -1)

continue;

if (page_table[i].page_num == page) {

cout << "page " << page << " found at location " << i << endl;

return i;

}

}

cout << "page " << page << " not found" << endl;

return -1;

}

void LRU() {

init();

int miss = 0;

int hit = 0;

for (int i = 0; i < CYCLES; i++) {

int page = get_random_page();

cout << "Requested page is: " << page << endl;

int location = search_page(page);

if (location > 0) {

page_table[location].last_access_time = sequence;

hit ++;

}

else {

location = request_frame_LRU();

page_table[location].page_num = page;

page_table[location].first_access_time = sequence;

page_table[location].last_access_time = sequence;

miss++;

}

cout << endl;

}

double hit_ratio = (double)hit/(hit+miss);

cout << "######## LRU ########" << endl;

cout << "hits: " << hit << endl;

cout << "misses: " << miss << endl;

cout << "hit ratio: " << hit_ratio << endl;

cout << "for frame size " << num_of_frames << endl;

cout << "#######################" << endl << endl;

}

void FIFO() {

init();

int miss = 0;

int hit = 0;

for (int i = 0; i < CYCLES; i++) {

int page = get_random_page();

cout << "Requested page is: " << page << endl;

int location = search_page(page);

if (location > 0) {

page_table[location].last_access_time = sequence;

hit ++;

}

else {

location = request_frame_FIFO();

page_table[location].page_num = page;

page_table[location].first_access_time = sequence;

page_table[location].last_access_time = sequence;

miss++;

}

cout << endl;

}

double hit_ratio = (double)hit/(hit+miss);

cout << "######## FIFO ########" << endl;

cout << "hits: " << hit << endl;

cout << "misses: " << miss << endl;

cout << "hit ratio: " << hit_ratio << endl;

cout << "for frame size " << num_of_frames << endl;

cout << "#######################" << endl << endl;

}

int main() {

srand(time(NULL));

num_of_frames = rand() % 7 + 1;

LRU();

FIFO();

}