Carnegie Mellon
Heap assumptions for lecture
Memory is word addressed (each word can hold a pointer)
Allocated block (4 words)
Free block (3 words)
Free word Allocated word
1
Carnegie Mellon
Allocation Example
p1 = malloc(4)
p2 = malloc(5)
p3 = malloc(6)
free(p2)
p4 = malloc(2)
2
Carnegie Mellon
Constraints
Applications
Can issue arbitrary sequence of malloc and free requests freerequestmustbetoamalloc’d block
Allocators
Can’t control number or size of allocated blocks Must respond immediately to malloc requests
i.e., can’t 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 GNU malloc (libc malloc) on Linux boxes Can manipulate and modify only free memory
Can’t move the allocated blocks once they are malloc’d
i.e., compaction is not allowed
3
Carnegie Mellon
Performance Goal: Throughput
Given some sequence of malloc and free requests:
R0, R1, …, Rk, … , Rn-1
Goals: maximize throughput and peak memory utilization
These goals are often conflicting
Throughput:
Number of completed requests per unit time Example:
5,000 malloc calls and 5,000 free calls in 10 seconds Throughput is 1,000 operations/second
4
Carnegie Mellon
Performance Goal: Peak Memory Utilization Given some sequence of malloc and free requests:
R0, R1, …, Rk, … , Rn-1
Def: Aggregate payload Pk
malloc(p) results in a block with a payload of p bytes
After request Rk has completed, the aggregate payload Pk is the sum of currently allocated payloads
Def: Current heap size Hk
Assume Hk is monotonically nondecreasing
i.e., heap only grows when allocator uses sbrk
Def: Peak memory utilization after k requests Uk =(maxi