Title: CSE 351 23au / LS21 Memory Allocation II

Q: Provide the correct order for fulfilling an allocation request:
1. Search for a suitable free block using the allocator’s allocation strategy.
        - If found continue,
        - If not found, return NULL
2. Return the address of the beginning of the payload
3. Compute the necessary block size
4. Compare the necessary block size against the size of the chosen block
        - If equal, allocate the block
        - If not, split the excess into a new free block before allocating the block
A: 3, 1, 4, 2
- Compute the necessary block size.
- Search for a suitable free block using the allocator's allocation strategy.
  - If found, continue.
  - If not found, return NULL.
- Compare the necessary block size against the size of the chosen block.
  - If equal, allocate the block.
  - If not, split off the excess into a new free block before allocating the block.
- Return the address of the beginning of the payload.

Q: The smallest possible block that the allocator can/will allocate is known as the ___
A: minimum block size

Q: The allocation strategy that searches the free list from the beginning and returns the first free block that is large enough is known as ___ fit
A: first

Q: When searching an implicit free list, what two things need to be true to be suitable for allocation?
A: It has to be free because we cannot reallocate an allocated block
It has to be large enough to fit the necessary block size

Q: The allocation strategy that searches the free list from wherever it last left off is known as ___ fit
A: next

Q: True or false: The best fit allocation strategy searches the entire free list every time and picks the “best” allocation space according to different metrics
A: True

Q: Why is coalescing neighoring free blocks in a free list necessary?
A: When we deallocate a heap block that is next to a free block, the allocator will treat them as individual free blocks, rather than one large free block with the sum of their sizes.

Q: The act of combining neighboring free blocks into a singular larger free block is known as ___
A: Coalescing

Q: True or false: The footer is an exact copy of the header but located at the end of the heap block
A: True, it's used for forward and backward coalescing and for backward traversal

Q: What is the general term for the header and footer combined?
A: boundary tags