程序代写代做代考 data structure Dynamic Memory Allocation II

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