Term
| What are the types of Data representation? |
|
Definition
- Primitive types (Boolean, char, byte, short)
- Enumerated types (Enum days {MON...SUN}
- Floating point types: Float (32 bits, 1st bit sign, 8 expnt, 23 mantissa) Double(64 bits, 1 - 11 - 52 )
- Record types: (Struct node{...})
- Pointer types (Struct node *p)
- Java objects
- Array types(node a[3])
|
|
|
Term
| What are some basic principles of array types? |
|
Definition
- Address computation: base + offset
- &a[i] = a + i * sizeof(node)
- node: possible alignment restrictions
- Multidimensional arrays:
- usually row-major // node a[n][m]
- address computation: base + offset
- &a[i][j] = a + (i*m+j)*sizeof(node)
|
|
|
Term
| What are some principles of object, class, inheritance and overriding representation? |
|
Definition
- Objects are
- Pointers to records
- Allocated on the heap
- Classes are
- Pointers to records
- Allocated statically
- Inheritance
- Extra fields appended to object and class-descriptors
- Overriding
- Overriding variable appended to object
- Overriding methods overwrites inherited method pointer in class descriptor
|
|
|
Term
| What are some principles of dynamic method invocation? |
|
Definition
- Class methods are static, resolvable at compile time
- Object methods are dynamic, not resolvable at compile time
- ...but their offset is always teh same in all class descriptors so always calls the right method
|
|
|
Term
| Show a representation of memory layout |
|
Definition
|
|
Term
| What are the principles of Static allocation? |
|
Definition
- Size(and position) must be known at compile time
- Mainly used for
- Program code
- Global variables
- Static variables (e.g. in C)
- Large constants(e.g. strings, blobs, ...)
- Some languages only use static allocation
- e.g. FORTRAN77
- no recursion
- no explicit allocation (malloc/free)
- "bad thing": no memory reuse between functions
|
|
|
Term
| What are activation records? |
|
Definition
- Data relevant to an activation (== individual call) of a function grouped together in one activation record:
- Parameters
- Local variables
- Temporary storage
- Housekeeping information
- Saved state, including return address
|
|
|
Term
| What are the principles of Stack allocation? |
|
Definition
- Problem with Recursion
- Multiple simultaneous activations of the same function
- Multiple activation records required
- Activation records created/discarded in LIFO order
- activations nested in time:
- p calls q -> activation of q must end before (or with) activation of p
- so store them in a stack
- Activation record on a stack == stack frame
|
|
|
Term
| What is the stack frame layout? |
|
Definition
|
|
Term
| What is the function call/return sequence? |
|
Definition
- Goal: pass parameters and results, hosue-keeping
- Split between caller and callee
- Maximize callee's part -> minimize code size
- Minimize memory traffic -> maximize speed
- Parameter(s) passed in registers unless:
- Too many parameters
- Too big for a register(floating point, arrays)
- Variable size (open arrays) /variable number
|
|
|
Term
| Show a diagram with an example of a function call/return sequence |
|
Definition
|
|
Term
| What are the Parameter Passing Mechanisms? |
|
Definition
- Call by value: Formal parameters act as local variable
- Pass copy of actual parameter
- Call by result: Formal parameter acts as local var
- Copied to actual parameter on return
- Call by value-result: copy-in, copy-out
- Result unique to caller, avoids aliasing
- Call by reference: formal parameter refers to caller
- Pass address of actual parameter
- Side efects and aliasing possible
- Call by name: Parameter not evaluated until required
- Pass address of evaluation function (thunk)
- Call by need: call by name with memoizing
- Only evaluated once(lazy evaluation)
|
|
|
Term
| How can access be granted to non-local data? |
|
Definition
- Restriction - no nested function declarations
- simplest solution (Chosen in C)
- Static links - frames contain pointer to frame of enclosing function
- Standard implementation technique
- Global displays - maintain array of pointers to frames active at different nesting levels
- Optimization of static links for deeply nested functions
- Lambda lifting - Turn non-local variables into additional parameters
- Common in functional languages
|
|
|
Term
| What are the downsides of accessing non-local data? |
|
Definition
- Accessiblity depends on static program structure...
- ...but correct frame position depends on dynamic excecution history...
- ...and cannot be determined at compile time
|
|
|
Term
| How to compute static links? |
|
Definition
- Simple Case: all calls explicit - No function variables
- computation depends on relation between nesting levels of caller x and callee y
- Complex case: function variables
- Many languages allow functions be passed as parameters:
- *int twice(int (*f) (int), int x) { return (*f) ((*f) (x)); };
- argument f is pointer to function with one int-argument returning int
- represented by entry-point (Address)
- no nesting, no problem
- Complex case II: Function variables + Nested scope
- Problem:
- Environment might use variables declared in outer scopes, but might be called completely outside of those scopes
- Solution:
- Pass the environment (static link) together with the function variable
|
|
|
Term
| What are the limits of stack allocation? |
|
Definition
- Stack allocation is fast
- Very large objects can cause too much "memory traffic"
- Size of data not known at compile time(open arrays)
- Cannot reserve space (Sometimes possible)
- Lifetime of data exceeds lifetime of creating function
- Function as return values
- Explicit creation/deletion of data objects and dynamic data structures (malloc+free)
|
|
|
Term
| What are the principles of heap allocation? |
|
Definition
- Heap == memory area for data with
- Unknown size
- Unknown lifetime
- Heap organization
- Memory divided into chunks (of different sizes)
- Aligned with OS memory pages
- Free list(s) pointing to available chunks
- Allocation: find "suitable" chunk, update free lists
- Usually: smallest possible, split larger chunks
- De-allocation: update free lists
- Might join smaller chunks
- "Never" return memory to OS
|
|
|
Term
| Give a comparison of Heap vs. Stack Allocation |
|
Definition
|
|
Term
| What is an example of fragmentation in heap management? |
|
Definition
- Initial heap:
- Three chunks of 2**(n+2) bytes each
- can be split into two equal chunks
- first fit search policy
- Memory allocation and deallocaiton causes chunks to be splitted and freed - internal fragmentation happens to the unused space
- Although it might seem there is enough space for a chunk, it might not fit due to fragmentation
|
|
|
Term
| How can fragmentation be countered? |
|
Definition
- internal: Split into unevenly-sized chunks
- Fibonacci heaps: H(n+2)=H(n+1)+H(n)
- Binning: Small sizes spaced tighter
- External: Use different search strategies
- First fit: take the first free chunk - easy+bad
- Best fit: Take smallest possible chunk - good
- Next fit: Take chunk closest to last one - locality
- External: Join adjacent free chunks
- Deferred join: Prevents repeated join/split cycles
- Buddy system: Only join chunks that were split together
|
|
|
Term
| What happens when the heap is full? |
|
Definition
- Increase heap size: Get more memory form OS
- Wilderness chunk of infinite size
- Compation: Move allocated memory to start of heap
- Difficult: find an adjust all pointers to heap items
- Often combined with garbage collection
|
|
|
Term
| What are the principles of garbage collection? |
|
Definition
- It is automatic de-allocation
- Reclaim heap memory that is no longer accessible
- Alternative to explicit(manual) de-allocation
- Avoids memory leakage and dangling pointers
|
|
|
Term
| What are some algorithms for Garbage collection? |
|
Definition
- Reference counting
- Slow and innefficient w cyclic data structures
- Maintain counter of references to objects
- de-allocate when reference counter==0
- Mark-and-sweep: two-phase algorithm
- Mark: Trace pointers from root set, mark objs
- Sweep: de-allocate unmarked objects
- Copy collection: Mark-and-sweep + Compaction
- Split heap into two semi-spaces, and compact on copy
- Generational Collection
- Not as efficient as most objects die young
- Split heap into generations
- Collect generation-by-generation until enough space
- Promote survivors to older generation
|
|
|
Term
| What are the principles of the Mark-and-sweep algorithm? |
|
Definition
- Garbage-collect:
- Mark all chunks as inaccessible
- Scan all global/static variables
- Scan all stack frames
- Add all chunks marked as inaccessible to free list(s)
- Scan storage region R:
- For each pointer p in R:
- If p points to a chunk c marked as inaccessible:
- Mark c as accessible;
- Scan c
|
|
|
