Green threads

Green threads are threads scheduled by a language runtime or a library instead of by the operating system kernel. A suspended green thread is a saved continuation or a small, growable stack on the heap, so creating one and switching between them costs little more than a function call and an allocation, and a program can have hundreds of thousands of them at once. The runtime multiplexes them onto a smaller number of kernel threads, M:N scheduling, and has to make sure that a blocking system call in one green thread does not block the others^[5]. Erlang processes^[4], Haskell's threads^[2], Go's goroutines^[11] and Java's virtual threads^[10] are green threads; OCaml implements them as libraries, with continuation-passing style in Lwt^[7] and with effect handlers in OCaml 5^[8]. The name comes from the Green Team at Sun, whose early Java virtual machine scheduled its threads itself.

A kernel thread has a stack reserved by the operating system, commonly megabytes of address space, and a context switch between kernel threads passes through the kernel: it saves the registers, changes the stack pointer, updates scheduler data structures, and may flush parts of the processor's state. That is cheap enough for dozens or thousands of threads, but a server that wants one thread per connection for a hundred thousand connections runs out of memory or spends its time switching. A green thread needs only the state that is actually live when it is suspended, and a switch is a jump into another continuation.

Threads can be written without any runtime support once continuations are available. Wand showed in 1980 how to implement multiprocessing in Scheme with first-class continuations: a thread that yields captures its continuation and puts it on a queue, and the scheduler resumes the continuation at the head of the queue^[1].

In a language without first-class continuations, a thread can be written in continuation-passing style: a computation takes the function to call with its result, and a thread that yields stores that function in the run queue and returns to the scheduler. Channels in the style of Hoare's communicating sequential processes^[6] park a receiver's continuation until a value arrives:

(* Green threads in continuation-passing style. A computation of type
   'a t takes the continuation that receives its result; a thread that
   yields or blocks stores its continuation and returns to the scheduler,
   whose run queue holds the continuations of runnable threads. *)
type 'a t = ('a -> unit) -> unit
 
let return x : 'a t = fun k -> k x
let ( let* ) (m : 'a t) (f : 'a -> 'b t) : 'b t = fun k -> m (fun x -> f x k)
 
let ready : (unit -> unit) Queue.t = Queue.create ()
let switches = ref 0
 
let yield : unit t = fun k -> Queue.push k ready
let spawn (m : unit t) = Queue.push (fun () -> m (fun () -> ())) ready
 
let run () =
  while not (Queue.is_empty ready) do
    incr switches;
    (Queue.pop ready) ()
  done
 
(* An unbounded channel. A receiver finding it empty parks its
   continuation; a sender finding a parked receiver makes it runnable.
   Sending also yields, so that a producer cannot run forever. *)
type 'a chan = { items : 'a Queue.t; receivers : ('a -> unit) Queue.t }
 
let chan () = { items = Queue.create (); receivers = Queue.create () }
let send c v : unit t = fun k ->
  if Queue.is_empty c.receivers then Queue.push v c.items
  else (let r = Queue.pop c.receivers in Queue.push (fun () -> r v) ready);
  Queue.push k ready
let recv c : 'a t = fun k ->
  if Queue.is_empty c.items then Queue.push k c.receivers else k (Queue.pop c.items)

open Green
 
(* Two threads taking turns. *)
let rec worker name n = if n = 0 then return () else
  let* () = return (Printf.printf "%s%d " name n) in
  let* () = yield in
  worker name (n - 1)
 
(* The concurrent prime sieve: a generator thread, and one filter thread
   per prime, connected by channels. *)
let rec generate out i = let* () = send out i in generate out (i + 1)
 
let rec filter inp out p =
  let* n = recv inp in
  let* () = if n mod p <> 0 then send out n else return () in
  filter inp out p
 
let rec sieve inp count found =
  if count = 0 then return ()
  else
    let* p = recv inp in
    found := p :: !found;
    let out = chan () in
    spawn (filter inp out p);
    sieve out (count - 1) found

a4 b4 a3 b3 a2 b2 a1 b1 
first primes: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

The sieve connects a generator of the integers to a chain of filter threads, one for each prime found so far, each passing on the numbers not divisible by its prime; it is the classic example of CSP-style concurrency, and needs one thread per prime, created on demand. Written with let*, the thread code looks sequential, and the continuation-passing is hidden in the bind, as in the continuation monad.

Cost

open Green
 
let rec loop n = if n = 0 then return () else let* () = yield in loop (n - 1)

100000 threads suspended at a yield: 1300000 words live, 13.0 words per thread
run to completion: 1000000 context switches

A suspended thread here is a closure and a queue cell, 13 words, about a hundred bytes. The same number of kernel threads would need a stack each, and a million switches between them would each cross into the kernel. The memory of a continuation-based thread is proportional to what it will still use, which is also why deep recursion inside a thread is paid for on the heap instead of the stack.

Green threads in this style are cooperative: a thread runs until it yields, blocks on a channel or finishes, and a thread in a long computation that never yields holds up all the others. Runtimes that manage their own stacks can preempt instead. GHC switches threads at heap-allocation checks when a timer has expired, and Go's runtime preempts goroutines at function entries and, since Go 1.14, asynchronously with signals. Erlang counts reductions, function calls, and switches processes after a fixed budget^[4].

M:N runtimes run the green threads on several kernel threads, one per core, and move them between cores, often by work stealing. Anderson, Bershad, Lazowska and Levy showed that the kernel has to cooperate for this to work well, notifying the runtime when a kernel thread blocks so that it can schedule another green thread on the processor^[5].

Blocking calls

A green thread that makes a blocking system call, such as a read from a socket, blocks the kernel thread it is running on, and with it every green thread scheduled there. Runtimes avoid this by issuing input and output through non-blocking system calls and an event loop, such as epoll or kqueue, suspending the green thread until the file descriptor is ready, and by running calls that cannot be made non-blocking, such as some file-system operations and foreign functions, on separate kernel threads. GHC's runtime does this for foreign calls marked safe^[3], and Capriccio showed that the approach could make a thread-per-connection web server as efficient as an event-driven one^[9]. Lwt in OCaml makes the event loop explicit: every blocking operation returns a promise, and threads are chains of promise callbacks^[7].

Erlang has had lightweight processes since the 1980s; each has its own heap and communicates only by message passing, and systems with millions of processes are common^[4]. Concurrent Haskell added threads to Haskell in 1996^[2], and GHC's runtime schedules them M:N onto its capabilities. Go's goroutines start with a stack of a few kilobytes that grows by copying^[11]. Early Java virtual machines used green threads and then abandoned them for kernel threads, and Java 21 brought them back as virtual threads, which are unmounted from their carrier kernel thread when they block^[10]. In OCaml 5, an effect handler captures the rest of a computation as a continuation backed by a separately allocated stack segment, so a scheduler for green threads is a few lines of handler code^[8], and libraries such as Eio build direct-style concurrency on it.

Coroutines and user-level threads predate kernel threads in several systems. Wand implemented threads with continuations in 1980^[1], and Hoare's CSP of 1978 gave a model of concurrency with many lightweight processes^[6]. Erlang's processes date from the 1980s, and Sun's Java 1.0 and 1.1 used green threads on Solaris before moving to native threads. Anderson and his coauthors' scheduler activations of 1992 addressed the interaction of user-level threads with the kernel^[5]. Go, released in 2009, and Java's virtual threads, released in 2023, made green threads mainstream again.

• Effect handlerA construct that runs code which may perform an effect, and handles each effect by receiving it together with the continuation from the point where it was performed. OCaml 5 has them, with one-shot continuations: each can be resumed at most once.
• Continuation-passing styleContinuation-passing style (CPS) is a way of writing programs in which no function returns: each takes an extra argument, its continuation, a function that represents the rest of the computation, and calls it with the result. Every call becomes a tail call, evaluation order is made explicit, and control operators such as exceptions, backtracking and call/cc become ordinary functions. Compilers for functional languages use CPS, or the closely related A-normal form, as an intermediate language.
• Chase–Lev dequeThe Chase–Lev deque is the lock-free double-ended queue used by work-stealing schedulers. Its owner thread pushes and pops tasks at the bottom with plain reads and writes, and other threads steal from the top with a compare-and-swap; the two ends only contend when one element is left, which both sides resolve with the same compare-and-swap on the top index. The buffer is a circular array that grows when full. Correctness depends on a store-load ordering in pop that weak memory models require a fence to provide.
• MonadIn functional programming, a monad is a type constructor m with two operations, return : a -> m a and bind : m a -> (a -> m b) -> m b, satisfying three laws. It lets code with some extra behaviour, such as failure, several results, configuration, state or I/O, be written as a sequence of ordinary steps, with the behaviour defined once in bind. The notion comes from category theory.

1. [1]M. Wand, “Continuation-based multiprocessing”, LISP Conference (1980).
2. [2]S. Peyton Jones, A. Gordon, S. Finne, “Concurrent Haskell”, POPL (1996).
3. [3]S. Marlow, S. Peyton Jones, W. Thaller, “Extending the Haskell foreign function interface with concurrency”, Haskell Workshop (2004).
4. [4]J. Armstrong, Making Reliable Distributed Systems in the Presence of Software Errors, PhD thesis, Royal Institute of Technology, Stockholm (2003).
5. [5]T. E. Anderson, B. N. Bershad, E. D. Lazowska, H. M. Levy, “Scheduler activations: effective kernel support for the user-level management of parallelism”, ACM Transactions on Computer Systems 10 (1992).
6. [6]C. A. R. Hoare, “Communicating sequential processes”, Communications of the ACM 21 (1978).
7. [7]J. Vouillon, “Lwt: a cooperative thread library”, ACM SIGPLAN Workshop on ML (2008).
8. [8]K. C. Sivaramakrishnan, S. Dolan, L. White, T. Kelly, S. Jaffer, A. Madhavapeddy, “Retrofitting effect handlers onto OCaml”, PLDI (2021).
9. [9]R. von Behren, J. Condit, F. Zhou, G. C. Necula, E. Brewer, “Capriccio: scalable threads for internet services”, SOSP (2003).
10. [10]R. Pressler, A. Bateman, “JEP 444: Virtual Threads”, OpenJDK (2023).
11. [11]A. A. A. Donovan, B. W. Kernighan, The Go Programming Language, ch. 8, Addison-Wesley (2015).

last updated 27 September 2026