c - 使用 fork() 以广度优先顺序打印序列

Question

给定一个进程树

             A
           /   \
          /     \
         B       C
        / \     / \
       D   E   F   G

我被要求以 BFS 顺序打印序列，即使用 fork() 系统调用 A-B-C-D-E-F-G，其中每个节点代表一个具有相同父子结构的进程，如树中所示(即 A 是 B 和 C 的父级， B 是 D 和 E 的父级，就像这样)。

我想出了这个解决方案，但我真的不明白如何让它递归打印。

static int count;
char *msg[] = {"A", "B", "C", "D", "E", "F", "G"};
main(){
  if(!fork()){ //Child 1
    printf("%s\t\t%d\t\t%d\n", msg[count++], (int)getpid(), (int)getppid());
  }
  else{
    if(!fork()){ //Child 2
        printf("%s\t\t%d\t\t%d\n", msg[count++], (int)getpid(), (int)getppid());
    }
  } 
}

这个逻辑只打印A-B-C，如何使其递归以便打印到G？请帮忙。谢谢。

Answer 1

以下代码可以满足您的需要，但不能保证首先打印哪一页(同一级别的打印顺序)。

#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <sys/wait.h>
#include <linux/wait.h>

typedef struct node {
  char data;
  struct node *left;
  struct node *right;
} node;

void pretty_print(node *nodes[], int size)
{
  int fork_cnt = 0;

  for (int i=0; i < size; i++) {
    if (fork() == 0) {
      // Child path.
      printf("%c (pid: %d, parent: %d)\n", nodes[i]->data, (int)getpid(), (int)getppid());
      node *children_nodes[256];
      int children_sizes = 0;
      if (nodes[i]->left)
    children_nodes[children_sizes++] = nodes[i]->left;
      if (nodes[i]->right)
    children_nodes[children_sizes++] = nodes[i]->right;
      if (children_sizes) {
    if (fork() == 0) {
      pretty_print(children_nodes, children_sizes);
      return;
    }
      }
      return;
    } else {
      // Parent path.
      fork_cnt++;
    }
  }

  for (int i=0; i < fork_cnt; i++) {
    // wait all children.
    int status;
    wait(&status);
  }
}

int main(void) 
{
  node g = {'G', NULL, NULL};
  node f = {'F', NULL, NULL};
  node e = {'E', NULL, NULL};
  node d = {'D', NULL, NULL};
  node b = {'B', &d, &e};
  node c = {'C', &f, &g};
  node a = {'A', &b, &c};

  node *root[1] = {&a};
  pretty_print(root, 1);
  return 0;
}