Skip to question

Q290FreeSystemVerilog

Implement best-fit allocation

Difficulty: Medium
Topic: Memory Systems
Language: SV

Interview prompt

Question

Replace first-fit with best-fit: choose the smallest free range that can satisfy the request. Explain the one-line comparison change for worst-fit.

Four free-range capacities filtered against an allocation request before best-fit selection — Best-fit chooses the smallest eligible range; the chosen result is intentionally left for the exercise.

Starting point

Question code

function bit alloc_best_fit(
  int unsigned size,
  output int unsigned addr
);

Reviewed example

Trace one case

Input

free capacities=[64,24,40]; request size=20

Expected output

select the 24-byte range; leave a 4-byte remainder

All ranges are sufficient, but 24 is the smallest capacity and therefore the best fit.

What to cover

Requirements

Inspect all sufficient ranges.
Select the minimum sufficient capacity.
Preserve exact-fit and partial-fit behavior.
Avoid signed sentinels for unsigned capacities.

Continue practicing

Q212 · Memory SystemsBuild a first-fit range allocator Q276 · Memory SystemsRandomize free-range allocation Q291 · Memory SystemsReject invalid deallocation