Operating System
OS Part-1
OS Part-2
- File Concepts and Access methods
- Free Space Management and Allocation methods
- Directory Systems and Protection
- File Organization, Sharing and Implementation issues
- Disk and Drum Scheduling
- I/O Devices Organisation & I/O Buffering
- I/O Hardware, Kernel I/O subsystem and Transforming I/O Requests to Hardware Operations
- Device Drivers and Path Management
- Device Driver Sub Modules and Procedure
- Device Scheduler and Handler
- Interrupt Service Routine (ISR)
- File System in Linux and Windows
OS Part-3
- Process and Process Control Block(PCB)
- Process Scheduling( Preemptive and Non Preemptive)
- Scheduling Algorithms
- Algorithm Evaluation
- Multiple Processor Scheduling
- Real Time Scheduling
- Operations on Processes
- Threads
- Inter-Process Communication
- Precedence Graphs
- Critical Section Problem
- Semaphores
- Classical Problems of Synchronization
- DeadLock
- Deadlock Prevention and Avoidance
- Deadlock Detection and Recovery
- Process Management in Linux
OS Part-4
- Memory Hierarchy in OS
- Concepts of Memory Management
- MFT and MVT
- Logical and Physical Address Space
- Swapping
- Contiguous and Non Contiguous Memory Allocation
- Paging
- Segmentation
- Paging Combined with Segmentation
- Structure and Implementation of Page Table
- Virtual Memory in OS
- Cache Memory Organization
- Demand Paging
- Page Replacement Algorithms
- Allocation of Frames and Thrashing
- Demand Segmentation
OS Part-5
- Distributed Operating System: Introduction and Types
- Distributed OS: Design Issues
- Distributed OS: File System
- Distributed OS: Remote File Access
- Remote Procedure Call(RPC)
- Remote Method Invocation(RMI)
- Distributed Shared Memory
- Parallel Processing and Concurrent Programming
- Security and Threats Protection in Distributed OS
- Security Design Principles and Authentication in Distributed OS
- Sensor Network and Parallel OS
Page Replacement Algorithms in Operating System
🔹 Introduction
Page Replacement Algorithms Operating System ke Demand Paging mechanism me important role play karte hain. Jab CPU kisi page ko access karna chahta hai aur wo page RAM me available nahi hota (Page Fault), tab OS ko naye page ko memory me load karna padta hai. Lekin agar RAM full hai, to kisi existing page ko replace karna padta hai naye page ke liye.
✅ Page Replacement Algorithm ye decide karta hai ki kaunsa page memory se remove hoga taaki naye page ko load kiya ja sake.
Example:
Maan lo ek system me 3-page frames available hain aur ek process 6 pages ko access kar raha hai. Jab koi naye page ko RAM me load karna ho aur RAM full ho, tab ek existing page ko remove karke naye page ko laana padta hai. Is decision ko optimize karne ke liye Page Replacement Algorithms ka use hota hai.
🔹 Types of Page Replacement Algorithms
1️⃣ First In First Out (FIFO) Page Replacement Algorithm
FIFO Algorithm oldest page ko remove karta hai jo sabse pehle RAM me load hua tha.
📌 Working of FIFO:
Pages ko ek queue me store kiya jata hai.
Jo page sabse pehle aaya wo sabse pehle replace hoga.
👉 Example:
Maan lo humare paas 3 page frames hain aur reference string ye hai:1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
| Step | Page Frames (3) | Page Fault? |
|---|---|---|
| 1 | 1 – – | ✅ Yes |
| 2 | 1 2 – | ✅ Yes |
| 3 | 1 2 3 | ✅ Yes |
| 4 | 2 3 4 | ✅ Yes |
| 5 | 3 4 1 | ✅ Yes |
| 6 | 4 1 2 | ✅ Yes |
| 7 | 1 2 5 | ✅ Yes |
❌ Disadvantage:
FIFO “Belady’s Anomaly” show karta hai jisme frames badhane ke baad bhi page faults increase ho sakte hain.
2️⃣ Optimal Page Replacement Algorithm (OPT / MIN Algorithm)
OPT algorithm sabse kam future me use hone wale page ko replace karta hai.
📌 Working of OPT:
OS future me access hone wale pages ka analysis karta hai.
Jo page sabse late access hoga, usko remove kar diya jata hai.
👉 Example:
Agar reference string hai:7, 0, 1, 2, 0, 3, 4, 2, 3, 0, 3, 2
| Step | Page Frames (3) | Page Fault? |
|---|---|---|
| 1 | 7 – – | ✅ Yes |
| 2 | 7 0 – | ✅ Yes |
| 3 | 7 0 1 | ✅ Yes |
| 4 | 0 1 2 | ✅ Yes |
| 5 | 0 1 2 | ❌ No |
| 6 | 1 2 3 | ✅ Yes |
| 7 | 2 3 4 | ✅ Yes |
✅ Advantage:
OPT algorithm sabse kam number of page faults deta hai.
❌ Disadvantage:
OPT algorithm practically implement karna difficult hai kyunki future ka prediction karna mushkil hota hai.
3️⃣ Least Recently Used (LRU) Page Replacement Algorithm
LRU algorithm wo page remove karta hai jo sabse pehle use hua tha.
📌 Working of LRU:
Har page ka last used timestamp maintain kiya jata hai.
Jo page sabse pehle use hua tha, usko remove kiya jata hai.
👉 Example:
Reference String: 7, 0, 1, 2, 0, 3, 4, 2, 3, 0, 3, 2
| Step | Page Frames (3) | Page Fault? |
|---|---|---|
| 1 | 7 – – | ✅ Yes |
| 2 | 7 0 – | ✅ Yes |
| 3 | 7 0 1 | ✅ Yes |
| 4 | 0 1 2 | ✅ Yes |
| 5 | 0 1 2 | ❌ No |
| 6 | 1 2 3 | ✅ Yes |
| 7 | 2 3 4 | ✅ Yes |
✅ Advantage:
LRU Belady’s anomaly ko avoid karta hai aur practical implementation possible hai.
❌ Disadvantage:
Timestamp maintain karna costly hota hai, aur performance impact ho sakti hai.
4️⃣ Least Frequently Used (LFU) Page Replacement Algorithm
LFU algorithm wo page remove karta hai jo sabse kam baar access kiya gaya hai.
📌 Working of LFU:
Har page ka access frequency maintain hota hai.
Jo page sabse kam use hua hai, usko replace kiya jata hai.
👉 Example:
Agar reference string hai:3, 1, 2, 5, 1, 3, 2, 4, 1, 3, 2, 5, 6
| Step | Page Frames (3) | Page Fault? |
|---|---|---|
| 1 | 3 – – | ✅ Yes |
| 2 | 3 1 – | ✅ Yes |
| 3 | 3 1 2 | ✅ Yes |
| 4 | 1 2 5 | ✅ Yes |
| 5 | 1 2 5 | ❌ No |
| 6 | 1 2 3 | ✅ Yes |
| 7 | 2 3 4 | ✅ Yes |
✅ Advantage:
LFU repeatedly used pages ko retain karta hai aur rarely used pages ko replace karta hai.
❌ Disadvantage:
Agar ek page bohot purane access ke karan high frequency gain kar chuka hai, to wo hamesha retain rahega, jo issue create kar sakta hai.
🔹 Comparison of Page Replacement Algorithms
| Algorithm | Performance | Complexity | Practical Use |
|---|---|---|---|
| FIFO | Poor | O(1) | No (Belady’s anomaly) |
| OPT | Best | O(n) | No (Needs future knowledge) |
| LRU | Good | O(log n) | Yes (Used in OS) |
| LFU | Average | O(n) | Rarely Used |
🔹 Conclusion
✔ Page Replacement Algorithms ka use memory management ko optimize karne ke liye hota hai.
✔ FIFO simple hota hai, lekin performance poor hoti hai.
✔ OPT best algorithm hai, lekin practically possible nahi hai.
✔ LRU real-world systems me use hota hai, kyunki ye good performance deta hai.
✔ LFU kam use hota hai, lekin specific scenarios me useful ho sakta hai.