CS 208 s21 — Learning Block #22

Which allocation strategy and requests remove external fragmentation in this heap?¹ B3 was the last fulfilled request.

1. best-fit: malloc(50), malloc(50)
2. first-fit: malloc(50), malloc(30)
3. next-fit: malloc(30), malloc(50)
4. next-fit: malloc(50), malloc(30)

What is the relationship between throughput and memory utilization?²

• section 9.9.12 walks through an implementation of an implicit free list
  • beware it is in 32-bit, and your will need to be in 64-bit (generally involves changing constants)
  • pay more attention to the text descriptions than the code
• use macros or helper functions like these for pointer manipulation
  • make sure you understand why these work/are necessary before you start coding

/* Round up size to the nearest multiple of 16 */
#define ALIGN(size) (((size) + (0xf)) & ~0xf)

#define WSIZE 8
#define DSIZE 16

/* Given block ptr bp, compute address of its header and footer (block pointer points to beginning of payload) */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))

• Allocator Policies
  • All policies offer trade-offs in fragmentation and throughput.
  • Placement policy:
    • First-fit, next-fit, best-fit
  • Splitting policy:
    • Always? Sometimes?
    • Be mindful of minimum block size—never split off a block smaller than the minimum
    • Which side of the split should the allocated block be on?
      • Left? Right? Alternate?
  • Coalescing policy:
    • Immediate vs. deferred

CSPP practice problem 9.7 (p. 852, 854)

Determine minumum block size for the following combinations of alignment requirements and block formats. Assumptions: implicit free list, zero-size payloads are not allowed, and headers and footers are stored in 4-byte words.³