Operating Systems

Fixed Partitions:
|  OS  | P1 (10KB) | P2 (20KB) | P3 (15KB) |  Free  |

Variable Partitions:
|  OS  |   P1 (12KB)   |  P2 (8KB)  |    Free     |

External Fragmentation:
Total free space enough, but not contiguous
Solution: Compaction (expensive)

Internal Fragmentation:
Allocated more than needed (within partition)
Solution: Smaller allocation units

Page size = Frame size (typically 4KB)

Logical Address:
| Page Number | Offset |
     p bits      d bits

Physical Address:
| Frame Number | Offset |
     f bits       d bits

Page Table Entry (PTE):
| Frame Number | Valid | Protection | Dirty | Reference |

Process pages map to physical frames:
Page 0 → Frame 5
Page 1 → Frame 2
Page 2 → Frame 7

Logical Address: Page 2, Offset 100
Page Table: Page 2 → Frame 7
Physical Address: Frame 7, Offset 100

If page size = 4KB = 4096 bytes
Physical = Frame × Page_Size + Offset
         = 7 × 4096 + 100 = 28772

Cache for page table entries
Hit: No memory access for translation
Miss: Access page table in memory

Effective Access Time (EAT):
EAT = hit_ratio × (TLB_time + mem_time) 
    + miss_ratio × (TLB_time + 2×mem_time)

Segment Table:
| Segment | Base | Limit |
|    0    | 1000 |  400  | (Code)
|    1    | 2000 |  600  | (Data)
|    2    | 3000 |  300  | (Stack)

Logical Address: Segment 1, Offset 200
Physical = Base + Offset = 2000 + 200 = 2200

If Offset > Limit → Segmentation Fault!

Virtual Address Space > Physical Memory

Only needed pages in RAM
Rest on disk (swap space)

Page Fault:
1. Access page not in memory
2. OS traps, finds page on disk
3. Load page to free frame
4. Update page table
5. Restart instruction

Load pages only when needed (on demand)
Initially: No pages in memory
Access → Page fault → Load from disk

Page Fault Rate (p):
EAT = (1-p) × memory_access + p × page_fault_time

Replace oldest page in memory

Reference: 7 0 1 2 0 3 0 4
Frames = 3

|7| | |  → 7
|7|0| |  → 0
|7|0|1|  → 1
|2|0|1|  → 2 (replaces 7, oldest)
|2|0|1|  → 0 (hit)
|2|3|1|  → 3 (replaces 0)
|2|3|0|  → 0 (replaces 1)
|4|3|0|  → 4 (replaces 2)

Page faults = 7

Replace page not used for longest time

Reference: 7 0 1 2 0 3 0 4
Frames = 3

|7| | |  → 7
|7|0| |  → 0
|7|0|1|  → 1
|2|0|1|  → 2 (7 LRU)
|2|0|1|  → 0 (hit)
|2|0|3|  → 3 (1 LRU)
|2|0|3|  → 0 (hit)
|4|0|3|  → 4 (2 LRU)

Page faults = 6 (better than FIFO)

Replace page not used for longest time in FUTURE
(Theoretical - needs future knowledge)

Gives minimum page faults
Used as benchmark for comparison

Too many page faults!
CPU spends more time swapping than executing

Cause: Working set > available frames
Solution: 
- Reduce multiprogramming
- Increase RAM
- Use better replacement algorithm