2006-7-7
CP2003 -- Principles of Programming Languages 1997
This course (subject) comes frome http://www.cs.jcu.edu.au/Subjects/cp2003/1997/lecturenotes.html, and you can find something here http://www.cs.jcu.edu.au/Subjects/cp2003/1997, and of courses if you want more cs courses, goto http://www.it.jcu.edu.au/Subjects or http://www.cs.jcu.edu.au/Subjects.
下面我没有把所有内容都整理了，这是一部分我想记录下来的。
CP2003 Lecture Notes - Storage
We will use a very simple model of storage
-
a store is a collection of cells (or locations)
-
cell status - allocated or unallocated
-
cell value/content - defined or undefined
-
/* C example */
void main {
int x; /* allocate a cell for x */
/* value is undefined */
x = 1; /* value is 1 */
}
-
we won't worry too much about the fact that different primitive values have different sizes, each cell can contain a single value
-
the values, called storables, vary from language to language, but are basically values of some primitive type. In Pascal the storables include
-
integers, floats, characters, booleans
-
sets
-
pointers
but not
since the latter are composite types which have values that are (possibly) composed of a number of cells.
In Perl the storables include
-
integers, reals
-
strings
-
references
but not
But what about composite values?
-
occupy more than one cell
-
computer hardware/software geared towards efficient manipulation of single cells so typically can selectively update single cells of composite values
-
Can composite variables grow (to occupy more cells) during run time? Yes, it has been found to be useful, for example in the case of arrays in compiled languages. We distinguish three flavours of arrays.
-
static array - index set fixed at compile-time
/* Ada example */
type Vector is array [1..10] of Real;
var a : Vector;
a[1] := 3;
a[11] := 4; /* error out of bounds! */
-
dynamic array - index set fixed on creation of the array variable, i.e., this is what is done in PostScript
/* Ada example */
procedure curt(m : integer)
type Vector is array (Integer range <1..10>) of Real;
a : Vector (2..m); /* uses current value of m */
a[4] := 3; /* maybe out of bounds! */
a[11] := 4; /* error out of bounds! */
-
flexible array - the index set is not fixed at all!
/* Hypothetical Ada example */
procedure curt(m : integer) {
type Vector is array (Integer range <>) of Real;
a : Vector (1..3); /* size 3 array*/
a[4] := 3; /* increase size to 4 positions! */
a := (4=>3); /* or maybe special syntax to distinguish between
user wanting to increase the size of the array
and user referencing an out-of-bounds position */
Some languages, such as Perl and Icon, have flexible arrays!
-
birth - when allocated
-
death - when deallocated
-
lifetime - time between birth and death
-
run-time storage manager/memory manager
-
allocates objects
-
deallocates objects
-
garbage collects when memory becomes fragmented
-
static (global)
-
allocated once
-
lifetime is entire program
-
immortal, never deallocated
-
canonical example, global variables
-
dynamic (local)
-
allocated at run-time
-
lifetime is (possibly) brief
-
deallocated explicitly or implicitly
-
canonical example, local variables in subroutine
-
example
-
int x; /* static */
void main() {
int y; /* dynamic */
}
void foo(int z) { /* z is dynamic */
char ch[10000]; /* dynamic */
}
-
CP2003 Lecture Notes - Dynamic Storage
Heap vs. Stack
-
visual depiction of run-time storage
-
heap
-
freelist - list of free space
-
on allocation - memory manager finds space and marks it as used changing freelist
-
on deallocation - memory manager marks space as free changing freelist
-
memory fragmentation - memory fragments into small blocks over lifetime of program
-
garbage collection - coalesce fragments, possibly moving objects (must be careful of pointers when moving!)
-
stack
-
clean and efficient support for nested functions and recursion
-
central concept is stack frame (also called activation record), includes
-
visual depiction of frame
-
parameters
-
return address - where to begin execution when function exits
-
dynamic link - pointer to caller's stack frame
-
static link - pointer to lexical parent (for nested functions)
-
return value - where to put the return value
-
local variables
-
local work space - for temporary storage of results
-
function call - push stack frame
-
function exit - pop stack frame
-
visual depiction of stack calls
-
example
·
int x; /* static storage */
·
void main() {
·
int y; /* dynamic stack storage */
·
char *str; /* dynamic stack storage */
·
·
str = malloc(100); /* allocates 100 bytes of dynamic heap storage */
·
·
y = foo(23);
·
free(str); /* deallocates 100 bytes of dynamic heap storage */
·
} /* y and str deallocated as stack frame is popped */
·
·
int foo(int z) { /* z is dynamic stack storage */
·
char ch[100]; /* ch is dynamic stack storage */
·
·
if (z == 23) foo(7);
·
·
return 3; /* z and ch are deallocated as stack frame is popped,
·
3 put on top of stack */
}
-
at the start of the program
-
after the first call to foo
-
after the second call to foo
Dead Objects
-
storage objects in stack storage die (are deallocated) when the stack frame is popped.
-
storage objects in heap storage must be explicitly killed in C, but in other languages are implicitly killed when they are no longer referenced.
·
/* C example */
·
char *str;
·
str = malloc(100); /* allocate 100 byte storage object in heap storage
·
put the pointer to it into str */
free(str); /* kill the allocated storage object */
-
the freelist is a list of free areas in heap storage. When an object is allocated, the freelist is searched to find a big enough free area, and then the list is updated to mark that space as no longer free. When an object is killed, the space for the object is added to the freelist. Garbage collection coalesces the heap storage areas pointed to by the freelist.
-
dangling reference - pointer to a dead object
·
/* C example */
·
char *str;
·
str = malloc(100); /* allocate 100 byte storage object in heap storage
·
put the pointer to it into str */
·
free(str); /* kill the allocated storage object */
·
*str = 'h'; /* str is now a dangling reference! attempt to put
·
the character 'h' to what is pointed at by str,
but str points to a dead object */
Persistent Variables
A persistent varible is a variable that lives beyond the execution of a program.
> 这边文章主要讲了编程时候与内存分配相关的一些知识，可以看看上一篇讲stack和heap的文章。