带叉子的二进制进程树（）

我的OS类的第一个项目是使用fork()创建一个进程树，它具有用户在命令行指定的深度。 每个叶级节点都需要对数据进行排序，并使用命名管道（FIFO）将其传递回父级。

我可以用fork()创建一个N深度树，每个进程有2个子节点。 我无法弄清楚的是如何将FIFO一直传递给树中的每个子进程 ，然后让这个进程对FIFO中的某些数据执行排序，然后将其从树中传递回顶部。

这是我到目前为止构建树的伪代码：

 void CreateTree(int level) { if level = 0 return int left_child = fork(); if(left_child != 0) //we are the parent { int right_child = fork(); if(right_child == 0) CreateTree(level - 1); } else { CreateTree(level-1); } } 

那么我如何单独抓取每个进程来与它们一起工作呢？

Answer 1

你提到了fifo，又名命名管道，所以我们来看看。 （这里的代码假定为* nix）：

这个快速示例显示了从父级向子级发送数据，让孩子操纵它，然后将其返回给父级。 所以你不是“传递”fifo，但每个进程（或子进程）都可以访问char * ，它给了他们fifo的名字，这样他们就可以根据需要打开它进行读或写。 您可以采用此概念并针对您拥有的每个子节点进行扩展：

 int main() { int fd, n, ret; fd_set rfds; char * myfifo = "/tmp/myfifo"; mkfifo(myfifo, 0666); // Create this buffer if(fork()) //Kid code { char kid_buffer[4] = {0}; char temp; fd = open(myfifo, O_RDONLY); //Open the fifo for reading n = read(fd, kid_buffer, 4); printf("Kid %d read %d bytes, parent gave us %s\n",getpid(), n, kid_buffer); fflush(stdout); close(fd); // "sort" the data the parent gave us temp = kid_buffer[0]; kid_buffer[0] = kid_buffer[1]; kid_buffer[1] = kid_buffer[2]; kid_buffer[2] = temp; kid_buffer[3] = '\0'; printf("Kid %d reoriginized the list %s\n",getpid(), kid_buffer); fflush(stdout); // send the data back fd = open(myfifo, O_WRONLY); write(fd, kid_buffer, strlen(kid_buffer)); close(fd); return 0; } else { char arr[] = "abc"; //Open the fifo for writing fd = open(myfifo, O_WRONLY); write(fd, arr, strlen(arr)); //Sent my data to kid printf("Parent process %d, just sent my data %s to the kid\n", getpid(), arr); fflush(stdout); close(fd); //Open the fifo for reading fd = open(myfifo, O_RDONLY); n = read(fd, arr, 4); // show the data we got back printf("Parent %d read %d bytes, kid gave us back %s\n",getpid(), n, arr); fflush(stdout); close(fd); } unlink(myfifo); return 0; } 

所以从这里的输出你可以看到父创建了它自己的数组“abc”，并且它被子节点（通过FIFO传递）修改为“bca”，现在它已经与父节点一起返回并格式化。

 mike@linux-4puc:~> ./a.out Parent process 4295, just sent my data abc to the kid Kid 4294 read 3 bytes, parent gave us abc Kid 4294 reoriginized the list bca Parent 4295 read 3 bytes, kid gave us back bca 

Answer 2

您没有说明任何数据流要求，例如要对叶子进行排序的数据源。 在分工方面，叶子节点将排序，但分支只需要合并。 从某种意义上说，您正在创建一个使用进程和FIFO而不是堆栈的混合mergesort 。

如上所述，您可以使用简单但不优雅的方法来分配要排序的值数组，并在主进程中预先创建所有FIFO。 根据每个孩子的标识符或索引号，它将从整个arrays和适当的FIFO中选择一系列数据（例如，节点N用于将数据传输到其父节点的FIFO的FIFO为N ）。 回想一下，使用fork创建的子进程共享其父地址空间，并且可以在全局范围内查看数组。

二叉树很好地包装到一个数组中。 根据维基百科上的二叉树

二叉树也可以以广度优先的顺序存储为数组中的隐式数据结构，如果树是完整的二叉树，则此方法不会浪费空间。 在这种紧凑的安排中，如果节点具有索引i ，则其子节点在索引2i + 1 （对于左子节点）和2i + 2 （对于右子节点）处找到，而其父节点（如果有的话）在索引处找到。 （i-1）/ 2⌋（假设根的索引为零）。

注意，⌊x⌋是不大于x的最大整数，也称为x的底数 。 在C中，您可以通过将(i-1)/2的值赋给int类型的变量来获得最终结果。

要在树周围创建节点标识符，可以使用诸如的代码

 #include  #include  #include  void proc_tree(int i, int current_depth, int max_depth) { pid_t kid = fork(); if (kid == -1) { fprintf(stderr, "[%d]: fork: %s\n", getpid(), strerror(errno)); } else if (kid == 0) { /* child */ printf("[%d]: i=%d (depth %d)\n", getpid(), i, current_depth); if (current_depth < max_depth) { proc_tree(2*i+1, current_depth+1, max_depth); proc_tree(2*i+2, current_depth+1, max_depth); } exit(EXIT_SUCCESS); } else { /* parent */ pid_t pid; int status; pid = waitpid(kid, &status, 0); if (pid == -1) fprintf(stderr, "[%z]: waitpid: %s\n", getpid(), strerror(errno)); } } 

用它调用它

 int main(int argc, char *argv[]) { int depth; if (argc != 2) { fprintf(stderr, "Usage: %s depth\n", argv[0]); return EXIT_FAILURE; } depth = atoi(argv[1]); if (depth < 0) { fprintf(stderr, "%s: depth must be non-negative\n", argv[0]); return EXIT_FAILURE; } proc_tree(0, 0, depth); return EXIT_SUCCESS; } 

样本输出：

  $ ./tree-sort 3
 [28837]：i = 0（深度0）
 [28838]：i = 1（深度1）
 [28839]：i = 3（深度2）
 [28840]：i = 7（深度3）
 [28841]：i = 8（深度3）
 [28842]：i = 4（深度2）
 [28843]：i = 9（深度3）
 [28844]：i = 10（深度3）
 [28845]：i = 2（深度1）
 [28846]：i = 5（深度2）
 [28847]：i = 11（深度3）
 [28848]：i = 12（深度3）
 [28849]：i = 6（深度2）
 [28850]：i = 13（深度3）
 [28851]：i = 14（深度3） 

Answer 3

• 为每个孩子分配一个号码（不是PID;你需要在有PID之前知道号码！）。
• 创建一个FIFO（ mkfifo() ），其名称为fifo.N ，其中N是数字。
• 然后每个孩子都知道要写入哪个FIFO。
• 每个父母都知道要从哪个FIFO读取。 （据推测，父母只是在进行合并而不是一种合并。）

据推测，孩子们不知何故都知道他们要分类的数据。

---

在我初始化所有我的FIFO之后，我如何知道正在执行哪个进程以及何时执行？ 在构建树之后，当我回到主程序中时，有没有办法根据PID和控制语句来判断哪个进程正在运行？

流程可分为“叶子”和“非叶子”流程。

叶子过程没有任何孩子。 他们进行排序分配并将排序后的数据写入其输出FIFO。 它们将被阻塞在FIFO上，直到它们的父进程打开它进行读取。 当它们完成写入时，它们关闭FIFO并且父进程获得EOF。

每个非叶子进程正在合并来自其两个子节点的排序数据。 每个非叶子进程需要知道它自己的输出FIFO是什么（根节点可能写入标准输出而不是FIFO），以及它的两个子FIFO是什么。 也许非叶子进程创建了fifo。$$。1和fifo。$$。2（其中’$$’是已经运行的非叶进程的PID），而不是让父进程创建它们面前。 然后它分叉它的两个孩子，一个变量向每个孩子指示使用哪个FIFO。 然后非叶进程打开两个FIFO进行读取（以及它自己的写入输出FIFO），然后合并两个数据流（从两者读取一行，将较小的写入输出，读取替换行，并保持一直到EOF，然后从另一个完成读数）。 完成后，该过程将删除它创建的两个FIFO（基本卫生）并关闭其输出FIFO并退出。

在顶层（原始过程），基本机制与任何非叶过程相同; 它会创建两个FIFO，启动两个子节点，打开FIFO进行读取，对两个流进行合并，写入标准输出而不需要弄乱另一个FIFO。