Short Notes: Runtime Environments | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


It refers how do we allocate the space for the generated target code and the data 
object of our source programs? The places of the data objects that can be 
determined to compile time will be allocated statically. But the places for the some 
of data objects will be allocated at run-time.
The allocation and de allocation of the data objects is managed by the run-time 
support package. 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
o if a new name is discovered
° if new information about an existing name is discovered
• Symbol table must have mechanism to:
o 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
Page 2


It refers how do we allocate the space for the generated target code and the data 
object of our source programs? The places of the data objects that can be 
determined to compile time will be allocated statically. But the places for the some 
of data objects will be allocated at run-time.
The allocation and de allocation of the data objects is managed by the run-time 
support package. 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
o if a new name is discovered
° if new information about an existing name is discovered
• Symbol table must have mechanism to:
o 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
/ \
/ P \ ° 
q S
Activation tree
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
Page 3


It refers how do we allocate the space for the generated target code and the data 
object of our source programs? The places of the data objects that can be 
determined to compile time will be allocated statically. But the places for the some 
of data objects will be allocated at run-time.
The allocation and de allocation of the data objects is managed by the run-time 
support package. 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
o if a new name is discovered
° if new information about an existing name is discovered
• Symbol table must have mechanism to:
o 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
/ \
/ P \ ° 
q S
Activation tree
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.
DATA: Locations of static data can also be determined at compile time.
CODE: Memory locations for code that are determined at compile time.
STACK: Data Objects allocated at run time, supports recursion.
HEAP: Dynamically allocated object at run time, supports explicit allocation and 
deallocation of memory.
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:
Page 4


It refers how do we allocate the space for the generated target code and the data 
object of our source programs? The places of the data objects that can be 
determined to compile time will be allocated statically. But the places for the some 
of data objects will be allocated at run-time.
The allocation and de allocation of the data objects is managed by the run-time 
support package. 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
o if a new name is discovered
° if new information about an existing name is discovered
• Symbol table must have mechanism to:
o 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
/ \
/ P \ ° 
q S
Activation tree
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.
DATA: Locations of static data can also be determined at compile time.
CODE: Memory locations for code that are determined at compile time.
STACK: Data Objects allocated at run time, supports recursion.
HEAP: Dynamically allocated object at run time, supports explicit allocation and 
deallocation of memory.
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.
Return Value
Actual Parameters
Optional Control Link
Optional Access Link
Saved Machine Status
Local Data
Temporaries
Activation record
Return Value: The returned value of the called procedure is returned in this field to 
the calling procedure. We can use a machine register for the return value.
Page 5


It refers how do we allocate the space for the generated target code and the data 
object of our source programs? The places of the data objects that can be 
determined to compile time will be allocated statically. But the places for the some 
of data objects will be allocated at run-time.
The allocation and de allocation of the data objects is managed by the run-time 
support package. 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
o if a new name is discovered
° if new information about an existing name is discovered
• Symbol table must have mechanism to:
o 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
/ \
/ P \ ° 
q S
Activation tree
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.
DATA: Locations of static data can also be determined at compile time.
CODE: Memory locations for code that are determined at compile time.
STACK: Data Objects allocated at run time, supports recursion.
HEAP: Dynamically allocated object at run time, supports explicit allocation and 
deallocation of memory.
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.
Return Value
Actual Parameters
Optional Control Link
Optional Access Link
Saved Machine Status
Local Data
Temporaries
Activation record
Return Value: The returned value of the called procedure is returned in this field to 
the calling procedure. We can use a machine register for the return value.
Actual parameters: The field for actual parameters is used by the calling procedure 
to supply parameter to the called procedure.
Optional control link: The optional control link points to the activation record of the 
caller.
Optional access link: It is used to refer to the non-local data held in the other 
activation record.
Saved Machine Status: The field for saved machine status holds Information about 
the state of the machine before the procedure is called
Local data: Local data field holds data that is local to an execution of a procedure. 
Temporaries: Temporary variables are stored in field of temporaries.