memory allocation schemes Flashcards
fixed length allocation scheme
memory is partitioned into blocks and we return an amount of blocks just large enough to accommodate the size of the request
variable length allocation scheme
give the amount of memory requested
fragmentation
things scattered in memory with small unusable gaps between them
how does fragmentation happen
when returning memory requests there may be amounts of memory between allocated memory which are too small to use and cannot be put together
defragmentation
shuffling code data etc to collect together unused space
why is defragmentation on ram difficult
we dont have enough understanding of what the apps are doing; programs store memory references anywhere e.g. registers, variables
why can defragmentation work with disks
we have more controlled access to memory due to file systems that structure and control whats stored
can understand internals and ensure consistency
what are the 3 different types of variable allocation scheme
first fit (+ next fit)
best fit
worst fit
first fit (variable allocation scheme)
scan the free list to find the first area of memory sufficient to serve the request
what is the variation of first fit (+ explain)
next fit; dont start at the beginning each time but continue the search from where you last served the request
best fit (variable allocation scheme)
scan the entire free list to find the first free area that is just sufficient to serve the request
basically the smallest size possible
worst fit (variable allocation scheme) and what is the point of it
go for the largest space you can find as it maximises the chance that any excess returned will be sufficient to hold another request; trying to minimise fragmentation
external fragmentation
free memory external to the request; space left between allocated memory (variable allocation scheme)
internal fragmentation
in fixed allocation; we usually round up the memory to a fixed size the app will usually have more memory than requested
how does internal fragmentation control fragmentation
the amount of fragmentation is bounded by the size of the blocks of memory created and the lifetime of the process/ allocation period
once the memory is returned its always in complete blocks of free memory
why do we use the buddy allocation scheme
we want to make sure that allocations in memory are continuous so pages allocated to the same thing are sat adjacent in memory
how does the buddy allocation scheme work
an area of memory that is the size of multiple pages can be divided into exactly two buddies as they come from the same parent block
they can be split multiple times to get a size just sufficient enough for the request
what are restrictions when freeing buddy allocation spaces
cant combine blocks with different parents
slab allocation
allocates memory while layering another allocation scheme on top
how doe slab allocation work
- the chosen scheme returns memory which is then split into slabs formed form memory areas with uniformed size suited to the object requested/ particular app
- we allocate space for multiple objects at once therefore we always know we can free and reuse the spaces returned
- each slab maintains a free list
what do we base object allocation on in slab allocation
size
word/cache alignment
guard spacing to catch overruns
word/cache alignment + benefit (slab allocation scheme)
have to consider the way the object would sit in cache memory as we want objects that would fit within the natural cache lines
by scaling the objects we can make more efficient use of the cache
guard spacing to catch write overruns (slab allocation scheme)
add guard memory so if an application strays beyond the given allocation it doesnt corrupt adjacent objects
