Concurrency/queue with specific, dynamic execution order

I have a program that collects some tasks to execute, and each task has a priority. Higher-priority tasks should be executed first. More tasks may be discovered during program's execution, and they should jump the queue if needed.

In a single thread it's easy to do with a BinaryHeap:

while let Some(task) = heap.pop() {
    task();
    heap.push(more_tasks());
}

However, how can I parallelize it without losing too much of the ordering?

Existing threadpools assume you push all tasks into their queue:

while let Some(task) = heap.pop() {
    rayon::spawn(task); // or channel.send(task) or such
    heap.push(more_tasks());
}

but then I'll immediately drain my heap into another queue, which won't give new tasks a chance to be sorted before the tasks that have already been sent to a threadpool.

Is there some library or design pattern that will "pull" tasks out of my binary heap lazily only immediately before spawning a new task?

Is it possible to solve this with an extra level of indirection?

Right now, each task = actual work to be done.

Extra indirection:
each task = closure with Arc to multi threaded heap
when 'task' is executed, it pops 'real task' from the multi threaded heap and executes it

Thus, each thread is pushed a bunch of 'lazy tasks', that when executed, pops the 'real task' off the multi threaded heap.

2 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.