Program for Page Replacement Algorithms (LRU)

// LRU.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include "pch.h"
#include <iostream>
#include <unordered_map>
#include <unordered_set>
using namespace std;


int pageFaults(int pages[], int n, int capacity)
{

unordered_set<int> s;

unordered_map<int, int> indexes;

// Start from initial page
int page_faults = 0;
for (int i = 0; i < n; i++)
{
// Check if the set can hold more pages
if (s.size() < capacity)
{
// Insert it into set if not present
// already which represents page fault
if (s.find(pages[i]) == s.end())
{
s.insert(pages[i]);

// increment page fault
page_faults++;
}

// Store the recently used index of
// each page
indexes[pages[i]] = i;
}

// If the set is full then need to perform lru
// i.e. remove the least recently used page
// and insert the current page
else
{
// Check if current page is not already
// present in the set
if (s.find(pages[i]) == s.end())
{
// Find the least recently used pages
// that is present in the set
int lru = INT_MAX, val;
for (auto it = s.begin(); it != s.end(); it++)
{
if (indexes[*it] < lru)
{
lru = indexes[*it];
val = *it;
}
}

// Remove the indexes page
s.erase(val);

// insert the current page
s.insert(pages[i]);

// Increment page faults
page_faults++;
}

// Update the current page index
indexes[pages[i]] = i;
}
}

return page_faults;
}

// Main Function
int main()
{
int pages[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 };
int n = sizeof(pages) / sizeof(pages[0]);
int capacity = 4;
cout << pageFaults(pages, n, capacity);
return 0;
}

Comments

Post a Comment

Popular posts from this blog

Dynamic Memory allocation in C++ for 1d, 2d and 3d array

#include <iostream> #define N 10 // Dynamically Allocate Memory for 1D Array in C++ int main() { // dynamically allocate memory of size N int* A = new int[N]; // assign values to allocated memory for (int i = 0; i < N; i++) A[i] = i + 1; // print the 1D array for (int i = 0; i < N; i++) std::cout << A[i] << " "; // or *(A + i) // deallocate memory delete[] A; return 0; } //2-Dimentional Array. // using single pointer; #include <iostream> // M x N matrix #define M 4 #define N 5 // Dynamically Allocate Memory for 2D Array in C++ int main() { // dynamically allocate memory of size M*N int* A = new int[M * N]; // assign values to allocated memory for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) *(A + i*N + j) = rand() % 100; // print the 2D array for (int i = 0; i < M; i++) { for (int j = 0; j < N; j++) std::cout << *(A + i*N + j) << "
Read more

Write Your Own String Class:

class OwnString { private : char *string1 = NULL; int size; public: OwnString(void) { string1 = NULL; } OwnString(const char * strData) { size = strlen(strData); string1  = new char[size + 1]; int i = 0; while (*strData) { string1[i] = *strData; strData++; i++; } } OwnString & operator=(OwnString & obj) { if (this != &obj) { delete[]string1; size = obj.size; string1 = new char[size+1]; int i = 0; while (i<size+1) { string1[i] = obj.string1[i]; //strData++; i++; } } return *this; } OwnString (const OwnString & obj) { if (this != &obj) { delete[]string1; size = obj.size; string1 = new char[size + 1]; int i = 0; while (i < size + 1) { string1[i] = obj.string1[i]; //strData++; i++; } } } void print() { for (int i = 0; i < size; i++) { cout << string1[i]; }
Read more

Printing the odd and even no using Pthread

#include<iostream> #include <pthread.h> using namespace std; void *even(void * size) {             int x = reinterpret_cast<int> (size);         cout << "even no" <<endl;     for(int i = 0; i<x; i++)     {         if(i%2 == 0){                         cout << i << endl;         }             }     cout <<endl;     cout <<"even thread is terminited ";     cout <<endl; } void *odd(void *size ) {     pthread_t tid2;         int x = reinterpret_cast<int> (size);         cout << "odd no" <<endl ;     for(int i = 0; i<x; i++)     {         if(i%2 != 0){                         cout << i <<endl ;         }             }             pthread_create(&tid2, NULL, even, (void*)x);         cout <<endl;     pthread_join(tid2, NULL);         cout <<"odd thread is terminited ";     cout <<endl; } int main() {     int size;         cout <<
Read more