Blocking, I/O, and the unification

So far our processes either run, yield, or get preempted. They never wait for something. A real kernel has to handle the case where a process can’t proceed until something external happens — input arrives, a disk read completes, a timer expires, another process sends a message.

This is where the unification pays its biggest dividend, because blocking is the same mechanism as everything else we’ve built. A blocked process is a continuation that’s been filed somewhere other than the ready queue. Unblocking is moving the continuation back to the ready queue. The data structures are different; the mechanism is identical.

Let’s add input. We’ll model a simulated input device — call it a keyboard for concreteness — that occasionally performs an effect saying “here’s a byte.” Processes that want input perform an effect saying “give me a byte, blocking until one arrives.”

Two new effects

effect ReadByte    : byte             (* user-process effect: block until byte available *)
effect KeyArrival  : byte -> unit     (* device-initiated effect: a byte arrived *)

ReadByte : byte is performed by user code. Its return type is byte — when the handler resumes the continuation, it provides a byte, which becomes the value of perform ReadByte at the call site. This is the first effect we’ve seen whose return type is not unit; the data flow goes both directions through the perform.

KeyArrival : byte -> unit is performed by the keyboard device. Its argument is the byte that arrived; its return type is unit because the device doesn’t care about a response, it just wants to deliver the byte.

The two effects together implement a channel: a one-byte queue that producers push to and consumers pull from. We’ve built a synchronization primitive — the kind you’d find in Erlang as a mailbox, in Go as a channel, in Linux as a pipe — out of the effect mechanism with no special support.

Extending the kernel

type sched_state = {
  mutable ready    : process queue;
  mutable waiters  : process queue;   (* processes blocked on ReadByte *)
  mutable inbox    : byte queue;      (* bytes received but not yet consumed *)
  mutable next_id  : int;
}

let rec scheduler () : unit =
  match Queue.pop sched.ready with
  | None -> 
      if Queue.is_empty sched.waiters then ()
      else scheduler ()    (* idle: spin waiting for device events *)
  | Some p ->
      handle
        invoke p.k ()
      with
      | Yield k ->
          Queue.push sched.ready { id = p.id; k };
          scheduler ()
      | Print msg k ->
          uart_write msg;
          invoke k ()
      | Tick _ k ->
          Queue.push sched.ready { id = p.id; k };
          scheduler ()
      | ReadByte k ->
          (match Queue.pop sched.inbox with
           | Some b -> 
               invoke k b               (* byte available, resume immediately *)
           | None ->
               Queue.push sched.waiters { id = p.id; k };
               scheduler ())
      | KeyArrival b k ->
          (match Queue.pop sched.waiters with
           | Some waiter ->
               Queue.push sched.ready { id = p.id; k };
               invoke waiter.k b
           | None ->
               Queue.push sched.inbox b;
               invoke k ())

let echo_proc () =
  let rec loop () =
    let b = perform ReadByte in
    perform (Print (Printf.sprintf "got: %d\n" b));
    loop ()
  in
  loop ()

let main () =
  spawn echo_proc;
  spawn (proc_loop "B" 5);
  scheduler ()

When run with a simulated keyboard that performs KeyArrival occasionally, this kernel correctly multiplexes: echo_proc blocks until input arrives, proc_b runs in the meantime, input arrival wakes echo_proc to handle the byte. Two new effect clauses, two new queues, one extra idle case.

The ReadByte clause

| ReadByte k ->
    (match Queue.pop sched.inbox with
     | Some b -> invoke k b
     | None ->
         Queue.push sched.waiters { id = p.id; k };
         scheduler ())

The handler is invoked when a process performs ReadByte. The continuation k represents “the process at the point just after perform ReadByte, waiting for a byte to be supplied.”

If the inbox has a byte, we deliver it by invoking k b. The process resumes with b as the value of its perform ReadByte expression. No yielding, no rescheduling — the process gets its byte and continues.

If the inbox is empty, we file the continuation in waiters and call the scheduler. The current process is now blocked — its continuation is in waiters, not in ready. The scheduler will pop a different ready process and run it. The blocked process will only resume when something puts it back in ready, which is exactly what KeyArrival does.

Key insight: the continuation k is the only thing that represents the blocked process. There’s no task_struct updated with a “blocked” status flag, no priority adjusted, no separate sleep queue. There is simply: the continuation is in waiters instead of ready. The location of the continuation is the process’s state.

The KeyArrival clause

| KeyArrival b k ->
    (match Queue.pop sched.waiters with
     | Some waiter ->
         Queue.push sched.ready { id = p.id; k };
         invoke waiter.k b
     | None ->
         Queue.push sched.inbox b;
         invoke k ())

The KeyArrival effect is performed by the device, not by user code. When the keyboard has a byte to deliver, it performs KeyArrival b from outside the user-process context.

But notice the structure: the handler is invoked while some user process is running. The device’s perform is, mechanistically, the same as a timer’s perform — it interrupts the currently-executing code. So when the KeyArrival clause runs, there’s a user process currently in flight, and k is that user process’s continuation, not the device’s.

This is a subtle bit. There are two continuations in play during KeyArrival:

• k: the continuation of whatever user process was running when the device perform arrived. The interrupted process.
• waiter.k: the continuation of the process that was previously blocked on ReadByte. The process we want to wake up.

The handler decides what to do with both. If there’s a waiter, we requeue the interrupted process (it’ll get its turn back later), and we invoke the waiter’s continuation with the byte. The waiter gets the byte, the interrupted process is fairly preempted, the scheduler will pick up where things continue.

If there’s no waiter, we buffer the byte in the inbox and invoke k () to resume the interrupted process. No scheduling happens; the user process gets right back to running.

This is exactly the semantics of read(2) in Unix when data arrives: a process blocked in read gets woken up; a process not blocked just sees data buffered for later. Implemented in eight lines of handler clause, with no special interrupt-context discipline, no separate kernel stack, no wake_up_interruptible.

The idle case

| None -> 
    if Queue.is_empty sched.waiters then ()
    else scheduler ()

When the scheduler tries to pop a ready process and finds the queue empty, there are two cases. Either there are no waiters either, in which case the system is genuinely done and we exit. Or there are waiters, in which case every process is blocked waiting on something — and we… spin.

This is the idle loop, and it’s where the design has its weakest moment. Spinning is bad: it burns CPU, generates heat, accomplishes nothing. A real kernel would issue HLT (x86) or WFI (ARM) to halt the core until an interrupt arrives.

On our ISA, the equivalent is perform Halt or similar: an effect that signals “I have nothing to do; wake me when a remote perform arrives.” The hardware implementation would gate the clock or otherwise reduce power until the NoC delivers a message. This is the HALT instruction in the ISA, and the scheduler’s idle case should perform it.

In the kernel as drafted, we busy-loop with scheduler () because the integration with HALT is an exercise for later. Worth flagging: real kernels need a hardware-supported idle, and a clean effect-based design surfaces this as just another instruction.

Why this is meaningfully different from threads

Take a moment with this: echo_proc is a function that calls ReadByte in a loop. It’s straight-line, blocking, sequential code. It reads like a script.

In Linux, the equivalent C code would call read(fd, &b, 1) — also blocking, also sequential. The kernel handles the blocking via its scheduler. So far this looks the same.

But the cost differs in important ways:

In Linux, each process has a kernel stack, a thread control block, page tables, and assorted machinery. A blocked process consumes kilobytes of kernel memory. Creating one is hundreds of microseconds of syscall and allocation. Linux can handle thousands of threads gracefully but starts to strain at tens of thousands.

In our kernel, a blocked process is a continuation in a queue. The continuation is a pointer to a frame tree. The frame tree’s size is the size of the process’s actual live state at the perform site. A process blocked at perform ReadByte after just starting has a tiny frame tree; a process blocked deep in a parser has a larger one. Cost is proportional to genuinely live state. Millions of blocked processes are plausible if their state is small.

This is why effect-handler-based concurrency is being explored as a replacement for thread pools in serious systems: the cost per blocked thing is fundamentally lower because the abstraction doesn’t bake in fixed-size overhead. You’re seeing the same thing async/await delivers in modern languages, except here it’s not bolted on: the language wasn’t designed with sync blocking and then patched to support async via state-machine transforms. The language is effect-native; sync and async are the same code path.

What’s still missing

This kernel can now:

• Run multiple cooperating processes
• Preempt them on a timer
• Block them on input
• Buffer input while no consumer is waiting
• Deliver buffered input immediately when a consumer asks

It still can’t:

• Talk to multiple devices (we have one keyboard; what about a UART send queue, a network card, a disk?)
• Time out a blocking read
• Send messages between processes
• Spawn a process from inside another process
• Exit a process cleanly

Each of these is another effect or two and another queue or table. The kernel grows feature by feature without restructuring. Process exit is an effect whose handler drops the continuation and calls the scheduler. Process-to-process messaging is a pair of effects and a per-process mailbox queue. Timeouts are an effect plus a sorted timer queue. Each addition fits cleanly into the existing match expression.

What this chapter committed to

Blocking I/O as a continuation-in-a-different-queue. The asymmetric data flow of ReadByte : byte (response carries value) vs. KeyArrival : byte -> unit (request carries value). The unification of “wake up a blocked process” with “schedule a runnable process” under one mechanism. The acknowledgment that real kernels need a HALT for the idle case.

The next chapter introduces linear types, which is what makes the next step — multicore — safe.