Runtime Environment Practice Questions

Dynamic linking resolves dependencies at program execution time rather than at compile time. The operating system must locate these libraries using defined search paths, which are typically determined during this runtime phase. Attackers can exploit this by manipulating the search environment (e.g., modifying $LD\_LIBRARY\_PATH$) to force the loader to load a malicious library instead of the legitimate one. Because the final library path is not fixed until the program actually starts, the loader cannot guarantee the authenticity of the library beforehand. This reliance on runtime resolution creates a significant security vulnerability.

In C, each function call pushes a new activation record (stack frame) onto the runtime stack, with the stack frame for $main$ residing at the base. The number of activation records between the current function and $main$ corresponds directly to the depth of the call chain, which fluctuates dynamically according to the specific sequence of function calls executed at runtime. Since this depth depends solely on the execution path, option B is correct. Options A, C, and D are invalid because call depth is variable, global visibility is determined by lexical scope, and all recursive calls share the same stack.

The compilation process generates object code with placeholder or relative addresses, as the final memory locations are often unknown. Since a program must run at a specific location in main memory, the system uses relocation to adjust the instructions and data references to match the assigned load address. While symbol resolution identifies where symbols are located, relocation is the specific process that performs the actual modification of the code and data to ensure correct execution at the final memory address.

The relocation constant for the first module starts at memory offset $0$.
Subsequent constants are calculated by cumulatively adding the lengths of all preceding modules:
$R_1 = 0$
$R_2 = 0 + 200 = 200$
$R_3 = 200 + 800 = 1000$
$R_4 = 1000 + 600 = 1600$
The sequence of relocation constants is $0, 200, 1000, 1600$.

The partition size required to load an overlay program is determined by the path from the root to a leaf node that has the largest total memory requirement. We calculate the sum of sizes for each distinct path:

• Path Root $\rightarrow$ A $\rightarrow$ D: $2 + 4 + 6 = 12\text{ KB}$
• Path Root $\rightarrow$ A $\rightarrow$ E: $2 + 4 + 8 = 14\text{ KB}$
• Path Root $\rightarrow$ B $\rightarrow$ F: $2 + 6 + 2 = 10\text{ KB}$
• Path Root $\rightarrow$ C $\rightarrow$ G: $2 + 8 + 4 = 14\text{ KB}$
  The maximum size required among all paths is $\max(12, 14, 10, 14) = 14\text{ KB}$.

In languages with nested scopes, accessing non-local variables via static links requires traversing a chain of pointers, resulting in $O(n)$ access time. A $display$ is an auxiliary array of pointers where each entry $display[i]$ points to the activation record of the procedure at nesting level $i$. By utilizing this structure, the compiler can access non-local variables directly through array indexing, which reduces the access time to $O(1)$. This optimization addresses the inefficiency of static link traversal by providing immediate access to required scopes. Therefore, the structure described is known as a $display$.

In a resident-OS architecture, the system relies on a monitor to manage program execution. A Loader is the critical component responsible for transferring programs from secondary storage into main memory so they can be executed. Since the operating system must be capable of initiating program execution at any given moment, the Loader must reside in the main memory permanently. Conversely, an Assembler, Linker, and Compiler are transient utility programs that are only loaded into memory when their specific services are requested. Therefore, the Loader is the only component among the options that must be resident at all times.

Heap allocation manages memory for objects whose size and lifetime are not known at compile-time. Unlike stack allocation, which is limited to the scope of a function call, heap allocation allows data to persist beyond the function that created it. While recursion primarily uses the stack (via activation records) and dynamic scoping relates to binding rules, dynamic data structures (like linked lists or trees) require memory that can grow, shrink, and exist independently of the current call stack. Consequently, the flexible nature of dynamic data structures necessitates the use of a heap.

Static memory allocation requires that the size of all variables be known at compile time to fix their memory addresses. Since the array sizes in language $L$ are determined during runtime, static allocation is insufficient to manage this memory. However, a compiler can generate machine code that invokes dynamic memory allocation (e.g., via heap management or runtime stack adjustments) during execution to request the necessary space. Thus, compilers are fully capable of handling such requirements by utilizing dynamic memory allocation.

The fundamental role of a linker is to bind separate object files by resolving cross-module references. To achieve this, the linker must know which symbols (functions or variables) are defined in a specific module and where they are located. An object module therefore must include a symbol table containing the names and locations of all external symbols to allow the linker to perform address resolution and binding. While other components like machine code are present, the symbol table is the critical metadata required for the linker to successfully connect disjointed modules into a single executable.

System software components like text editors, assemblers, and linkers are transient utilities loaded into the main memory ($RAM$) only when specifically invoked by the user. The loader, however, is a critical system program responsible for mapping executable files from secondary storage into the main memory to facilitate program execution. Unlike the other utilities, the loader provides the essential interface for initializing and placing code within the $RAM$ so that the operating system can manage processes. Because the functionality of the loader is inherently tied to the requirement of managing code placement in the memory space for execution, it is the appropriate choice among the given options.

A link editor, commonly known as a linker, is a system utility that processes object files generated by a compiler or assembler. Its primary function is to resolve external references between independently compiled program modules. This process involves matching external names (symbols or function identifiers) defined in one module with their specific memory locations or addresses in other modules to create a single executable program or library. Options A and C relate to preprocessor or compiler-level tasks, while D and E are unrelated to the linker's core function.

Call by Name: The actual argument 'a[i]' is substituted textually for x. Inside P, x is textually replaced by a[i]:

Step 1: i = i + 1 → i becomes 2 (was 1)
Step 2: x = x + 1 becomes a[i] = a[i] + 1
Since i is now 2: a[2] = a[2] + 1 = 30 + 1 = 31

So a[1] remains 20, a[2] becomes 31.

This is the key subtlety of call by name - the argument is re-evaluated each time it is used. The change in i before using x means a[2] (not a[1]) is modified. Answer: A.

A: TRUE - In circular structures (e.g., A→B→A), both A and B have reference count ≥ 1 even if unreachable from roots, so they are never collected. Reference counting cannot handle cycles.
B: TRUE - Classic mark-and-sweep pauses all application threads while marking and sweeping (stop-the-world). Modern incremental/concurrent GCs reduce this pause but original mark-and-sweep does pause.
C: TRUE - Copying GC copies all live objects to a new memory space (to-space), automatically compacting them. The old space is completely freed, eliminating fragmentation.
D: TRUE - The generational hypothesis: most dynamically allocated objects become unreachable quickly. Generational GC exploits this by collecting the young generation (nursery) more frequently.
E: FALSE - Reference counting has overhead at EVERY pointer assignment (increment target's count, decrement old target's count), not just at allocation. This per-assignment overhead can be significant.

Internal Fragmentation: When an allocator gives a block LARGER than what was requested (e.g., request 25 bytes, given a 32-byte block → 7 bytes wasted inside the allocated block). The wasted space is internal to the allocated block. Common in fixed-size block allocators or when blocks are rounded to alignment boundaries.

External Fragmentation: Total free memory is sufficient, but it is scattered across many small non-contiguous holes. No single hole is large enough to satisfy the request. Common in variable-size allocation over time (allocate-free-allocate cycles create 'swiss cheese' memory).

Option D is partially true (rounding causes internal fragmentation) but incomplete. Option A is the complete and correct definition. Compaction reduces external fragmentation; slab/buddy allocation reduces internal fragmentation.

The runtime stack (call stack) grows with each function call. The most recently called function is at the TOP of the stack.

Execution sequence: global scope starts → outer() is called → inner() is called from inside outer().

At the moment inner() is executing:

• Bottom of stack: global activation record (first to be set up)
• Middle: outer()'s activation record
• Top: inner()'s activation record

From top to bottom: inner → outer → global. Answer: A.

Note: The access links follow the static scope: inner's access link → outer's AR; outer's access link → global AR. This allows a, b, c to all be resolved.

A: TRUE - The root always represents the main program's initial activation.
B: TRUE - Each call creates exactly one node; a procedure called k times creates k nodes.
C: TRUE - Children are ordered left-to-right based on the temporal order of calls during execution.
D: TRUE - The depth of the runtime stack at any point equals the depth of the current node in the activation tree. The MAXIMUM stack depth = height of the activation tree.
E: FALSE - A procedure never called has NO node at all in the activation tree (it's not even present, let alone a leaf).
F: TRUE - An activation is live (on the stack) for exactly as long as execution is within its subtree. When we enter the subtree, the activation is pushed; when we leave, it is popped.

Initial: x = 10

(i) Call by value: a gets copy = 10. Inside f: a=10+5=15, x=10+1=11, a=15+1=16. a is local, so x stays 11. Answer: x = 11.

(ii) Call by reference: a is an alias for x. a=a+5 → x=15; x=x+1 → x=16 (a also=16); a=a+1 → x=17. Answer: x = 17.

(iii) Call by value-result: Copy-in: a=10. Execute: a=10+5=15; x=10+1=11; a=15+1=16. Copy-out on return: x = a = 16 (overwrites x=11). Answer: x = 16.

Final: (i)=11, (ii)=17, (iii)=16. Option A.

In a stack-based model, activation records are pushed on call and popped on return. This works because normally, a callee's lifetime is contained within the caller's lifetime.

However, closures (functions that capture variables from their enclosing scope) can ESCAPE their defining scope - they can be returned from functions, stored in data structures, and called later. If the enclosing function has already returned (its stack frame popped), the closure still holds references to variables from that frame → those variables would be dangling.

Solution: Captured variables of closures must be allocated on the HEAP, not the stack. This is why languages with closures (Python, JavaScript, Haskell, Lisp) use heap allocation for captured variables or entire activation records, with garbage collection to manage lifetime.