4 ms·

Interesting. I hadn't heard the "green thread" term before. Does anyone happen to know how this compares to Windows' "fiber" mechanism? I can't recall whether f

by jerryr 9y ago

Interesting. I hadn't heard the "green thread" term before. Does anyone happen to know how this compares to Windows' "fiber" mechanism? I can't recall whether fibers actually run in user land.

roblabla 9y ago
A Fiber is a cooperative multitasking strategy. As such, a fiber must yield at some point to allow other fibers to do their work. Green threading is just the idea of doing the scheduling of threads in user-space. It can be preemptive or cooperative. Fibers and green threading aren't mutually exclusive, afaik.
- baruch 9y ago
  Are there actual examples of green threads that are not cooperative? All the implementations I've seen are cooperative.
  - chrisseaton 9y ago
    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?
    - derefr 9y ago
      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.
      - timow1337 9y ago
        If loops are implemented as tail calls, doesn't the call opcode get optimized away thus preventing the reduction checker from being run?
        jacquesm 9y ago
        It marks the point just before the call as a yield. That yield remains after optimization.
    - Scramblejams 9y ago
      Goroutines are not preemptive. They yield at well-defined points.
      - collinvandyck76 9y ago
        I remember hearing that the scheduler will indeed pre-empt occasionally if none of the active goroutines are attempting to perform blocking calls.
        Scramblejams 9y ago
        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-scheduler 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.
    - phamilton 9y ago
      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.
  - padator 9y ago
    OCaml uses green threads where you can cooperate (yield()) or be preempted every 50ms.
  - tinco 9y ago
    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'.
    - JulianWasTaken 9y ago
      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.
    - dragonwriter 9y ago
      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).
  - twoodfin 9y ago
    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.
  - derefr 9y ago
    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.
  - Scramblejams 9y ago
    Erlang/Elixir's are preemptive.
  - dragonwriter 9y ago
    > 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.
    - dllthomas 9y ago
      > by definition Is it? It seems like one could theoretically implement thread switch on signal, and I'd probably still call that "green threads".
  - bonzini 9y ago
    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.
  - astrobe_ 9y ago
    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.
deleted 9y ago
[deleted]
barrkel 9y ago
You could use fibers to implement green threads; you could also use fibers to implement coroutines. There's an abstraction mismatch between the terms, though. Green threads is having separate threads of control (meaning separate program counters and contexts like stack and registers) running concurrently, with switching controlled in user space, whereas OS threads switch in the kernel. It's a description of an architecture. You could implement green threads in a VM, where the program counter and context is switched by a VM loop, yet the VM interpreter itself might be single-threaded. Or you could have multiple VM interpreter loops implemented using fibers, and switch between them that way. Fibers are a way of switching program counter and context explicitly in userland. Like I said, you could use them to implement coroutines, iterators, or other code that resembles continuation passing style (like async) instead (the context being switched includes the return address, which is the continuation - the RET instruction in imperative code is a jump to the continuation). Fibers let you hang on to the continuation and do something else in the meantime. But they're a low-level primitive, and confusing to work with directly unless you wrap them up in something else. Here's a chap who used Fibers to implement native C++ yield return (iterators) similar to C#: https://www.codeproject.com/Articles/20015/Yield-Return-Iterator-for-Native-C-Using-Fibers https://www.codeproject.com/Articles/20015/Yield-Return-Iter...

by jerryr 9y ago

Interesting. I hadn't heard the "green thread" term before. Does anyone happen to know how this compares to Windows' "fiber" mechanism? I can't recall whether fibers actually run in user land.

roblabla 9y ago

A Fiber is a cooperative multitasking strategy. As such, a fiber must yield at some point to allow other fibers to do their work. Green threading is just the idea of doing the scheduling of threads in user-space. It can be preemptive or cooperative. Fibers and green threading aren't mutually exclusive, afaik.

baruch 9y ago
Are there actual examples of green threads that are not cooperative? All the implementations I've seen are cooperative.
- chrisseaton 9y ago
  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?
  - derefr 9y ago
    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.
    - timow1337 9y ago
      If loops are implemented as tail calls, doesn't the call opcode get optimized away thus preventing the reduction checker from being run?
      - jacquesm 9y ago
        It marks the point just before the call as a yield. That yield remains after optimization.
  - Scramblejams 9y ago
    Goroutines are not preemptive. They yield at well-defined points.
    - collinvandyck76 9y ago
      I remember hearing that the scheduler will indeed pre-empt occasionally if none of the active goroutines are attempting to perform blocking calls.
      - Scramblejams 9y ago
        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-scheduler 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.
  - phamilton 9y ago
    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.
- padator 9y ago
  OCaml uses green threads where you can cooperate (yield()) or be preempted every 50ms.
- tinco 9y ago
  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'.
  - JulianWasTaken 9y ago
    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.
  - dragonwriter 9y ago
    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).
- twoodfin 9y ago
  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.
- derefr 9y ago
  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.
- Scramblejams 9y ago
  Erlang/Elixir's are preemptive.
- dragonwriter 9y ago
  > 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.
  - dllthomas 9y ago
    > by definition Is it? It seems like one could theoretically implement thread switch on signal, and I'd probably still call that "green threads".
- bonzini 9y ago
  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.
- astrobe_ 9y ago
  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.

deleted 9y ago

[deleted]

barrkel 9y ago

You could use fibers to implement green threads; you could also use fibers to implement coroutines. There's an abstraction mismatch between the terms, though. Green threads is having separate threads of control (meaning separate program counters and contexts like stack and registers) running concurrently, with switching controlled in user space, whereas OS threads switch in the kernel. It's a description of an architecture. You could implement green threads in a VM, where the program counter and context is switched by a VM loop, yet the VM interpreter itself might be single-threaded. Or you could have multiple VM interpreter loops implemented using fibers, and switch between them that way. Fibers are a way of switching program counter and context explicitly in userland. Like I said, you could use them to implement coroutines, iterators, or other code that resembles continuation passing style (like async) instead (the context being switched includes the return address, which is the continuation - the RET instruction in imperative code is a jump to the continuation). Fibers let you hang on to the continuation and do something else in the meantime. But they're a low-level primitive, and confusing to work with directly unless you wrap them up in something else. Here's a chap who used Fibers to implement native C++ yield return (iterators) similar to C#: https://www.codeproject.com/Articles/20015/Yield-Return-Iterator-for-Native-C-Using-Fibers https://www.codeproject.com/Articles/20015/Yield-Return-Iter...