3

私の OS クラスの最初のプロジェクトはfork()、ユーザーがコマンド ラインで指定した深さを持つプロセス ツリーを作成することです。各リーフ レベル ノードはデータを並べ替え、名前付きパイプ (FIFO) を使用して親に戻す必要があります。

fork()各プロセスに 2 つの子を持つN 深度ツリーを作成できます。私が理解できないのは、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);
    }
}

では、各プロセスを個別に取得して作業するにはどうすればよいでしょうか?

4

3 に答える 3

1

リーフがソートするデータのソースなど、データフローの要件については何も述べていません。分業の観点から、リーフ ノードはソートされますが、ブランチはマージするだけで済みます。ある意味では、スタックの代わりにプロセスと FIFO を使用するハイブリッド マージソートを作成しています。

前述のように、並べ替える値の配列を割り当て、すべての FIFO をメイン プロセスの前に作成するという、シンプルだが洗練されていないアプローチを使用できます。各子の識別子またはインデックス番号に基づいて、配列全体と適切な FIFO (たとえば、ノードNが親にデータを送信するために使用する FIFO) からデータの範囲を選択します。たとえば、 で作成された子プロセスは親のアドレス空間を共有し、グローバル スコープで配列を参照できることを思い出してください。fifo.Nfork

二分木はうまく配列に詰め込まれます。ウィキペディアの二分木によると

二分木は、配列内の暗黙的なデータ構造として幅優先の順序で格納することもできます。木が完全な二分木である場合、この方法はスペースを無駄にしません。このコンパクトな配置では、ノードにインデックスiがある場合、その子はインデックス2i+1 (左の子の場合) と2i+2 (右の子の場合) で見つかり、親 (存在する場合) はインデックス ⌊ で見つかります。 <em>(i-1)/2⌋ (ルートのインデックスが 0 であると仮定)。

⌊<em>x⌋ は x を超えない最大の整数であり、xの下限とも呼ばれます。C では、 の値を 型の変数に代入することでフロアを取得できます。(i-1)/2int

ツリーの周りにノード識別子をスレッド化するには、次のようなコードを使用できます。

#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

名前付きパイプとも呼ばれる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
于 2012-10-23T17:53:37.050 に答える
0
  • 各子に番号を割り当てます (PID ではなく、PID を作成する前に番号を知る必要があります!)。
  • mkfifo()などの名前でFIFO ( ) を作成しますfifo.N。N は数字です。
  • 各子は、どの FIFO に書き込むかを認識します。
  • 各親は、どの FIFO から読み取るかを認識しています。(おそらく、親はソートではなくマージを実行しているだけです。)

おそらく、どのデータをソートする必要があるかは、子供たち全員が何らかの形で知っているでしょう。

すべての FIFO を初期化した後、どのプロセスがいつ実行されているかを知るにはどうすればよいですか? ツリーを作成した後でメイン プログラムに戻ったときに、PID と制御ステートメントに基づいて実行中のプロセスを分類する方法はありますか?

プロセスは、「リーフ」プロセスと「非リーフ」プロセスに分けることができます。

リーフ プロセスには子がありません。それらはソートの割り当てを行い、ソートされたデータを出力 FIFO に書き込みます。親プロセスが読み取り用に開くまで、FIFO でブロックされます。書き込みが完了すると、FIFO が閉じられ、親プロセスは EOF を取得します。

各非リーフ プロセスは、2 つの子からソートされたデータをマージしています。各非リーフ プロセスは、自身の出力 FIFO が何であるか (ルート ノードはおそらく FIFO ではなく標準出力に書き込みます)、およびその 2 つの子の FIFO が何であるかを知る必要があります。おそらく、非リーフ プロセスは fifo.$$.1 と fifo.$$.2 ('$$' は既に実行中の非リーフ プロセスの PID です) を作成し、親にすべて作成させるのではありません。フロント。次に、どの FIFO を使用するかを示す変数を使用して、2 つの子をフォークします。次に、非リーフ プロセスは読み取り用に 2 つの FIFO (および書き込み用の独自の出力 FIFO) を開き、2 つのデータ ストリームのマージを行います (両方から行を読み取り、小さい方を出力に書き込み、置換行を読み取り、一方ではEOFまで続行し、もう一方からの読み取りを終了します）。

最上位 (元のプロセス) では、基本的なメカニズムはリーフ以外のプロセスと同じです。2 つの FIFO を作成し、2 つの子を開始し、読み取り用に FIFO を開き、2 つのストリームをマージして、別の FIFO をいじる必要なく標準出力に書き込みます。

于 2012-10-23T17:57:27.443 に答える