- 2068 Magh · 2+6 marks
Optimal replacement; fragmentation, utilization
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%.
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.
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%.)
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Race condition; optimal page replacement limits · Operating System, chapter 3
- Page size impact; internal, external fragmentation · Operating System, chapter 4
- Page faults: FIFO, Optimal, LFU, LRU · Operating System, chapter 4 · asked 2×
- Banker's algorithm, 5 processes, 4 resources · Operating System, chapter 7
- Page fault; allocation and replacement · Operating System, chapter 4
- Hits and faults: FIFO, LRU, Optimal · Operating System, chapter 4
- Cache write policy and replacement algorithm · Embedded System, chapter 4
- Memory characteristics and LRU replacement · Computer Organization and Architecture, chapter 6
- Optimal equalizer weights using MSE algorithm · Wireless Communication, chapter 5 · asked 3×
- Mapping function and replacement algorithm · Computer Organization and Architecture, chapter 6