Cs 431 Final Exam

Front 1

Activation Record

Back 1

Block of memory that stores the activation-specific data of a function.

-Return address, local variables, caller's activation record

Front 2

Static Activation Record Allocation

Back 2

-Efficient, simple
-Allocates record for each function before running
-Drawback: Can only run one instance (activation) at a time
-Recursion would overwrite data

Front 3

Dynamic Activation

Back 3

-Each instance has its own record
-Records pushed onto stack so function knows where to look (since dynamic, doesn't know where the instances will be)

Front 4

Nested Function Handling

Back 4

Uses a nesting link to store most recent activation of the calling function.

Front 5

Block Activation Records

Back 5

-Blocks inside functions (if,else,for,etc)
-could pre-allocated
-could extend the parent function's activation record
-could create own separate activation record

Front 6

Nesting Link

Back 6

Used to keep track of calling function by inner functions
- If calling top level, set to null
-If calling nested function from top level, set to caller's activation record
- If calling nested from nested, set to nested's nested link

Front 7

Function as Parameter

Back 7

Function will pass nested link of parametered functions activation record

Front 8

Long Lived Activation Records

Back 8

If activation record still has a link from some active function, cannot be deallocated from the stack. This allows the record to be called from later functions.

Front 9

Memory Stack Allocation

Back 9

-Uses One more word than requested
-Last word stores the previous top location so can return when deallocated

Front 10

Memory Heap

Back 10

A pool of blocks of memory with an interface for unordered allocation and deallocation

Front 11

First-Fit (Heap)

Back 11

-heap manager maintains linked list of free blocks
-For allocate, manager searches list for first block big enough for request
-To deallocate, returns block to front of list
-end of list denoted by -1 value

Front 12

Coalescing

Back 12

After deallocating from a heap, checks if adjacent blocks are also free and, if so, merges

Front 13

Quick Lists (Heap)

Back 13

-One list of free blocks are all small and same size (more popular). Use delayed coalescing.
-Other list of larger blocks, treated normally

Front 14

Delayed Coalescing (Heap)

Back 14

In a Quick List, deallocated blocks are not immediately coalesced. Only after certain threshold.

Front 15

Fragmentation

Back 15

Many disjointed allocated and unallocated blocks

Front 16

Heap Mechanisms

Back 16

Placement - Where to allocate blocks
Splitting - How to split up larger blocks
Coalescing - When and how to recombine

Front 17

Placement (Heap)

Back 17

First Fit
Best Fit
Next Fit
Can use balanced binary tree

Front 18

Splitting (Heap)

Back 18

Split to requested size
Split to bigger size
Round up to given multiple

Front 19

Coalescing (Heap)

Back 19

No coalescing - never
Eager coalescing - ASAP
Delayed coalescing - after run out of space

Front 20

Current Heap Links

Back 20

A memory location where a value is stored that the running program will use as a heap address

Front 21

Tracing current heap links

Back 21

-Start with root set (all memory locations, static variables, activation records that haven't returned. Not variables that cannot b used as heap address (ie int)
-do this for each memory location

Front 22

Errors in current heap links

Back 22

-Exclusion errors: mem location that is a current heap link, but left out
-Unused inclusion errors: mem location included, but never used by the program
-Used inclusion errors: mem location is included, but not used as a heap address

Front 23

Heap Compaction

Back 23

Defragment the heap

Front 24

Garbage Collection

Back 24

Automatically reclaims deallocated blocks
3 types
-Mark and sweep
-copying
-reference counting

Front 25

Mark and Sweep

Back 25

2 stage process
-Mark all live heap links and mark heap blocks linked to them
-Sweep through and return unmarked blocks to the pool
-Heap remains fragmented
-Resistant to both Inclusion Errors

Front 26

Copying Collection

Back 26

-Divides memory in half and uses one half at a time
-When one half becomes full, copies all live blocks to other half, compacting as it goes
-Deletes first half
-Sensitive to Used Inclusion Errors

Front 27

Reference Counting

Back 27

-Each block has a counter of heap links to it
-Increment when heap link is copied, decrement when discarded
-when count = 0, block is garbage and is released
-Does not use current heap links
-poor performance, cannot collect cycles

Front 28

Garbage Collecting Refinements

Back 28

-Generational: divide blocks according to age & collect younger blocks more often
-Incremental: Collect a little at a time

Front 29

Formal Parameter

Back 29

In the method definition, the parameter given that will exist in the body of the method

Front 30

Actual Parameter

Back 30

In the program, the parameter that is passed to the function or method.

Front 31

Positional Parameters

Back 31

How languages match up parameters. nth formal parameter matched with nth actual parameter

Front 32

Keyword Parameters

Back 32

Matches actual parameters to keywords of the function
ex) (DIVIDEND => x, DIVISOR => y)

Front 33

Optional Parameters

Back 33

Given default values if left blank
Good for shorthand of overloaded functions

Front 34

Unlimited Parameter Lists

Back 34

keyword ... indicates a variable amount of parameters

Front 35

Pass By Value

Back 35

Java
-formal parameter is just like a local variable in the activation record of the calling method, but it is initialized with the actual value of the actual parameter
-Actual value is not affected by method

Front 36

Pass By Result

Back 36

-Formal parameter starts uninitialized
-After method is run, final value of formal is assigned to actual

Front 37

Pass By Value-Result

Back 37

-formal is initialized with the value of the actual
-After method is run, final value of formal is assigned to actual
-1st half of Value, 2nd half of Result

Front 38

Pass By Reference

Back 38

-formal parameter is an alias for the actual parameter
-points to same memory location

Front 39

Pass By Macro Expansion

Back 39

-Define the macro
-Basic textual substitution

Front 40

Preprocessing

Back 40

-Replaces all macros with the code, replacing formals with actuals
-Each parameter is re-evaluated every time it is used

Front 41

Capture

Back 41

When a macro has a parameter passed to it that is the same name as a variable in the macro

Front 42

By Name

Back 42

Each actual is evaluated in the caller's context on every use of the formal parameter.
-Both lvalue and rvalue.

Front 43

By Need

Back 43

-like By Name, but only the first time
-after first assignment, used as local variable