COMP0020: Functional Programming
Example Programs
COMP0020 Functional Programming Lecture 18
Automatic Memory Management
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 7 / 58
COMP0020: Functional Programming
Example Programs
Contents
What is DMM ? What is AMM ?
I Programmer control vs system control I Reuse/recycling of memory
How does AMM work ?
I Memory allocation I Garbage collection
Issues
I How is garbage created, detected, reused ? I What overheads do we incur ? (space/time) I Fragmentation
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 8 / 58
COMP0020: Functional Programming
Example Programs
What is Dynamic Memory Management (DMM) ?
Problem to be solved : (i) don’t know until run-time what memory will be needed ; and (ii) desire to re-use memory locations (memory is a scarce resource)
Problem to be solved : required blocks of memory may be of di ering sizes
A solution : write a Storage Manager (SM) library, with functions “malloc” and “free” Give malloc the size of memory required, it returns a pointer
Give free a pointer to a block that is not longer required, it makes it available for re-use
The library functions will manage the di erently-sized blocks of “live” and “free’ memory in an optimal way
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 9 / 58
COMP0020: Functional Programming
Example Programs
What is AMM ?
Biggest source of bugs : POINTERS A solution :
I Don’t let programmers have direct access to memory locations (NO POINTERS) I Let system manage memory allocation/deallocation
I Functional languages, Java
An onerous responsibility for the system
I must never go wrong
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 10 / 58
COMP0020: Functional Programming
Example Programs
How does AMM work ?
Just like DMM, a storage manager (SM) subroutine services requests from the rest of the program
I Program (runtime system) requests “N bytes of memory” from the SM I SM:
F searches for appropriate chunk of “free” memory F Allocates the chunk (tags it “in use” or “live”) F returns a pointer to that chunk
I Programmer never sees the pointer – only used by runtime system SM detects when “in use” chunk becomes garbage and tags it “free”
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 11 / 58
COMP0020: Functional Programming
Example Programs
How does AMM work ? (2)
Memory allocation techniques
I Which chunk (block) of memory should the SM return in response to a request ? Does it matter ? Garbage collection techniques
I How to identify garbage I How to collect garbage
Compaction/defragmentation techniques
I How does fragmentation occur
I How can it be reduced or removed
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 12 / 58
COMP0020: Functional Programming
Example Programs
Issues : Garbage collection
How is garbage created ?
I Beta reduction, delta reduction … How is garbage identified ?
I Number of references ? … or connectivity How is garbage collected ?
I Use a free list? … or not How is garbage reused ?
I Cooperation with memory allocation
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 13 / 58
COMP0020: Functional Programming
Example Programs
Issues : how much does it cost ?
Time
I Performance degradation I Embarrassing pause ?
F Real-time systems ? Space
I Some memory set aside for administration ? I Some extra memory required per cell ?
I Size of code ?
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 14 / 58
COMP0020: Functional Programming
Example Programs
Issues : fragmentation
What is it?
Why is it a problem ?
I Embedded systems
I Virtual memory – paging overhead
How can it be solved ?
I Coalescing
I Compaction :
F Copying F Sliding
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 15 / 58
COMP0020: Functional Programming
Example Programs
Summary
Summary
What is AMM ?
I Programmer control vs system control I Reuse/recycling of memory
How does AMM work ?
I Memory allocation I Garbage collection
Issues
I How is garbage created, detected, reused ? I What overheads do we incur ? (space/time) I Fragmentation
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 16 / 58
COMP0020: Functional Programming
Example Programs
Summary
END OF LECTURE
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 17 / 58