M06-Memory Management

Memory Management Overview

CS 439 Principles of Computing Systems focuses on the critical aspects of memory management, which is a vital part of computer system operation, ensuring efficient use of memory resources in various computing contexts.

The Storage Hierarchy

2.1 Components of the Hierarchy

The storage hierarchy consists of various storage mediums including Tapes, CDs, Disks, Flash/SSD/SCM, Main Memory, and CPU cache levels (L1, L2, L3). Each component plays a distinct role in data access speed, capacity, and cost-effectiveness.

2.2 Properties of Storage

• The price per byte significantly decreases as one moves down the hierarchy from L1 cache to tapes, while the speed of memory access similarly trends downward, reflecting a trade-off between cost and performance.

• CPU speed has stagnated, yet the sizes of memory storage options continue to expand, highlighting an ongoing need for efficient memory management strategies.

Access Speed by Level

• L1 Cache: Access time is approximately 1-2 CPU cycles, providing the fastest data retrieval.

• L2 Cache: Slightly slower, taking 10's of CPU cycles.

• Main Memory: Typically around 60 nanoseconds, reflecting the increasing access time as one moves from cache to RAM.

• Disk Storage: Slower access times, measured in milliseconds, which leads to noticeable delays in data retrieval.

• CD ROM: 10's of milliseconds, making it less suitable for rapid access needs.

• Tape Storage: Extremely slow, with access times ranging from seconds to minutes, generally used for archiving purposes.

Memory Sizes

• L1 Cache: Ranges from 8-64KB, providing high-speed data access with limited storage capacity.

• L2 Cache: Ranges from 256KB to 2MB, balancing speed and size requirements.

• L3 Cache: Between 2MB and 32MB, optimized for larger datasets.

• Main Memory: Vastly varying sizes from 16MB to 160TB, accommodating diverse application needs.

• Disks: Ranging from 1GB to 30TB, used for bulk data storage.

• Tapes: Can manage petabytes, suitable for long-term data storage solutions.

Memory Size vs. Speed

• Strategies for increasing size while maintaining performance are feasible but require advanced technologies.

• Pursuing greater speeds while maintaining memory size is possible but often incurs high costs.

• Both goals generally cannot be pursued simultaneously without significant investment or technological breakthroughs.

Programmer’s View of Memory

Memory is conceptualized as a linear array of bytes with addresses ranging from 0 to 2^64 - 1 for a 64-bit address space, facilitating straightforward data access for programmers. Memory does not retain values once a program terminates or when the power is lost, necessitating careful management of data within program lifetimes.

Program Types

7.1 Non-Relocatable Programs

These programs must load and execute at specific memory addresses or ranges, often limiting flexibility in memory usage.

7.2 Relocatable Programs

These can be loaded at any address in memory, allowing for more efficient use of memory resources. Linkers prepare relocatable programs, enabling them to execute regardless of their loading positions in memory.

Implementing Relocation

8.1 Methods

• Relocating Linker: Handles address mapping before execution, facilitating versatile program loadability.

• Relocating Loader: Resolves addresses at the time of loading into memory, which adds a layer of flexibility but incurs additional overhead during program startup.

• Relocation Register: Enables addressing relative to a base register, simplifying how programs reference memory addresses during execution.

Memory Management Goals

• Enable effective use of memory for programmers, optimizing both performance and resource consumption.

• Protect programs from interfering with each other, enhancing system stability.

• Achieve efficient management of physical memory resources, ensuring better system performance.

Early Memory Systems

Historical systems featured basic configurations lacking advanced protection or relocation mechanisms. The structure was simple, involving a single program running alongside a monitor.

Overlaying

Overlaying allows programs larger than available memory to be executed by loading segments or pieces sequentially. Each overlay operates independently, meaning one cannot directly access data from another overlay without explicit loading and management.

Memory Allocation Strategies

12.1 Fixed Partition Allocation

Memory is divided into fixed-size partitions, simplifying the loading process but possibly resulting in internal fragmentation and wasted space.

12.2 Dynamic Partition Allocation

Allocates memory based on the specific requirements of programs, providing greater flexibility. Utilizes relocation registers to support relocatable code, allowing more efficient use of memory.

External Fragmentation

Refers to memory fragmentation where available free spaces are large but not contiguous, leading to inefficient memory utilization and potential allocation problems.

Compaction Strategies

Involves moving programs in memory to consolidate free spaces, often referred to as "burping," which helps minimize fragmentation and optimizes memory usage.

Allocation Policies

15.1 Strategies Introduced

• First Fit: Quickly finds the first sufficient block for allocation, ensuring ease of implementation.

• Best Fit: Aims to minimize leftover space post-allocation but can be slower due to the overhead of searching.

• Worst Fit: Allocates the largest available block, potentially leading to inefficient space usage.

• Buddy Allocation: Divides memory blocks into sizes that are powers of two, making it easier to find suitable allocations.

Multiprogramming and Swapping

16.1 Multiprogramming Defined

Enables the execution of multiple programs concurrently, with limits based on available memory resources.

16.2 Swapping Mechanics

Involves temporarily moving inactive or less critical processes to disk storage, allowing the system to manage memory loads more effectively.

Memory Management with Paging

17.1 Challenges

Fragmentation and contiguity issues arise, complicating memory management strategies.

17.2 Paged Memory Approach

Utilizes a memory management unit (MMU) to translate logical addresses into physical addresses, subdividing addressable space into pages, which are then mapped onto physical frames to enhance access efficiency.

Virtual Memory Concepts

Extends physical memory onto disk space by maintaining only the necessary pages in active memory. Demand paging allows for efficient memory management, preventing the system from being overwhelmed by excessive allocations.

Garbage Collection Techniques

19.1 Reference Counting

Objects maintain a count of references; deallocation occurs when this count reaches zero, primarily used in languages such as C and C++.

19.2 Mark and Sweep

A context-aware method involving marking reachable objects and reclaiming those that are unreachable, aiding in efficient memory utilization.

Conclusion

Effective memory management is crucial for optimizing computing performance and ensuring efficient resource allocation, thereby impacting overall system efficiency and functionality.