Skip to main content

Page Replacement Algorithm

Image
By



    Brief Description
   
        The basic idea of Page Replacement is; if there is a free page in the memory then use it. If there is no free page available, then we select one victim page which we would swap out of the virtual memory to the disk. Then we read the desired page to the new free frame. The page tables are then updated and the process is restarted. The main objective of a good replacement algorithm is to achieve a low page fault rate. For that we need to insure that the heavily used pages stay in the memory, and the replaced page should not be needed for some time. Secondly, we need to reduce the latency of a page fault. That can be assured by writing an efficient code, and replace the pages that do not need to be written out.

    Flow Chart

Flow Chart
   

    Algorithm Implementation
       
  • FIFO
        This Page Replacement Algorithm treats the page frames allocated to a process as a circular buffer:

        1. when the buffer is full, the oldest page is replaced. Hence First-in
First-out.
         2. we require only one pointer, that circles through the page frames of the process.

The OS keeps the tracks of all the pages in memory in a queue, with most recent arrival at the back, and the oldest arrival in the front. When a page needs to be replaced, the page at the front of the queue(oldest) is selected.


FIFO Page Fault Table
       
    Code:

    
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <windows.h>
#include <conio.h>
#include <time.h>
#define SIZE 3

int fullframe = 0; //check all frames
int input[21]; //input of reference string
int frame[SIZE];
int rep_point = 0; //replaced page Pointer
int count = 0; //page faults counter

int display() //Display Frames
{
int i;
printf("\nThe elements in the frame are\n");
for (i = 0; i < fullframe; i++)
printf("%d\n", frame[i]);
}

int page_rep(int ele) //Returns the victim page
{
int temp;
temp = frame[rep_point];
frame[rep_point] = ele;
rep_point++;
if (rep_point == SIZE)
rep_point = 0;

return temp;
}

int page_fault(int ele) //for checking if fault was there or not
{
if (fullframe != SIZE)
frame[fullframe++] = ele;
else
printf("The page replaced is %d", page_rep(ele));
}

int search(int ele) //search the element in a frame
{
int i, flag;
flag = 0;
if (fullframe != 0)
{
for (i = 0; i < fullframe; i++)
if (ele == frame[i])
{
flag = 1;
break;
}
}
return flag;
}

int main()
{
int n, i;
FILE *out;
out = fopen("pages.in", "r");
printf("The number of page requested are:");
fscanf(out, "%d", &n);
printf("%d", n);
for (i = 0; i < n; i++)
fscanf(out, "%d", &input[i]);
fclose(out);
printf("\nThe pages present in the requested string are\n");
for (i = 0; i < n; i++)
printf("%d ", input[i]);
printf("\n\n");
for (i = 0; i < n; i++)
{
if (search(input[i]) != 1)
{
page_fault(input[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n", count);
return 0;
}
 
  Results:

C Program Output(FIFO)
     
  • LFU
        In this Page Replacement Algorithm, we assign a counter to every page. All the counters are initialized by 0. Each time a reference is made to that page, the counter value is incremented by one. When the cache reaches the capacity, and a request for a page that is not present in the memory is made, the system will search for the page with the least number of references (counter value) and replace it from the cache.

    Code:
    
   
#include <stdio.h>
#define SIZE 3
int fullframe = 0; //check all frames
int input[21], n; //input of reference string
int frame[SIZE];
int ctr[SIZE] = {
0};

int rep_point; //replaced page Pointer
int count = 0;
int display()
{
int i;
printf("\nThe elements in the frame are\n");
for (i = 0; i < fullframe; i++)
printf("%d\n", frame[i]);
}
int Longestopt()
{ //The page with least frequency is selected as victim
int i, min;
min = 0;
for (i = 0; i < SIZE; i++)
if (ctr[min] > ctr[i])
min = i;

rep_point = min;
return rep_point;
}
int page_rep(int ele)
{
int temp;
rep_point = Longestopt();
temp = frame[rep_point];
frame[rep_point] = ele;
ctr[rep_point] = 1; //page bought , counter set to 1

return temp;
}
int page_fault(int ele)
{
if (fullframe != SIZE)
{
ctr[fullframe]++; //The counters of frame increase initially till they
    are full
frame[fullframe++] = ele;
}
else
printf("The page replaced is %d", page_rep(ele));
}
int search(int ele)
{
int i, flag;
flag = 0;
if (fullframe != 0)
{
for (i = 0; i < fullframe; i++)
if (ele == frame[i])
{
flag = 1;
ctr[i]++;
break;
}
}
return flag;
}
int main()
{
int i;
FILE *out;
out = fopen("pages.in", "r");
printf("The number of page request are:");
fscanf(out, "%d", &n);
printf("%d", n);
for (i = 0; i < n; i++)
fscanf(out, "%d", &input[i]);
printf("\nThe pages present in the requested string are\n");
for (i = 0; i < n; i++)
printf("%d ", input[i]);
printf("\n\n");
for (i = 0; i < n; i++)
{
if (search(input[i]) != 1)
{
page_fault(input[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n", count);
getche();
return 0;
}

    Results:

C Program Output(LFU)

 
    • LRU
    Every page entry has a counter.Every time a page is
referenced, increment a global counter and store it in the
page counter.For replacement, search the page with the lowest
counter value and replace it.

    • LRU Stack
    Maintain a stack of page numbers in a doubly linked list.
When a reference to a page is made, move it to the top of the
stack.For replacement, choose the bottom page.

    • LRU Counter
    Every page entry has a counter. Every time a page is
referenced, increment a global counter and store For
replace it.replacement, search the page with the lowest
counter value and replace it.

Step of LRU

    LRU-Counter Code:
   
#include <stdio.h>
#define SIZE 3
int fullframe = 0; //check all frames
int input[21], n; //input of reference string
int frame[SIZE];
int ctr[SIZE] = {
0};
static int f = 0;
int rep_point; //replaced page Pointer
int count = 0; //page faults counter
int display()
{ //Display Frames
int i;
printf("\nThe elements in the frame are\n");
for (i = 0; i < fullframe; i++)
printf("%d\n", frame[i]);
}
int Longestopt() //Fucntion for discovering the LRU page using
their corresponding counter values
{
int i, min;
min = 0;
for (i = 0; i < SIZE; i++)
if (ctr[min] > ctr[i])
min = i;

rep_point = min;
return rep_point;
}
int page_rep(int ele)
{ //page replacement
int temp;
rep_point = Longestopt();
temp = frame[rep_point];
frame[rep_point] = ele;
ctr[rep_point] = f;

return temp;
}
int page_fault(int ele)
{ //page fault
if (fullframe != SIZE)
{
ctr[fullframe] = f;
frame[fullframe++] = ele;
}
else
printf("The page replaced is %d", page_rep(ele));
}
int search(int ele)
{
int i, flag;
flag = 0;
if (fullframe != 0)
{
for (i = 0; i < fullframe; i++)
if (ele == frame[i])
{
flag = 1;
ctr[i] = f;
break;
}
}
return flag;
}
int main()
{
int i;
FILE *out;
out = fopen("pages.in", "r");
printf("The number of page request are:");
fscanf(out, "%d", &n);
printf("%d", n);
for (i = 0; i < n; i++)
fscanf(out, "%d", &input[i]);
printf("\nThe pages present in the frame are\n");
for (i = 0; i < n; i++)
printf("%d ", input[i]);
printf("\n\n");
for (i = 0; i < n; i++)
{
f++;
if (search(input[i]) != 1)
{
page_fault(input[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n", count);
getche();
return 0;
}

    Results :
    
C Program Output(LRU-CTR)
 

    LRU-Stack Code:

   
#include <stdio.h>
#define SIZE 3
int fullframe = 0; //check all frames
int input[21], n; //input of reference string
int frame[SIZE];
int stk[SIZE]; //Stack for storing the page numbers as per their
reference criteria

int rep_point; //replaced page Pointer
int count = 0; //page faults counter
int display()
{ //display Frame
int i;
printf("\nThe elements in the frame are\n");
for (i = 0; i < fullframe; i++)
printf("%d\n", stk[i]);
}
int LRstackopt(int p)
{
int temp;
int i;
for (i = 0; i < n; i++)
if (stk[i] == p)
break;
temp = stk[i];
while (i != SIZE - 1) //Moving the elements thus TOP is empty
{
stk[i] = stk[i + 1];
i++;
}
stk[i] = temp; //Storing the element to TOP from temp
}
int page_rep(int ele)
{ //page replacement
int temp;

rep_point = stk[0]; //victim page is selected as the 1st element
of the stack

temp = frame[rep_point];
frame[rep_point] = ele;
LRstackopt(rep_point);

return temp;
}
int page_fault(int ele)
{ //page fault
if (fullframe != SIZE)
{
stk[fullframe] = fullframe;
frame[fullframe++] = ele;
}
else
printf("The page replaced is %d", page_rep(ele));
}
int search(int ele)
{
int i, flag;
flag = 0;
if (fullframe != 0)
{
for (i = 0; i < fullframe; i++)
if (ele == frame[i])
{
flag = 1;
LRstackopt(i);
break;
}
}
return flag;
}
int main()
{
int i;
FILE *out;
out = fopen("pages.in", "r");
printf("The number of page request are:");
fscanf(out, "%d", &n);
printf("%d", n);
for (i = 0; i < n; i++)
fscanf(out, "%d", &input[i]);
printf("\nThe pages present in the requested string are\n");
for (i = 0; i < n; i++)
printf("%d ", input[i]);
printf("\n\n");
for (i = 0; i < n; i++)
{
if (search(input[i]) != 1)
{
page_fault(input[i]);

count++;
}
display();
}
printf("\nThe number of page faults are %d\n", count);
getche();
return 0;
}

    Results:
C Program Output(LRU-STK)
   
    • MFU
    In this Page Replacement Algorithm, we assign a counter to
every page. All the counters are initialized by 0. Each time a
reference is made to that page, the counter value is
incremented by one. When the cache reaches the capacity, and a
request for a page that is not present in the memory is made,
the system will search for the page with the most number of
references (counter value) and replace it from the cache.

Page Fault = 10

    Code:
   
#include <stdio.h>
#define SIZE 3
int fullframe = 0; //check all frames
int input[21], n; //input of reference string
int frame[SIZE];
int ctr[SIZE] = {
0};
static int f;
int rep_point; //replaced page Pointer
int count = 0; //page faults counter
int display()
{
int i;
printf("\nThe elements in the frame are\n");
for (i = 0; i < fullframe; i++)
printf("%d\n", frame[i]);
}
int Longestopt()
{
int i, max;
max = 0;
for (i = 0; i < SIZE; i++) //maximum frequency page is selected
if (ctr[max] < ctr[i])
max = i;

rep_point = max;
return rep_point;
}
int page_rep(int ele)
{
int temp;
rep_point = Longestopt();
temp = frame[rep_point];
frame[rep_point] = ele;
ctr[rep_point] = 1;

return temp;
}
int page_fault(int ele)
{
if (fullframe != SIZE)
{
ctr[fullframe]++;
frame[fullframe++] = ele;
}
else
printf("The page replaced is %d", page_rep(ele));
}
int search(int ele)
{
int i, flag;
flag = 0;
if (fullframe != 0)
{
for (i = 0; i < fullframe; i++)
if (ele == frame[i])
{
flag = 1;
ctr[i]++;
break;
}
}
return flag;
}
int main()
{
int i;
FILE *out;
out = fopen("pages.in", "r");
printf("The number of page request are:");
fscanf(out, "%d", &n);
printf("%d", n);
for (i = 0; i < n; i++)
fscanf(out, "%d", &input[i]);
printf("\nThe pages present in the requested string are\n");
for (i = 0; i < n; i++)
printf("%d ", input[i]);
printf("\n\n");
for (i = 0; i < n; i++)
{
f = i;
if (search(input[i]) != 1)
{
page_fault(input[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n", count);
getche();
return 0;
}

    Results:
C Program Output(MFU)
 
  • OPT
    An optimal page-replacement algorithm has the lowest
page-fault rate.Replace the page that has not been referenced
for the longest period of time.

OPT
   
  Code:
   
#include <stdio.h>
#define SIZE 3
int fullframe = 0; //check all frames
int input[21], n; //To take the input
int frame[SIZE];
static int f = 0;
int rep_point; //replaced page Pointer
int count = 0; //page faults counter
//Display Frames
int display()
{
int i;
printf("\nThe elements in the frame are\n");
for (i = 0; i < fullframe; i++)
printf("%d\n", frame[i]);
}
//Returning the replacement pointer with the value of victim page
int Longestopt()
{
int temp[SIZE] = {
0}; //checking the occurence of nearest possible future pages,Assumming
zero page is nearest in the beginning
int c = 0;
int id, i, k, j = SIZE;
id = 0;

for (i = f + 1; i < n; i++) //Checking from the current time of use till
the end of string for future references
{
for (k = 0; k < j; k++) //page occurs in future or not
{
if (input[i] == frame[k])
{
if (temp[k] != 1)
{
temp[k] = 1;
c++;
}

break;
}
}

if (c == 2) //Once we get two future pages then break
break;
}

id = 2;
while (id != 0)
{
if (temp[id] == 0) //the page which is not the nearest future reference then break
break;
id--;
}

rep_point = id;
return rep_point;
}
int page_rep(int ele)
{
int temp;
rep_point = Longestopt();
temp = frame[rep_point];
frame[rep_point] = ele;

return temp;
}
int page_fault(int ele)
{
if (fullframe != SIZE)
frame[fullframe++] = ele;
else
printf("The page replaced is %d", page_rep(ele));
}
int search(int ele)
{
int i, flag;
flag = 0;
if (fullframe != 0)
{
for (i = 0; i < fullframe; i++)
if (ele == frame[i])
{
flag = 1;
break;
}
}
return flag;
}
int main()
{
int i;
FILE *out;
out = fopen("pages.in", "r");
printf("The number of page request are:");
fscanf(out, "%d", &n);
printf("%d", n);
for (i = 0; i < n; i++)
fscanf(out, "%d", &input[i]);
printf("\nThe pages present in the requested string are\n");
for (i = 0; i < n; i++)
printf("%d ", input[i]);
printf("\n\n");
for (i = 0; i < n; i++)
{
f = i;
if (search(input[i]) != 1)
{
page_fault(input[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n", count);
getche();
return 0;
}

    Results:
   
C Program Output(OPT)

    Second Chance:
    This algorithm is a FIFO replacement algorithm with a small
modification that causes it to approximate to LRU.When a page
is selected according to FIFO order, we check its reference
bit.If it is set (the page was referenced), we clear it and
look for another page.

Second Chance


    Code:

#include <stdio.h>
#define SIZE 3
int fullframe = 0; //check all frames are filled
int input[21]; //To take the input
int ref[SIZE]; //This is for reference bits for each frame
int frame[SIZE];
int ret_point = 0; //replaced page Pointer
int count = 0; //page faults counter
int display()
{
int i;
printf("\nThe elements in the frame are\n");
for (i = 0; i < fullframe; i++)
printf("%d\n", frame[i]);
}
int page_rep(int ele)
{
int temp;
while (ref[ret_point] != 0)
{
ref[ret_point++] = 0;
if (ret_point == SIZE)
ret_point = 0;
}
temp = frame[ret_point];
frame[ret_point] = ele;
ref[ret_point] = 1;

return temp;
}
int page_fault(int ele)
{
if (fullframe != SIZE)
{
ref[fullframe] = 1; //refrence bits = 1 as each frame is being filled firstly
frame[fullframe++] = ele;
}
else
printf("The page replaced is %d", page_rep(ele));
}
int search(int ele)
{
int i, flag;
flag = 0;
if (fullframe != 0)
{
for (i = 0; i < fullframe; i++)
if (ele == frame[i])
{
flag = 1;
ref[i] = 1; //When page reference occurs, it's rference bit = 1
break;
}
}
return flag;
}
int main()
{
int n, i;
FILE *out;
out = fopen("pages.in", "r");
printf("The number of page request are:");
fscanf(out, "%d", &n);
printf("%d", n);
for (i = 0; i < n; i++)
fscanf(out, "%d", &input[i]);
printf("\nThe pages present in the requested string are\n");
for (i = 0; i < n; i++)
printf("%d ", input[i]);
printf("\n\n");
for (i = 0; i < n; i++)
{
if (search(input[i]) != 1)
{
page_fault(input[i]);
display();
count++;
}
}
printf("\nThe number of page faults are %d\n", count);
getche();
return 0;
}

    Results:
C Program Output(Second Chance)
       

    Technical Specification:
    1. Code Language – C and Python 2.7
    2. Code compatibility – UNIX and Windows
    3. Input – Randomly generated page numbers using Python
    4. Output – Number of page faults and intermediate pages in frame
    5. Data structures used – Stack, Array, Linked list


    Analysis of most used Algorithm:
    A table with number of page faults, for each algorithm, with page frame size 2, 3 and 4 is generated as shown in table 1. With 2 page frames, FIFO generates 11 page faults, LRU generates 11 page faults and Optimal generates 8 page faults. Similarly with 3 page frames, FIFO generates 9 page faults, LRU generates 9 page faults and Optimal generates 6 page faults. With 4 page frames, FIFO generates 5 page faults, LRU generates 6 page faults and Optimal generates 5 page faults.

Analysis Table

Bar Chart View


Reference:

[1] Operating System internals and Design Principles, 7th ed. Pearson
[2] ”LRU Implementations”, Cs.jhu.edu, 2016. [Online]. Available:
http://www.cs.jhu.edu/~yairamir/cs418/os6/tsld021.htm.
[Accessed : 07 − Dec − 2016].
[3] ”Operating System - Virtual Memory”, www.tutorialspoint.com,
2016. [Online]. Available: https://www.tutorialspoint.com/
operating_system/os_virtual_memory.htm.
[Accessed : 07 − Dec − 2016].
[4] ”Operating Systems”, Www2.cs.uregina.ca, 2016. [Online]. Available:
http://www2.cs.uregina.ca/~hamilton/courses/330/notes/
memory/page_replacement.html. [Accessed : 07 − Dec − 2016].
[5] ”Page replacement algorithm”, En.wikipedia.org, 2016. [Online].
Available:
https://en.wikipedia.org/wiki/Page_replacement_algorithm.
[Accessed : 07 − Dec − 2016].
[6] ”What’s the difference between clock and Second chance
page-replacement algorithm?,” 2016. [Online]. Available:
http://cs.stackexchange.com/questions/29092/
whats-the-difference-between-clock-and-second-\
chance-page-replacement-algorithm. Accessed: Dec. 7, 2016.
[7] ”Page Replacement Algorithm”, http://www.cs.utexas.edu/users/
witchel/372/lectures/16.PageReplacementAlgos.pdf, 2016.
[8] Optimal (OPT) Page replacement Algorithm,http:
//faculty.salina.k-state.edu/tim/ossg/_images/optimal.png
2016.
[9] Most Frequently Used(MFU) Page replacement Algorithm, http:
//images.slideplayer.com/20/6026617/slides/slide_56.jpg
2016.


 


Labels:

Comments

  1. UnknownMay 18, 2020 at 10:35 AM

    Oooh wow this webpage information is well organised and useful for me, keep it up

    ReplyDelete

Post a Comment

Thanks

Popular posts from this blog

Emotional and Psychological Trauma

By
What is Emotional and psychological trauma ? Emotional and psychological trauma is any stressful event that occurs in a lifetime that makes you struggle with your emotions, memory,different activities and make you feel helpless and hopeless in this ruthless world. The event may not be objectively scaled it is a subjective sensation about a event and every individual respond differently to the event . For example a death in a family due to accident due to an pothole makes one dad react positively and he goes on to correct every pothole of the city and some other may react it negatively Emotional and psychological trauma can be caused by: In Indian scenarios emotional and psychological trauma can be caused by accident,disasters, sexual assault that may have occurred at any course of life Ongoing family issues, neighbourhood problems , continues rejection from various interviews , household violence , neglect, low performance at school or institution, contin
15 comments
Read more

Office of the Personnel Management (OPM) Data Breach: A Case Study

By
WHAT HAPPENED IN THE OPM DATA BREACH      As the relationship between humanity and technology develops, an emergent area of concern lies in the security of the information ferried over and handled by this technology. A myriad of information security and data breaches reported upon by news media in the recent past has had the simultaneously fortunate and unfortunate effect of bringing information and network security into the public consciousness. One such incident was the United States (US) Office of the Personnel Management (OPM) data breach.      While there are many aspects of the OPM data breach that are notable, chief among them is that the perpetrator of this data breach has been widely attributed to China. As China increases its economic clout and develops its technological capabilities, its international presence is becoming more and more pronounced—and not always in the best light. Sanger (2018) has noted that by 2009, Google executives had noticed state-sponsored
5 comments
Read more

Are You Prepared Against Cyber Threats?

By
What is the worth of information Security in 21 st century? Imagine small or medium scale business having around 2500-4000 employees working. What if there is a data bridge of small or medium scale compony? Information carries by Venture are employees’ names, Address, Banking Forms, Tax forms which also includes Social incurrence Number and their dependents names and supporting information which may be sell or used for personal blackmails by intruders which was kind of storyline of Scotty’s Holdings data bridge [1] . Main base of this data bridge was email phishing which were send to all over compony employee pretending to be CEO. Which contains Employer identification number (EIN), Employer’s name, address, and ZIP code, Wages, tips, other compensation and many more fields. But it’s not the first or last compony to be a part of Email phishing Attack. Main purpose of Email Phishing scams is stealing banking credentials or any other form of credentials. Preventions Employer and Emp
24 comments
Read more