L-5.22: Page Replacement Introduction | FIFO Page Replacement algorithm | Operating System
Summary
TLDRThis script discusses the concept of virtual memory and page replacement algorithms, focusing on the First-In-First-Out (FIFO) method. It explains how virtual memory allows for more processes to be managed by swapping pages in and out of main memory, minimizing page faults and maximizing performance.
Takeaways
- π The concept of virtual memory allows for more processes to be accommodated in the main memory by not loading the entire process at once, but rather loading pages on demand.
- π Paging divides processes into pages and places them in the main memory's frames, while virtual memory manages the loading and unloading of these pages to optimize memory usage.
- π Virtual memory involves 'swiping in' and 'swiping out' pages from main memory as needed, which is the basis for page replacement algorithms.
- π€ The need for page replacement arises when the main memory is full and a new page needs to be loaded, necessitating the removal of an existing page.
- π οΈ Three common page replacement algorithms are discussed: First-In-First-Out (FIFO), Optimal Page Replacement, and Least Recently Used (LRU).
- π’ The script uses a reference string to demonstrate how page replacement works, particularly focusing on the FIFO algorithm.
- π The FIFO algorithm replaces pages starting with the one that was loaded first, regardless of whether it will be needed again soon.
- π« Page faults occur when a requested page is not found in the main memory, leading to a time-consuming fetch from the hard disk.
- π The goal of page replacement algorithms is to minimize page faults, as they significantly slow down the system due to the slow speed of the hard disk.
- π― The script illustrates the process of page replacement with an example, showing how pages are loaded into frames and when replacements occur based on demand.
- π The hit ratio and miss ratio (or page fault ratio) are calculated at the end of the script, providing a measure of the efficiency of the page replacement strategy used.
Q & A
What is the concept of paging in operating systems?
-Paging is a memory management technique where the operating system divides the process's memory into fixed-size blocks called pages and maps these pages to frames in the main memory. This allows for efficient memory utilization and the execution of processes that are larger than the available physical memory.
How does virtual memory differ from paging?
-Virtual memory is a broader concept that includes paging. It provides an illusion to the programmer that an unlimited amount of memory is available, while in reality, only a subset of the process's pages are kept in the main memory at any given time, with others being swapped in and out as needed.
What is the purpose of a page replacement algorithm?
-A page replacement algorithm is used to determine which page to remove from the main memory when it is full, and a new page needs to be loaded. The goal is to minimize page faults and optimize the use of the limited main memory.
What are the three common page replacement algorithms mentioned in the script?
-The three common page replacement algorithms mentioned are First-In-First-Out (FIFO), Optimal Page Replacement, and Least Recently Used (LRU).
How does the First-In-First-Out (FIFO) page replacement algorithm work?
-The FIFO algorithm works by maintaining a queue of pages in the main memory. When a new page needs to be loaded and there is no free space, the page that has been in the memory the longest (i.e., the first in the queue) is replaced with the new page.
What is a page fault in the context of page replacement algorithms?
-A page fault occurs when the CPU requests a page that is not currently in the main memory. This results in a delay as the system must fetch the page from secondary storage (like a hard disk) and load it into the main memory.
Why is minimizing page faults important in operating systems?
-Minimizing page faults is important because each page fault involves accessing the slower secondary storage, which can significantly increase the response time and decrease the overall performance of the system.
What is a page hit in the context of page replacement algorithms?
-A page hit occurs when the CPU requests a page that is already present in the main memory. This is a desirable event as it avoids the delay associated with a page fault.
How is the hit ratio calculated in page replacement algorithms?
-The hit ratio is calculated as the number of page hits divided by the total number of page references (requests) made by the CPU. It is expressed as a percentage to show the efficiency of the page replacement algorithm.
What is the significance of the miss ratio or page fault ratio in evaluating a page replacement algorithm?
-The miss ratio or page fault ratio indicates the frequency of page faults relative to the total number of page requests. A lower miss ratio suggests a more efficient page replacement algorithm, as it implies fewer page faults and thus better use of the main memory.
Outlines
π Introduction to Page Replacement Algorithms
This paragraph introduces the concept of page replacement algorithms in the context of virtual memory management. It explains the limitations of main memory and the necessity of swapping pages in and out to accommodate multiple processes. The paragraph outlines three common page replacement methods: First-In-First-Out (FIFO), Optimal Page Replacement, and Least Recently Used (LRU). The explanation emphasizes the importance of these algorithms in minimizing page faults, which occur when a demanded page is not found in the main memory, leading to delays due to disk access.
π The Working of First-In-First-Out (FIFO) Algorithm
The second paragraph delves into the specifics of the First-In-First-Out (FIFO) page replacement algorithm. It describes the process of servicing page faults by loading pages from the hard disk into the main memory. The paragraph illustrates how FIFO works by filling empty frames first and then replacing the oldest page with a new one when all frames are occupied. The summary includes an example with a reference string and explains the sequence of page faults and hits that occur as the CPU demands pages in a specific order.
π Analyzing Page Faults and Hits in FIFO
This paragraph continues the discussion on the FIFO algorithm, focusing on the analysis of page faults and hits. It explains the method of tracking page faults and hits as they occur and the importance of this tracking for calculating hit and miss ratios. The paragraph provides a step-by-step guide on how to identify page faults and hits, emphasizing the sequential replacement of frames when all are filled and a new page needs to be loaded. It concludes with an example calculation of the hit ratio and miss ratio based on the number of page hits and faults.
π Conclusion on FIFO Algorithm Efficiency
The final paragraph wraps up the discussion on the FIFO page replacement algorithm by summarizing the process and its implications for system performance. It highlights the simplicity of the FIFO method, which involves sequentially replacing frames regardless of the reference string's order. The paragraph concludes with a note on calculating the hit ratio, which is crucial for understanding the efficiency of the algorithm. It emphasizes that a higher hit ratio indicates better memory utilization and system performance.
Mindmap
Keywords
π‘Page Replacement Algorithm
π‘Paging
π‘Virtual Memory
π‘Page Fault
π‘Main Memory
π‘Reference String
π‘First In First Out (FIFO)
π‘Page Hit
π‘Page Miss
π‘Hit Ratio
Highlights
Introduction to the concept of paging and virtual memory, explaining how processes are divided into pages and managed in main memory.
Virtual memory allows for the illusion of accommodating more processes than the physical memory can handle.
The main memory's finite size necessitates the use of page replacement algorithms to manage memory efficiently.
Explanation of the page replacement concept, where old pages are removed to make space for new ones.
Introduction to three common page replacement algorithms: First-In-First-Out (FIFO), Optimal, and Least Recently Used (LRU).
Description of the process when there is enough space in the main memory for new pages.
The challenge of limited main memory size in handling large processes and a high number of processes.
The necessity of removing old pages to accommodate new ones in a full main memory.
Detailed explanation of the First-In-First-Out (FIFO) page replacement algorithm using a reference string.
How a page fault occurs when a demanded page is not found in the main memory.
The importance of minimizing page faults to improve performance, as they involve time-consuming disk operations.
Demonstration of how to handle a page fault by bringing a page from the hard disk into main memory.
The FIFO algorithm's method of replacing pages based on the order they were loaded into memory.
How to calculate the hit ratio and miss ratio to evaluate the efficiency of a page replacement algorithm.
Final summary of the FIFO algorithm, emphasizing the methodical frame-wise replacement process.
Transcripts
Page replacement algorithm
We have seen in the concept of paging that by dividing the processes in pages
we put them in the frames of main memory,
what does the concept of virtual memory say?
That we never bring the entire process inside the main memory
and not all the pages of a process
at the same time we try to keep in the main memory
no, Here we provide the reason to the programmer through virtual memory
that all the processes you have.
We can accommodate the maximum number of processes inside the main memory.
but actually how it is done
If we will keep the entire process in the main memory
So it may be that our main memory is completely finite.,
so my main memory will get filled with one or two processes.
So what do we do instead? Virtual memory
one or two pages, Each process brings one or two pages into the main memory.
which have demand.
When their need runs out, we swipe out those pages
and then swipe in fresh pages.
So this swipe in and swipe out funda we saw in virtual memory.
Now which page do we have to bring inside the main memory?
And when that page will come inside main memory
it is possible that the main memory is already filled,
all the frames are already filled in it.
So if I want to bring the new page inside the main memory
and get it accommodated,
So for that one page from the main memory
will have to be taken out from there
So that I can clear a frame over there
So what is my concept here?
of page replacement, Means
I am bringing a page to the main memory
If my main memory is full,
then I will remove the old page from there by swiping out
and make space on it and place the new page in that place.
So how to replace these pages?
There are three methods,
first is the first in first out,
optimal page replacement
and least recently used.
These three algorithms which are common and most of the time are used
to replace the page.
If there is a space in the main memory
then there is no problem
Then you can put the new page on that empty space.
But the problem is that the size of the processes are very big,
and the number of processes are very high
but the size of main memory is limited and it is finite.
So in order to bring more and more processes
What I have to do?
I have to remove old pages
and replace them with new pages
So how do we replace it?
let's start with first of all first in first out,
here I have one string
this is what? It is called a reference
reference string
reference string means
the CPU is demanding pages
Let's say the CPU is executing a process.
Executing any process
and we have divided that process into different pages
Now the CPU has sent a demand
that first I want page number 7
then one then 0, then 1, then 2 and again 0,
this is the sequence, means
this is the reference, it is in sequence
it is already in the order, here I have taken this sequence
now whenever the CPU is demanding, for what?
that is page number 7
then 0, then 1, then 2
and this is how it moves
and here I have three frames of the main memory
Means in this process, its pages
out of these three frames
can appear anywhere
Now if we see this in real time,
then in real time
pages of a process
we do not give the 5th number of frames
Meaning the number of frames can be more or less.
But Just for Solving the Example or Numerical
So that we can understand these three concepts very well.
So I fixed here
that for this process,
for the pages of this process
three frames have been given in the main memory
Frame 1, Frame 2, Frame 3
Now let's start with solving
how first-in-first-out works?
So here's what the CPU has demanded first
that is of page No.7
Means the CPU is saying that the byte
because the CPU does not even know that we have used any paging concept,
then the byte that the CPU has demanded
the byte that it is demanding, Where is that byte?
on page No. 7,
We converted the logical address and found out
that it is demanding for page number 7
When I saw page number 7 in the main memory,
it is neither in frame one nor in two nor in three,
that is, that page is not present anywhere
So if that page is nowhere then what do we call?
Page fault
We have already discussed this
whenever the CPU is looking for a page
and that page is absent in main memory
we call it page fault.
So whenever a page fault happens, we service it.
Means we bring it from the hard disk
and keep it in the main memory.
Although it is very time consuming
And one of the motives of the page replacement algorithm is
to minimize page faults.
Because whenever a page fault happens
My time is wasted because the hard disk gets involved.
and where hard disk is involved,
definitely hard disk is very slow
so obviously my time will increase
and performance will decrease.
So for this we would like to minimize the page fault.
but that is just numerical so we check how many page faults occur in it.
Or how many page hits occur,
when page number 7 comes, page number 7 is not here.
So that means what happened here
fault happened, then we called page number 7 from the hard disk
and let's say we put it in frame number 1.
Along with this, you should also mention here's what it actually is,
a page fault because the page you were looking for was not there
now it has arrived, now that page has arrived
Now page No. 0
Second of CPU is saying that I have demand for page number zero.
But even if you look carefully for zero, it is not there.
Zero also have to be brought
that is also called a page fault.
So here too there is a page fault
because zero page is also not present in main memory
so I will bring page number 0 from the hard disk
and place it in frame 2 of main memory.
Now there is no need to replace
do not replace this 7 because you already have vacant space.
So when the space is empty, fill that space first.
Why are you replacing it? The point of replacement will come
when the entire space is filled.
But still the slot was empty, so I put this 0 here,
You can start from the top also,
it is our own way of practice
I was used to practice this from beginning
I used to solve like this
I first placed 7 here then 0 in the second
now next frame came 1
sorry next is page number 1,
Now if you look carefully So page number one is also not there
So here again page fault is occurring
so I will bring page number one from the hard disk
and put it in the main memory.
So the three frames here are all filled up
and all of these three are page faults.
Next frame No. 2
Page No. 2
there is demand for page number 2
whether I have page number 2 first you have to check that.
That if page number 2 is there it is a hit, isn't it?
The page got hit, but if you look carefully,
the CPU is demanding page number 2,
but page number two is not here.
and here the space also ran out
Means we have three frames saved and all are full
then what will I do an old page will have to be replaced.
So what does FIFO do?
First in first out, means
the frame which was filled first
empty that frame first
Means what will I fill here in place of 7, 2
and rest as it is
rest as it is, means
means we brought 2 in place of 7,
and 0 and 1 as it is,
So what is this? This is also a page fault.
Because the page you were asking for is not present.
After that, if you look carefully,
Whose demand has come next? page number zero,
So is my page number zero present here?
You have to check here recently
as this is an updated report. You have to check it in the updated
Is page number zero there?
Yes, my page number zero is present.
So if page number zero is present then what is it called? Page hit,
Hit means?
The thing you were asking for is already present in main memory.
So we copy the hit case as it is.
Means copy it here as it is
if hit occurs
I also note here, Let me write,
that is called a hit
because the page you were demanding was found.
Next 3
Check if 3 is there or not? No, 3 is not there,
So I'll have to replace it.
Which frame was the first to be replaced according to First In First Out?
Which frame did we change? In frame one,
now which one has to be changed?
frame 2, means you have to remove frames one by one.
Will send this zero out of the frame.
and we'll bring 3 in place of that zero.
Means we will replace this zero with 3
keep the rest as it is.
And what is this too? Page fault
because the number three page was not present
We have brought it now.
Next 0,
Zero, page No. 0
Is page no. 0 there?
No it's not there.
Now again we have to do replacement
with whom we will replace now?
with frame No. 3
first of all frame No. 1
then replaced in 2
now in 3, you have to replace line-wise
so in frame no. 3 we replaced 1 with 0
we are in this frame
on this page No.
3, 2
and what is this?
This is miss or page fault.
because the page you were having demand for is not there.
after that we come on page No. 4
Is page No. 4 present there? No, it is not
Page No. 4 is not present, so what will we replace?
Frame 1, Why?
because first we replaced frame 1, then 2 then 3
now we have come back on frame No. 1
so we will replace 2 with 4
and rest write as it is
and this is also page fault, because
because page No. 4 was also not present
Next is 2,
Is 2 present?
No, 2 is not present
as 2 is not present so we will replace 3 with 2
and rest 2, 0, 4
because after frame 1, replacement will be in frame 2
Next 3,
Now we are on this page No.
Is page No. 3 there? No, it is not.
So again page fault occur here
What we will replace? Frame No .3
You just have to replace line-wise
After this comes page No. 0,
Page No. 0
Is Page No. 0 present? No it is not.
So we are again on frame No. 1
We replaced 4 with 0
2, 3
Again what I am having here? Miss
then after 0, I am having 3
Page No. 3
Is page No. 3 present?
Yes page No. 3 is already there.
So the page which CPU is demanding is present in main memory
This we call hit.
So when there is hit you don't have to do any changes
just copy previous one as it is.
and write here that it is a hit
then, page No. 1
Is page No. 1 present here?
No, page No. 1 is not present.
So, what will we replace?
this one, because we have already replaced frame No.1
now it's turn of frame 2
So in frame 2 we replace 2 with 1 and
keep rest as it is.
that is again called a miss.
or page fault
after that Page No. 2
Is page No. 2 present? No Page No. 2 is not present
So what do we replace now
3rd frame, replaced 3rd frame
put 2 in its place
and rest as it is.
That is again called a page fault.
After that came page No. 0,
Is page No. 0 present?
Yes page No. 0 is present.
So when it is present we call it hit,
So you copy it as it is.
That is called a hit.
So this is how we have to follow.
No matter how big this referencing is
you will not face any problem
because you have to follow a simple method
that you have to replace frame wise
first you have to replace frame 1
then 2, then 3
then again 1, 2 and 3
again 1, 2, 3
but when? when frames are already full
means all slots are filled
and the page which CPU is making demand
is not there.
means there is page fault.
So now you can check here how much hit I am having?
and how many page fault or miss are there.
We can call this page fault
or page miss.
and this is page hit.
So how many page hit came
1, 2, 3
That is called page hit.
and how many page fault came?
1, 2, 3, 4, 5, 6, 7
8, 9, 10, 11, 12
So 12 No. of page faults.
and how many hits 3
Many times you can be asked
What is the... all this question is given
at last it is asked what is the hit ratio?
or what is the miss ratio?
So if you want to find hit ratio or miss ratio first of all
find number of hits and number of miss
now I know if I have to find hit ratio
How will you find hit ratio?
number of hits divided by
total number of references
so the number of hits I am having is 3
number of hits are 3,
and the number of references 1, 2, 3
15
So 3 divided by 15
multiplied by 100
and what is the miss ratio or page fault ratio?
12 divide by 15
multiplied by 100
So this is the way how we can solve.
Solve it further
So 20% is the hit ratio
and if you solve this
definitely it will come 80 %
If hit ratio is 20 %
so what would be 100 - 20%
that would be miss 80%
This is how we can solve the question of
FIFO
first in first out, in which you
have to go frame wise just frame wise
don't worry about how reference came
just go on replacing frames one by one
in sequence
So this is all about first in first out
Thank You.
Browse More Related Video
L-5.19: Virtual Memory | Page fault | Significance of virtual memory | Operating System
But, what is Virtual Memory?
Sistemas Computacionais - Técnica de memória virtual: paginação e segmentação
L-5.9: What is Paging | Memory management | Operating System
What is Virtual Memory? What Does it Do?
L-5.8: Need of Paging | Memory Management | Operating System
5.0 / 5 (0 votes)