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.

Practice

1. What is the main purpose of dynamic memory allocation in programming?

easy

A. To store program instructions permanently

B. To allocate memory only at the start of the program

C. To allocate memory during program execution as needed

D. To speed up the compilation process

Solution

1. Step 1: Understand dynamic memory allocation

   Dynamic memory allocation allows a program to request memory while it is running, not just before it starts.

2. Step 2: Compare with static allocation

   Static allocation reserves memory only at compile time or program start, unlike dynamic allocation which is flexible during execution.

3. Final Answer:

   To allocate memory during program execution as needed -> Option C

4. Quick Check:

   Dynamic allocation = allocate memory at runtime [OK]

Hint: Dynamic means memory allocated while program runs [OK]

Common Mistakes:

• Confusing dynamic with static allocation
• Thinking memory is allocated only once at start
• Assuming dynamic allocation speeds up compilation

2. Which of the following is the correct way to allocate memory dynamically in C language?

easy

A. int ptr = new int;

B. int ptr = malloc(int);

C. int *ptr = allocate(int);

D. int *ptr = malloc(sizeof(int));

Solution

1. Step 1: Recall C dynamic memory syntax

   In C, malloc is used with the size in bytes, e.g., malloc(sizeof(int)).

2. Step 2: Check each option

   int *ptr = malloc(sizeof(int)); uses correct syntax with pointer and malloc. Others use incorrect functions or syntax.

3. Final Answer:

   int *ptr = malloc(sizeof(int)); -> Option D

4. Quick Check:

   C malloc syntax = int *ptr = malloc(sizeof(type)) [OK]

Hint: malloc needs pointer and size in bytes [OK]

Common Mistakes:

• Using malloc without sizeof
• Assigning malloc result to non-pointer
• Using non-C functions like allocate or new

3. Consider this C code snippet:

int *p = malloc(3 * sizeof(int));
p[0] = 10;
p[1] = 20;
p[2] = 30;
printf("%d", p[1]);

What will be the output?

medium

A. 20

B. 10

C. 30

D. Runtime error

Solution

1. Step 1: Understand memory allocation and indexing

   Memory for 3 integers is allocated. Values assigned are p[0]=10, p[1]=20, p[2]=30.

2. Step 2: Identify printed value

   The printf prints p[1], which is 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   p[1] = 20 printed [OK]

Hint: Array index 1 holds second value assigned [OK]

Common Mistakes:

• Confusing p[0] with p[1]
• Expecting runtime error without free()
• Misunderstanding pointer indexing

4. Identify the error in this C code snippet:

int *ptr;
*ptr = 5;
ptr = malloc(sizeof(int));

medium

A. Memory is allocated after dereferencing pointer

B. malloc syntax is incorrect

C. Pointer is not declared

D. No error, code is correct

Solution

1. Step 1: Analyze pointer usage order

   The code dereferences ptr before allocating memory with malloc.

2. Step 2: Understand consequences

   Dereferencing an uninitialized pointer causes undefined behavior or crash.

3. Final Answer:

   Memory is allocated after dereferencing pointer -> Option A

4. Quick Check:

   Dereference before malloc = error [OK]

Hint: Always malloc before using pointer dereference [OK]

Common Mistakes:

• Ignoring pointer initialization order
• Thinking malloc syntax is wrong
• Assuming no error without free()

5. You want to store a list of names where the number of names is unknown at compile time. Which approach best uses dynamic memory allocation?

hard

A. Allocate a fixed-size array large enough for all names

B. Use malloc to allocate memory for each name as it is added

C. Declare all names as global variables

D. Use static arrays inside functions

Solution

1. Step 1: Understand problem requirements

   The number of names is unknown, so fixed-size arrays may waste memory or be insufficient.

2. Step 2: Choose dynamic allocation strategy

   Allocating memory for each name as it is added allows flexible, efficient use of heap memory.

3. Final Answer:

   Use malloc to allocate memory for each name as it is added -> Option B

4. Quick Check:

   Unknown size = allocate dynamically per item [OK]

Hint: Allocate memory as data arrives, not fixed size [OK]

Common Mistakes:

• Using fixed arrays wasting memory
• Declaring globals wastes flexibility
• Using static arrays limits size