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.

Practice

1. What is the main purpose of garbage collection in programming?

easy

A. To automatically free memory that is no longer used by the program

B. To speed up the execution of the program

C. To compile the program faster

D. To store data permanently on disk

Solution

1. Step 1: Understand what garbage collection does

   Garbage collection automatically frees memory that the program no longer uses, preventing memory waste.

2. Step 2: Compare options with this purpose

   Only To automatically free memory that is no longer used by the program describes this automatic freeing of unused memory, while others describe unrelated tasks.

3. Final Answer:

   To automatically free memory that is no longer used by the program -> Option A

4. Quick Check:

   Garbage collection = automatic memory freeing [OK]

Hint: Garbage collection frees unused memory automatically [OK]

Common Mistakes:

• Thinking garbage collection speeds up program execution
• Confusing garbage collection with compiling
• Believing garbage collection stores data permanently

2. Which of the following is a correct statement about garbage collection syntax in most programming languages?

easy

A. You declare garbage collection using gc start; in code

B. You must manually call a function named garbageCollect() to free memory

C. Garbage collection runs automatically without explicit syntax

D. Garbage collection is triggered by writing freeMemory() in the program

Solution

1. Step 1: Recall how garbage collection works in modern languages

   Most modern languages run garbage collection automatically without needing explicit calls or syntax.

2. Step 2: Evaluate each option

   Options B, C, and D suggest manual calls or commands that are not standard syntax; only A correctly states automatic operation.

3. Final Answer:

   Garbage collection runs automatically without explicit syntax -> Option C

4. Quick Check:

   Garbage collection = automatic, no manual calls [OK]

Hint: Garbage collection usually needs no manual commands [OK]

Common Mistakes:

• Assuming you must call garbage collection manually
• Looking for special syntax to start garbage collection
• Confusing garbage collection with memory free functions

3. Consider this pseudocode snippet:

var a = new Object()
var b = a
b = null
// Garbage collection runs here

Which object(s) will be collected by garbage collection?

medium

A. No objects will be collected because a still references the object

B. The object referenced by a and b

C. The object referenced by b only

D. Both a and b variables will be collected

Solution

1. Step 1: Analyze references to the object

   Initially, both a and b point to the same object. After b = null, only a references it.

2. Step 2: Determine if object is unreachable

   Since a still references the object, it is reachable and will not be collected.

3. Final Answer:

   No objects will be collected because a still references the object -> Option A

4. Quick Check:

   Object referenced = not collected [OK]

Hint: Object with any reference is not collected [OK]

Common Mistakes:

• Thinking object is collected when one reference is null
• Confusing variable collection with object collection
• Assuming variables themselves are garbage collected

4. Identify the error in this pseudocode related to garbage collection:

var x = new Object()
var y = x
x = null
// Garbage collection runs here
print(y.property)

What problem might occur?

medium

A. Syntax error due to missing garbage collection call

B. Runtime error because y is null

C. Garbage collector frees object causing y.property to fail

D. No error; object is still referenced by y

Solution

1. Step 1: Check references after x = null

   Even though x is null, y still references the object, so it remains reachable.

2. Step 2: Understand garbage collection behavior

   Garbage collection only frees objects with no references. Since y references the object, it won't be freed, so y.property is safe.

3. Final Answer:

   No error; object is still referenced by y -> Option D

4. Quick Check:

   Object referenced = no error [OK]

Hint: Object referenced by any variable is safe from collection [OK]

Common Mistakes:

• Assuming object is freed when one reference is null
• Expecting syntax error for missing manual garbage call
• Confusing variable null assignment with object deletion

5. In a program, you have a complex data structure where some objects reference each other in a cycle, but no external variables reference any of them. What will happen during garbage collection?

hard

A. Only some objects in the cycle will be collected, others remain

B. The cycle of objects will be collected because they are unreachable from outside

C. The cycle will never be collected because objects reference each other

D. Garbage collection will cause a runtime error due to the cycle

Solution

1. Step 1: Understand reachability in garbage collection

   Garbage collection frees objects unreachable from any external references, even if they reference each other.

2. Step 2: Apply this to cyclic references

   Since no external variables reference the cycle, the entire cycle is unreachable and will be collected.

3. Final Answer:

   The cycle of objects will be collected because they are unreachable from outside -> Option B

4. Quick Check:

   Unreachable cycles = collected [OK]

Hint: Unreachable cycles are collected despite internal references [OK]

Common Mistakes:

• Believing cycles prevent garbage collection
• Thinking only some objects in cycle are collected
• Expecting runtime errors from cycles