01:198:214 Lecture Notes - Lecture 5: C Dynamic Memory Allocation
//-------Systems Programming Notes 10/12/17-------\\
//-------I am Malloc-------\\
First Fit - Find the first block that is free and is at least the size of the
storage request.
First fit.
Good time effciency, bad space effciency.
Best Fit - Best block free as close as possible as size of allocation
Good space effciency, Bad time effciency
Worst Fist - Scan the whole thing and find the biggest allocation and use that
Bad time effciency, Bad space effciency. WORST ALLOCATION ALGORITHM
EVER
We want to organize the memory so that first fit and best fit look similar.
//-------Buddy System Allocator-------\\
Continue breaking in half until you have a small enough size to store your
variable
it becomes a binary decision tree.
where the value at each step is the size of that block
h
| |
| |
split split
| | | |
| | | |
L R L R
Buddy System - Everybody has a Buddy
-Split successive chunks into halves ... recursively until you get a 'best
fit' availble based on:
-Minimal block size chosen
-Minimal power of 2 chosen
Internal Vs. External Fragmentation
Internal -
Free or wasted space within the allocation unit. Ask for 3 give me 5 (I
have 2 extra bytes not being used) byte padding for struct
A struct is at least the size of its parts
External -
Unused space inbetween blocks. Free or wasted space between allocation
units. ()
Link to how memory looks - duartes.org/gustavo/blog/post/anatomy-of-a-program-
in-memory/
//-------Realloc-------\\
realloc(void * ptr, size_t size);
"takes memory, finds a new size and then copys the current pointers information
to that address and at that location is as much information as denoted by
size_t. Then realloc frees the old memory"
0. Malloc(size);
1. memcpy(into what is above); is better than memmove look at manual and memcpy
has a size that way you dont go beyond your allocated amount of space
2. Free(ptr);
ptr = (type*) realloc(ptr....)
ptr* memory is slow and hasnt caught up to describe ptr and ptr gets reset
afterward
Saftey Net:
newptr = NULL;
newptr = (type*) realloc(ptr....)
if(newptr != NULL)
ptr = newptr;
//-------Memory is Slow-------\\
int write(fd,buff,10) returns the number of bytes that is has written
Blocking - Function they will keep running when the system stop giving it
run time and resume when given back
Non - Blocking - Will run until its run time is done then when it returns
and then it returns instead of resume (Lot of control, but a ton of managment)
|-> Sends status so you know what is done
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
First fit - find the first block that is free and is at least the size of the storage request. Best fit - best block free as close as possible as size of allocation. Worst fist - scan the whole thing and find the biggest allocation and use that. We want to organize the memory so that first fit and best fit look similar. Continue breaking in half until you have a small enough size to store your variable it becomes a binary decision tree. where the value at each step is the size of that block h split split. Split successive chunks into halves recursively until you get a "best. Buddy system - everybody has a buddy fit" availble based on: Free or wasted space within the allocation unit. Ask for 3 give me 5 (i have 2 extra bytes not being used) byte padding for struct. A struct is at least the size of its parts.
