Dynamic Memory Allocation II
– * –
CS 367
Lab 3
The purpose of this set of slides is to
Show you the relationship between:
what the heap would look like after a series of allocation/deallocation and
what your simulation data structure should look like
Show you a little bit about the inner workings of the driver that your simulation code will be running with.
– * –
CS 367
p1 = malloc(4)
p2 = malloc(5)
p3 = malloc(6)
free(p2)
p4 = malloc(3)
Going to show what the simulation data structure
should look like for this series of alloc/dealloc
free(p4)
p5 = malloc(5)
– * –
CS 367
Notes
You will build/maintain your simulation data structure using C malloc/free calls.
In these slides, I have ignored things like alilgnment (i.e. block sizes must be multiples of 8) and bookkeeping info (adding bytes to keep track of size, etc) to focus on the relationship between what the actual heap might look like and your simulation data structure.
– * –
CS 367
p1 = malloc(4) – node splitting
Initially (empty heap)
addr = 0
size = 17
Heap
Simulation
Data structure
Heap
Heap
addr = 4
size = 13
Simulation
Data structure
Heap
– * –
CS 367
p2 = malloc(5)
Simulation
Data structure
Heap
Simulation
Data structure
Heap
Heap
addr = 9
size = 8
Heap
addr = 4
size = 13
– * –
CS 367
p3 = malloc(6)
Simulation
Data structure
Heap
Simulation
Data structure
Heap
Heap
addr = 9
size = 8
Heap
addr = 15
size = 2
– * –
CS 367
free(p2)
Simulation
Data structure
Heap
Simulation
Data structure
Heap
addr = 4
size = 5
addr = 15
size = 2
Heap
addr = 15
size = 2
Heap
– * –
CS 367
p4 = malloc(3)
Heap
Simulation
Data structure
Heap
Simulation
Data structure
addr = 4
size = 5
addr = 15
size = 2
Heap
addr = 7
size = 2
addr = 15
size = 2
Heap
– * –
CS 367
free(p4) – note the coelesing
Heap
Simulation
Data structure
Heap
Simulation
Data structure
addr = 7
size = 2
addr = 15
size = 2
Heap
addr = 4
size = 5
addr = 15
size = 2
Heap
– * –
CS 367
p5 = malloc(5)
Heap
Simulation
Data structure
Heap
Simulation
Data structure
addr = 4
size = 5
addr = 15
size = 2
Heap
addr = 15
size = 2
Heap
– * –
CS 367
Lab 3
The purpose of this set of slides is to
Show you the relationship between:
what the heap would look like after a series of allocation/deallocation and
what your simulation data structure should look like
Show you a little bit about the inner workings of the driver that your simulation code will be running with.
– * –
CS 367
The driver program
The driver maintains a data structure to save the pointers returned by your mm_malloc() implementation
It uses this pointer as a parameter to mm_free so that that function has a pointer to the node it needs to modify.
Notice that you can create ‘garbage’ just as you can in the real world but putting in a trace file something like:
1 4 10
1 4 20
The pointer to the node allocated by the first line will get overwritten by the value returned when setting up the second line.
– * –
CS 367
p1 = malloc(4)
addr = 0
size = 17
Heap
addr = 0
size = 4
Heap
mdriver
addr = 4
size = 13
mdriver
– * –
CS 367
p2 = malloc(5)
addr = 0
size = 4
Heap
addr = 4
size = 13
mdriver
addr = 0
size = 4
Heap
addr = 9
size = 8
mdriver
addr = 4
size = 5
– * –
CS 367
p3 = malloc(6)
addr = 0
size = 4
Heap
addr = 9
size = 8
mdriver
addr = 4
size = 5
addr = 0
size = 4
Heap
addr = 15
size = 2
mdriver
addr = 4
size = 5
addr = 9
size = 6
– * –
CS 367
free(p2)
addr = 0
size = 4
Heap
addr = 15
size = 2
mdriver
addr = 4
size = 5
addr = 9
size = 6
addr = 0
size = 4
Heap
addr = 4
size = 5
mdriver
addr = 9
size = 6
addr = 15
size = 2
– * –
CS 367
p4 = malloc(3)
addr = 0
size = 4
Heap
addr = 4
size = 5
mdriver
addr = 9
size = 6
addr = 15
size = 2
addr = 0
size = 4
Heap
addr = 7
size = 2
mdriver
addr = 9
size = 6
addr = 15
size = 2
addr = 4
size = 3
– * –
CS 367
free(p3)
addr = 0
size = 4
Heap
addr = 7
size = 2
mdriver
addr = 9
size = 6
addr = 15
size = 2
addr = 4
size = 3
addr = 0
size = 4
Heap
addr = 7
size = 10
mdriver
addr = 4
size = 3