Course outcomes addressed: Apply scheduling algorithm to calculate turnaround time and average waiting time
1.2 Actual Resources used:
Sr. no Name of Resources Specification Quantity Resources 1 Computer dell 1 System Processor: i5 core Ram: 20GB
2 Internet Websites: 1. www.tutorialspoint.co - m
3 Books Operating system concepts 2
4 Browser Chrome 1 5 Editor
1.3 Actual methodology:
1) Discussion with our subject teacher about micro project.
2) Selection of project name.
3) To collect basic information about the project.
4) Discussed with group members about requirements.
5) To divide work into group members.
6) To start actually working on a project with proper knowledge.
Page replacement algorithm in OS
In operating systems, memory management is an important aspect that determines the efficiency and performance of a system. As modern applications demand more memory than ever before, it’s essential to have effective strategies for managing memory, and one such strategy is page replacement algorithms.
What are page replacement algorithms?
In a virtual memory system, programs are divided into fixed-size blocks called pages. These pages are stored in the main memory (RAM) or in secondary storage (like a hard disk) as needed. However, since the physical memory is limited, the operating system needs to decide which pages to keep in RAM and which pages to replace when new pages need to be loaded. This is where page replacement algorithms come into play.
There are the three page replacement algorithums
1. FIFO (first-in-first-out).
2. LRU (least recently used).
3. OPR (Optimal page replacement).
OPR Optimal page replacement
The optimal algorithm replaces the page that will not be used for the longest time in the future. While this algorithm guarantees the minimum possible number of page faults, it’s often impractical due to its reliance on future knowledge. In particular, the OPT algorithm starts with a set of empty slots in the main memory and performs the following steps for each page request.
First, it checks if the requested page is already present in the main memory. If so, it detects a page hit and proceeds to the next page request. If the page is not found in the main memory, it triggers a page miss and checks if the main memory is full. When the main memory is not full, it loads the requested page into an empty slot and moves on to the next page request. If the main memory is full, it first makes room for the new page. To do so, it finds the page that will not be accessed for the longest period in the future. After that, it replaces the selected page with the newly requested page. This ensures that the main memory remains occupied by the most relevant and frequently accessed pages.
Initially, the memory is empty, and the OPT algorithm inserts page in the memory. It is a page miss: Advantage: Provides the best theoretical performance by replacing the page that will be used farthest in the future. Disadvantage: Often not implementable in practice since it requires knowledge of future memory access patterns.
First In First Out (FIFO): This is the simplest page replacement algorithm. In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced page in the front of the queue is selected for removal.
Example 1: Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3 page frames.Find the
number of page faults. Initially, all slots are empty, so when 1, 3, 0 came they are allocated to the empty slots —> 3 Page Faults. when 3 comes, it is already in memory so —> 0 Page Faults. Then 5 comes, it is not available in memory so it replaces the oldest page slot i.e 1. —>1 Page Fault. 6 comes, it is also not available in memory so it replaces the oldest page slot i.e 3 —>1 Page Fault. Finally, when 3 come it is not available so it replaces 0 1 page fault. Belady’s anomaly proves that it is possible to have more page faults when increasing the number of page frames while using the First in First Out (FIFO) page replacement algorithm. For example, if we consider reference strings 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4, and 3 slots, we get 9 total page faults, but if we increase slots to 4, we get 10-page faults Least Recently Used: In this algorithm, page will be replaced which is least recently used. Example-3: Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4 page frames. Find number of page faults. Initially, all slots are empty, so when 7 0 1 2 are allocated to the empty slots —> 4 Page faults 0 is already their so —> 0 Page fault. when 3 came it will take the place of 7 because it is least recently used —>1 Page fault 0 is already in memory so —> 0 Page fault. 4 will takes place of 1 —> 1 Page Fault Now for the further page reference string —> 0 Page fault because they are already available in the memory. Program:
#include <stdio.h> // Function to find the page that will be used farthest in the future int findOptimalPage(int pages[], int frame[], int n, int current) { int res = -1, farthest = current; for (int i = 0; i < n; i++) { int j; for (j = current; j < n; j++) { if (frame[i] == pages[j]) { if (j > farthest) { farthest = j; res = i; } break; } } if (j == n) return i; } return (res == -1) ? 0 : res; } // Function to simulate the optimal page replacement algorithm void optimalPageReplacement(int pages[], int n, int capacity) { int frame[capacity]; int pageFaults = 0; for (int i = 0; i < capacity; i++) { frame[i] = -1; } for (int i = 0; i < n; i++) { int page = pages[i]; int j; for (j = 0; j < capacity; j++) { if (frame[j] == page) { break; } } if (j == capacity) { int replace = findOptimalPage(pages, frame, n, i + 1); frame[replace] = page; pageFaults++; } } printf("Page Faults: %d\n", pageFaults); } 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 = 3; optimalPageReplacement(pages, n, capacity); return 0;
} 2.1 Skills developed:
1. Communication Skills. 2. Group Discussion. 3. Basic knowledge of java. . .
2.2 Conclusion:
In this article, we discussed the OPT algorithm that minimizes page faults in theory and is a benchmark for practical algorithms. We then use an illustrative example to explain how the OPT algorithm works. In the end, we discuss the potential advantages and disadvantages of the OPT algorithm.
