Memory Allocation - Memory Management Goals | OneNoughtOne

0/236

Operating SystemsMemory Management Goals

Memory Management Goals

LevelIntermediate

Duration90 mins

TopicMemory Management Goals

1 / 5

Memory Allocation

The Foundation of Multiprogramming

Memory is the lifeblood of computation. Every instruction executed, every variable stored, every data structure created exists in memory. When you run a program on your computer, something profound must happen before any code executes: the operating system must allocate memory to that program.

This seemingly simple act—assigning memory regions to processes—is one of the most critical functions of an operating system. Get it wrong, and programs crash, systems freeze, and data corrupts. Get it right, and dozens of processes coexist harmoniously, each believing it has the entire machine to itself.

Memory allocation is the first of five fundamental goals that drive memory management in operating systems. Understanding it deeply is essential for anyone who wants to comprehend how modern computing really works.

What You Will Learn

By the end of this page, you will understand: what memory allocation is and why it matters, the fundamental challenges of memory allocation in multiprogrammed systems, static vs dynamic allocation strategies, the role of the memory allocator, key allocation policies and their tradeoffs, and how allocation decisions ripple through entire system behavior.

What is Memory Allocation?

At its most fundamental level, memory allocation is the process of assigning portions of physical memory (RAM) to processes, the operating system kernel, and other system components. When a process needs memory—whether to load its code, store its data, or create runtime structures—it must request that memory from the operating system, which decides where in physical memory to place the process and how much memory to grant.

This definition, while accurate, barely scratches the surface of the complexity involved. To truly understand memory allocation, we must examine it through multiple lenses: the hardware perspective, the operating system perspective, and the process perspective.

Three Perspectives on Memory Allocation

•Hardware Perspective — Physical RAM consists of addressable bytes. The memory controller accesses these bytes through physical addresses. From the hardware's view, memory allocation is about which physical addresses are in use and which are free.
•Operating System Perspective — The OS maintains data structures tracking memory usage. It implements policies deciding which processes get memory, how much, and where. The OS must balance competing demands while ensuring system stability.
•Process Perspective — A process sees memory as its private address space. It uses logical addresses that the hardware translates to physical addresses. From the process's view, it has a contiguous block of memory all to itself—an illusion the OS carefully maintains.

The allocation act itself involves several key decisions:

How much memory? — Determining the quantity to allocate based on process requirements
Where in memory? — Selecting a suitable location from available regions
When to allocate? — Deciding if allocation happens at load time or on demand
How to track? — Recording allocation information for future reference
When to deallocate? — Reclaiming memory when no longer needed

Each decision involves tradeoffs between performance, memory utilization, and complexity. The choices made fundamentally shape system behavior.

The Historical Context: From Simplicity to Complexity

Understanding memory allocation requires appreciating how dramatically computing has evolved. In the earliest computers, memory allocation was trivial—because there was only one program running at a time.

The Monoprogramming Era (1940s-1960s)

In early batch processing systems, the entire memory (often just a few kilobytes) was divided into two parts: one for the operating system and one for the currently running program. Memory allocation was static and absolute. A program was written for specific memory addresses and ran in exactly those locations.

If a program was too large for available memory, it simply couldn't run. If it used less memory than allocated, that memory was wasted. There was no flexibility, but also no complexity—the allocation problem was barely a problem at all.

Evolution of Memory Allocation Complexity
Era	Memory Model	Allocation Challenge	Solution
1950s	Single program	None—one program owns all memory	Static partition
1960s	Batch multiprogramming	Multiple jobs waiting in memory	Fixed partitions
1970s	Time-sharing	Interactive processes with varying needs	Variable partitions
1980s	Virtual memory	Processes larger than physical RAM	Demand paging
1990s+	Complex workloads	Mixed workloads, real-time constraints	Sophisticated allocators
2000s+	Massive scale	Terabytes of RAM, NUMA architectures	Hierarchical allocation

The Multiprogramming Revolution

The advent of multiprogramming in the 1960s transformed memory allocation from triviality into a central OS challenge. When multiple programs share memory simultaneously, new questions emerge:

How do we divide memory among competing programs?
How do we prevent one program from accessing another's memory?
What happens when a program needs more memory than initially allocated?
How do we reclaim memory when a program terminates?

These questions spawned memory management as a discipline. Every modern operating system—from the kernel on your smartphone to the hypervisor in a data center—grapples with sophisticated versions of these same questions.

The Multiprogramming Imperative

Multiprogramming arose from economic necessity. Early computers were enormously expensive, and letting the CPU idle while waiting for I/O was wasteful beyond measure. By keeping multiple programs in memory, the OS could switch to another program whenever one blocked on I/O, dramatically improving CPU utilization. Memory allocation was the key enabler of this efficiency revolution.

Fundamental Allocation Strategies

Memory allocation strategies can be broadly classified along two dimensions: when allocation occurs and how allocation is determined. Understanding these fundamental strategies is essential for grasping more advanced memory management concepts.

Static Allocation

•Memory assigned at compile/load time
•Size and location fixed before execution
•No runtime allocation overhead
•Predictable memory usage
•Inflexible—can't adapt to runtime needs
•Examples: global variables, fixed arrays

Dynamic Allocation

•Memory assigned at runtime as needed
•Size determined during execution
•Incurs runtime overhead for allocation
•Flexible—adapts to actual requirements
•Can lead to fragmentation issues
•Examples: heap allocation, malloc/free

Contiguous vs. Non-Contiguous Allocation

Another fundamental distinction is whether a process's memory must be contiguous (a single block of consecutive addresses) or can be scattered across non-contiguous regions:

Contiguous Allocation:

Each process occupies a single, continuous region of memory
Simplifies address translation (base + offset)
Limited by the size of available contiguous free blocks
Leads to external fragmentation as allocations and deallocations create holes

Non-Contiguous Allocation:

A process's memory can be spread across multiple non-adjacent regions
Requires more sophisticated address translation mechanisms
Eliminates external fragmentation
Forms the basis for paging and segmentation

Modern systems predominantly use non-contiguous allocation through paging, but understanding contiguous allocation is essential because:

It's the foundation upon which non-contiguous methods were built
It still applies at various levels (e.g., within pages, for DMA buffers)
Its problems motivated the development of modern techniques

The Granularity Spectrum

Allocation granularity ranges from individual bytes (as in heap allocation) to large blocks like pages (4KB typically) or segments (variable size). Finer granularity offers flexibility but increases management overhead. Coarser granularity is more efficient but may waste memory through internal fragmentation. Modern systems use multiple granularities at different levels.

The Memory Allocator: Architecture and Responsibilities

The memory allocator is the OS component responsible for managing physical memory allocation. It's a critical piece of system software that must be highly efficient, absolutely reliable, and carefully designed. A bug in the allocator can crash the entire system; inefficiency in the allocator degrades every process's performance.

Modern operating systems typically implement a hierarchical allocation architecture with multiple allocators operating at different levels:

Memory Allocator Hierarchy

•Boot-time Allocator — A simple allocator that operates during system startup before the main allocators are initialized. Typically uses a basic bump-pointer or bitmap approach.
•Page Frame Allocator — The kernel's primary allocator, managing physical memory in page-sized chunks (typically 4KB). Examples include Linux's Buddy System allocator.
•Slab/SLUB Allocator — Built on top of the page allocator, manages memory for kernel objects of specific sizes. Caches frequently used object types for fast allocation.
•User-Space Heap Allocator — Libraries like glibc's malloc manage the heap for user processes, requesting pages from the kernel and sub-dividing them for application use.

allocator_interface.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Conceptual interface for a page frame allocator
// These represent the fundamental operations any allocator must support
 
// Allocate n contiguous page frames
// Returns physical address of first frame, or NULL on failure
void* alloc_pages(size_t n, gfp_flags flags);
 
// Free n contiguous page frames starting at addr
void free_pages(void* addr, size_t n);
 
// Query: how many free frames are available?
size_t get_free_frame_count(void);
 
// Query: is this physical address allocated?
bool is_allocated(void* addr);
 
// Example flags controlling allocation behavior
#define GFP_KERNEL    0x01  // Normal kernel allocation
#define GFP_ATOMIC    0x02  // Cannot sleep/block
#define GFP_DMA       0x04  // Must be in DMA-able memory region
#define GFP_ZERO      0x08  // Zero the allocated memory

Key Allocator Responsibilities:

1. Tracking Free Memory The allocator must maintain accurate records of which memory regions are free and which are allocated. Data structures for this include:

Bitmaps: One bit per allocation unit (page). Simple but requires linear search for large allocations.
Free Lists: Linked lists of free regions. Fast allocation but can fragment.
Buddy System: Hierarchical structure enabling efficient coalescence of adjacent free blocks.
Trees: Red-black or similar trees for fast search by size or address.

2. Satisfying Allocation Requests When a request arrives, the allocator must:

Find a suitable free region (applying a placement policy)
Update its tracking structures
Return the address to the requester
Handle failure gracefully if no suitable region exists

3. Reclaiming Deallocated Memory When memory is freed:

Validate the deallocation request
Mark the region as free
Potentially coalesce with adjacent free regions
Update tracking structures

4. Minimizing Fragmentation Over time, allocation and deallocation create fragmented free space. The allocator must minimize this through:

Intelligent placement policies
Coalescing adjacent free blocks
Sometimes compaction or defragmentation

Allocator Complexity is Non-Trivial

Writing a correct, efficient memory allocator is among the hardest systems programming tasks. The allocator runs in kernel mode with no safety net. It cannot allocate memory to track memory (chicken-and-egg). It must handle concurrent requests, respect memory zones, and never corrupt its own data structures. Bugs here cause system crashes, data loss, and security vulnerabilities.

Allocation Policies: Where to Place Memory

When a process requests memory, and multiple free regions could satisfy the request, the allocator must choose one. This choice is governed by the allocation policy (also called the placement algorithm). Different policies optimize for different goals: speed, memory utilization, or fragmentation minimization.

Classic Allocation Policies
Policy	Description	Pros	Cons
First Fit	Use the first region that's large enough	Fast—stops searching on first match	Tends to fragment start of memory
Best Fit	Use the smallest region that's large enough	Minimizes wasted space in chosen region	Slow—must search all; creates tiny fragments
Worst Fit	Use the largest available region	Leaves larger leftover fragments	Slow—must search all; degrades large allocations
Next Fit	Like First Fit, but start from last allocation point	Distributes allocations evenly; fast	May create more fragmentation than First Fit

Empirical Analysis of Policies

Research and practical experience have generated interesting findings about these policies:

First Fit typically performs well because:

Fast search termination improves overall performance
Loading memory from the front allows large allocations at the end
Simple to implement correctly

Best Fit often performs worse than expected because:

Creates many tiny, unusable fragments
Search overhead can be substantial
The 'perfect' fit is rarely optimal in the long run

Worst Fit rarely used because:

Eventually fragments all large blocks
No clear advantage in most workloads

Next Fit trades fragmentation for speed:

Avoids repeated searches of the same region
But spreads fragmentation throughout memory

Modern systems rarely use these simple policies directly. Instead, they employ sophisticated techniques like the Buddy System, slab allocation, or segregated free lists that provide O(1) allocation for common cases.

The 50-Percent Rule

A remarkable result from queuing theory states that under steady-state allocation/deallocation with First Fit, approximately one-third of memory becomes fragmented (unusable holes). If N blocks are allocated, approximately N/2 holes exist. This "50-percent rule" highlights that fragmentation is fundamental—it cannot be eliminated, only managed.

Allocation in Practice: Real System Examples

Let's examine how real operating systems implement memory allocation, moving from abstract policies to concrete implementations.

Linux Memory Allocation Architecture

Linux uses a hierarchical approach with two primary allocators:

The Buddy Allocator

Manages physical page frames
Allocates memory in power-of-2 page blocks (1, 2, 4, 8, ... pages)
When a block is split, the two halves are "buddies"
When both buddies are freed, they're coalesced back together
Provides O(log n) allocation and excellent coalescence

The Slab Allocator (SLUB)

Built on top of the Buddy allocator
Manages kernel objects of specific types (inodes, task_structs, etc.)
Pre-allocates object caches to reduce allocation overhead
Reduces internal fragmentation for common small objects
Provides O(1) allocation for cached object types

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// Linux kernel memory allocation APIs
#include <linux/slab.h>
#include <linux/gfp.h>
 
// Low-level: allocate 2^order contiguous pages
struct page *alloc_pages(gfp_t gfp_mask, unsigned int order);
 
// Common: allocate virtually contiguous kernel memory
void *kmalloc(size_t size, gfp_t flags);
void kfree(const void *ptr);
 
// Slab: allocate from a specific object cache
void *kmem_cache_alloc(struct kmem_cache *cache, gfp_t flags);
void kmem_cache_free(struct kmem_cache *cache, void *ptr);
 
// Flags control behavior:
// GFP_KERNEL - may sleep, used in process context
// GFP_ATOMIC - never sleeps, used in interrupt context
// GFP_DMA    - allocate from DMA-capable zone

Allocation Challenges and Solutions

Memory allocation would be straightforward if we knew exactly how much memory each process needed, for how long, and in what order. Reality is messier. Modern allocators must handle numerous challenges:

Key Allocation Challenges

•Fragmentation — Over time, allocated and free regions become interleaved, making it impossible to satisfy large allocation requests even when total free memory is sufficient. Both external fragmentation (free memory scattered in small blocks) and internal fragmentation (allocated blocks larger than needed) waste memory.
•Concurrency — Multiple cores allocating simultaneously create contention on allocator data structures. Lock-free or per-CPU allocators are essential for scalability.
•Memory Zones — Not all physical memory is equal. Some devices can only DMA to the first 16MB (ISA DMA). Some kernel structures must never be paged. The allocator must respect these constraints.
•NUMA Locality — In NUMA systems, memory access time depends on which CPU core is accessing which memory bank. Allocating memory 'near' the requesting CPU dramatically improves performance.
•Allocation Size Distribution — Workloads have different allocation patterns. Web servers allocate many small objects; databases allocate large buffers. One-size-fits-all policies underperform specialized approaches.
•Memory Pressure — When memory is nearly exhausted, allocation becomes contentious. The allocator must decide how aggressively to reclaim memory, when to trigger swapping, and whether to fail allocations or block.

Solutions and Mitigations:

Segregated Free Lists — Maintain separate free lists for different allocation sizes. Small allocations go to small-block lists, large to large-block lists. Eliminates searching and reduces fragmentation within size classes.

Per-CPU/Per-Thread Caches — Each CPU or thread maintains its own pool of recently freed objects. Allocations and deallocations on the same CPU require no synchronization. Dramatically improves concurrent allocation performance.

Lazy Coalescing — Don't merge adjacent free blocks immediately. Wait until memory pressure requires it, or batch the work. Reduces overhead when the same memory is reallocated soon after being freed.

Memory Compaction — Periodically move allocated objects to consolidate free space. Expensive but sometimes necessary for long-running systems. Must be done carefully to update all pointers.

Overcommit and Demand Paging — Don't actually allocate physical memory until it's accessed. Allow total virtual allocations to exceed physical memory. This works because programs often allocate more than they use.

The Allocator Arms Race

Allocator design is an active research area. Recent innovations like jemalloc, tcmalloc, and mimalloc have pushed allocation performance to new heights. Modern allocators can perform millions of allocations per second per core while maintaining low fragmentation—a far cry from the simple first-fit algorithms of early systems.

Why Memory Allocation is Fundamental

We've covered the mechanisms of memory allocation in depth. But why is it considered a fundamental goal of memory management, rather than just a necessary chore?

Memory allocation is fundamental because it enables multiprogramming—the ability to run multiple processes concurrently. Without effective allocation:

We could run only one program at a time, wasting CPU cycles during I/O waits
Programs would need to be written for fixed memory addresses, eliminating portability
System resources couldn't be shared efficiently among users and applications
Modern interactive computing would be impossible

The Cascading Impact of Allocation Decisions

•System Throughput — Efficient allocation maximizes the number of processes that can be memory-resident, reducing time wasted swapping processes in and out.
•Process Response Time — Quick allocation and deallocation keep interactive applications responsive. Slow allocation creates perceptible lag.
•Memory Utilization — Good allocation policies minimize wasted memory, allowing more processes to run or larger datasets to be processed.
•System Stability — Robust allocation handles edge cases gracefully, preventing crashes when memory is tight or requests are unusual.
•Security — Proper allocation ensures processes can't access each other's memory, providing the foundation for memory protection (our next major topic).

The Allocation-Protection Connection:

Allocation and protection are deeply intertwined. When the allocator grants memory to a process, it must also ensure that:

The process can access its own memory freely
The process cannot access memory belonging to other processes or the kernel
Memory permissions (read, write, execute) are correctly established
Hardware protection mechanisms are configured appropriately

This connection leads us directly to the second fundamental goal of memory management: Protection—the subject of our next page.

Key Takeaways

Memory allocation is the foundational act that enables multitasking operating systems. It involves complex decisions about how much memory to grant, where to place it, when to allocate it, and how to track it. Modern allocators use sophisticated techniques like hierarchical allocation, segregated free lists, and per-CPU caches to achieve high performance. Understanding allocation deeply prepares you for the remaining memory management goals: protection, sharing, and organization.

Summary: Memory Allocation

This page has provided a comprehensive exploration of memory allocation as the first fundamental goal of memory management. Let's consolidate what we've learned:

Chapter Summary

•Memory allocation is the process of assigning physical memory regions to processes and system components.
•Historical evolution from single-program systems to multiprogramming created the need for sophisticated allocation strategies.
•Static vs. dynamic allocation trade predictability for flexibility; modern systems use both.
•Contiguous vs. non-contiguous allocation affects fragmentation and address translation complexity.
•Memory allocators maintain tracking structures, apply placement policies, and handle concurrent requests.
•Allocation policies (First Fit, Best Fit, etc.) optimize for different goals with different tradeoffs.
•Real systems use hierarchical allocators (Buddy + Slab in Linux, Pool allocators in Windows) for efficiency.
•Challenges include fragmentation, concurrency, NUMA locality, and handling memory pressure.
•Allocation enables multiprogramming and is thus foundational to modern operating systems.

What's Next:

With memory allocated to multiple processes, a new question arises: How do we prevent these processes from interfering with each other? How do we protect the kernel from buggy or malicious user programs? The next page explores Protection—the second fundamental goal of memory management.

Page Complete

You now have a deep understanding of memory allocation as a fundamental OS goal. You understand why it matters, how it works, what challenges it faces, and how real systems implement it. This knowledge forms the foundation for understanding protection, sharing, and memory organization in the pages ahead.