Hacker News Reader

Comment by baruch | Hacker News Reader

Are there actual examples of green threads that are not cooperative?

All the implementations I've seen are cooperative.

Haskell has green (N to M) threads that are pre-emptive. As does Go (but it calls them coroutines). Erlang (but it calls them processes) I'm not sure about. Maybe it only re-schedules on message sends and receives?

Erlang does a different thing called "reduction-counting": the active process in a scheduler-thread gets a budget of virtual CPU cycles (reductions/"reds"), tracked in a VM register, and part of the implementation of each op in the VM's ISA is to reduce that reduction-count by an amount corresponding to the estimated time-cost of the op. Then, the implementation of the call and ret ops in the ISA both check the reduction-counter, and sleep the process (scheduling it to resume at the new call-site) if it has expended all its reds.

(If you're wondering, this works to achieve soft-realtime guarantees because, in Erlang, as in Prolog, loops are implemented in terms of recursive tail-calls. So any O(N) function is guaranteed to hit a call or ret op after O(1) time.)

If you're writing an Erlang extension in C (a "NIF"), though, and your NIF code will be above O(1), then you have to ensure that you call into the runtime reduction-checker yourself to ensure nonblocking behavior. In that sense, Erlang is "cooperative under the covers"—you explicitly decide where to (offer to) yield. It's just that the Erlang HLL papers over this by having one of its most foundational primitives do such an explicit yield-check.

If loops are implemented as tail calls, doesn't the call opcode get optimized away thus preventing the reduction checker from being run?

It marks the point just before the call as a yield. That yield remains after optimization.

Goroutines are not preemptive. They yield at well-defined points.

I remember hearing that the scheduler will indeed pre-empt occasionally if none of the active goroutines are attempting to perform blocking calls.

No, the scheduler cannot preempt. The scheduler is called by the goroutine and given the opportunity to pause it whenever the goroutine does a channel send/receive or calls a non-inlined function or, of course, makes a blocking I/O call[1]. But the scheduler can't do anything if nobody calls it. To wit:

http://www.sarathlakshman.com/2016/06/15/pitfall-of-golang-s...

IIRC, work is underway (may be finished) to add a scheduler yield check to loops as well, which would fix the pathological case in that blog entry.

If your code is doing a lot of channel sends and/or calling a lot of non-inlined functions, it may look like preemption, but it's still cooperative. If you're writing latency-sensitive code this distinction should be kept in mind.

[1] Or whenever time.Sleep() is called, or somebody calls runtime.Gosched(). There might be other cases, would be happy to hear about it.

Haskell's green threads are cooperative on memory allocation. If no memory is allocated, then a green thread will not be preempted.

In practice, memory allocation happens a lot, so it's pretty close to preemptive.

If your implementation is interpreted, or at least can act indistinguishably from an interpreter, it's possible to interrupt a green thread every N operations.

Obviously if you block in the OS for IO, your interpreter won't have a chance to preempt you, which is one of several issues with M:N threading models.

> Are there actual examples of green threads that are not cooperative?

From the "client" side, there are many that are preemptive in that user code does not explicitly yield (Ruby threads pre-1.9, Erlang processes, etc.)

The runtime implementation is, by definition, cooperative scheduling on top of one (1:N) or many (M:N) native threads.

> by definition

Is it? It seems like one could theoretically implement thread switch on signal, and I'd probably still call that "green threads".

IIRC the Squeak Smalltalk VM has "green threads" (in the sense that they're threads implemented by the VM scheduler) which are pre-emptive. On architectures the VM runs on that have with OS threading, the VM just translates the requests to create green threads into requests to create native threads, and lets the OS manage them. On architectures that don't, it "brings its own" pre-emptive scheduling logic.

Erlang/Elixir's are preemptive.

That might be a feature, actually.

The advantage of being cooperative is that context switches are deterministic. Raw preemptive multi-threading, on the other hand, leaves open the possibility of hard-to-reproduce timing-related bugs.

Smalltalk-80 had green threads that have multiple priorities. Scheduling within each priority was round-robin, and timeouts (instances of the Delay class) were handled by a single high-priority thread that woke up threads whose deadline has passed. As a result, you could be preempted at any time not just by a higher-priority that, but also by another thread waiting on a Delay.

OCaml uses green threads where you can cooperate (yield()) or be preempted every 50ms.

Ruby, Python are the prime examples of this. They use the multiple OS threads to run them, but actually use locks to force them to be 'green'.

That's not really accurate.

CPython threads are honest to goodness OS threads, the GIL has nothing to do with green-ness (and the GIL can be released).

greenlets are green threads, but they're cooperative.

That's not green threading, it's just 1:1 native threading with a big lock, which has very different behavior than green threading (either 1:N or M:N).

Reply on news.ycombinator.com