Harvey Mudd CS 105 - Dynamic Memory Allocation II (36 pages)

Previewing pages 1, 2, 17, 18, 19, 35, 36 of 36 page document View the full content.
View Full Document

Dynamic Memory Allocation II



Previewing pages 1, 2, 17, 18, 19, 35, 36 of actual document.

View the full content.
View Full Document
View Full Document

Dynamic Memory Allocation II

68 views


Pages:
36
School:
Harvey Mudd College
Course:
Cs 105 - Computer Systems
Computer Systems Documents

Unformatted text preview:

CS 105 Tour of the Black Holes of Computing Dynamic Memory Allocation II Topics Explicit doubly linked free lists Segregated free lists Garbage collection Memory related perils and pitfalls Keeping Track of Free Blocks Method 1 Implicit list using lengths links all blocks 20 16 24 8 Method 2 Explicit list among the free blocks using pointers within the free blocks 20 16 24 8 Method 3 Segregated free list Different free lists for different size classes Method 4 Blocks sorted by size not discussed 2 For example balanced tree Red Black with pointers inside each free block block length used as key CS 105 Explicit Free Lists A B C Use data space for link pointers Typically doubly linked Still need boundary tags for coalescing Forward links A 16 16 16 16 24 24 16 C 3 16 16 B 16 Back links Links aren t necessarily in same order as blocks CS 105 Allocating From Explicit Free Lists pred Before succ free block pred After with splitting 4 succ free block CS 105 Freeing With Explicit Free Lists Insertion policy Where in free list to put newly freed block LIFO last in first out policy Insert freed block at beginning of free list Pro simple and constant time Con studies suggest fragmentation is worse than address ordered Address ordered policy Insert freed blocks so list is always in address order i e addr pred addr curr addr succ Con requires search using boundary tags Pro studies suggest fragmentation is better than LIFO 5 CS 105 Freeing With a LIFO Policy pred p Case 1 a a a Insert self at beginning of free list a succ s self a p Case 2 a a f before a Remove next from free list coalesce self and next and add to beginning of free list after 6 s self f p a s f CS 105 Freeing With a LIFO Policy cont p Case 3 f a a Remove prev from free list coalesce with self and add to beginning of free list s before f after p 7 Remove prev and next from free list coalesce with self and add to beginning of list a s f p1 Case 4 f a f self a s1 p2 s2 before f after p1 self s1 f p2 s2 f CS 105



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Dynamic Memory Allocation II and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Dynamic Memory Allocation II and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?