二进制过程树与叉（） [英] Binary Process Tree with fork()

问题描述

我对我的操作系统级的第一个项目是创建一个使用叉一个进程树（）具有深度用户指定的命令行。每个叶级节点需要对数据进行排序，并使用命名管道传回给其父（FIFO的）。

My first project for my OS class is to create a process tree using fork() that has a depth that the user specifies at the command line. Each leaf level node needs to sort data and pass it back to its parent using named-pipes (FIFOs).

我可以创建的N深度树叉（），每个进程有2名儿童。我无法弄清楚如何在一个FIFO传递给每个孩子一路下滑的树，然后有这样的处理的某些数据FIFO中的进行排序，然后也传回了树的顶端。

I can create an N-depth tree with fork(), each process having 2 children. What I can’t figure out is how to pass a FIFO to each child all the way down the tree and then have this process perform a sort on certain data in the FIFO and then also pass it back up the tree to the top.

下面是我有什么伪code迄今为止建造的树：

Here is the pseudo-code of what I have so far for building the tree:

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);
    }
}

那么，如何抓住每个进程单独做的工作与他们？

So how do I grab each process individually to do work with them?

推荐答案

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

You did not state any dataflow requirements such as the source of the data that the leaves are to sort. In terms of division of labor, the leaf nodes will sort, but the branches need only merge. In some sense, you are creating a hybrid mergesort that uses processes and FIFOs instead of the stack.

如前所述，您可以使用分配值数组的简单，但不雅的方法来进行排序，并在主要的过程中创造的所有的FIFO锋线。根据每个孩子的标识或索引号，它会从整体阵列和适当的FIFO（例如， FIFO选择一定范围内的数据。 N 该节点的 N 的使用将数据传输到它的父）的FIFO中。回想一下，用叉创建一个子进程共享其父的地址空间，可以看到在全局范围内阵列，例如。

As stated, you could use the simple but inelegant approach of allocating an array of values to be sorted and creating all FIFOs up front in the main process. Based on each child’s identifier or index number, it would select a range of data from the overall array and the appropriate FIFO (say, fifo.N for the FIFO that node N uses to transmit data to its parent). Recall that a child process created with fork shares its parent’s address space and can see an array at global scope, for example.

一个二叉树很好地包到一个数组。据二叉树维基百科

A binary tree packs nicely into an array. According to Binary tree on Wikipedia

二进制树，也可以存储在广度优先顺序在阵列的隐式数据结构，并且如果树是一个完整的二进制树中，此方法不浪费空间。在这种安排紧凑，如果一个节点有一个索引的 I 的，其子女在指数中的 2I + 1 的（左子）和 2I + 2 的（合适），而其母公司（如果有的话）是在索引中找到⌊的（I-1）/ 2 的⌋（假设根的索引值为零）。

Binary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index i, its children are found at indices 2i+1 (for the left child) and 2i+2 (for the right), while its parent (if any) is found at index ⌊(i-1)/2⌋ (assuming the root has index zero).

注意⌊<青霉> X 的⌋是最大的整数不大于<青霉> X 的更大，也被称为中的 X 的楼。在C语言中，可以通过指定的价值（I-1）/ 2 来类型的变量 INT 。

Note that ⌊x⌋ is the greatest integer not greater than x, also known as the floor of x. In C, you can get the floor by assigning the value of (i-1)/2 to a variable of type int.

要围绕线程你的树节点标识符，你可以用code，如

To thread node identifiers around your tree, you could use code such as

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

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 (depth 0)
[28838]: i=1 (depth 1)
[28839]: i=3 (depth 2)
[28840]: i=7 (depth 3)
[28841]: i=8 (depth 3)
[28842]: i=4 (depth 2)
[28843]: i=9 (depth 3)
[28844]: i=10 (depth 3)
[28845]: i=2 (depth 1)
[28846]: i=5 (depth 2)
[28847]: i=11 (depth 3)
[28848]: i=12 (depth 3)
[28849]: i=6 (depth 2)
[28850]: i=13 (depth 3)
[28851]: i=14 (depth 3)

这篇关于二进制过程树与叉（）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！