{{ summaryTitle }}
{{ summaryValue }}

{{ summaryLine }}

Policy {{ resultsReady ? computation.values.simulation.algorithmLabel : '—' }} Largest hole {{ resultsReady ? formatUnits(selectedMetrics.largestHole) : '—' }} Alert {{ formatPercent(selectedMetrics.fragmentationRatio) }}

Allocation visual unavailable.

The same queue can produce different placements under each policy.
units
Enter a whole number from 1 to 4,096.
Syntax: O1 allocate A 25 or O6 free A. Use 1–12 rows.
The sample creates three differently sized holes before the final allocation.
{{ resultsReady ? `${selectedStep} / ${totalSteps}` : '—' }}
Step 0 is the initial free address space; later steps reveal placements, frees, and failures.
%
The neutral default is 0%, which disables the alert without changing the simulation.
Selected address map
Allocated
{{ formatUnits(selectedMetrics.totalAllocated) }}
Total free
{{ formatUnits(selectedMetrics.totalFree) }}
Largest hole
{{ formatUnits(selectedMetrics.largestHole) }}
External fragmentation
{{ formatUnits(selectedMetrics.externalFragmentation) }} · {{ formatPercent(selectedMetrics.fragmentationRatio) }}
Decision
{{ selectedDecision }}
Search path
{{ selectedSearchPath }}

The chart renderer is unavailable. The same values remain available in the operation ledger.

StepOperationOutcomePlacementFreeLargest holeCopy
{{ row.step }}{{ row.operation }}{{ row.success ? 'Applied' : 'Failed' }}{{ row.placement }}{{ row.totalFree }}{{ row.largestHole }}
Page Replacement Algorithm Simulator Compare four page-replacement policies with step-by-step frame traces and see how fault counts, hit ratios and frame capacity change.
CPU Scheduling Algorithm Simulator Compare CPU scheduling policies through dispatch traces and ready-queue decisions, including context-switch overhead and per-process timing metrics.
Banker's Algorithm Deadlock Avoidance Simulator Test Banker’s algorithm states and resource requests with step-by-step safety traces, safe-sequence witnesses, and rollback decisions.
Process Synchronization Simulator Trace producer-consumer and dining synchronization with repeatable mutex and semaphore evidence for blocking, wakeups, progress and deadlock.

A contiguous allocator must place each request into one uninterrupted run of free addresses. As allocations arrive and leave, the free space can split into holes of different sizes. The allocator may have enough free memory in total and still fail because no single hole is large enough.

Placement policy determines which suitable hole is chosen. First Fit accepts the first sufficient hole in address order. Best Fit prefers the smallest sufficient hole, hoping to leave larger spaces intact. Worst Fit takes the largest hole. Next Fit continues from a moving cursor and wraps to the beginning only after searching the later addresses.

Hole
A contiguous free block with a starting address and size.
External fragmentation
Free memory outside the largest hole. It measures how much free capacity cannot join the largest available request space.
Coalescing
Merging adjacent free blocks after a release so one larger hole becomes available.

No fit policy is universally best. A choice that saves space for the next request may create awkward holes for later requests, and a policy that scans less of one layout may scan more of another. Fair comparisons therefore replay the same ordered allocation and free requests from the same capacity.

This model isolates external fragmentation with whole-number addresses, one-unit alignment, and no allocator metadata. Real memory managers may add headers, alignment padding, size classes, compaction, paging, or noncontiguous virtual mappings. Those details can change both usable capacity and placement behavior.

How to Use This Tool:

Replay one operation queue under several policies and inspect the same trace step each time.

  1. Choose First Fit, Best Fit, Worst Fit, or Next Fit, then enter an Address-space capacity from 1 to 4,096 whole units.
  2. Enter 1 to 12 operation rows. Use O1 allocate A 25 to allocate and O6 free A to release an active allocation. Operation IDs must be unique, and an allocation ID cannot be reused later in the same queue.
  3. Move Trace step from the initial free address space through each placement, release, coalescing event, or failure. The selected address map and search path explain that step.
  4. Set a Fragmentation alert threshold only when a warning band helps the comparison. A value of 0% disables the alert; otherwise it appears when the selected ratio is greater than or equal to the threshold.
  5. Compare total free memory, largest hole, external fragmentation, and the operation outcome. Restore the same queue before switching policy.

Interpreting Results:

Total free answers how much unused capacity remains. Largest hole answers the largest single request that could fit at the selected step. Their difference is external fragmentation. A failed allocation with enough total free memory is therefore different from a failure caused by insufficient total free memory.

  • An Applied allocation names its exact address range; a release may also report adjacent boundaries that were coalesced.
  • An external fragmentation failure means total free memory is at least the requested size, but every contiguous candidate is too small.
  • An insufficient total free failure means even combining all holes would not satisfy the request.
  • The alert is a chosen teaching threshold, not a universal allocator health standard. Read it with the hole sizes and next expected request.

Technical Details:

The address space begins as one free block from 0 through capacity minus 1. Each successful allocation replaces part of a free block with an allocated block and preserves any free prefix or suffix. A successful release changes the matching block to free, then merges every adjacent free pair in address order.

Rule Core:

PolicyCandidate orderTie or cursor behavior
First FitFree holes in ascending address order.Select the first sufficient hole.
Best FitSmallest hole first.Equal sizes use the lower starting address.
Worst FitLargest hole first.Equal sizes use the lower starting address.
Next FitSearch from the cursor toward the end, then wrap to address 0.A successful allocation moves the cursor to the first address after it, modulo capacity; releases do not move it.

Every candidate records the address segment searched and whether it can hold the request. Next Fit may begin inside a hole when the cursor lies within it, leaving a free prefix before the placement.

Formula Core:

Let F be total free memory and H the largest free hole at the selected step. External fragmentation is the free memory outside that largest hole.

E=max0,F-H r=EFif F > 00if F = 0

The displayed percentage is 100 × r, rounded to one decimal place. The alert is active only when its threshold is above 0% and 100 × r is greater than or equal to that whole-percent threshold.

Failure and identity rules:

Allocation and operation IDs begin with a letter and may contain letters, digits, underscores, or hyphens. Allocation IDs are compared without case and remain reserved after being freed, so a later request cannot reuse one. Freeing an allocation that is not active records a failed operation without changing the address map.

Worked Examples:

Enough free memory, but no large-enough hole

Suppose a 100-unit address space has two free holes of 20 and 30 units. Total free memory is 50, the largest hole is 30, and external fragmentation is 20. A 40-unit allocation fails because neither hole is contiguous enough, even though the total free amount exceeds the request.

References: