Transcript ppt

A Short Digression
Stacks and Heaps
CS-502, Operating Systems
Fall 2007
(Slides include materials from Operating System Concepts, 7th ed., by Silbershatz, Galvin, & Gagne and
from Modern Operating Systems, 2nd ed., by Tanenbaum)
CS-502 Fall 2007
Stacks and Heaps
1
Digression: the “Stack”
• Imagine the following program:–
int factorial(int n){
if (n <= 1)
return (1);
else
int y = factorial(n-1);
return (y * n);
}
• Imagine also the caller:–
int x = factorial(100);
• What does compiled code look like?
CS-502 Fall 2007
Stacks and Heaps
2
Compiled code: the caller
int x = factorial(100);
• Put the value “100” somewhere that
factorial can find
• Put the current program counter somewhere
so that factorial can return to the right place
in caller
• Provide a place to put the result, so that
caller can find it
CS-502 Fall 2007
Stacks and Heaps
3
Compiled code: factorial function
• Save the caller’s registers somewhere
• Get the argument n from the agreed-upon place
• Set aside some memory for local variables and
intermediate results – i.e., y, n - 1
• Do whatever it was programmed to do
• Put the result where the caller can find it
• Restore the caller’s registers
• Transfer back to the program counter saved by the
caller
CS-502 Fall 2007
Stacks and Heaps
4
Question: Where is “somewhere”?
• So that caller can provide as many
arguments as needed (within reason)?
• So that called routine can decide at run-time
how much temporary space is needed?
• So that called routine can call any other
routine, potentially recursively?
CS-502 Fall 2007
Stacks and Heaps
5
Answer: a “Stack”
• Stack – a linear data structure in which
items are added and removed in last-in,
first-out order.
• Calling program
• Push arguments & return address onto stack
• After return, pop result off stack
CS-502 Fall 2007
Stacks and Heaps
6
“Stack” (continued)
• Called routine
• Push registers and return address onto stack
• Push temporary storage space onto stack
• Do work of the routine
• Pop registers and temporary storage off stack
• Leave result on stack
• Return to address left by calling routine
CS-502 Fall 2007
Stacks and Heaps
7
Stack (continued)
• Definition: context – the region of the stack
that provides the execution environment of
a particular call to a function
• Implementation
• Usually, a linear piece of memory and a stack
pointer contained in a (fixed) register
• Occasionally, a linked list
• Recursion
• Stack discipline allows multiple contexts for the
same function in the stack at the same time
CS-502 Fall 2007
Stacks and Heaps
8
Stacks in Modern Systems
• All modern programming languages require
a stack
• Fortran and Cobol did not (non-recursive)
• All modern processors provide a designated
stack pointer register
• All modern process address spaces provide
room for a stack
• Able to grow to a large size
• May grow upward or downward
CS-502 Fall 2007
Stacks and Heaps
9
Process Address Space (Typical)
0xFFFFFFFF
stack
(dynamically allocated)
SP
Virtual
address space
heap
(dynamically allocated)
static data
0x00000000
program code
(text)
PC
See also Silbershatz, figure 3.1
CS-502 Fall 2007
Stacks and Heaps
10
Stacks in Multi-threaded Environments
• Every thread requires its own stack
• Separate from all other stacks
• Each stack may grow separately
• Address space must be big enough to accommodate
stacks for all threads
CS-502 Fall 2007
Stacks and Heaps
11
Stacks in Multi-threaded Address Space
thread 1 stack
SP (T1)
0xFFFFFFFF
thread 2 stack
SP
SP (T2)
thread 3 stack
SP (T3)
Virtual
address space
heap
static data
0x00000000
CS-502 Fall 2007
PC
PC (T2)
PC (T1)
PC (T3)
code
(text)
Stacks and Heaps
12
Stacks in Multi-threaded Environments
• Every thread requires its own stack
• Separate from all other stacks
• Each stack may grow separately
• Address space must be big enough to accommodate
stacks for all threads
• Some small or RT operating systems are
equivalent to multi-threaded environments
CS-502 Fall 2007
Stacks and Heaps
13
Heap
• A place for allocating memory that is not
part of last-in, first-out discipline
• I.e., dynamically allocated data structures
that survive function calls
• E.g., strings in C
• new objects in C++, Java, etc.
CS-502 Fall 2007
Stacks and Heaps
14
Process Address Space (Typical)
0xFFFFFFFF
stack
(dynamically allocated)
SP
Virtual
address space
heap
(dynamically allocated)
static data
0x00000000
program code
(text)
PC
See also Silbershatz, figure 3.1
CS-502 Fall 2007
Stacks and Heaps
15
Dynamically Allocating from Heap
• malloc() – POSIX standard function
• Allocates a chunk of memory of desired size
• Remembers size
• Returns pointer
• free () – POSIX standard function
• Returns previously allocated chunk to heap for
reallocation
• Assumes that pointer is correct!
CS-502 Fall 2007
Stacks and Heaps
16
Dynamically Allocating from Heap
• malloc() – POSIX standard function
• Allocates a chunk of memory of desired size
• Remembers size
• Returns pointer
• free () – POSIX standard function
• Returns previously allocated chunk to heap for
reallocation
• Assumes that pointer is correct!
• Storage leak – failure to free something
CS-502 Fall 2007
Stacks and Heaps
17
Heaps in Modern Systems
• Many modern programming languages
require a heap
• C++, Java, etc.
• NOT Fortran
• Typical process environment
• Grows toward stack
• Multi-threaded environments
• All threads share the same heap
• Data structures may be passed from one thread to
another.
CS-502 Fall 2007
Stacks and Heaps
18
Heap in Multi-threaded Address Space
thread 1 stack
SP (T1)
0xFFFFFFFF
thread 2 stack
SP
SP (T2)
thread 3 stack
SP (T3)
Virtual
address space
heap
Heap
static data
0x00000000
CS-502 Fall 2007
PC
PC (T2)
PC (T1)
PC (T3)
code
(text)
Stacks and Heaps
19
Stacks in Multi-threaded Address Space
thread 1 stack
SP (T1)
0xFFFFFFFF
thread 2 stack
SP
SP (T2)
thread 3 stack
SP (T3)
Virtual
address space
heap
static data
0x00000000
CS-502 Fall 2007
PC
PC (T2)
PC (T1)
PC (T3)
code
(text)
Stacks and Heaps
20
Questions?
CS-502 Fall 2007
Stacks and Heaps
21