Garbage Collection (L13)

Question 1

Which type of memory allocation must be explicitly handled by the programmer (or by GC)?

Answer 1

Dynamic.

Question 2

What is a memory leak?

Answer 2

Failure to reclaim unused, previously dynamically
allocated memory.

Question 3

What is the most fundamental, two phase garbage collection technique called?

Answer 3

Mark and sweep.

Question 4

What are tracing collectors?

Answer 4

These are a class of garbage collectors that identify/reclaim unreachable objects by tracing the program’s execution.

Question 5

What is the root set?

Answer 5

It is the initial set of objects that are directly accessible and serve as the starting point for marking all other reachable objects.

Question 6

What types of variables make up the root set?

Answer 6

Any global variables, and variables/references on the current call stack.

Question 7

Describe the mark phase of the mark and sweep algorithm.

Answer 7

Starting from the root set, all accessible objects in memory are looked at and marked as “in use” by setting a flag (if in use).

Question 8

When are in use flags cleared?

Answer 8

At the start of a GC cycle (prior to mark phase).

Question 9

Describe the sweep phase of the mark and sweep algorithm.

Answer 9

The GC cycles through all objects in the heap and, if their flags aren’t set, reclaims their memory.

Question 10

Does GC run continuously?

Answer 10

No, since it steals processing cycles away from the application.

Question 11

What is the most common strategy for choosing to invoke the garbage collector?

Answer 11

When memory is low.

Question 12

Can the GC be invoked on a predefined schedule?

Answer 12

Yes.

Question 13

In practice, when do (naive) mark and sweep algorithms begin to fail?

Answer 13

In large applications.

Question 14

What is the tri colour approach?

Answer 14

GC in which candidates for reclamation are iteratively moved between three sets until it is certain that they are no longer required.

Question 15

What is the generational technique?

Answer 15

GC in which the age of objects impacts the frequency of testing - older objects are likely long term and thus considered less.

Question 16

Is it possible to provide GC for languages like C?

Answer 16

Yes, using an external collector that the compiler does not need to directly support.

Question 17

Name an external GC that can be used by C?

Answer 17

Boehm GC.

Question 18

What algorithm does the Boehm GC use?

Answer 18

Mark and sweep.

Question 19

The Boehm GC is considered a black box, meaning what?

Answer 19

It is not integrated into the C compiler.

Question 20

The Boehm GC is conservative, meaning what?

Answer 20

It may have false negatives (items that could be reclaimed, but aren’t), but never has false positives (never reclaims items that shouldn’t be).

Question 21

Which function call does the BGC replace with its own version?

Answer 21

Stadard malloc calls - functionality remains the same, but BGC maintains additional information about all dynamically allocated memory.

Question 22

What memory regions are monitored by the BGC?

Answer 22

The stack frame and static region.

Question 23

BGC knows a word sized value on the stack isn’t a pointer value if it cannot be interpreted as what kind of address?

Answer 23

As a valid heap address.

Question 24

How do transient memory leaks occur?

Answer 24

Transient memory leaks occur when BGC interprets non-address values on the current stack frame as valid pointers.

Question 25

Why are transient memory leaks considered transient?

Answer 25

Transient as in temporary, and temporary because the memory leak is rectified once the stack frame ends.

Question 26

Why are transient memory leaks not common on modern 64 bit systems?

Answer 26

Because the heap represents a tiny portion of the total process space - it is thus unlikely for random sequences of bits to present a valid pointer.

Question 27

Why do performance sensitive systems use manual collection over GC?

Answer 27

Manual collection is faster and more predictable.

Question 28

What GC method does Python implement?

Answer 28

Reference counting.

Question 29

Describe reference counting.

Answer 29

References/assignments are kept track of, the memory they point to is reclaimed when none are left.

Question 30

Why are the issues with reference counting?

Answer 30

Cyclic references are difficult to detect, and lots of overhead due to constant count updates.

Question 31

Does reference counting fall under the umbrella of tracing collectors?

Answer 31

No.