--- title: "Optimal replacement; fragmentation, utilization" subject: "Operating System" chapter: 4 key: "semester_6/operating_system:optimal-fragmentation-utilization" source: https://www.bctengineer.com/q/semester_6/operating_system/optimal-fragmentation-utilization site: BCT Engineering --- # Optimal replacement; fragmentation, utilization Operating System · Chapter 4: Memory Management - Asked in: 2068 Magh, 2+6 marks - Video: [Optimal Page Replacement with example in OS](https://www.youtube.com/watch?v=Knb1uhHdLJg) — GATE GIST - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/operating_system/optimal-fragmentation-utilization - Whole chapter: https://www.bctengineer.com/md/semester_6/operating_system/chapter-4 ## Question What is optimal page replacement algorithm? Suppose that a total of 64MB memory is available in a system. This memory space is partitioned into 8 fixed size slots of 8MB each. Assume 8 processes are currently requesting memory usages with size indicated below. 2MB, 4MB, 3MB, 7MB, 9MB, 1MB, 8MB Calculate the size of memory wasted due to external and internal fragmentation and memory utilization ratio. ## Short answer Optimal replaces the page that will not be used for the longest future time, giving minimal page faults but requiring future knowledge. With 8 fixed 8MB slots, internal fragmentation is 23 MB, external 16 MB (since 9MB process rejected), and memory utilization is 39%. ## Answer #### Optimal page replacement The **optimal (OPT / MIN) algorithm** replaces the page that will not be used for the longest time in the future. It gives the lowest possible page-fault rate and never suffers Belady's anomaly, but it needs knowledge of future references, so it cannot be implemented in practice. It is used as a benchmark to compare other algorithms. #### Fragmentation numerical Assumptions: memory 64 MB = 8 fixed slots of 8 MB. Seven request sizes are listed (the "8 processes" in the statement has only 7 sizes), so the seven given are used. A process occupies exactly one slot and a slot holds one process. | Process | Size | Fits in 8 MB slot? | Internal fragment | |---|---|---|---| | P1 | 2 MB | yes | 6 MB | | P2 | 4 MB | yes | 4 MB | | P3 | 3 MB | yes | 5 MB | | P4 | 7 MB | yes | 1 MB | | P5 | 9 MB | no (larger than 8 MB) | rejected | | P6 | 1 MB | yes | 7 MB | | P7 | 8 MB | yes | 0 MB | - Allocated: 6 processes using 6 slots; memory actually used by processes = 2+4+3+7+1+8 = **25 MB**. - **Internal fragmentation** = 6+4+5+1+7+0 = **23 MB** (unused space inside allocated slots). - Two slots (2 × 8 = 16 MB) remain completely free, but the 9 MB process cannot use them because a slot is only 8 MB and a process cannot span slots. This unusable free memory is **external fragmentation = 16 MB**. - Total memory wasted = 23 + 16 = 39 MB. Check: 25 + 39 = 64 MB. - **Memory utilization** = useful memory / total memory = 25 / 64 = 0.39 = **39.06%**. **Answer: internal fragmentation 23 MB, external fragmentation 16 MB, utilization about 39%.** (If only allocated slots are counted, utilization is 25/48 = 52.1%.) ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What does the optimal algorithm replace? A. The page not used for the longest time in the future B. The oldest page C. The least recently used page D. The most frequently used page Answer: A. It needs future knowledge so is only a benchmark. (Key point: Optimal replacement) 2. Why is the 9 MB process not allocated? A. It arrives last B. It exceeds the 8 MB slot size and cannot span slots C. It is below the minimum size D. Memory is full Answer: B. A process occupies exactly one fixed slot. (Key point: Rejected process) 3. What is the internal fragmentation total? A. 16 MB B. 39 MB C. 23 MB D. 25 MB Answer: C. 6+4+5+1+7+0 = 23 MB of unused space within allocated slots. (Key point: Internal fragmentation) 4. How is memory utilization computed here? A. 25/48, about 52% B. 23/64 C. 39/64 D. 25/64, about 39% Answer: D. Useful memory (2+4+3+7+1+8 = 25 MB) divided by total 64 MB. (Key point: Utilization) ## Related in Operating System - [Race condition; optimal page replacement limits](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Arace-condition-optimal-limitation) — Operating System, chapter 3 - [Page size impact; internal, external fragmentation](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-size-impact-fragmentation) — Operating System, chapter 4 - [Page faults: FIFO, Optimal, LFU, LRU](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-faults-fifo-optimal-lfu-lru-5frames) — Operating System, chapter 4, asked 2× - [Banker's algorithm, 5 processes, 4 resources](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Abanker-five-process-four-resource) — Operating System, chapter 7 - [Page fault; allocation and replacement](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Apage-fault-allocation-replacement) — Operating System, chapter 4 - [Hits and faults: FIFO, LRU, Optimal](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Ahits-faults-fifo-lru-optimal-3frames) — Operating System, chapter 4 ## Related in other subjects - [Cache write policy and replacement algorithm](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Acache-write-policy-replacement) — Embedded System, chapter 4 - [Memory characteristics and LRU replacement](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Amemory-char-lru) — Computer Organization and Architecture, chapter 6 - [Optimal equalizer weights using MSE algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Amse-optimal-weights) — Wireless Communication, chapter 5, asked 3× - [Mapping function and replacement algorithm](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Amapping-replacement) — Computer Organization and Architecture, chapter 6