Study Notes Runtime Environments

The allocation and deallocation of the data objects is managed by the run-time support package. The run-time support package is loaded together with the generated target code. The structure of the run-time support package depends on the semantics of the programming language (especially the semantics of procedures in that language).

Symbol Table

• Compiler uses symbol table to keep track of scope and binding information about names
• symbol table is changed every time a name is encountered in the source; changes to table occur
  • if a new name is discovered
  • if new information about an existing name is discovered
• Symbol table must have mechanism to:
  • add new entries
  • find existing information efficiently
• Two common mechanism:
  • linear lists, simple to implement, poor performance
  • hash tables, greater programming/space overhead, good performance
• Compiler should be able to grow symbol table dynamically
• if size is fixed, it must be large enough for the largest program

Procedure Activation

Each activation of a procedure is called as activation of that procedure. An execution of a procedure starts at the beginning of the procedure body. When the procedure is completed, it returns the control to the point immediately after the place, where that procedure is called. Each execution of the procedure is called as its activation.

• Lifetime of an activation of that procedure (including the other procedures called by that procedure).
• If a and b are procedure activations, then their lifetimes are either non-overlapping or are nested.
• If a procedure is recursive, a new activation can begin before an earlier activation of the same procedure has ended.

Activation Tree

We can create a tree (known as activation tree) to show the way control enters and leaves activations. In an activation tree

• Each node represents an activation of a procedure.
• The root represents the activation of the main program.
• The node a is a parent of the node b if and only if the control flows from a to b.
• The node a is left to the node b if the lifetime of a occurs before the lifetime of b.

Example:

Program main; enter main Procedure s; enter p Begin … end; enter q Procedure p; exit q Procedure q; enter s Begin...end; exit s Begin q; s; end; exit p Begin p;s; end; enter s exit s exit main

Control Stack

The flow of the control in a program corresponds to a depth first traversal of the activation tree that

1. Starts at the root.
2. Visits a node before its children.
3. Recursively visits children at each node and a left-to-right order.

• A stack called control stack can be used to keep track of live procedure activations.

1. An activation record is pushed onto the control stack as the activation starts.
2. That activation record is popped when that activation ends.

• When node n is at the top of the control stack, the stack contains the nodes along the path from n to the root.

Variable Scope

The scope rules of the language determine, which declaration of a name applies when the name appears in the program.

An occurrence of a variable is local, if that occurrence is in the same procedure in which that name is declared and the variable is non-local, if it is declared outside of that procedure.
Example: Procedure q; Var a: real; Procedure r; Var b: integer; Begin b=1; a=2; end; Begin…end; Variable b is local to procedure r and variable a is non-local to procedure r.

Storage Organisation

Storage Allocation Strategies

• Static allocation: lays out storage at compile time for all data objects
• Stack allocation: manages the runtime storage as a stack
• Heap allocation :allocates and de-allocates storage as needed at runtime from heap

Static allocation:

• Names are bound to storage as the program is compiled
• No runtime support is required
• Bindings do not change at run time
• On every invocation of procedure names are bound to the same storage
• Values of local names are retained across activations of a procedure
• Type of a name determines the amount of storage to be set aside
• Address of a storage consists of an offset from the end of an activation record
• Compiler decides location of each activation
• All the addresses can be filled at compile time
• Constraints:
  • Size of all data objects must be known at compile time
  • Recursive procedures are not allowed
  • Data structures cannot be created dynamically

Stack Allocation:

• Address can bind during run-time.
• Recursion supported
• Run time allocation supported but can not be managed explicitly.

Heap Allocation:

• Stack allocation cannot be used if:
  • The values of the local variables must be retained when an activation ends
  • A called activation outlives the caller
• In such a case de-allocation of activation record cannot occur in last-in first-out fashion
• Heap allocation gives out pieces of contiguous storage for activation records
• There are two aspects of dynamic allocation -:
• Runtime allocation and de-allocation of data structures.
• Languages like Algol have dynamic data structures and it reserves some part of memory for it.

Activation Record

Information needed by a single execution of a procedure is managed using a contiguous block of storage called activation record. When a procedure is entered, an activation record is allocated and it is deallocated when that procedure exits. Size of each field can be determined at compile time, although actual location of the activation record is determined at run-time.

Key Points

• If a procedure has a local variable and its size depends on a parameter, its size is determined at run-time.
• Some part of the activation record of a procedure is created by that procedure immediately after that procedure is entered and some part is created by the caller of that procedure before that procedure is entered.

You can follow the detailed champion study plan for GATE CS 2022 from the following link:

Detailed GATE CSE 2022 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU'S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series!(100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering

Thanks