Notes on Heartbeat Scheduling

First of all, the information I have about “Heartbeat Scheduling” is from the Zig implementation of it, not the original paper. The Coq proof said to be provided by the original paper is corrupted and can’t be found anywhere, not even on the source code repo they provided. sighs

The main idea is every idle thread checks gets a new task every 100 microseconds (configurable), and every busy thread shares a task. Threads are sent heartbeat like barrels of a Gatling gun to reduce contention on the global state mutex.

A busy thread executing a task must call Task.tick() every so often to respond to heartbeat event. Basically, these are like preemption points, except it shares a task.

To summarize:

• Gatling gun-like task sharing (give and take)
• A thread can only share or fetch a task on every heartbeat received
• Use the smallest grain possible / Split tasks into smallest chunks

Fundamental synchronization primitives used on Linux:

• timer -> high resolution timers
• mutex -> futex
• semaphore -> also futex
• condition -> also also futex