Deadlock avoidance scheduling with semaphores?

[robinchrist]

Assume we have the following example:

#include <iostream>
#include "taskflow/taskflow/core/executor.hpp"
#include "taskflow/taskflow/core/semaphore.hpp"
#include "taskflow/taskflow/taskflow.hpp"

int main() {
    tf::Executor exec(24);

    tf::Taskflow flow;

    tf::Semaphore semaphore(8);

    for(size_t i = 0; i < 5; ++i) {

        tf::Task commonTask = flow.emplace([i]() {
            std::string str;
            str.append("Common task for i = ").append(std::to_string(i)).append("\n");
            std::cout << str;
        }).name(std::string("Common i = ").append(std::to_string(i)));

        for(size_t j = 0; j < 8; ++j) {
            tf::Task preTask = flow.emplace([i, j]() {
                std::string str;
                str.append("Pre task for i = ").append(std::to_string(i)).append(", j = ").append(std::to_string(j)).append("\n");
                std::cout << str;
            }).name(std::string("Pre task i = ").append(std::to_string(i)).append(", j = ").append(std::to_string(j)));

            tf::Task postTask = flow.emplace([i, j]() {
                std::string str;
                str.append("Post task for i = ").append(std::to_string(i)).append(", j = ").append(std::to_string(j)).append("\n");
                std::cout << str;
            }).name(std::string("Post task i = ").append(std::to_string(i)).append(", j = ").append(std::to_string(j)));

            preTask.precede(commonTask);
            postTask.succeed(commonTask);

            preTask.acquire(semaphore);
            postTask.release(semaphore);
        }
    }

    flow.dump(std::cout);

    std::cout << "Start!" << std::endl;
    exec.run(flow).wait();
    std::cout << "End!" << std::endl;
}

Where we want to limit the concurrency, e.g. due to memory allocation constraints

The issue is that, as I feared it would, taskflow schedules itself into a deadlock.

Output looks like:

Start!
Pre task for i = 0, j = 0
Pre task for i = 0, j = 5
Pre task for i = 0, j = 4
Pre task for i = 0, j = 2
Pre task for i = 0, j = 3
Pre task for i = 0, j = 7
Pre task for i = 0, j = 1
Pre task for i = 0, j = 6
Common task for i = 0
Post task for i = 0, j = 7
Post task for i = 0, j = 0
Post task for i = 0, j = 2
Post task for i = 0, j = 3
Pre task for i = 3, j = 3
Pre task for i = 1, j = 0
Post task for i = 0, j = 5
Post task for i = 0, j = 1
Pre task for i = 1, j = 3
Pre task for i = 2, j = 2
Pre task for i = 1, j = 1
Post task for i = 0, j = 6
Pre task for i = 4, j = 1
Post task for i = 0, j = 4
Pre task for i = 2, j = 6
Pre task for i = 1, j = 2

...and then hangs

What would be the best way to rewrite this issue and still limit the concurrency?

Maybe adding another separate acquire (precedes all 8 pre tasks) and release (succeeds all post tasks) task?

And would it be feasible for taskflow to get a scheduler that understands such issue and avoids them? I could imagine that this is, as always, an NP-complete issue or would come with great implications.

Anyway, I think adding a warning to the documentation would be good - Warn users that taskflow may schedule itself into deadlocks when using semaphores