c - c中的叉树取决于特定参数

Question

所以我必须用 fork 制作一棵树，然后我需要使用 pstree 来显示它。 这棵树是基于一些参数的，这里有一个选项:2 0 3 0 1 0 3。 含义:原进程需要fork 2个children，左边一个什么都不做，右边一个fork 3个children。左边一个和右边一个什么都不做，中间一个 forks 1 个进程，那个进程比 forks 多 3 个子进程。

这是一个方案:

     o
    / \
   o   o
      /|\
     o o o
       |
       o
      /|\
     o o o

我不知道如何开始这个，我只有这个:(记住我不需要硬编码) 编辑:我不知道如何确定从哪个 child fork 。 (我怎么知道这 3 个中的哪个 child 是中间那个？)

    char c; int n;
    int *array = (int*)malloc(20*sizeof(int));
    int i = 0;
    //reads the cmdline arguements
    while ((scanf("%d", &n))!=EOF) {
        array[i]=n;
        //printf("%d ", array[i]);
        i++;
    }
    //gets pid of original process and makes a string to call pstree
    int d=getpid();
    char str[50] = "pstree -c ";
    char str1[20];
    sprintf(str1, "%d", d);
    strcat(str,str1);

Answer 1

都快一天了，不知道评论有没有用。
这是一个建议的实现 - 我知道您想先尝试自己做，所以首先是提示。如果您需要一些线索，请查看底部的 C 程序。

假设:

• 字符串由许多数字组成，每个数字至少由一个空格分隔。
• 在字符串结束后，指令相当于“0 fork”
• 和限制(在底部)。

首先，您可能会注意到递归模式(但同样的算法也可能以迭代方式开发)

• fork n次
• 让 child 1 .. n 叉 x1 .. xn 次，同时喂给他们下一个操作
• 每个 child 重复相同的算法

提示

• 创建两个函数，一个获取字符串中的下一个数字，一个跳过字符串中的 n 个数字
• 制作一个带两个参数的递归函数
  • 要执行的 fork 数
  • 字符串中为该特定 child 的下一个 fork (如果有的话)提供说明的部分(在所有 child 中，只有一个 should for again)
• 如果不执行 fork ，则函数等待一分钟
• 如果必须执行 N 次 fork ，
  • 在那个调用的所有 child 都被跳过后得到一个指向字符串的S(例如“2 0 3 4 0 0” fork 两次，0和3是 fork 的数量由 child 完成，第二个 child 得到一个指向“4 0 0”的 S。
  • 做 N 次 fork ， children 用参数递归调用函数(例如，相同的例子 0 和 3 用于 2 个 fork )
  • 子端，递归调用后返回
  • 父进程(这个)每次都让 S 指向下一个数字，前提是子进程至少创建了一个 fork 。
• 最后等待上面创建的所有进程

就是这样。

限制:此处建议的算法假定操作字符串为每组 fork 仅生成一个事件分支 - 您提供的字符串“2 0 3 0 1 0 3”符合该限制(否则算法会更难；例如使用“2 2 3 ...”你会有 2 个并行的事件分支，它们有自己的生命并且必须从字符串中获取!意思是在字符串中搜索哪一部分是给深度 D fork F...)。

---

你应该得到类似的东西(是的，我的程序名称是“x”)，通过 pstree -c

可以看到大约一分钟

-bash───x─┬─x
          └─x─┬─x
              ├─x───x─┬─x
              │       ├─x
              │       └─x
              └─x

---

实现建议

• 首先是 2 个辅助函数

要到达下一个数字(或 0 即 '\0')是字符串

char *nextdigit(char *s) {
    while (*s && (*s<'0' || *s>'9')) s++; // skip non digits
    return s;
}

跳过n位

char *skipndigits(int n, char *s) {
    while (n--) {
        s = nextdigit(s);
        if (*s) s++;
    }
    return s;
}

接下来是应该如何调用递归函数(例如从main())，函数名称为forkering()

char *op = "2 0 3 0 1 0 3";

forkering(atoi(op), op+1);

最后是递归函数。

#define WAITING 60

void forkering(int n, char *op) {
    printf("forkering %d, with %s\n", n, op);

    if ( ! n) {
        sleep(WAITING); // no forking, wait WAITING seconds
        return;
    }

    char *nextop = skipndigits(n, op); // next op (for children)

    while(n--) {
        op = nextdigit(op);
        int nop = atoi(op);  // number of forks that child has to do
        if ( ! fork()) {
            forkering(nop, nextop);
            return;
        }
        if (nop) nextop = skipndigits(1, nextop); // only skip if non zero
        op = skipndigits(1, op); // for our children
    }

    while (wait(NULL) > 0); // wait all processes created above
}

如您所见，该函数非常短。