memory management - TarisMajor/5143-OpSystems GitHub Wiki

Memory Management in Operating Systems

Memory management is a cornerstone of operating systems, enabling efficient resource allocation, process isolation, and optimal performance. This entry explores key concepts, techniques, and algorithms associated with memory management.

Table of Contents

Logical Address vs. Physical Address

  • Logical Address: Virtual address generated by the CPU.
  • Physical Address: Actual memory location in RAM.
  • Key Component: The Memory Management Unit (MMU) maps logical addresses to physical addresses.

Logical vs Physical Addressing

Memory Allocation Techniques

Contiguous Allocation

Allocates a single continuous block of memory.

  • Advantages: Simplifies address calculation.
  • Drawbacks: Prone to fragmentation and requires large continuous memory blocks.

Non-Contiguous Allocation

Allocates scattered memory blocks, often using paging or segmentation.

  • Advantages: Efficient memory utilization.
  • Drawbacks: Increases complexity in memory management.

Contiguous vs Non-Contiguous Allocation

Paging

Memory is divided into fixed-size pages, which are mapped to physical frames using page tables.

  • Advantages: Eliminates external fragmentation.
  • Drawbacks: Adds overhead due to page table management.

Example Table:

Logical Page Physical Frame
Page 1 Frame 4
Page 2 Frame 7
Page 3 Frame 1

Paging Example

Segmentation

Memory is divided into logical segments such as code, data, and stack.

  • Key Difference: Segmentation uses variable-sized segments, while paging uses fixed-sized blocks.

Comparison Table:

Feature Paging Segmentation
Block Size Fixed Variable
Purpose Divide memory uniformly Divide logically

Segmentation Example

Page Tables

Page tables store mappings between logical pages and physical frames.

  • Single-Level Page Tables: Easy to implement but consumes a lot of memory.
  • Multi-Level Page Tables: Use a hierarchical structure to save memory.
  • Inverted Page Tables: Use a single table for the entire system to reduce space requirements.

Page Table Structure

Virtual Memory

Allows processes larger than physical memory to run by using disk space as an extension of RAM.

  • Page Fault: Occurs when a required page is not in memory.
  • Demand Paging: Loads pages into memory only when required, saving memory space but increasing page fault latency.

Virtual Memory Diagram

Page Replacement Algorithms

First-In-First-Out (FIFO)

Replaces the oldest page in memory.

  • Drawback: Suffers from Belady's anomaly, where increasing memory size can lead to more page faults.

FIFO Example
Figure 1: FIFO Page Replacement Algorithm.

Least Recently Used (LRU)

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

  • Implementation: Uses counters or stacks to track usage.

LRU Example
Figure 2: LRU Page Replacement Algorithm.

Optimal Page Replacement

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

  • Serves as a theoretical benchmark but is difficult to implement practically.

Optimal Example
Figure 3: Optimal Page Replacement Algorithm.

Clock (Second-Chance) Algorithm

A practical approximation of LRU, using a circular queue to track usage.

Clock Algorithm
Figure 4: Clock (Second-Chance) Page Replacement Algorithm.

Thrashing

Occurs when excessive paging activity leads to a significant slowdown of the system.

  • Cause: High memory demand exceeding available capacity.
  • Solution: Implementing the working set model to limit active processes or allocating more memory.

Thrashing Example

Fragmentation

Internal Fragmentation

Wasted space within allocated memory blocks due to fixed-size allocation.

Internal Fragmentation
Figure 1: Example of Internal Fragmentation.

External Fragmentation

Scattered free memory prevents allocation of large contiguous blocks.

External Fragmentation
Figure 2: Example of External Fragmentation.

Conclusion

Memory management is critical for modern operating systems, ensuring efficient resource utilization and process execution. Techniques like paging, segmentation, and virtual memory play a key role in balancing performance and complexity.

References

  1. Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts. Wiley.
  2. Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems. Pearson.