Where to put the heap? Let both stack and heap share the same memory area,but grow towards each other from opposite ends! SB Stack memory area ST [Stack grows downward [Heap can expand upward HT Heap memory area HB
Where to put the heap? Let both stack and heap share the same memory area, but grow towards each other from opposite ends! grow towards each other from opposite ends! SB ST Stack memory area Sk d d tac k grows downwar d HT Heap can expand upward Heap memory area HB
How to keep track of free memory? Stack is LIFO allocation =ST moves up/down everything above ST is in use/allocated.Below is free memory.This is easy！But… Heap is not LIFO,how to manage free space in the "middle"of the heap? SB Free HT Allocated Mixed: Allocated ST reuse's and ↓Free Free HB
How to keep y track of free memory? Stack is LIFO allocation => ST moves up/down everything above ST is in use/allocated. Below is free memory. This is easy! But … Heap is not LIFO, how to manage free space in the “middle” of the heap? the heap? HT SB Free Allocated Mixed: ST Allocated S reuse? and Free Free HB
How to keep track of free memory? How to manage free space in the "middle"of the heap? =keep track of free blocks in a data structure:the "free list".For example we could use a linked list pointing to free blocks freelist A freelist! HT Free Nex Good idea! But where do we find the memory to Free Next store this data structure? Free Next HB
How to keep y track of free memory? How to manage free space in the “middle” of the heap? => keep track of free blocks in a data structure > keep track of free blocks in a data structure: the “free list”. For example we could use a linked list pointing to free blocks. freelist HT Free Next A freelist! Good idea! But where do we find the memory to Free Next find the memory to store this data structure? HB Free Next
How to keep track of free memory? Q:Where do we find the memory to store a freelist data structure? A:Since the free blocks are not used for anything by the program =memory manager can use them for storing the freelist itself. HT HF- free block size HE next free HB
How to keep y track of free memory? Q: Where do we find the memory to store a freelist data structure? A: Since the free blocks are not used for anything by the program => memory manager can use them for storing the f li t it lf HT freelist itself. HF HF free block size next free HB
Why Garbage Collection? Today's programs consume storage freely 1GB laptops,1-4GB deskops,8-512GB servers -64-bit address spaces(SPARC,Itanium,Opteron) 。.and mismanage it Memory leaks,dangling references,double free,misaligned addresses,null pointer dereference,heap fragmentation -Poor use of reference locality,resulting in high cache miss rates and/or excessive demand paging Explicit memory management breaks high-level programming abstraction slide 20
Why Garbage Collection? • Today’s programs consume storage freely – 1GB laptops, 1-4GB deskops, 8-512GB servers – 64 -bit address spaces (SPARC Itanium Opteron) bit address spaces (SPARC, Itanium, Opteron) • … and mismanage it – Memor y gg g p leaks, dan glin g references, double free, misali gned addresses, null pointer dereference, heap fragmentation – Poor use of reference locality, resulting in high cache miss rates and/or excessive demand pg g a gin g • Explicit memory management breaks high-level programming abstraction slide 20