COMP0020: Functional Programming
Example Programs
COMP0020 Functional Programming Lecture 19
Memory Allocation Techniques
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 18 / 58
COMP0020: Functional Programming
Example Programs
Contents
Pointer increment
Free list – sequential fits Segregated free lists Buddy systems
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 19 / 58
COMP0020: Functional Programming
Example Programs
Pointer increment
Ideal world :
I all allocated memory would be at one end I All free memory at other end
Single pointer to boundary
To allocate a block of size N, increment the boundary pointer by N and return the original value of the boundary pointer
Problems : to achieve an “ideal world” may be costly
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 20 / 58
COMP0020: Functional Programming
Example Programs
Free list : sequential fits
Assume all free blocks chained together into a linked list.
I A pointer holds the start of this chain
I Freed blocks either added to start (LIFO) or end (FIFO) of chain, or inserted into chain in order of
address (AO)
First fit allocation
I Larger blocks near start of list tend to be split first, resulting in many small fragments at start of list Next fit allocation
I Tends to increase fragmentation in practice Best fit allocation
I Tiny fragments ? Not in practice. I Slow ? Not always.
Worst fit? Good fit?
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 21 / 58
COMP0020: Functional Programming
Example Programs
Segregated free lists
Set of free lists
I each for blocks of a specific size I or for a range of sizes
F Use first-fit or next-fit etc within free list “Good fit”
I Or even “worst fit”
Use an array of pointers to the free lists Or a tree of pointers to the free lists
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 22 / 58
COMP0020: Functional Programming
Example Programs
Buddy systems
Variant of segregated free lists
I Aimed to optimize splitting and coalescing
A free area may only be merged with its buddy
When block freed – (unique) buddy found by simple address arithmetic
I wholly in use, or wholly free (so can merge) Binary buddies
I problem with internal frags (25%) Double buddies
I uses powers-of-two (2, 4, 8…) AND double-from-three (3, 6, 12…) I Better frags (12.5%) but restricted coalescing
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 23 / 58
COMP0020: Functional Programming
Example Programs
Summary
Summary
Pointer increment
Free list – sequential fits Segregated free lists Buddy systems
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 24 / 58
COMP0020: Functional Programming
Example Programs
Summary
END OF LECTURE
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 25 / 58