Memory Management

Memory Management

Memory management is a crucial function of the operating system that handles allocation and deallocation of memory to processes. It ensures efficient use of memory and provides memory protection.

Memory Hierarchy

Computer systems have a memory hierarchy:

1. Registers: Fastest, smallest, most expensive
2. Cache: Fast, small, expensive
3. Main Memory (RAM): Medium speed, medium size, medium cost
4. Secondary Storage (Disk): Slow, large, cheap

Memory Management Techniques

1. Contiguous Memory Allocation

Memory is divided into partitions. Each process is allocated a contiguous block of memory.

Fixed Partitioning:

• Memory divided into fixed-size partitions
• Process allocated to partition of appropriate size
• Internal fragmentation (unused space within partition)

Variable Partitioning:

• Memory divided into variable-size partitions
• Process allocated exact size needed
• External fragmentation (small holes between partitions)

Compaction: Move processes to eliminate external fragmentation.

2. Paging

Paging divides physical memory into fixed-size blocks called frames and logical memory into blocks of same size called pages.

Advantages:

• No external fragmentation
• Simple memory allocation
• Efficient use of memory

Disadvantages:

• Internal fragmentation (last page may not be full)
• Overhead of page table

Page Table: Maps logical page numbers to physical frame numbers.

Example:

• Page size = 4 KB
• Logical address = 16 bits
• Page number = 12 bits (4096 pages)
• Page offset = 4 bits (16 bytes per page)

Address Translation:

1. Extract page number from logical address
2. Look up page number in page table
3. Get frame number
4. Combine frame number with offset to get physical address

Physical Address = (Frame Number × Page Size) + Offset

3. Segmentation

Segmentation divides logical memory into variable-size segments based on program structure (code, data, stack).

Advantages:

• Reflects program structure
• Easy sharing of segments
• Protection at segment level

Disadvantages:

• External fragmentation
• Complex memory allocation

Segment Table: Maps segment numbers to base addresses and limits.

4. Paged Segmentation

Combines paging and segmentation:

• Segments are divided into pages
• Eliminates external fragmentation
• Provides benefits of both

Virtual Memory

Virtual Memory allows execution of processes that may not be completely in memory. It enables:

• Programs larger than physical memory
• More processes in memory simultaneously
• Better memory utilization

Demand Paging

Demand Paging: Pages are loaded into memory only when needed (on demand).

Page Fault: When a page is not in memory, a page fault occurs:

1. Trap to OS
2. Save process state
3. Locate page on disk
4. Find free frame
5. Load page into frame
6. Update page table
7. Restart instruction

Page Fault Service Time: Time to handle page fault (disk access time).

Page Replacement Algorithms

When a page fault occurs and no free frame is available, we must replace an existing page.

1. First-In-First-Out (FIFO)

Replace the page that has been in memory longest.

Example:

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Frames: 3

7: [7] - Page fault
0: [7, 0] - Page fault
1: [7, 0, 1] - Page fault
2: [0, 1, 2] - Replace 7, Page fault
0: [0, 1, 2] - Hit
3: [1, 2, 3] - Replace 0, Page fault
...

Page Faults: 15

Belady's Anomaly: More frames can lead to more page faults (counter-intuitive).

2. Optimal Page Replacement

Replace the page that will not be used for longest time in future.

Example:

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Frames: 3

7: [7] - Page fault
0: [7, 0] - Page fault
1: [7, 0, 1] - Page fault
2: [0, 1, 2] - Replace 7 (7 used at position 18), Page fault
0: [0, 1, 2] - Hit
3: [0, 1, 3] - Replace 2 (2 used at position 9), Page fault
...

Page Faults: 9 (optimal)

Problem: Requires future knowledge (not practical).

3. Least Recently Used (LRU)

Replace the page that has not been used for longest time.

Example:

Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

Frames: 3

7: [7] - Page fault
0: [7, 0] - Page fault
1: [7, 0, 1] - Page fault
2: [0, 1, 2] - Replace 7 (LRU), Page fault
0: [0, 1, 2] - Hit (update LRU)
3: [0, 2, 3] - Replace 1 (LRU), Page fault
...

Page Faults: 12

Implementation:

• Counter: Each page has counter, update on access
• Stack: Move accessed page to top

4. Least Frequently Used (LFU)

Replace the page with smallest count of accesses.

5. Most Frequently Used (MFU)

Replace the page with largest count of accesses.

6. Second Chance (Clock)

FIFO with reference bit. If page has reference bit set, give it second chance.

Thrashing

Thrashing: System spends more time swapping pages than executing processes.

Causes:

• Too many processes in memory
• Insufficient frames per process

Solution:

• Reduce degree of multiprogramming
• Increase memory
• Use better page replacement algorithm

GATE CS Important Points

1. Paging: Understand page table, address translation, TLB
2. Page Replacement: Know FIFO, Optimal, LRU algorithms thoroughly
3. Page Fault Calculation: Practice calculating page faults for different algorithms
4. Virtual Memory: Understand demand paging, page fault handling
5. Memory Allocation: Know contiguous vs non-contiguous allocation

Practice Tips

1. Draw Page Tables: Visualize page-to-frame mapping
2. Trace Page Replacement: Step through algorithms with reference strings
3. Calculate Page Faults: Practice with different algorithms and frame counts
4. Address Translation: Practice converting logical to physical addresses
5. Previous Year Questions: Solve GATE memory management questions