Thoughts on a task system

TASK.md

• WORK ITEM:

  • Work closure
  • pointer to TASK

• TASK:

  • WORK ITEMs Array
  • Atomic num_open_work_items counter - init to number of WORK ITEMs
  • Permits pointer to TASK which depends on this one

• WORKER

  • Work stealing SPMC deque of WORK ITEMs.

WORKERS do the usual thread stealing business, trying to pop from their thread-local deque, or failing that, to steal work from other deques (presumably stealing in blocks to amortise steal cost).

When a TASK is started it pushes all of its WORK ITEMs onto the thread local WORKER's deque.

When a WORK ITEM is completed by a WORKER it atomically decrements the num_open_work_items counter.

If the num_open_work_items counter is made to be 0 by a WORK ITEM being completed then we consider the TASK to be completed.

When a TASK is completed we start the task pointed to by the optional permits pointer.

WORKERs are parked / unparked heuristically based on work availability. (At least that's the theory, haven't thought that through entirely)

API

// Multiple submit calls refrencing the same depends Task is
// an API Failure.
fn submit<F: FnOnce()>(tasks: &[F], depends: Task) -> Task;
fn run(task: Task);

Why?

The point of having the permit instead of a dependency is to avoid having to maintain a global NOT READY queue of blocked work.

The reason for having a single permit is to avoid having to deal with storing a thread-safe list of permits for each task.

Relying on a single permit would be an unreasonable limitation, so we allow multiple work items for each TASK. Since the WORK ITEM list is only ever used by a single thread (created in submit, used in TASK finish()) we don't have to worry about such things.

Not considered yet

• Allocation

  • plan is to just use the system allocator for TASKs, but perhaps a more sophisticated method would be a good idea.

• Deallocation

  • do I need to be clever about deallocating TASKs to avoid use-after-free?

• Sanity

  • is this in fact, absolute madness?