]> git.hungrycats.org Git - bees/commit
task: add an `insert` method for priority-queueing Tasks by age
authorZygo Blaxell <bees@furryterror.org>
Sun, 12 Jan 2025 04:21:31 +0000 (23:21 -0500)
committerZygo Blaxell <bees@furryterror.org>
Sun, 12 Jan 2025 05:35:37 +0000 (00:35 -0500)
commit74d8bdd60fab1d8d5149f66f73fb5bc3438fcc82
tree5ce8b99d9c3cffe3e3d8be2748e63401097895ce
parenta5d078d48bec7f7038f1cded0b3ccafe4ff784b4
task: add an `insert` method for priority-queueing Tasks by age

Task started out as a self-organizing parallel-make algorithm, but ended
up becoming a half-broken wait-die algorithm.  When a contended object
is already locked, Tasks enter a FIFO queue to restart and acquire the
lock.  This is the "die" part of wait-die (all locks on an Exclusion are
non-blocking, so no Task ever does "wait").  The lock queue is FIFO wrt
_lock acquisition order_, not _Task age_ as required by the wait-die
algorithm.

Make it a 25%-broken wait-die algorithm by sorting the Tasks on lock
queues in order of Task ID, i.e. oldest-first, or FIFO wrt Task age.
This ensures the oldest Task waiting for an object is the one to get
it when it becomes available, as expected from the wait-die algorithm.

This should reduce the amount of time Tasks spend on the execution queue,
and reduce memory usage by avoiding the accumulation of Tasks that cannot
make forward progress.

Note that turning `TaskQueue` into an ordered container would have
undesirable side-effects:

 * `std::list` has some useful properties wrt stability of object
 location and cost of splicing.  Other containers may not have these,
 and `std::list` does have a `sort` method.

 * Some Task objects are created at the beginning and reused continually,
 but we really do want those Tasks to be executed in FIFO order wrt
 submission, not Task ID.  We can exclude these tasks by only doing the
 sorting when a Task is queued for an Exclusin object.

Signed-off-by: Zygo Blaxell <bees@furryterror.org>
include/crucible/task.h
lib/task.cc