Dynamic memory allocation (heap) in Compiler Design - Step-by-Step Execution

Concept Flow - Dynamic memory allocation (heap)

Program requests memory

↓

Check heap for free block

↓

Allocate block

↓

Return pointer to program

↓

Program uses memory

↓

Program frees memory

↓

Heap marks block free

↓

Heap ready for next allocation

Shows how a program requests memory from the heap, the heap allocates or fails, and later frees memory for reuse.

Execution Sample

Compiler Design

1. Program calls malloc(20)
2. Heap finds free 20-byte block
3. Heap allocates block and returns pointer
4. Program uses memory
5. Program calls free(pointer)

This sequence shows a program requesting 20 bytes from the heap, using it, then freeing it.

Analysis Table

Step	Action	Heap Free Blocks	Heap Allocated Blocks	Pointer Returned	Notes
1	Program requests 20 bytes	[1000-2000]	[]	None	Initial heap has one free block from 1000 to 2000
2	Heap searches free blocks	[1000-2000]	[]	None	Found free block large enough
3	Heap allocates 20 bytes at 1000	[1020-2000]	[1000-1020]	1000	Allocated block from 1000 to 1020
4	Program uses memory at 1000	[1020-2000]	[1000-1020]	1000	Memory in use
5	Program frees memory at 1000	[1000-2000]	[]	None	Freed block merged back to free list
6	Heap ready for next allocation	[1000-2000]	[]	None	Heap restored to initial free state

💡 Program frees memory, heap returns to full free block state

State Tracker

Variable	Start	After Step 3	After Step 5	Final
Heap Free Blocks	[1000-2000]	[1020-2000]	[1000-2000]	[1000-2000]
Heap Allocated Blocks	[]	[1000-1020]	[]	[]
Pointer Returned	None	1000	None	None

Key Insights - 3 Insights

Why does the heap split the free block when allocating memory?

Because the requested size (20 bytes) is smaller than the free block (1000-2000), the heap splits it to allocate only the needed part (1000-1020) and keeps the rest (1020-2000) free, as shown in execution_table step 3.

What happens if the program frees memory that was never allocated?

This can cause heap corruption or errors because the heap expects only allocated blocks to be freed. The execution_table assumes correct free calls as in step 5 where the block is properly merged back.

Why does the heap merge adjacent free blocks after freeing?

To avoid fragmentation and keep larger continuous free blocks available. In step 5, the freed block merges with the adjacent free block, restoring the original free block from 1000 to 2000.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the size of the allocated block?

A 980 bytes

B 20 bytes

C 1000 bytes

D 2000 bytes

💡 Hint

Check the allocated block range in step 3: from 1000 to 1020 means 20 bytes.

At which step does the heap merge free blocks back together?

A Step 5

B Step 2

C Step 3

D Step 6

💡 Hint

Look at step 5 in execution_table where free blocks are combined.

If the program requested 500 bytes instead of 20 at step 1, how would the free blocks change after allocation?

A [1500-2000] and [1000-1500]

B [1000-1500]

C [1500-2000] only

D [1500-2000]

💡 Hint

Allocating 500 bytes from 1000 would leave free block starting at 1500, as per variable_tracker logic.

Concept Snapshot

Dynamic memory allocation uses the heap to provide memory at runtime.
Program requests size; heap finds or splits free blocks.
Heap returns pointer to allocated block.
Program uses and later frees memory.
Heap merges free blocks to reduce fragmentation.
Proper free calls prevent heap corruption.

Full Transcript

Dynamic memory allocation on the heap works by the program requesting memory of a certain size. The heap checks its free blocks to find a suitable space. If a large enough free block exists, the heap splits it to allocate only the requested size and returns a pointer to the program. The program uses this memory and later frees it. When freed, the heap marks the block as free and merges adjacent free blocks to keep memory contiguous and reduce fragmentation. This process repeats as the program runs, allowing flexible memory use. The execution table shows a step-by-step example of allocating 20 bytes, using it, and freeing it back to the heap.