Heap

Question 1

Heap Memory Management

1. Explicit memory management is essentially required for languages that allow users to access memory directly.
   (a) [3pts] What allocator do these algorithms typically use?

Answer 1

*-fit allocation

Question 2

(b) [3pts] Why is garbage collection ineffective for these languages?

Answer 2

You can’t rearrange memory after allocating, as that would invalidate pointers given to the user

Question 3

2. A user allocates five variables: a, b, c, d, and e, so that they are allocated on the heap as such: a b c d e
   (a) Later, she frees()’s b. After the free, what happens
   i. [2pts] to a?
   ii. [2pts] to c?

Answer 3

i. [2pts] to a?

Nothing, other pointers should not change in explicit memory management

ii. [2pts] to c?

Nothing, other pointers should not change in explicit memory management

Question 4

Heap Memory Management
1. [3pts] When we studied automatic memory management, we discussed three algorithmic components that make up all implementations of automatic memory managers. What were they?

Answer 4

Allocation
Identification
Reclamation

Question 5

2. [3pts] We also discussed how explicit pointers reduce the ability of a system to perform automatic memory management. Why?

Answer 5

The addresses of the pointers cannot be altered because they are in use by the user.

Question 6

3. [4pts] Name and describe one copying garbage collector.

Answer 6

Mark-Compact: Trace the heap for unreachable objects when the entire heap fills up and then apply compaction to move all the objects together to the beginning of the heap.

Semi-space - Split the heap into two parts (to and from space) and when one part fills up, copy all reachable objects into the other half and reclaim all the memory in the from space.

Question 7

1. In explicit memory management, who is responsible for:
   (a) [2pts] allocating memory?

(b) [2pts] deallocating memory?

Answer 7

(a) [2pts] allocating memory?

User

(b) [2pts] deallocating memory?

User

Question 8

2. In automatic memory management, who is responsible for:
   (a) [2pts] allocating memory?

(b) [2pts] deallocating memory?

Answer 8

(a) [2pts] allocating memory?

User

(b) [2pts] deallocating memory?

Runtime system / garbage collector

Question 9

Heap Memory Management
1. In class, we studied both explicit and automatic memory management.

(a) [4pts] In explicit memory management, we recommend that you assign NULL to freed pointers. Why?

Answer 9

This is so that we do not accidentally refer freed memory locations in the future. If we do so, we would get an exception stating dereferencing a null pointer which is easier to fix than find memory errors caused by accessing unmapped memory.

Question 10

(b) [4pts] In automatic memory management systems, the runtime system manages the pointers and the users are not given access to them. Why?

Answer 10

So we can rearrange memory to reduce fragmentation.

Question 11

2. As part of automatic memory management, we studied the interactions between two allocators, free list and bump pointer, and two reclamation algorithms, mark-sweep and mark-compact.
   (a) [4pts] Which allocator is used by the mark-sweep algorithm? Why is it an appropriate choice?

Answer 11

Free list - it is appropriate because it does not perform copying. In such a case if bump pointer is used, we may lose freed space.

Question 12

(b) [4pts] Which allocator is used by the mark-compact algorithm? Why is it an appropriate choice?

Answer 12

Bump pointer - it is appropriate because we will be copying memory to the front of the heap on garbage collection, so bump pointer allows us to quickly allocate

Question 13

Heap Memory Management

1. [3pts] Where is heap management implemented?

Answer 13

Heap management is implemented by the runtime system of a process.

Question 14

2. [2pts] Which allocator should a copying garbage collector use? Defend your answer.

Answer 14

Bump pointer, because we can copy memory to the beginning of the heap, we can always allocate in order using a bump pointer to increase performance

Question 15

3. [3pts] What happens if multiple processes try to dynamically allocate memory in the heap at the same time?

Answer 15

Each process has its own heap.

Question 16

Heap Memory Management

Automatic memory management has three main algorithmic components: allocation, identification, and reclamation.

1. [4pts] Name two allocation techniques and an advantage and disadvantage of each.

Answer 16

Free List:
Non-copying (adv)
Slow allocation

Bump Pointer:
Fast allocation, good contemporaneous locality.
Does not reuse freed memory.

Question 17

2. In the identification step, we identify garbage.

(a) [2pts] Since we’re not actually just pointing to a trash can, how do we define garbage?

Answer 17

Unreachable objects

Question 18

(b) [2pts] Name and describe (in twenty words or less!) two identification techniques.

Answer 18

Reference counting - count references to objects on the heap, and if the count is zero, reclaim the object.

Tracing - trace from the program’s roots (registers, stack, SDS) to find all of the reachable objects, and reclaim unreachable objects.

Question 19

3. Because you love Pintos so much, you found your first job as a systems programmer. Your first task is to write a garbage collector for the new runtime system for your company. There are two main factors that you need to consider: your client dynamically allocates a lot of memory and your client wants to have efficient use of the heap.
   (a) [2pts] Which garbage collection algorithm would you want to implement and why is it good for this purpose?

Answer 19

Mark-sweep - the algorithm is non-copying so overhead during reclamation is small. Can perform incremental reclamation too.

Question 20

(b) [3pts] Now your client also wants to have good locality in the heap, would you change your choice of algorithm? If so, to what and why? If not, why not?

Answer 20

Yes, mark-sweep has dummy bad locality so I would change it to something like mark-compact, which has good contemporaneous locality

Question 21

Heap Memory Management
Heap memory managers fall into two categories: explicit memory managers and automatic memory managers, the latter of which is also known as garbage collectors.

1. [3pts] What is the heap? What sort of data does it contain? Who manages it?

Answer 21

The heap is an area of a process’ address space for dynamically allocated data. It is managed by the runtime system.

Question 22

2. [2pts] Garbage collectors are made possible due to “safe pointers”. What are safe pointers?

Answer 22

Safe pointers are pointers that are not given to the user.

Question 23

3. [2pts] What are unsafe pointers? Why are they called unsafe?

Answer 23

Unsafe pointers are pointers where the user can do direct address manipulation. They are unsafe because the user is allowed to do whatever they want to their address space.

Question 24

4. [2pts] We discussed two potential allocation algorithms: bump pointer and free list. We determined that bump pointer was faster, though free list had the benefit of space reuse.
   When choosing a free spot using free-list allocation, what are some possible algorithms that the system might choose? Name two.

Answer 24

Best Fit, Worst Fit, First Fit, Next Fit

Question 25

5. [4pts] Now consider an application that has many short-lived functions and it allocates lots of dynamic data in each function. It does not pass that data out of the function. Which garbage collection algorithm would you select for that application? Defend your answer.

Answer 25

Generational, lots of short-lived data (most objects die young)