lOMoARcPSD|47050196
Index
Sr.no Name
1 Aim
2 Course Outcome Address
3 Proposed Methodology
4 Literature Review
Resource Required
5
6 Output of the Micro project
7 Skill Developed/Learning Outcomes
8 Application
Downloaded by Sachin boy (sachinboy9999@gmail.com)
lOMoARcPSD|47050196
Annexure II
Micro-Project Report
“Make a comparative statement to calculate page fault for a given page
reference string by using different page replacement algorithms.”
1.0 Aim of Micro-Project –
Make a comparative statement to calculate page fault for a given page reference string
by using different page replacement algorithms.
2.0 Course Outcomes Addressed-
CI501.1 Operate3 & Install operating system and configure it.
CI501.2 Explain2 the use of operating system tools to perform various functions.
CI501.3 Execute3 process commands for performing process management operations.
CI501.4 Solve3 turnaround time and average waiting time of different scheduling algorithms.
CI501.5 Solve 3 efficiency of different memory management techniques and Use of file
management techniques.
3.0 Proposed Methodology –
1. Gathered the necessary data for the selected project related to page fault calculations
using various page replacement algorithms.
2. Analysed the collected data and formulated the design for the comparative study on
page fault calculations.
3. Studied and applied various syntax and functions in the context of the selected
operating system environment.
4. Created an interactive user interface for the comparative analysis of page fault
calculations using different page replacement algorithms.
5. Implemented object-oriented programming concepts within the application to enhance
code modularity and maintainability.
6. Chose different page replacement algorithms and their respective event handling
mechanisms to design the application effectively.
7. Established connections between the application's user interface and the simulated
operating system's page replacement subsystem.
Downloaded by Sachin boy (sachinboy9999@gmail.com)
lOMoARcPSD|47050196
8. Developed the core algorithms and code logic to simulate page fault occurrences using
different page replacement algorithms.
9. Generated code to meet the specific criteria outlined for the comparative study
10. Compiled a comprehensive final report summarizing the project's objectives,
methodology, results, and conclusions regarding page fault calculations with varying
page replacement algorithms in the selected operating system environment.
4.0 Literature Review –
"Numerous studies in the field of operating systems have extensively evaluated and
compared various page replacement algorithms, including FIFO (First-In-First-Out), LRU (Least
Recently Used), LFU (Least Frequently Used), and optimal algorithms. These evaluations
typically involve analyzing their performance in terms of minimizing page faults when faced
with different types of page reference strings. While FIFO is simple to implement, it often
performs poorly on realistic workloads due to the lack of adaptability. LRU, on the other hand,
exhibits better performance by evicting the least recently used page, but its high computational
overhead may limit its practicality. LFU prioritizes pages based on their usage frequency but
may struggle with changing access patterns. Optimal, though theoretical, serves as a benchmark
for optimal page replacement but is impractical to implement in real systems. Researchers have
developed hybrid and adaptive approaches as well, seeking to strike a balance between simplicity
and performance. The choice of the most suitable page replacement algorithm depends on the
specific workload and system requirements, highlighting the ongoing relevance of this topic in
the realm of operating systems research."
5.0 Actual Methodology Followed –
First Phase: Identified the project's goals, objectives, and scope.
Second Phase: Analyzed the collected data to define the functional requirements of the project.
Third Phase: Developed an abstract or project overview that provides a concise introduction to
the project.
Fourth Phase: Created a step-by-step procedure that explains how the project works and its core
functionality.
Fifth Phase: Written the project's code following the defined procedures and functional
requirements.
Sixth Phase: Compiled a comprehensive project report that documents the entire project
lifecycle.
Seventh Phase: Demonstrated the functioning project to stakeholders or project evaluators.
Downloaded by Sachin boy (sachinboy9999@gmail.com)
lOMoARcPSD|47050196
5.0 Resource Required –
Sr. No. Name of Resource Specifications Quantity
1 Computer System Win 10 (7hGeneration i5,8GB RAM, 1
256GB HDD)
2 Operating System Linux(Ubuntu) 1
6.0 Output of Micro-project –
Part A - Introduction
Page Fault: A page fault happens when a running program accesses a memory page that is mapped into
the virtual address space but not loaded in physical memory. Since actual physical memory is much
smaller than virtual memory, page faults happen. In case of a page fault, Operating System might have
to replace one of the existing pages with the newly needed page. Different page replacement algorithms
suggest different ways to decide which page to replace. The target for all algorithms is to reduce the
number of page faults.
Page Replacement Algorithms
There are three types of Page Replacement Algorithms. They are:
• Optimal Page Replacement Algorithm
• First In First Out Page Replacement Algorithm
• Least Recently Used (LRU) Page Replacement Algorithm
Part B - Project Execution and Results
First in First out Page Replacement Algorithm:
This is the first basic algorithm of Page Replacement Algorithms. This algorithm is basically dependent
on the number of frames used. Then each frame takes up the certain page and tries to access it. When the
frames are filled then the actual problem starts. The fixed number of frames is filled up with the help of
first frames present. This concept is fulfilled with the help of Demand Paging
After filling up of the frames, the next page in the waiting queue tries to enter the frame. If the frame is
present then, no problem is occurred. Because of the page which is to be searched is already present in
the allocated frames.
If the page to be searched is found among the frames, then, this process is known as Page Hit.
If the page to be searched is not found among the frames, then, this process is known as Page Fault.
When Page Fault occurs this problem arises, then the First in First Out Page Replacement Algorithm
comes into picture.
The First in First Out (FIFO) Page Replacement Algorithm removes the Page in the frame which is
allotted long back. This means the useless page which is in the frame for a longer time is removed and
Downloaded by Sachin boy (sachinboy9999@gmail.com)
lOMoARcPSD|47050196
the new page which is in the ready queue and is ready to occupy the frame is allowed by the First in First
Out Page Replacement.
Example:
Consider the reference string 6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0 for a memory with three
frames and calculate number of page faults by using FIFO (First In First Out) Page replacement
algorithms.
Points to Remember
Page Not Found - - - > Page Fault
Page Found - - - > Page Hit
Reference String:
Number of Page Hits = 8
Number of Page Faults = 12
The Ratio of Page Hit to the Page Fault = 8 : 12 - - - > 2 : 3 - - - > 0.66
The Page Hit Percentage = 8 *100 / 20 = 40%
The Page Fault Percentage = 100 - Page Hit Percentage = 100 - 40 = 60%
Explanation: First, fill the frames with the initial pages. Then, after the frames are filled, we need to
create a space in the frames for the new page to occupy. So, with the help of First in First Out Page
Replacement Algorithm we remove the frame which contains the page is older among the pages. By
removing the older page, we give access for the new frame to occupy the empty space created by the First
in First out Page Replacement Algorithm.
-------------------------------------------------------------------------------------------------------------------------------
-------
Downloaded by Sachin boy (sachinboy9999@gmail.com)
lOMoARcPSD|47050196
Optimal Page Replacement Algorithm:
This is the second basic algorithm of Page Replacement Algorithms. This algorithm is basically
dependent on the number of frames used. Then each frame takes up the certain page and tries to access it.
When the frames are filled then the actual problem starts. The fixed number of frames is filled up with the
help of first frames present. This concept is fulfilled with the help of Demand Paging
After filling up of the frames, the next page in the waiting queue tries to enter the frame. If the frame is
present then, no problem is occurred. Because of the page which is to be searched is already present in
the allocated frames.
If the page to be searched is found among the frames, then, this process is known as Page Hit.
If the page to be searched is not found among the frames, then, this process is known as Page Fault.
When Page Fault occurs this problem arises, then the OPTIMAL Page Replacement Algorithm comes
into picture.
The OPTIMAL Page Replacement Algorithms works on a certain principle. The principle is:
Replace the Page which is not used in the Longest Dimension of time in future
This principle means that after all the frames are filled then, see the future pages which are to occupy the
frames. Go on checking for the pages which are already available in the frames. Choose the page which
is at last.
Example:
Consider the reference string 6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 4, 0 for a memory with three
frames and calculate number of page faults by using OPTIMAL Page replacement algorithms.
Points to Remember
Page Not Found - - - > Page Fault
Page Found - - - > Page Hit Reference String:
Number of Page Hits = 8
Downloaded by Sachin boy (sachinboy9999@gmail.com)
lOMoARcPSD|47050196
Number of Page Faults = 12
The Ratio of Page Hit to the Page Fault = 8 : 12 - - - > 2 : 3 - - - > 0.66
The Page Hit Percentage = 8 *100 / 20 = 40%
The Page Fault Percentage = 100 - Page Hit Percentage = 100 - 40 = 60%
Explanation:
First, fill the frames with the initial pages. Then, after the frames are filled we need to create a space in
the frames for the new page to occupy.
Here, we would fill the empty spaces with the pages we and the empty frames we have. The problem
occurs when there is no space for occupying of pages. We have already known that we would replace the
Page which is not used in the Longest Dimension of time in future.
There comes a question what if there is absence of page which is in the frame.
Suppose the Reference String is:
0, 2, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0
6, 1, 5 are in the frames occupying the frames.
Here, we can see that page number 5 is not present in the Reference String. But the number 5 is present
in the Frame. So, as the page number 5 is absent we remove it when required and other page can occupy
that position.
Least Recently Used (LRU) Replacement Algorithm:
This is the last basic algorithm of Page Replacement Algorithms. This algorithm is basically dependent
on the number of frames used. Then each frame takes up the certain page and tries to access it. When the
frames are filled then the actual problem starts. The fixed number of frames is filled up with the help of
first frames present. This concept is fulfilled with the help of Demand Paging
After filling up of the frames, the next page in the waiting queue tries to enter the frame. If the frame is
present then, no problem is occurred. Because of the page which is to be searched is already present in
the allocated frames.
If the page to be searched is found among the frames, then, this process is known as Page Hit.
Downloaded by Sachin boy (sachinboy9999@gmail.com)
lOMoARcPSD|47050196
If the page to be searched is not found among the frames, then, this process is known as Page Fault.
When Page Fault occurs this problem arises, then the Least Recently Used (LRU) Page Replacement
Algorithm comes into picture.
The Least Recently Used (LRU) Page Replacement Algorithms works on a certain principle. The
principle is:
Replace the page with the page which is less dimension of time recently used page in the past.
Example:
Suppose the Reference String is:
6, 1, 1, 2, 0, 3, 4, 6, 0
The pages with page numbers 6, 1, 2 are in the frames occupying the frames.
Now, we need to allot a space for the page numbered 0.
Now, we need to travel back into the past to check which page can be replaced.
6 is the oldest page which is available in the Frame.
So, replace 6 with the page numbered 0.
Let us understand this Least Recently Used (LRU) Page Replacement Algorithm working with the help
of an example.
Example:
Consider the reference string 6, 1, 1, 2, 0, 3, 4, 6, 0, 2, 1, 2, 1, 2, 0, 3, 2, 1, 2, 0 for a memory with three
frames and calculate number of page faults by using Least Recently Used (LRU) Page replacement
algorithms.
Points to Remember
Page Not Found - - - > Page Fault
Page Found - - - > Page Hit Reference String:
Downloaded by Sachin boy (sachinboy9999@gmail.com)
lOMoARcPSD|47050196
Number of Page Hits = 7
Number of Page Faults = 13
The Ratio of Page Hit to the Page Fault = 7 : 12 - - - > 0.5833 : 1
The Page Hit Percentage = 7 * 100 / 20 = 35%
The Page Fault Percentage = 100 - Page Hit Percentage = 100 - 35 = 65% Explanation:
First, fill the frames with the initial pages. Then, after the frames are filled, we need to create a space in
the frames for the new page to occupy.
Here, we would fill the empty spaces with the pages we and the empty frames we have. The problem
occurs when there is no space for occupying of pages. We have already known that we would replace the
Page which is not used in the Longest Dimension of time in past or can be said as the Page which is very
far away in the past.
Comparative Statement for Page Fault Calculation
Page Reference String: 1 2 3 4 1 2 5 1 2 3 4 5
Number of Pages in Memory: 3
Algorithm Page Faults
--------------------------------
FIFO X
LRU Y
Optimal Z
Where:
- X represents the number of page faults using the FIFO algorithm.
- Y represents the number of page faults using the LRU algorithm.
- Z represents the number of page faults using the Optimal algorithm.
Analysis:
- The FIFO algorithm incurred X page faults.
- The LRU algorithm incurred Y page faults.
- The Optimal algorithm incurred Z page faults.
Downloaded by Sachin boy (sachinboy9999@gmail.com)
lOMoARcPSD|47050196
7.0 Skill Developed/Learning Outcomes –
• Critical Thinking
• Leadership
• Active listening Skill
• Scheduling and Time Management
• Technical Skill
8.0 Applications –
Operating Systems: These algorithms are fundamental in managing physical memory
and ensuring efficient process execution.
Cache Management: In computer architecture, these algorithms are used to manage
cache memory for frequently accessed data.
File Systems: They play a crucial role in managing disk pages and optimizing file access.
Database Management Systems (DBMS): Page replacement algorithms are utilized for
managing buffer pools in DBMSs.
Web Browsers: Browsers employ these algorithms to manage web page caching for
faster browsing.
Virtual Memory Systems: These algorithms enable efficient use of virtual memory by
deciding which pages to load or swap out.
Network Routers: Some routers use these algorithms to manage packet buffers and
prioritize network traffic.
Ms.Borhade S.S
Subject Teacher
Downloaded by Sachin boy (sachinboy9999@gmail.com)
