Garbage collection basics in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ query_result

intermediate

Output of reference counting example

Consider a simple reference counting garbage collector. If an object has 0 references, it is collected. Given the following sequence:

1. Create object A
2. Create object B referencing A
3. Remove reference from B to A
4. Remove all references to B

How many objects remain after step 4?

A 1 object remains (A)

B 2 objects remain (A and B)

C 1 object remains (B)

D 0 objects remain

💡 Hint

Think about how reference counts change when references are removed.

When B removes its reference to A, A's reference count drops to 0, so A is collected. Then removing all references to B causes B's count to drop to 0, so B is also collected. No objects remain.

🧠 Conceptual

intermediate

Understanding mark-and-sweep phases

In a mark-and-sweep garbage collector, what is the main purpose of the 'mark' phase?

A To free all objects immediately

B To identify all objects that are still reachable

C To compact memory by moving objects

D To count references to each object

💡 Hint

Think about what the collector needs to know before freeing memory.

The mark phase traverses all reachable objects and marks them so they are not collected in the sweep phase.

📋 Factual

advanced

Identify error in pseudo-code for reference counting

Given this pseudo-code for decrementing reference count:

``` function decrement_ref(obj): obj.ref_count -= 1 if obj.ref_count == 0 free(obj) ```

What is the main problem with this code?

Compiler Design

function decrement_ref(obj):
  obj.ref_count -= 1
  if obj.ref_count == 0
    free(obj)

A free(obj) should be called before decrementing ref_count

B Should check if ref_count < 0 instead of == 0

C Missing colon after if statement causes syntax error

D No problem, code is correct

💡 Hint

Look carefully at the syntax of the if statement.

In many languages like Python, the if statement requires a colon at the end. Missing it causes a syntax error.

❓ optimization

advanced

Choosing a garbage collection strategy for cyclic references

Which garbage collection method can handle cyclic references without leaking memory?

A Mark-and-sweep

B Reference counting only

C Manual memory management

D Stack allocation

💡 Hint

Think about which method can detect unreachable cycles.

Reference counting cannot detect cycles because objects in a cycle keep each other's counts above zero. Mark-and-sweep can find unreachable cycles and collect them.

🔍 Analysis

expert

Debugging memory leak in reference counting

A program uses reference counting but has a memory leak. Which of these scenarios is the most likely cause?

A Objects form a cycle, keeping reference counts above zero

B Reference counts are decremented twice accidentally

C Objects are freed too early causing crashes

D Garbage collector runs too frequently

💡 Hint

Think about what reference counting cannot detect.

Reference counting cannot detect cycles where objects reference each other, so their counts never reach zero, causing leaks.