Universitario

Memory Allocation

Copyright ©: University of Illinois CS 241 Staff

1

Variable Size Partitions
 

Idea
   

Allocate memory in small units Give each job as many units as it needs
≈ A B C D E ≈

 

Key Challenges
   

Keep track of free / allocated memory regions Allocation policy to assign free regions to jobs

Copyright ©: University of Illinois CS 241 Staff

2Malloc: Dynamic Allocation
 

Idea
   

Allocate memory in small units Give each request as many units as it needs
≈ A B C D E ≈

 

Key Challenges
   

Keep track of free / allocated memory regions Allocation policy to assign free regions to objects

Copyright ©: University of Illinois CS 241 Staff

3

Malloc and Friends
     

void* malloc(size_t size) voidfree(void* ptr) void* realloc(void* ptr, size_t size)
     

Allocate new object if old is smaller If so, copy memory and free old memory Return new memory malloc count*size and zero the bytes
Copyright ©: University of Illinois CS 241 Staff 4

 

void* calloc(size_t count, size_t size)
 

Dynamic allocation: Metrics
 

Memory Usage: Max, avg. heap size
 

Minimizefragmentation Choose large enough free region Find object size Return to free list
Copyright ©: University of Illinois CS 241 Staff 5

 

Allocation speed: Avg cost per malloc
 

 

Deallocation speed: Avg cost per free
   

Pieces of the Puzzle
1. 

“Free list”
 

Tracking, finding free regions Choosing free region for allocation Speed up searches; minimize fragmentation

2. Allocation Policy:
 

3. 

Deallocation Policy:
 

Copyright ©: University of Illinois CS 241 Staff

6

1. Tracking Free Regions
 

Goals
   

Keep track of free / allocated memory regions Find free regions of sufficient size Bitmaps
 

 

Mechanisms for tracking memory regions
 

Each bit corresponds to a single unit of memory Each list entry corresponds tocontiguous region

 

Linked lists
 

Copyright ©: University of Illinois CS 241 Staff

7

Bit Maps and Linked Lists
8 16 24

≈

A

B

C

D

E

 

Part of memory with 5 processes, 3 holes
   

≈

Tick marks show allocation units Green regions are free

Copyright ©: University of Illinois CS 241 Staff

8

Bit Maps and Linked Lists
8 16 24

≈

A

BC

D

E

≈

11111000 11111111 11001111 11111000

≈
 

Part of memory with 5 objects, 3 holes
   

Tick marks show allocation units Green regions are free

Copyright ©: University of Illinois CS 241 Staff

9

Bit Maps and Linked Lists
8 16 24

≈

A

B

C

D

E

≈

11111000 11111111 11001111 11111000

P 0 5 H 18 2
Hole Starts Length at 18 2

H 5 3P 8 6

P 14 4

P 20 6

P 26 3
Object

H 29 3 X

≈
 

Part of memory with 5 objects, 3 holes
   

Tick marks show allocation units Green regions are free

Copyright ©: University of Illinois CS 241 Staff

10

Storage Tracking Schemes
 

Bitmap vs. link list
 

Which one occupies more space?

 

Which one is faster to reclaim freed space?

 

Which oneis faster to find a free hole?

Copyright ©: University of Illinois CS 241 Staff

11

Storage Tracking Schemes
 

Bitmap vs. link list
 

Which one occupies more space?
   

Depends on the individual memory allocation scenario In most cases, bitmap usually occupies more space On average, bitmap is faster because it just needs to set the corresponding bits On average, a linklist is faster because we can link all free holes together

 

Which one is faster to reclaim freed space?
 

 

Which one is faster to find a free hole?
 

Copyright ©: University of Illinois CS 241 Staff

12

2. Storage Allocation Policies
 

Goals: Given allocation size:
   

Choose a large enough free region (hole) Assign part of that hole and “save” rest

 ...