KOI: Some solutions to exercise 8

Please note that these are suggested solutions. There can be other solutions that are also correct.

Question 1

The memory

In the activation record for the function main there are two local variables (C calls them "variables with automatic storage"): k and m. In the activation record for g there is one parameter variable, h, and two local variables, i and p. The parameter variable h is just like a local variable, except that it gets its initial value from the argument in the function call. In the activation record for h there are two parameter variables, c and d, and two (normal) local variables, b and p.

Note that a local name hides a global name, so in the assignment of b in f the variable that is assigned is the local b. In the assignment of b in g there is no local b, so the variable that is assigned is the global b. (C calls "global" variables "variables with external storage".)

Question 2

a) The program no longer has a pointer to those memory areas, so we can't reach them, and we can't use them for anything. We can't even deallocate them, since we no longer have any pointers to them, and we would need those pointers when we call free.

b) The automatic garbage collector must have some way to go through all allocated memory areas. The heap management system (the system that handles calls to malloc and free) will have some sort of table or list of those areas, and the garbage collector could use that table or list. Then the garbage collector starts with the "root set", which consists of all directly accessible variables (the global variables and the variables on the stack), and it finds which areas on the heap are reachable from pointers in those variables, possible indirectly through other memory areas. Areas on the heap that are not reachable from the root set can't be reached from the program, and since they can't be reached, they can't ever again be used by the program, so they can be safely deallocated.

Question 3

a)

The memory

b)

The memory

The program continues to recursively call the function g. The figure shows the stack after two more calls to g. Execution will continue until the stack is full, and the program (probably) crashes. (C calls this "undefined behavior". Anything can happen.)

c) Yes. The recursive call to g in g is an example of tail recursion. A compiler that performs elimination of tail recursion, which gcc does with the flag -O2 or -O3, will remove the recursive call, and not allocate a new activation record on the stack. Since no more work needs to be done in the current activation of g, it can be re-used for the next activation of g, so there will only be a single activation record for g on the stack.

Question 4

a)

The memory

The reference variable h in main is not a pointer, but an alias for the variable c. The reference parameter r in f is an alias for b in main, and the reference parameter rp in f is an alias for e in main.


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) November 29, 2021