在linux编程中通过管道在进程之间发送链表结构的最佳方式是什么

发布于 2024-10-20 21:45:41 字数 217 浏览 7 评论 0原文

我尝试在来自同一父进程的子进程之间发送链接列表。 Child1 需要找到列表中的第一个素数并删除它及其倍数，然后发送给 Child2。 Child2 执行相同操作并将其发送到 Child3，ChildN 执行相同操作并将其发送到 Child1。但是，我尝试在而不是所有数字之间发送地址数据，但这是否是正确的方法，因为也许我强迫我的子进程进入另一个地址空间。那么您认为最好的方式是什么，或者除了发送地址之外的任何其他方式？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

混浊又暗下来 2024-10-27 21:45:41

您还可以使用 System V 共享内存（查看诸如 shmat 之类的函数）或 mmap 在进程之间共享内存。 Boost.Interprocess 对这些调用有一个 C++ 包装器，这样您就可以直接在共享内存中创建链接列表，而无需复制。

回复收藏 0 原文

浮萍、无处依 2024-10-27 21:45:41

我假设您正在尝试使用多处理来实现埃拉托尼筛法。除非我误解了你所描述的内容，否则你的算法可以改进。您所描述的是一个系统，其中将数字列表传递给子进程，该子进程在将列表的其余部分传递给下一个子进程之前检查所有值。

我将该算法实现为进程管道，

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

其中下一个 Prime 进程由链上的最后一个进程创建。因此，当生成 8 时，它会被 Prime2 过滤掉并丢弃。当发送 9 时，它被传递到 Prime2，Prime2 将其传递到 Prime3，Prime3 将其丢弃。然后将 10 减 2，然后将 11 传递到整个链，并且由于 Prime7 之后的链中没有链接，因此它会分叉一个以 11 作为参数的新进程。 Prime2 消耗值的速度应该与生成值的速度一样快。当Prime 2 计算20 时，Prime3 计算19 等等。（优化：从实现的角度来看，Prime2 基本上是不必要的）。

当进程 PrimeP 创建新进程 PrimeN 时，父进程创建 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（此时返回的值不能保证是素数；可能需要进行进一步的分析），并发送一批新的整数。

为了回答您的问题，据我所知，发送链接列表没有意义。您将把它们沿着链一一发送，或者至少作为一个数组发送。

I am assuming you are trying to implement a Sieve of Eratothenes using multiprocessing. Unless I am misintepreting what you are describing, then your algorithm can be improved. What you describe is a system where a list of numbers is passed to a child process that checks ALL of the values before handing the rest of the list to the next child.

I would implement the algorithm as a pipeline of processes

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

where the next Prime process is created by last process on the chain. So when 8 is generated, it gets filtered out by Prime2 and dropped. When 9 is sent, it is passed to Prime2, which passes it to Prime3 which drops it. 10 is then dropped by 2, and 11 is passed through the whole chain, and because Prime7 has no link in the chain after it, it forks a new process with 11 as the argument. Prime2 should be consuming values as fast as they are being generated. When Prime 2 is calculating 20, Prime3 is calculating 19 and so on. (Optimization: Prime2 is largely unnecessary from an implementation view).

When a new process PrimeN is created by process PrimeP, the parent creates 2 pipes, one for writing to the new process, and the other for reading from the new process. Each non-terminal process node will then have a total of 4 pipes: two are leading to/from the successor node, and two are leading to/from the predecessor node. The unused end of each node can be closed, but this isn't strictly necessary.

This algorithm is nice because the pipes block on read until a value can be read. The numbers can be sent as binary data through pipes:

read(parent, &value, sizeof(value))

to read data from the previous process and

write(stdout, &value, sizeof(value))

to write data to the next link.

When the last number is generated, the chain can be halted in several ways:

A PoisonPill (e.g. the value 0 or some other invalid number) is passed down. This works nicely with blocks while reading from pipes.
A SIGTERM is sent to all of the processes in the Process Group.
A SIGTERM is passed down the chain like the PoisonPill (probably not as efficient as 2).

If the generator needs to collect all of the values then they could be sent back up the chain using the other set of pipes when a PoisonPill is sent; A second PoisonPill could also be used as some sort of control as well.

There are some issues with this:

A lot of the action is handled by the first few primes.
There is a lot of waiting.
There is an upper limit to the number of real processes a system can handle. If you are using something like Haskell, this isn't a problem, but it is for C.
There are a lot of pipes being used. The second set of pipes for value return could be shmem, or a shared fifo, etc.
Most machines have a small number of processors... Only a few can run at the same time. One way around this is to cap the number of threads, but have each process manage several numbers. In this case, you would want to send a block array of numbers at once to each PrimeProcessor. The processor nulls out all of the non-prime values, and returns the remaining list (array) back to the parent. The parent then assigns these primes to the PrimeProcessor (the returned values are not guaranteed to be prime at this point; further analysis may have to be done) and a new batch of integers are sent out.

To answer your question, sending a linked list doesn't make sense as far as I can tell. You are going to send them down the chain one by one, or at the very least, as an array.

回复收藏 0 原文