Lambda the Ultimate

I'm mostly clueless, so this might be a mostly useless comment, but: I am under the impression that Erlang basically does that, by counting the number of "reductions" it is doing in a given process? So I guess that (a) is not a different way, as you were apparently seeking, but (b) apparently works well enough in practice?

Isn't that basically the same problem as inserting safe-points to interrupt a program's execution (e.g. in a stop-the-world GC)? You have the same tradeoff between check overhead & timeliness. If you don't care too much about timeliness but only want to make sure execution is bounded, then you can, e.g., only insert checks before potentially (mutually) recursive calls and backward branches. The tricks to reduce the overhead of each check might not all be applicable; I don't think MMU hacks are what you're after here :)

The smart thing is to couple it with an operation that is expensive anyway, and possibly has a non-predictable branch (the latter may or may not be a good idea).

The Larceny Scheme compiler makes a primitive preemption facility in the form of timer interrupts available to the programmer. These interrupts are currently based on a count-down software timer which is decremented and checked on every procedure call and backward branch. When the timer reaches 0, a user-installable handler procedure is called.

This along with Schemes's call/cc provides sufficient machinery to implement a green/fair threading system with pseudo-preemptive traits.

The handler procedure is a parameterizable so a simple
(timer-interrupt-handler
(lambda ()
(task-switch #t #f)))
is all you need.

See Larceny note:
http://www.ccs.neu.edu/home/lth/larceny/notes/note1-timer.html

For an implementation based off of work original work done by the Larceny developers see
http://github.com/GreyLensman/rl3/tree/e90a1de202f4081ae45ac9959fbc6d8aa6ae10e2/rl3/concurrency/tasks.sls
for details.

I'm looking at similar things now too. I noticed that in the OpenFirmware (Forth-based firmware of Sun/Powerbook/OLPC) the address of the main interpreter/VM loop is kept in a register, and on x86 each Forth word ends with:
jmp edi
to dispatch the next instruction. This seems very amenable to preemption: a timer interrupt could poke the address of a 'yield' routine into edi and it'd be automatically run on the next invocation.

MMU/breakpoint tricks should be lots of fun too :-)

One less expensive approach then checking on every function call would be to check on every garbage collection. If you were using a generational garbage collector with a small initial generation and did not do tail-call optimization the recursion depth available before preemption would be bounded. To ensure tail calls do not take up extra space use the garbage collector and continuation-passing style.

Be aware however that it is possible to slow a machine very easily without recursion. If denormal numbers are turned on, then a malicious thread could simply do a clever division. Depending on the CPU being used this could lead to epic slowdowns. Funny memory access patterns and space leaking can cause issues. And if you are using mark-sweep then memory fragmentation is another attack vector.

Thanks for all of the suggestions. I was trying to avoid signals, but then I found SML/NJ's handling of signals as continuation-producing functions. This seems sufficient for providing a green threading framework entirely within a language. Anyone have any experience or comments on this?

...that, assuming a code fragment taking T(n) to complete getting m yields inserted, another code fragment taking T(2n) to complete 2m yields, if the compiler analyses a program fragment as not halting, it is going to insert infinitely many yields?

That is, to do this you'll have to completely unify code and data plus solve the halting problem.

I think you're better off just using preemptive multitasking, also because it scales better to real parallelism: Most of your yields will be placed utterly wrong if you have more than one cpu.

Just as another data point. GHC implements pre-emptive threading by (potentially) yielding on heap checks (which, conceptually at least, occur on every allocation). It is possible to DoS a GHC computation by having a tight loop that doesn't allocate. It would be easy enough to fix this by inserting explicit yields in recursions if there aren't already heap checks. This hasn't been done yet as it hasn't been much of a problem.

Marc Feeley, "Polling efficiently on stock hardware", FPCA 1993. Here: http://www.iro.umontreal.ca/~feeley/papers/polling.ps.gz