3

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).

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.

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?

4

3 回答 3

1

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

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

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

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

注意 ⌊<em>x⌋ 是不大于x的最大整数，也称为x的下限。(i-1)/2在 C 语言中，您可以通过将 的值分配给类型为 的变量来获得发言权int。

要在树周围线程节点标识符，您可以使用代码，例如

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

样本输出：

$ ./树排序 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）
于 2012-10-23T20:24:51.423 回答
1

You mentioned fifo, aka a named pipe, so we'll look at that. (code here assumes *nix):

This quick example shows sending data from the parent to the child, having the child manipulate it, then returning it to the parent. So you're not "passing" the fifo, but each process (or child process) will have access to the char * which gives them the name of the fifo so they can open it for reading or writting as they need to. You can take this concept and expand upon it for each of the children nodes you have:

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

So from the output here you can see the parent created it's own array "abc" and it got modified by the child (passed via FIFO) to "bca", now it's back with the parent and formated.

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
于 2012-10-23T17:53:37.050 回答
0
  • 为每个孩子分配一个数字（不是 PID；在有 PID 之前您需要知道数字！）。
  • 创建一个mkfifo()名称如下的 FIFO ( )，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 混淆。

于 2012-10-23T17:57:27.443 回答