CS 354 - EXAM 2 STUDY GUIDE
Posix API - Answer -standard for maintaining comp. between different UNIX OS
brk - Answer -"program break" - OS's ptr to top of heap
sbrk - Answer -attempts to change the program's top of heap by incr bytes
Dynamically allocated memory - Answer -allocated during runtime to satisfy uncertain
memory needs (process data files/doc/images/spreadsheets)
Heap - Answer -- a segment of processes virtual addr space used for dynamically
allocated memory
- a collection of various-sized memory blocks that are managed by an allocator
Block - Answer -- contiguous chunk of memory
- contains payload and overhead
Payload - Answer -part of block that is usable by process
Overhead - Answer -part of the block that is used by allocator to manage heap
structure
Allocator - Answer -code that allocates and frees blocks as well as "splits" and
"merges" them
Throughput - Answer -- #of malloc and free ops/sec
- higher is better
- free O(1) independent of number of heap blocks
- malloc O(N) linearly dep. on # heap blocks
Memory utilization - Answer -- % of memory used for payload: mem-requests
- mem requests(bytes)/heap allocated(bytes)
- higher is better
Double word alignment - Answer -1) heap blocks size must be a multiple of 8
2) payload address must be word-aligned (multiple of 8)
External fragmentation - Answer -when there is enough free heap memory, but it is
divided into blocks that are too small to satisfy request
Internal fragmentation - Answer -memory in block is used as overhead instead of
payload
Size - Answer -# of bytes in heap block (payload + overhead)
, Status - Answer -whether block is allocated or free
Explicit free list - Answer -- allocator uses data structure that contains free blocks
- code: only need to track size of each block
- space(-): potentially more memory needed to store free list
- time(+): a bit faster since just searching through free blocks
Implicit free list - Answer -- allocator uses a "header" block as its D.S.
- code: must track size and status of each heap block
- space(+): potential less memory required
- time(-): more time needed to "skip over" allocated block; O(N) but more alloc. blocks
than free block, so N is larger
Placement policies - Answer -algorithms used to search heap for Free block to satisfy
request
First fit - Answer -- start from: beginning of heap
- stop at: first free block that is big enough
- fail if: END MARK is reached
- mem util(+): like to choose block close to desired size
- throughput(-): requests for large blocks must skip through many smaller blocks
Next fit - Answer -- start from: block most recently allocated
- stop at: first free block that's big enough
- fail if: start block is reached ("wrap-around")
- mem util(-): might choose a block that's too big
- throughput(+): faster than first fit since each request does not start at beginning
Best fit - Answer -- start from: beginning of heap
- stop at: END MARK, and choose block closest to desired size "big enough"
- stop early: if exact size match is found
- fail if: no block found that's big enough
- mem util(+): closest to best size
- throughput(-): slowest in general, since entire heap is searched
False fragmentation - Answer -when there is a large enough contiguous free space, but
it is divided into blocks that are too small to satisfy request
Immediate coalescing - Answer -do every time a block is free'd - check next + prev
block
Delayed coalescing - Answer -do only when needed to satisfy request for a larger block
Footer - Answer -contains size of free block
Pred - Answer -addr of prev free block
Posix API - Answer -standard for maintaining comp. between different UNIX OS
brk - Answer -"program break" - OS's ptr to top of heap
sbrk - Answer -attempts to change the program's top of heap by incr bytes
Dynamically allocated memory - Answer -allocated during runtime to satisfy uncertain
memory needs (process data files/doc/images/spreadsheets)
Heap - Answer -- a segment of processes virtual addr space used for dynamically
allocated memory
- a collection of various-sized memory blocks that are managed by an allocator
Block - Answer -- contiguous chunk of memory
- contains payload and overhead
Payload - Answer -part of block that is usable by process
Overhead - Answer -part of the block that is used by allocator to manage heap
structure
Allocator - Answer -code that allocates and frees blocks as well as "splits" and
"merges" them
Throughput - Answer -- #of malloc and free ops/sec
- higher is better
- free O(1) independent of number of heap blocks
- malloc O(N) linearly dep. on # heap blocks
Memory utilization - Answer -- % of memory used for payload: mem-requests
- mem requests(bytes)/heap allocated(bytes)
- higher is better
Double word alignment - Answer -1) heap blocks size must be a multiple of 8
2) payload address must be word-aligned (multiple of 8)
External fragmentation - Answer -when there is enough free heap memory, but it is
divided into blocks that are too small to satisfy request
Internal fragmentation - Answer -memory in block is used as overhead instead of
payload
Size - Answer -# of bytes in heap block (payload + overhead)
, Status - Answer -whether block is allocated or free
Explicit free list - Answer -- allocator uses data structure that contains free blocks
- code: only need to track size of each block
- space(-): potentially more memory needed to store free list
- time(+): a bit faster since just searching through free blocks
Implicit free list - Answer -- allocator uses a "header" block as its D.S.
- code: must track size and status of each heap block
- space(+): potential less memory required
- time(-): more time needed to "skip over" allocated block; O(N) but more alloc. blocks
than free block, so N is larger
Placement policies - Answer -algorithms used to search heap for Free block to satisfy
request
First fit - Answer -- start from: beginning of heap
- stop at: first free block that is big enough
- fail if: END MARK is reached
- mem util(+): like to choose block close to desired size
- throughput(-): requests for large blocks must skip through many smaller blocks
Next fit - Answer -- start from: block most recently allocated
- stop at: first free block that's big enough
- fail if: start block is reached ("wrap-around")
- mem util(-): might choose a block that's too big
- throughput(+): faster than first fit since each request does not start at beginning
Best fit - Answer -- start from: beginning of heap
- stop at: END MARK, and choose block closest to desired size "big enough"
- stop early: if exact size match is found
- fail if: no block found that's big enough
- mem util(+): closest to best size
- throughput(-): slowest in general, since entire heap is searched
False fragmentation - Answer -when there is a large enough contiguous free space, but
it is divided into blocks that are too small to satisfy request
Immediate coalescing - Answer -do every time a block is free'd - check next + prev
block
Delayed coalescing - Answer -do only when needed to satisfy request for a larger block
Footer - Answer -contains size of free block
Pred - Answer -addr of prev free block
