Каков наилучший способ отправки структуры связанного списка между процессами через канал в программировании Linux

Вы также можете использовать разделяемую память System V (посмотрите на такие функции, как shmat) или mmap, чтобы разделить память между процессами. Boost.Interprocess имеет оболочку C++ для этих вызовов, так что вы можете создать связанный список непосредственно в общей памяти без копирования.

Я предполагаю, что вы пытаетесь реализовать сито Eratothenes, используя многопроцессорность. Если я неправильно истолковываю то, что вы описываете, ваш алгоритм можно улучшить. То, что вы описываете, представляет собой систему, в которой список чисел передается дочернему процессу, который проверяет ВСЕ значения, прежде чем передать остальную часть списка следующему дочернему процессу.

Я бы реализовал алгоритм как конвейер процессов

Generator -> [Prime2] -> Prime3 -> Prime5 -> Prime7 -> ... PrimeP

где следующий процесс Prime создается последним процессом в цепочке. Поэтому, когда генерируется 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))

для записи данных в следующую ссылку.

Когда сгенерировано последнее число, цепочка может быть остановлена ​​несколькими способами:

1. PoisonPill (например, значение 0 или другое недопустимое число) передается вниз. Это хорошо работает с блоками при чтении из каналов.
2. SIGTERM отправляется всем процессам в группе процессов.
3. SIGTERM передается по цепочке, как PoisonPill (вероятно, не так эффективно, как 2).

Если генератору необходимо собрать все значения, они могут быть отправлены обратно вверх по цепочке с использованием другого набора каналов при отправке PoisonPill; Вторую PoisonPill также можно использовать в качестве своего рода контроля.

С этим есть некоторые проблемы:

1. Большая часть действий обрабатывается первыми несколькими простыми числами.
2. Есть много ожидания.
3. Существует верхний предел количества реальных процессов, которые может обрабатывать система. Если вы используете что-то вроде Haskell, это не проблема, но это для C.
4. Используется большое количество труб. Вторым набором каналов для возврата значения может быть shmem, общий fifo и т. д.
5. Большинство машин имеют небольшое количество процессоров... Одновременно могут работать лишь некоторые из них. Один из способов обойти это — ограничить количество потоков, но каждый процесс должен управлять несколькими числами. В этом случае вы хотели бы отправить блочный массив чисел одновременно каждому PrimeProcessor. Процессор обнуляет все непростые значения и возвращает оставшийся список (массив) обратно родителю. Затем родитель присваивает эти простые числа процессору PrimeProcessor (на данный момент не гарантируется, что возвращаемые значения будут простыми; может потребоваться дальнейший анализ), и отправляется новая партия целых чисел.

Чтобы ответить на ваш вопрос, отправка связанного списка не имеет смысла, насколько я могу судить. Вы собираетесь отправлять их по цепочке один за другим или, по крайней мере, в виде массива.

Либо отправьте индексы в список вместо указателей, либо сожмите список в массив и отправьте его вместо этого.

(Похоже, вы внедряете решето Эратофена, которое в любом случае работает быстрее с массивами.)

Если вы используете каналы, вы «удаляете» записи, не записывая эту запись в канал. Поэтому не беспокойтесь об удалении данных из списка, просто подумайте о том, следует ли вам записывать запись, которую вы читаете, из канала ввода в канал вывода.