Coroutines for pre-emptive multitasking

JBR

I really wanted to translate some of the ideas in Coroutines for cooperative multitasking to this page and use the interp limit features to create a control structure that would allow a master interpreter to run several slaves while interrupting them when resources were exhausted (time or # of commands). Then the slave procs could be resumed where they left off using the coroutine command.

Conceptually the interp limit command callback would yield and some other code could be run. The master could run its own code or call one of its slave coprocs, waiting for the limit command to yield again.

I didn't make it very far. The fact that coroutines need to loop until done (or forever) and the limit mechanism requires its command to return after adjusting the interp limit seems incompatible.

Is this at all possible with our current coroutine and interp limit features?


OK -- Here is a more clearly laid out attempt at code. It fails with:

 $ ./preemptive.tcl
 Call one
 one 1
 one 2
 one 3
 Preempt one
 cannot yield: C stack busy


 #!/home/john/bin/tclsh8.6a2
 #
 namespace path ::tcl::unsupported

 set Tasks {}

 proc Task { task args } {
    interp create I$task
    interp eval   I$task proc p$task {} $args


    coroutine $task RunTask $task

    lappend ::Tasks $task
 }

 proc Drop { task } {
    set here [lsearch $::Tasks $task]
    set ::Tasks [lreplace $::Tasks $here $here]

    interp delete $task
 }


 proc RunTask { task } {
        yield
        interp eval I$task p$task
 }

 proc Preempt { task commands } {
    catch {
        puts "Preempt $task"

        set ::Limit($task) [expr $::Limit($task) + $commands]
        interp limit I$task command -value $::Limit($task)

        yield

        puts "Return to $task"
    } reply; puts $reply
 }

 Task one {} {
        while { 1 } {
                incr x
                puts "one $x"
        }
 }

 Task two {} {
        while { 1 } {
                incr x
                puts "two $x"
        }
 }

 proc PreemptiveRoundRobin  { commands } {

    foreach task $::Tasks {
        set ::Limit($task) [expr [interp eval I$task info cmdcount] + $commands]
        interp limit I$task command -command [list Preempt $task $commands]
        interp limit I$task command -value $::Limit($task)
    }

    while { 1 } {
        foreach task $::Tasks {
            puts "Call $task"
            $task
        }
    }
 }

 # Run the two tasks 6 Tcl commands at a time
 #
 PreemptiveRoundRobin 6



ferrieux So you want Green Threads in Tcl too: I bow to your courage ;-) Now as to the implementation, what about using single-step execution traces instead of interp limit ? Of course it will be slower... but exec traces, contrarily to interp limit, are not linked to an interp's end-of-life (assuming this is the problem; is it ?).

JBR We already have cooperative green threads, via coroutines. Now I want a master thread to select and limit the execution of its slaves instead of just dispatching them.

ferrieux I know :) Matter of terminology here: by "green" I meant "userland", which includes both preemptiver and cooperative... But you didn't answer the suggestion about traces.

MS notes that forcing an interp to yield seems quite feasible to me (without having thought too hard about it). I lack the mental bandwidth at the moment to really think things through but: given well designed syntax and semantics (TIP quality), I volunteer to do the basic implementation. Ball's on your court :P

NEM can't answer the question as to whether this is feasible now with interp limit -- perhaps DKF can answer definitively? It's an interesting idea. The fact that it uses a single interpreter per "thread" would make it seem rather similar to Tcl's native threading model. So the advantage would presumably be that these threads are lighter-weight and so you can (a) run more of them (if you have an extremely concurrent application), and/or (b) there is less context-switching overhead. Is that the idea? (I'm not entirely sure about (b) -- is a coroutine switch cheaper than an OS level context switch?)

JBR The idea is to have a master routine controlling the execution of several children, without OS threads and without incurring a mass amount of recursion. Both interp limits or execution traces alone would work at some level, but what to do when the trace fires? To call into other code would mean recursing, and you would be unable to return to "other" tasks without coroutines and yield.

JBR I have posted some better code above. It "should" work. It seems that the interp eval or the limit callbacks push another layer on the NRE stack?

DKF: Yes, it does. Feel free to provide a patch if you can figure out how to fix it. :-)

ferrieux Just tried with enterstep traces: same result (C stack busy). Oh, to NR-enable traces...

DKF: NRE-enabling traces and limit callbacks... the changes required scare me, but the results would be "pretty neat".

ferrieux That scares me too ;-) Now what about the following shortcut: [return -code yield], or [return -yield]. The idea is to use the usual "return code" signalling pathway to instruct one's _caller_ to yield. Thus, even if we are buried in an extra layer of C stack (like all those non-NRE-enabled contexts), we can still remote-control the yielding of the caller. Is it doable ?

Lars H: Can't help remarking that with suspend and resume that would have worked out of the box, but it was not to be… As for yield and tailcall, I believe there remains much work in the area of getting these to cooperate with Tcl's traditional return code based flow control mechanisms.[L1 ]