Dynamic Memory Allocation
Amanpreet Kaur Boparai
Deptt Applied Science
Chemistry Group
Chandigarh University Gharuan
Objectives
Be able to analyze a memory allocators
performance
Memory usage efficiency (fragmentation)
Speed of allocation and deallocation operations
Locality of allocations
Robustness
Be able to implement your own efficient
memory allocator (Malloc Project)
Be able to analyze the advantages and
disadvantages of different garbage
collector designs
Memory is not unbounded
It must be allocated and managed
Many applications are memory dominated
E.g., applications based on complex graph algorithms
Memory referencing bugs especially
pernicious
Effects are distant in both time and space
Memory performance is not uniform
Cache and virtual memory effects can greatly
affect program performance
Adapting program to characteristics of memory
system can lead to major speed improvements
Memory Allocation
Static size, static allocation
Global variables
Linker allocates final virtual addresses
Executable stores these allocated addresses
Static size, dynamic allocation
Local variables
Compiler directs stack allocation
Stack pointer offsets stored directly in the code
Dynamic size, dynamic allocation
Programmer controlled
Allocated in the heap how?
Dynamic Memory Allocation
Application
Dynamic Memory Allocator
Heap Memory
Explicit vs. implicit memory allocator
Explicit: application allocates and frees space
e.g., malloc and free in C
Implicit: application allocates, but does not free space
e.g., garbage collection in Java, ML or Lisp
Allocation
In both cases the memory allocator provides an abstraction of
memory as a set of blocks
Doles out free memory blocks to application
We will first discuss simple explicit memory allocation
0xFFFFFFFF
0xFFBEC000
%sp
0xFF3DC000
Process Memory Image
void *sbrk(int incr)
User Stack
Shared Libraries
brk
Heap
Read/Write Data
0x00010000
0x00000000
Read-only Code and Data
Unused
Used by allocators to
request additional memory
from the OS
brk initially set to the end
of the data section
Calls to sbrk increment
brk by incr bytes (new
virtual memory pages are
demand-zeroed)
incr can be negative to
reduce the heap size
Constraints
Applications:
Can issue arbitrary sequence of malloc and free requests
Free requests must correspond to an allocated block
Allocators
Cant control number or size of allocated blocks
Must respond immediately to all allocation requests
i.e., cant reorder or buffer requests
Must allocate blocks from free memory
i.e., can only place allocated blocks in free memory
Must align blocks so they satisfy all alignment requirements
8 byte alignment for libc malloc on many systems
Can only manipulate and modify free memory
Cant move the allocated blocks once they are allocated
i.e., compaction is not allowed
Goals of Good malloc/free
Primary goals
Good time performance for malloc and free
Ideally should take constant time (not always possible)
Should certainly not take linear time in the number of blocks
Good space utilization
User allocated structures should use most of the heap
Want to minimize fragmentation
Some other goals
Good locality properties
Structures allocated close in time should be close in space
Similar objects should be allocated close in space
Robust
Can check that free(p1) is on a valid allocated object p1
Can check that memory references are to allocated space
Implicit Memory
Deallocation
+ Programmers dont need to free data
explicitly, easy to use
+ Some implementations could achieve better
spatial locality and less fragmentation in the
hands of your average programmers
- Price to pay: depends on implementation
But HOW could a memory manager know when
to deallocate data without instruction from
programmer?
Implicit Memory Management:
Garbage Collection
Garbage collection: automatic reclamation of
heap-allocated storage application never has to
free
void foo() {
int *p = malloc(128);
return; /* p block is now garbage */
}
Common in functional languages, scripting
languages, and modern object oriented languages:
Lisp, ML, Java, Perl, Mathematica
Variants (conservative garbage collectors) exist for
C and C++
Cannot collect all garbage
Garbage Collection
How does the memory manager know when
memory can be freed?
In general we cannot know what is going to be
used in the future since it depends on conditionals
But we can tell that certain blocks cannot be used
if there are no pointers to them
Need to make certain assumptions about
pointers
Memory manager can distinguish pointers from
non-pointers
All pointers point to the start of a block
Cannot hide pointers (e.g., by coercing them to an
int, and then back again)
