Я предполагаю, что вы пытаетесь внедрить Сито Эратотенов с использованием многопроцессорной обработки. Если я неправильно истолковываю то, что вы описываете, ваш алгоритм может быть улучшен. То, что вы описываете, - это система, в которой список чисел передается дочернему процессу, который проверяет ВСЕ значения, прежде чем передать остальную часть списка следующему дочернему элементу.
Я бы реализовал алгоритм как конвейер процессов
Generator -> [Prime2] -> Prime3 -> Prime5 -> Prime7 -> ... PrimeP
где следующий основной процесс создается последним процессом в цепочке. Таким образом, когда генерируется 8, он отфильтровывается Prime2 и удаляется. Когда 9 отправлено, оно передается Prime2, который передает его Prime3, который сбрасывает его. 10 затем отбрасывается на 2, а 11 проходит через всю цепочку, и поскольку у Prime7 нет связи в цепочке после нее, он разветвляет новый процесс с аргументом 11. Prime2 должен потреблять значения так же быстро, как они генерируются. Когда Prime 2 вычисляет 20, Prime3 вычисляет 19 и так далее. (Оптимизация: Prime2 в основном не нужен с точки зрения реализации).
Когда новый процесс PrimeN создается процессом PrimeP, родитель создает 2 канала, один для записи в новый процесс, а другой для чтения из нового процесса. Каждый нетерминальный узел процесса будет тогда иметь в общей сложности 4 канала: два ведут в / из узла-преемника, а два ведут в / из узла-предшественника. Неиспользуемый конец каждого узла можно закрыть, но это не является строго обязательным.
Этот алгоритм хорош, потому что каналы читаются до считывания значения. Числа могут быть отправлены в виде двоичных данных по каналам:
read(parent, &value, sizeof(value))
для чтения данных из предыдущего процесса и
write(stdout, &value, sizeof(value))
для записи данных по следующей ссылке.
Когда генерируется последнее число, цепочку можно остановить несколькими способами:
- PoisonPill (например, значение 0 или другое недопустимое число) передается вниз. Это хорошо работает с блоками при чтении из каналов.
- SIGTERM отправляется всем процессам в группе процессов.
- SIGTERM передается по цепочке, как PoisonPill (вероятно, не так эффективно, как 2).
Если генератору нужно собрать все значения, то они могут быть отправлены обратно по цепочке, используя другой набор каналов, когда отправляется PoisonPill; Второй PoisonPill также может быть использован в качестве некоторого элемента управления.
Есть некоторые проблемы с этим:
- Большая часть действия обрабатывается первыми несколькими простыми числами.
- Там много ожидания.
- Существует верхний предел количества реальных процессов, которые может обрабатывать система. Если вы используете что-то вроде Haskell, это не проблема, но для C.
- Есть много используемых труб. Второй набор каналов для возврата значения может быть shmem или разделяемым fifo и т. Д.
- Большинство машин имеют небольшое количество процессоров ... Только несколько могут работать одновременно. Одним из способов решения этой проблемы является ограничение количества потоков, но каждый процесс должен управлять несколькими числами. В этом случае вы захотите отправить массив чисел блоков сразу каждому PrimeProcessor. Процессор обнуляет все не простые значения и возвращает оставшийся список (массив) обратно родителю. Затем родительский элемент назначает эти простые числа PrimeProcessor (возвращаемые значения не обязательно будут простыми на этом этапе; может потребоваться дальнейший анализ), и отправляется новый пакет целых чисел.
Чтобы ответить на ваш вопрос, отправка связанного списка не имеет смысла, насколько я могу судить. Вы собираетесь отправить их по цепочке один за другим или, по крайней мере, в виде массива.