Run-time Environment and Memory Allocation

60 mins

Understand how compiled code behaves in memory during execution. Covers Activation Records, parameter passing mechanisms, dynamic memory concepts, scope vs lifetime, procedure activation tracing, and value return mechanisms.

Learning Goals

Describe the complete runtime memory layout: Code Segment, Static/Global Data, Stack, and Heap.
Define Activation Records (Stack Frames) and detail their internal structure (return value, parameters, links, local data).
Trace the push/pop of activation records for recursive function calls using StepByStepBlock.
Explain how a function returns a value via the Return Value field in the activation record.
Distinguish between Scope (compile-time visibility) and Lifetime (runtime storage duration) with examples including static locals.
Compare parameter passing mechanisms: Call-by-Value, Call-by-Reference, Call-by-Name, and Call-by-Need.
Understand Dynamic Memory concepts, including Heap Allocation, Dangling References, and Garbage Collection.
Compare Absolute Loader, Relocatable Loader, and Dynamic Linking Loader schemes.
Differentiate between Dynamic Link and Static Link in an activation record.
Write a comprehensive short note on Activation Records as frequently required in exams.

Runtime Memory Layout

When a program runs, the operating system allocates several distinct regions of memory, each serving a different purpose:

Region	Contents	Growth	Lifetime
Code Segment	Compiled machine instructions	Fixed	Entire program
Static/Global Data	Global and static variables	Fixed	Entire program
Stack	Activation records (function calls)	Downward (↓)	Function duration
Heap	Dynamically allocated objects (`malloc`, `new`)	Upward (↑)	Until explicitly freed

The Stack and Heap grow toward each other. If they collide, the program runs out of memory — this is called stack overflow (for the stack) or heap exhaustion (for the heap).

In an Absolute Loading scheme, the compiler or programmer assigns fixed, hardcoded memory addresses. The loader simply copies the executable into those exact locations.

Pros: Extremely fast loading, minimal loader complexity. Cons: Cannot relocate programs; prevents multitasking; conflicts if two programs use the same addresses.

Used in simple embedded systems where only one program runs at a time.

The Activation Record (Stack Frame)

Whenever a function is called, a block of memory is pushed onto the Run-Time Stack. This block is called an Activation Record (also called a Stack Frame). It contains all the context the function needs to execute and return properly.

Structure of an Activation Record:

Each field holds specific data during a function call. Consider the call result = add(5, 3) from main():

Field	Purpose	Example Value
Return Value	Space for the function's output	`8` (computed by `add`)
Actual Parameters	Arguments passed by the caller	`5` and `3`
Control (Dynamic) Link	Pointer to caller's AR	Address of `main`'s AR
Access (Static) Link	Pointer to lexical parent's AR	Address of `main`'s AR (if `add` is nested inside `main`)
Saved Machine Status	CPU registers + return address	PC = address in `main` after call
Local Data	Local variables declared in function	`int sum;` inside `add`
Temporaries	Intermediate computation results	Temporary register for `5+3`

Accessing Variables

How does the CPU actually find your variables in memory?

Local Variables: Accessed via fixed offsets from the Stack Pointer (SP). If int x is the first local variable, the compiler generates code like LOAD SP + 8.
Global / Non-Local Variables: The compiler uses the Access (Static) Link to walk up the chain of activation records until it finds the frame where the global/parent variable is stored. This is called access chaining — if a variable is $k$ scopes away, the static link is followed $k$ times.

Procedure Activation Trace: factorial(3)

Step 1

main() calls factorial(3). The stack gets a new activation record:

| factorial(3) AR         |
|  n = 3                  |
|  return addr = main     |
|  dynamic link → main AR |

Step 2

Inside factorial(3), the recursive call factorial(2) is made. Stack now has two ARs:

| factorial(2) AR            |
|  n = 2                     |
|  return addr = fact(3)     |
|  dynamic link → fact(3) AR |
| factorial(3) AR            |
|  n = 3                     |
|  return addr = main        |
|  dynamic link → main AR    |

Step 3

factorial(2) calls factorial(1). Stack now has three ARs:

| factorial(1) AR            |
|  n = 1                     |
|  return addr = fact(2)     |
|  dynamic link → fact(2) AR |
| factorial(2) AR            |
|  n = 2                     |
|  return addr = fact(3)     |
|  dynamic link → fact(3) AR |
| factorial(3) AR            |
|  n = 3                     |
|  return addr = main        |
|  dynamic link → main AR    |

Step 4

The base case n <= 1 is true. factorial(1) writes 1 into its Return Value field and pops its AR. Stack shrinks:

| factorial(2) AR            |
|  n = 2                     |
|  return addr = fact(3)     |
|  dynamic link → fact(3) AR |
| factorial(3) AR            |
|  n = 3                     |
|  return addr = main        |
|  dynamic link → main AR    |

Step 5

factorial(2) receives return value 1, computes 2 * 1 = 2, writes 2 into its Return Value field, and pops its AR. Stack shrinks:

| factorial(3) AR         |
|  n = 3                  |
|  return addr = main     |
|  dynamic link → main AR |

6
Step 6
factorial(3) receives return value 2, computes 3 * 2 = 6, writes 6 into its Return Value field, and pops its AR. The stack returns to only main's AR. The final result 6 is available to main.

Value Return Mechanism

When a function returns a value, a precise protocol is followed between the caller and callee using the activation record:

Detailed flow:

The caller pushes a new activation record onto the stack, including space for the Return Value field (initially empty/uninitialized).
The caller saves its current program counter in the Saved Machine Status field, then jumps to the callee.
The callee executes its function body, computing the result.
Before returning, the callee writes the computed result into the Return Value field of its own AR.
The callee restores the machine status and jumps back to the saved Return Address.
The caller reads the Return Value from the (now-popped) AR and continues execution.

For functions returning large structures (e.g., in C++), the caller may allocate hidden space on its own stack frame for the return value, and the callee writes directly into that space.

Scope is a compile-time concept. It defines the region of program text where a name (variable, function) is visible and can be referenced.

Local Scope: A variable declared inside a function is visible only within that function's body.
Global Scope: A variable declared outside all functions is visible throughout the entire program.
Block Scope: A variable declared inside a { } block (e.g., inside a for loop) is visible only within that block.

Scope is determined entirely by the lexical structure of the program — where the declaration appears in the source code. It has nothing to do with runtime execution.

Scope vs Lifetime — Key Exam Concept

A static local variable has scope limited to the function body (only visible inside that function), but lifetime spanning the entire program execution (memory persists between calls). This is the classic example where scope and lifetime diverge — a distinction frequently tested in compiler design examinations.

Scope vs Lifetime Examples

Variable Type	Scope	Lifetime	Storage
`int x;` (local)	Function body	Function execution	Stack
`static int x;` (local)	Function body	Entire program	Static data segment
`int x;` (global)	Entire program	Entire program	Static data segment
`int *x = malloc(...);`	Block where pointer is declared	Until `free(x)` is called	Heap

Consider this example:

1void counter() {
2    static int count = 0;  // scope: counter() body only
3    count++;               // but lifetime: entire program
4    printf("%d\n", count);
5}

Calling counter() three times prints 1, 2, 3. The variable count retains its value between calls because its lifetime persists, even though its scope is limited to counter().

The calling function passes a copy of the variable's value. The callee receives a new storage location containing the copied value.

1void addOne(int x) {
2    x = x + 1;
3}
4int main() {
5    int a = 5;
6    addOne(a);
7    // a is still 5. The copy was modified, not the original.
8}

Pros: Safe — caller's data cannot be accidentally modified. Cons: Copying overhead for large structures; callee cannot modify caller's variables.

Dynamic Memory Management

While Activation Records handle local variables (Stack memory), the compiler also manages the Heap for data whose size or lifetime is not known at compile time.

Heap Allocation: Required for languages that allow dynamic data structures (Linked Lists, Trees, Dynamic Arrays) where memory must be allocated at runtime using malloc, calloc, or new, and freed manually using free or delete.
Dangling References: A critical memory error where a pointer still holds the address of deallocated storage. Accessing such a pointer causes undefined behavior or runtime crashes.
Garbage Collection: In languages like Java, Python, and C#, the runtime system automatically tracks references and reclaims unreachable heap objects. Common algorithms include Mark-and-Sweep (mark all reachable objects, sweep the rest), Reference Counting (free when count hits zero), and Generational GC (frequent collection of young objects).

Common Questions on Activation Records & Runtime Environment

Knowledge Check

Question 1 of 6

Q1Single choice

Which field of the activation record points to the activation record of the calling procedure?

Static Link

Dynamic Link

Return Address

Local Data

Activation Records and Stack Frames — GeeksforGeeks

web

Symbol Table Management

Semantic Analysis and Type Checking