dynamic storage

Question 1

dynamic storage allocation

Answer 1

run-time allocation of storage for variables, structures, procedure calls
most lang, total amount storage cannot be determined at compile time (except fortran)

Question 2

language features that require dynamic storage

Answer 2

• recursion
• pointers, explicit allocation
• dynamic data structs( list/dynamic arrays, trees, graphs)
• hof (lambda)

Question 3

heap space via free-list

Answer 3

• available blocks of storage chained together in linkedlist
• when block is needed, removed from FL
• when block is reclaimed, insert into FL

Question 4

disadvantage free list

Answer 4

• must search for block of right size
• fragmented memory
• expensive allocation, cheap reclamation

Question 5

heap pointer method

Answer 5

• maintain available space as contiguous block of byes
• similar to stack pter, points to next available byte
• when object allocated, HP bumped by object size

Question 6

disadvantages heap pointer

Answer 6

• requires compaction of live objects (pushing togeher)

- cheap allocation, expsensive reclamation

Question 7

gc task

Answer 7

• find block of storage for dead objects

- make storage available for use

Question 8

gc types

Answer 8

• 1. mark/sweep: det set of all LIVe objects

2. ref count - during execution determine when object dies

Question 9

mark/sweep live objects

Answer 9

• live means: pointer exists for x in activation record; register exists for x; object y in heap containing pointer to x and y is alive
• live objects found by graph traversal; start at root (local var on stack, global var, and registers)
• any object not reachable by root is dead

Question 10

mark/sweep gc

Answer 10

• each obj has mark bit
• heap filled, program suspended, gc starts
• traversal (mark phase). sweep for those not marked.

Question 11

mark/sweep disadvantage

Answer 11

• non compacting; use free list
• expensive allocation
• program suspension (stop and collect)

Question 12

copying gc

Answer 12

• two heaps (FROM and TO)
• obj allocated in FROM. when from fills up, gc starts
• traversal copies FROM to TO live objects
• space FROM vs TO flipped
• use heap pointer (use forwarding address) in old object

Question 13

fwding address vs ordinary pointer

Answer 13

fwding address is an address in TO space. no ordinary pter can point from FROM space into TO space

Question 14

disadvantage cc gc

Answer 14

• stop and copy

- heap half size, can occur twice freq (but space can be swapped to disk)

Question 15

ref counting

Answer 15

• ref count
• increment when copied
• decrement when object ref distroyed
• obj space reclaimed at rc = 0
• free list

Question 16

ref counting advantage

Answer 16

• storage reclaimation incremental

- not as long interruption

Question 17

ref counting disadvatage

Answer 17

• cycles (use backup m/s)
• hard to implement
• evey object have ref count; possible overflow

Question 18

compact m/s gc advan

Answer 18

• fast allocation use HP

- larger heap

Question 19

generational gc

Answer 19

• older object lives longer
• temp values live short
• global ilve long thus
• many heaps (with age)
• younger heap are gc more often
• when older gc filels up, then that gc will be collected

Question 20

m/s vs rc gc

Answer 20

m/s can collect cyclical structures

Question 21

cc gc vs m/s

Answer 21

cc is compact (use simple heap). cost of cc is proportional to size of live object. m/s/ proportional to size of heap.

Question 22

private type in ada

Answer 22

a type whose only operations are assignemnt (:=) and equality (=); users dont know about how it is implemented