This is a note of the book The Node Experiment - Exploring Async Basics with Rust. It developes a Node.js-like event loop runtime to show the why and how of concurrent programming.

1 Concurrency vs Parallel

There are two types of multitasking:

Concurrency is about dealing with a lot of things at the same time, progressing one task at one time. Tasks are in progress at the same time. Tasks must be interruptable. Parallelism is about doing a lot of things at the same time, progressing multiple tasks at the same time.

Efficiency is to avoid wasting resources. Parallelism means additional resources for tasks and is not about efficiency. Conccurency is to achieve efficiency by utilizing resources better and finishing a set of tasks faster – it cannot make one single task go faster.

It is the same as LEAN process: eliminate waiting and non-value-adding tasks. In programming, it means avoid blocking and polling in a busy loop. There are two major use cases for concurrency:

  • you have slow IO tasks and other tasks: run another task when an IO task is sent to its devices.
  • you have one or more tasks, such as a UI, that should not wait too long: pause the current task, update UI every 16ms, then resume the task.

Concurrency is about working smarter. Parallelism is a way of throwing more resources at the problem.

Though the IO devices work in a parallel way and the computer has multiple cores running multiple threads in parallel, the reference frame is the programmer and the program code/process, not the whole system. A system often has mutliple cores that each core runs multiple hyperthreads, in addition to multiple IO devices that work in parallel.

2 Operating System

An operating system provides services to processes and uses preemptive multitasking to run processes and manage IO devices.

A program uses syscall to use OS services. There are thre levels of syscall.

  • In the lowest level, you use inline assembly to call OS services by setting CPU registers directly.
  • The next level is to use OS provided API. Every Linux installation comes with a version of libc which is a C-library for communicating with the operating system. Rust makes an unsafe call to FFI (foreign function interface) in the C-library.
  • The highest level to call OS functions exposed in the current programming langauge. In Rust, it is something like println!.

Modern CPU provides basic infrastructure such as memoery managment and security that OS uses. When an OS boots, it sets handlers in Interrupt Descriptor Table (IDT) to use the CPU services. OS runs in Ring 0 that has access to all functions. User programs runs in Ring 3 and has restricted access to I/O, CPU registers and instructions.

3 Handling I/O

When a program calls an I/O syscall, itregisters an event with the OS that can be handled in one of three ways:

  • The OS suspends program thread and wakes it up when the call completes.
  • The OS returns a handler that the program can poll. When the call completes, the poll gets the result. The program thread keeps running.
  • The program uses an event queue that has many events. The program thread blocks when it polls the event queue. When the call completes, OS wakes up the thread and the poll gets the result.

The OS, I/O controlllers and device driver process the I/O request. They use the hardware/software interrupt and IDT to communicate.

A program has three strategies for I/O tasks:

  • 1 One OS thread per task
  • 2 One green thread per task
  • 3 Poll-based event loop supported by the OS. I/O tasks are suspended when wait and are resumed when tasks complete.

Both Node and Rust’s async use option 3. Node uses OS async calls and for async I/O tasks and a thread pool (default size of 4) for CPU-bound tasks.

4 Design

The runtime has two event queues: one for thread pool and one for os async operations. The basic logics are:

  • store callbacks to be run later
  • send task to thread pool
  • subscribe to os event queue
  • poll the two queues
  • handle timers
  • provide a way for program to register http, file system and crypto tasks
  • progress all tasks unitl complete

5 Runtime Run

The RT run() function runs the main function first, then runs an event loop. The event loop checks pending_events. If it 0, it exits. Othwerwise, keep looping.

  1. check if three is any timers has expired. If there is any, store the the expired callbacks.
  2. call run_callbacks() for the expired timers.
  3. idel/prepar: exists in node but unused here.
  4. poll the event queues of thread pool and epoll: it set epoll_timeout to the next timer or Infinity. Both the thread pool threads and epoll thread holds a sending part of the channel event_receiver. Then send result when a thread task or I/O task is completed. The main thread blocks until something happens, or a timeouot event created by epoll thread occurs. When it resumes, it pushes the corresponding thread pool or epoll event into callbacks stack and do nothing for timeout. Then it calls run_callbacks().
  5. check. In Node, this executes setImmediate calls. Do nothing in this RT.
  6. Close callbacs to release resources such as sockets and file descriptors.

The the loop exits, RT close all threads and free resources.

5 Create Runtime

It first creates a channel, all threads get a copy of the sender and RT keeps the reciever.

Then it creates the thread pool. For each thread, there is a channel whose sender is pushed to the pool and receiver is use to get tasks. A new thread is created and listens on the channel. if there is a task, the thread runs it.

The next is to create an event queue and an epoll thread. This thread runs a loop and waits on an event or a timeout.