Допустим, нужно проделать много каких-то вычислений, и хочется разбросать их на разные треды. Но одни вычисления зависят от других.
Например если надо посчитать (sin((a+b+c+d)*(e+f+g)))^((a+b+c+d)+(h+i+j)) то можно построить такое дерево:
(_^_)
^ ^
| |
+----+ +---+
| |
sin(_) |
^ |
| |
(_*_) (_+_)
^ ^ ^ ^
| | | |
+----+ +-+------+ |
| | |
(e+f+g) (a+b+c+d) (h+i+j)
Как я себе это представляю:
Надо строить направленный ациклический граф, в каждой вершине храним указатель на следующие вершины(в примере у (a+b+c+d) две следующих вершины: (_*_) и (_+_)); счетчик числа вершин, указывающих на эту вершину, указатель на функцию, которую надо вызвать; массив указателей на данные, которые в эту функцию надо передавать; указатель на область памяти, куда надо записать результат выполнения функции.
Вначале нужно создать очередь, в которую помещаем указатели на те вершины, на которые никакие другие вершины не указывают. Запускаем некоторое количество тредов. По завершени обработки задачи, каждый тред декрементирует счетчик числа вершин в тех вершинах, на которые указывает та вершина, задача из которой была завершена этим тредом(например по завершении (a+b+c+d) надо декрементировать счетчик у вершин (_*_) и (_+_)). Если оказывается что после декрементирования счетчика в только одной вершине оказался 0, тред немедленно приступает к выполнению задачи из той вершины. Если в двух и более счетчиках в вершинах оказался 0, тред добавляет в очередь указатели на все такие вершины, кроме одной, и выполняет задание из той «одной» вершины, которая не добавлена в очередь. Иначе он берет задачу из очереди. Если в очереди ничего нет, тред выставляет особое значение в некоторой переменной, означающее что этот тред бездействует, после чего этот тред сам себе шлет сигнал SIGSTOP. И надо сделать так, чтобы при добавлении задач в очередь, проверялось наличие бездействующих тредов, и слать им сигнал SIGCONT.
Как подобная модель многопоточности называется? Есть ли уже готовые реализации подобного для C или других языков программирования? Через вызов clone() и всякие там CAS спинлоки такое реализовать нетрудно, как мне кажется. Поверх этого можно еще сделать реактивное программирование.
