2013-11-30

stackless mem'mgt

9.3: adda/mem'mgt/stackless:
[11.20: what stackless python does:
. a tasklet is like a separate program:
it has its own stack,
but for multi-threading it also
shares some state with some other program  .
. pickling is the saving of a running program
into a file until needed,
when the file is unpickled to become
the same running program it was before .
pickling stackless python's tasklets:
This allows you to take a tasklet mid-execution,
serialise it to a chunk of data
and then unserialise that data at a later point,
creating a new tasklet from it
that resumes where the last left off.]

. stackless python allows simulation of the stack,
so it can freeze your program's long operation,
and restart it when you have the computer back .
. even though we cannot freeze the C`stack,
we can impl' our own stack .
. see also notes on a system for ensuring
user interaction was not interrupted by
a long operation from an uncooperative subprogram
(in our system for ensuring this,
the compiler is rewriting each subprogram
by sprinkling it with calls to the gui;
so that no subprogram causes the gui to be
starved for cpu time).


[11.9: stack impl' requires a call operation:
. in order to implement our own stack,
we'll also need to simulate our own calls,
ie, we need a "sim'call" or "apply" operation
that puts our parameters on our own stack
instead of the platform's stack .]

[11.16: need sim'calls to simulate a stack?:
. do we really need sim'calls?
if we want full multi-tasking with suspend/resume
then we need to have some simulated calls
(we can still use c calls for uninterrupted routines
if we are sure they are well-behaved and brief)
. without sim'calls there is still multitasking
but only for tending the gui
or whatever else the system wants to do
when the current subroutine
makes the periodic check-in call .
. without sim'calls there is no suspend/resume
which is where every subprogram
stops at each of a sprinkling of checkpoints
and asks if the user or the scheduler
wants to suspend;
any subprogram that can call a suspendable sub'
is itself called with a sim'call,
so that the adda`stack includes the chain of calls .
. in a sim'call we storing a resume record
on the adda`stack, consisting of
the function to resume (the caller)
and the checkpoint number showing where to resume
after the call is done .
conclusion:
. a stackless design for adda2c
would produce very bulky c code because
any time it calls a suspendable subprogram, f,
it needs to stack its restart record on the adda`stack
then do a c`call of f,
then check whether f completed successfully,
and if so then remove the restart record from the adda`stack,
else if f came back saying it got suspended,
then f's caller's need to do the same recursively
(reporting to their callers that they got suspended)
until the c stack is unwound to the adda`exec,
which would save the adda`stack in a file,
allowing for a resume to happen later .
...
[11.20: really? try another impl:
. a subprogram is converted to a sequence of Segments,
which are short c-coded subprograms
that are sure to return with a second;
so the subprogram becomes an array of function pointers .
. the c's main program consists of
running a virtual scheduler that is creating
a set of virtual processes (adda`processes),
each with its own virtual adda`stack,
and on the stack are virtual activation records;
so, the scheduler is deciding which process to run,
then it starts calling Segments
as they are listed by our virtual subprograms .
. each call to a subprogram is translated into
the scheduler adding an act'rec to the adda`stack
-- the stack of the current adda`process .
. the subprogram code that is associated with an act'rec
is represented by pointer to an array of
c-coded Segment function pointers,
and the scheduler's primary activity is then a loop:
for the # of processes do loop:
 for the # of segments of current subprogram do loop:
  is it time to suspend the current process?
    save the seg# for restarting this thread;
    -- exit inner loop to go to thread-starting routine;
  else
    call the next segment;
. for when the subprogram being translated has a loop,
our representation of the subprogram
needs not just an array of pointers to subprogram`Segments,
but a sort of assembly code,
so that a loop header is translated into
calling a loop guard function that sets a flag,
then having an opcode that says
branch on flag for jumping to
either the next Segment
or to the Segment beyond the loop's end .
11.21: control functions:
. a alternative design that retains the idea that
the virtual subprogram is an array of function pointers,
is to have a "loop control Segment"
whose job it is to look at the loop header variables
to determine where to jump next,
and then use that info to adjust the program counter;
ie, the Scheduler's typical action,
after a Segment returns from being called,
is to increment the Segment array's index,
and then call Segment_array#(index);
so, what a loop control function needs to do
is modify the array's index,
so that when the scheduler increments it,
it is going to the intended Segment,
which is either jumping to exit the loop,
or entering the loop (by not modifying the index).
]
. for the sake of efficiency and simplicity,
our policy for stackless should
confine it to adda2addm rather than adda2c;
ie, if you want a program to be suspendable,
you will compile it to bytecode not c code,
and the only time you'll use adda2c's all-c code
is for well-behaved algorithms (like core library functions)
that are sure to terminate promptly .
so:
. the following applies to addm not adda ...
11.21: are you sure?:
. the "inefficient" things we need for a
simple stackless implementation
are also needed for virtual concurrency
-- a must-have feature; so,
the following applies to adda and addm .
]
. for each function with multiple param's
we view that as a single tuple-typed param;
eg, here's declaring tu to be a tuple:
tu: (x.real, y.str, z.int);
and then "f(x,y,z)" can be launched with "apply(f, tu)"
after we fill tu with actual param's .

[11.12: continuation codes:
[11.22: summary:
. the following is alternative to the stackless design;
it breaks up a c function into Segments,
but the function's instantiation
still happens on C's stack not a adda's stack .
]
. we want cooperative multitasking,
which means that a subprogram has to
stop at numbered checkpoints, and ask
whether it should suspend itself;
and if so, then it returns with the number of
the checkpoint where it wants to restart;
and then to restart that function,
we give it the checkpoint number,
and it jumps to that place in its routine .
. so, when we first call, it looks like
f(checkpoint=0 , params),
then if we need to resume it, we use:
f(checkpoint= "what it previously gave us", params).
. in order to be able to restart it like this,
none of the locals can be stack-based:
everything has to come from the heap,
through c's malloc calls .]

9.3: 11.16: 11.22:
. to be stackless,
each subroutine call by addm or adda
holds 2things on the virtual stack (vs C's stack),
#1: some return info:
# resume point of the caller, (the Segment index)
# pointer to caller;
#2: the activation record of the subprogram being called:
# pointer to the subprogram;
# pointer to parameter's record;
# pointer to callee's subheap
(the caller needs to use the callee's subheap
in cases where the parameter is a value (vs a pointer)
and it comes with a trailer, which needs to exist within
sthe subheap that is local to it).
-- the subheap can hold the pointer to local's tuple .
. after the scheduler finishes calling a Segment,
it checks to see if a suspend is requested,
and, if so, schedules the source of the request .

[11.9: 11.16: copying and rebuilding the stack:
. the addm`stack is an extendable array of
pointers to c malloc objects,
each of which includes
an indication of its size in bytes,
so that without having to know the parameter types,
the stack copier can see the whole parameter list
as one array of bytes,
or one array of links to malloc arrays .]

11.22: exceptions:
. there may be platform`routines we call
that we cannot apply segmentation to,
and in that case we need to
precede launching it with a user dialog:
"( this could result in a 5min freeze
of your addx.app's gui;
[ ] check here to always allow max 5min freeze
by this function
[ ] allow max 5min freeze by any function
unless there are other restrictions on a specific function .

27: 11.27: adda/mem'mgt/the only safe stack is a virtual stack:
. if instead of placing the param's tuple on the stack
we place a pointer on the stack
for pointing to a param'tuple in the heap,
then we have preceded every call
with a call to C's malloc or other heap service,
which means we can avoid unexpected stack exhaustion,
because, stack and heap use the same mem'segment
growing towards each other from opposite ends,
so a lack of stack space is equivalent to
a lack of heap space;
and if the call to ptr`= malloc() fails
or if the malloc doesn't have eno' heap to
return non-nil,
then since our ptr started out nil
if it is still nil after the attempted malloc,
then we know there is no more stack left,
and we can unwind the stack for some more mem',
so that we can then save the user's data
before making an exit that explains
the operation failed due to lack of memory  .
. of course, getting an act'rec with a malloc
instead of stack pushes
requires another pointer per call:
so to avoid much of that
we can have each call add the param'tuple size
to the global stack depth counter .
. and only when that counter gets very large,
do we preface each call by
asking for some mem, and then releasing it,
so if we don't get the mem as requested,
we know that soon our stack will be denied too?
... if we go stackless
then the users stack can be as large as their harddrive .

No comments:

Post a Comment