个人中心
gpt4 book ai didi

c - 使用 fork 在进程的二叉树中进行广度优先搜索

转载 作者：太空狗 更新时间：2023-10-29 12:40:36 25 4
gpt4 key购买 nike

我正在尝试使用 c 中的 fork() 构建具有四个级别的进程二叉树.

类似于:this

我的目标是按顺序打印进程的每个编号(如广度优先搜索)例如:

输出

I'm the process 1I'm the process 2I'm the process 3...I'm the process 15

So I wrote this code:

#include <stdio.h>
#include <unistd.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>

double last;

void new_tree(int);

int main(int narg, char * argv[]){
    int n;

    n = atoi(argv[1]);
    last = pow(2,(n-1));
    new_tree(1);
    return 0;
}

void new_tree(int x){
    char buff[60];
    sprintf(buff, "Im the procces %d with pid %d and ppid %d\n",x,getpid(),getppid());
    write(1,buff,strlen(buff));
    if (x >= last) 
    return;

    if (!fork()){ 
        new_tree(2*x);
        exit(0);
    }

    if(!fork()){ 
        new_tree(2*x+1);
        exit(0);
    }
    wait(NULL);
    wait(NULL);
}

但是当我运行代码 (./tree 4) 时，我无法控制进程的执行顺序。我的输出有点正确，但仍然困惑，因为某些进程在同一级别的其他进程之前完成。任何人都可以帮我解决这个问题吗？

到目前为止我的输出是:

Im the procces 1  Im the procces 3  Im the procces 2  Im the procces 6  Im the procces 7  Im the procces 5  Im the procces 13Im the procces 15Im the procces 4Im the procces 8Im the procces 14Im the procces 12Im the procces 11Im the procces 10Im the procces 9

每次我执行它都会改变。

编辑 1:我的代码可以创建进程的二叉树，但问题是以我想要的顺序执行这些进程。

编辑 2:我的输出不是一点点正确。我以为是，但我错了。

最佳答案

您的原始代码几乎可以在我的首选选项下干净地编译，这是一种恭维。我修改它以将 n 初始化为 4 并在计算 n 之前测试 if (narg == 2) argv[1]，它可以防止程序在没有参数的情况下运行时崩溃。

该程序的版本是 ptree29.c。当使用参数 3 运行时，它按顺序产生结果，但是使用参数 4(或没有参数)或参数 5，结果完全不同乱序:

$ ptree29 3
Im the procces 1 with pid 92986 and ppid 41763
Im the procces 2 with pid 92987 and ppid 92986
Im the procces 3 with pid 92988 and ppid 92986
Im the procces 4 with pid 92989 and ppid 92987
Im the procces 5 with pid 92991 and ppid 92987
Im the procces 6 with pid 92990 and ppid 92988
Im the procces 7 with pid 92992 and ppid 92988
$ ptree29 5
Im the procces 1 with pid 92993 and ppid 41763
Im the procces 2 with pid 92994 and ppid 92993
Im the procces 3 with pid 92995 and ppid 92993
Im the procces 4 with pid 92996 and ppid 92994
Im the procces 6 with pid 92997 and ppid 92995
Im the procces 5 with pid 92998 and ppid 92994
Im the procces 7 with pid 92999 and ppid 92995
Im the procces 8 with pid 93000 and ppid 92996
Im the procces 12 with pid 93001 and ppid 92997
Im the procces 10 with pid 93002 and ppid 92998
Im the procces 9 with pid 93003 and ppid 92996
Im the procces 13 with pid 93004 and ppid 92997
Im the procces 14 with pid 93005 and ppid 92999
Im the procces 11 with pid 93006 and ppid 92998
Im the procces 16 with pid 93007 and ppid 93000
Im the procces 24 with pid 93008 and ppid 93001
Im the procces 15 with pid 93009 and ppid 92999
Im the procces 25 with pid 93014 and ppid 93001
Im the procces 18 with pid 93011 and ppid 93003
Im the procces 28 with pid 93015 and ppid 93005
Im the procces 20 with pid 93010 and ppid 93002
Im the procces 26 with pid 93012 and ppid 93004
Im the procces 17 with pid 93013 and ppid 93000
Im the procces 22 with pid 93016 and ppid 93006
Im the procces 21 with pid 93017 and ppid 93002
Im the procces 30 with pid 93019 and ppid 93009
Im the procces 27 with pid 93018 and ppid 93004
Im the procces 19 with pid 93020 and ppid 93003
Im the procces 29 with pid 93021 and ppid 93005
Im the procces 23 with pid 93022 and ppid 93006
Im the procces 31 with pid 93023 and ppid 93009
$

您需要设计一种机制来控制进程打印“我是进程”消息的顺序。通过系统调用，您可以使用 (fork()、wait()、waitpid()、fflush()、getpid()、getppid()、pipe()、dup(), dup2(), read(), write(), close(), execl(), execv(), execle(), execlp(), execvp() >) — 我希望使用 open() too 不会成为阻碍 - 然后您可以创建一个文件，其中包含最后一个进程的编号以打印其“我是进程”消息。每个进程都会等到轮到它——它通过检查文件中的数字是它的数字减一来知道这一点。其他进程也可以读取该文件。当进程写入“我是进程”消息时，它会启动它的两个子进程，然后等待它们完成。

我选择使用我的 stderr.c 和 stderr.h 代码(可从 Github 获得，地址为 https://github.com/jleffler/soq/tree/master/src/libsoq )因为其中的函数(其名称均以 err_) 使得使用 PID 和时间记录错误和消息变得微不足道，这在诸如同时运行许多进程的上下文中是非常宝贵的。另一个优点是它提供单行错误处理，而不是每个错误 3 行或更多行(如果您没有此类函数)——这让我不太愿意编写错误处理代码。

代码还使用了nanosleep()因此，如果进程读取的数字太小(或太大——但代码无法处理该错误情况)，它会在重试前休眠一毫秒。这充分限制了重试率。

新代码在 ptree17.c 的源代码中:

/* SO 4574-5483 */
#include "stderr.h"
#include <fcntl.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>

static const char filename[] = "pt-next.dat";
static double last = 0.0;

static void new_tree(int num);
static void write_file(int num);

int main(int argc, char *argv[])
{
    err_setarg0(argv[0]);
    err_setlogopts(ERR_PID|ERR_MILLI);

    int n = 4;
    if (argc == 2)
        n = atoi(argv[1]);
    write_file(0);
    last = pow(2, (n - 1));
    new_tree(1);
    return 0;
}

static void write_file(int num)
{
    int fd = open(filename, O_WRONLY | O_CREAT | O_TRUNC, 0600);
    if (fd < 0)
        err_syserr("failed to create file '%s' for writing\n", filename);
    if (write(fd, &num, sizeof(num)) != sizeof(num))
        err_syserr("failed to write %d to file '%s'\n", num, filename);
    close(fd);
    err_remark("wrote %2d to '%s'\n", num, filename);
}

static int read_file(void)
{
    int num = -1;
    int fd = open(filename, O_RDONLY);
    if (fd > 0)
    {
        if (read(fd, &num, sizeof(num)) != sizeof(num))
            num = -1;
        close(fd);
    }
    err_remark("read %2d from '%s'\n", num, filename);
    return num;
}

static void wait_for_turn(int num)
{
    struct timespec ms = { .tv_sec = 0, .tv_nsec = 1000000 };
    while (read_file() != num - 1)
    {
        err_remark("dozing\n");
        nanosleep(&ms, 0);
    }
}

static void new_tree(int x)
{
    char buff[60];
    err_remark("Process = %2d\n", x);
    wait_for_turn(x);
    sprintf(buff, "I'm process %2d with pid %5d and ppid %5d\n", x, getpid(), getppid());
    write(1, buff, strlen(buff));
    write_file(x);
    if (x >= last)
        return;

    if (!fork())
    {
        new_tree(2 * x);
        exit(0);
    }

    if (!fork())
    {
        new_tree(2 * x + 1);
        exit(0);
    }

    int corpse, status;
    while ((corpse = wait(&status)) > 0)
        err_remark("child %5d exited with status 0x%.4X\n", corpse, status);
}

示例输出 1 — 发送到 /dev/null 的错误:

$ ptree17 5 2>/dev/null
I'm process  1 with pid 93174 and ppid 41763
I'm process  2 with pid 93175 and ppid 93174
I'm process  3 with pid 93176 and ppid 93174
I'm process  4 with pid 93177 and ppid 93175
I'm process  5 with pid 93178 and ppid 93175
I'm process  6 with pid 93179 and ppid 93176
I'm process  7 with pid 93180 and ppid 93176
I'm process  8 with pid 93181 and ppid 93177
I'm process  9 with pid 93182 and ppid 93177
I'm process 10 with pid 93183 and ppid 93178
I'm process 11 with pid 93184 and ppid 93178
I'm process 12 with pid 93185 and ppid 93179
I'm process 13 with pid 93186 and ppid 93179
I'm process 14 with pid 93187 and ppid 93180
I'm process 15 with pid 93188 and ppid 93180
I'm process 16 with pid 93189 and ppid 93181
I'm process 17 with pid 93190 and ppid 93181
I'm process 18 with pid 93191 and ppid 93182
I'm process 19 with pid 93192 and ppid 93182
I'm process 20 with pid 93193 and ppid 93183
I'm process 21 with pid 93194 and ppid 93183
I'm process 22 with pid 93195 and ppid 93184
I'm process 23 with pid 93196 and ppid 93184
I'm process 24 with pid 93197 and ppid 93185
I'm process 25 with pid 93198 and ppid 93185
I'm process 26 with pid 93199 and ppid 93186
I'm process 27 with pid 93200 and ppid 93186
I'm process 28 with pid 93201 and ppid 93187
I'm process 29 with pid 93203 and ppid 93187
I'm process 30 with pid 93202 and ppid 93188
I'm process 31 with pid 93204 and ppid 93188
$

示例输出 2 — 标准错误可见:

$ ptree17
ptree17: 2017-08-17 20:03:20.798 - pid=93210: wrote  0 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.799 - pid=93210: Process =  1
ptree17: 2017-08-17 20:03:20.799 - pid=93210: read  0 from 'pt-next.dat'
I'm process  1 with pid 93210 and ppid 41763
ptree17: 2017-08-17 20:03:20.800 - pid=93210: wrote  1 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.801 - pid=93211: Process =  2
ptree17: 2017-08-17 20:03:20.801 - pid=93211: read  1 from 'pt-next.dat'
I'm process  2 with pid 93211 and ppid 93210
ptree17: 2017-08-17 20:03:20.801 - pid=93212: Process =  3
ptree17: 2017-08-17 20:03:20.801 - pid=93212: read -1 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.801 - pid=93212: dozing
ptree17: 2017-08-17 20:03:20.804 - pid=93211: wrote  2 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.804 - pid=93212: read  2 from 'pt-next.dat'
I'm process  3 with pid 93212 and ppid 93210
ptree17: 2017-08-17 20:03:20.804 - pid=93212: wrote  3 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.804 - pid=93213: Process =  4
ptree17: 2017-08-17 20:03:20.805 - pid=93213: read  3 from 'pt-next.dat'
I'm process  4 with pid 93213 and ppid 93211
ptree17: 2017-08-17 20:03:20.805 - pid=93214: Process =  6
ptree17: 2017-08-17 20:03:20.805 - pid=93215: Process =  5
ptree17: 2017-08-17 20:03:20.805 - pid=93216: Process =  7
ptree17: 2017-08-17 20:03:20.805 - pid=93213: wrote  4 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.805 - pid=93216: read  4 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.805 - pid=93214: read  4 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.805 - pid=93215: read  4 from 'pt-next.dat'
I'm process  5 with pid 93215 and ppid 93211
ptree17: 2017-08-17 20:03:20.805 - pid=93216: dozing
ptree17: 2017-08-17 20:03:20.805 - pid=93214: dozing
ptree17: 2017-08-17 20:03:20.805 - pid=93215: wrote  5 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.806 - pid=93217: Process =  8
ptree17: 2017-08-17 20:03:20.806 - pid=93217: read  5 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.806 - pid=93217: dozing
ptree17: 2017-08-17 20:03:20.806 - pid=93218: Process =  9
ptree17: 2017-08-17 20:03:20.806 - pid=93219: Process = 10
ptree17: 2017-08-17 20:03:20.806 - pid=93219: read  5 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.806 - pid=93218: read  5 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.806 - pid=93219: dozing
ptree17: 2017-08-17 20:03:20.806 - pid=93218: dozing
ptree17: 2017-08-17 20:03:20.806 - pid=93220: Process = 11
ptree17: 2017-08-17 20:03:20.806 - pid=93220: read  5 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.806 - pid=93216: read  5 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.806 - pid=93220: dozing
ptree17: 2017-08-17 20:03:20.806 - pid=93216: dozing
ptree17: 2017-08-17 20:03:20.806 - pid=93214: read  5 from 'pt-next.dat'
I'm process  6 with pid 93214 and ppid 93212
ptree17: 2017-08-17 20:03:20.807 - pid=93214: wrote  6 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.807 - pid=93217: read  6 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.807 - pid=93217: dozing
ptree17: 2017-08-17 20:03:20.807 - pid=93218: read  6 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.807 - pid=93219: read  6 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.807 - pid=93218: dozing
ptree17: 2017-08-17 20:03:20.807 - pid=93221: Process = 12
ptree17: 2017-08-17 20:03:20.807 - pid=93219: dozing
ptree17: 2017-08-17 20:03:20.808 - pid=93221: read  6 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.808 - pid=93220: read  6 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.808 - pid=93221: dozing
ptree17: 2017-08-17 20:03:20.808 - pid=93220: dozing
ptree17: 2017-08-17 20:03:20.808 - pid=93222: Process = 13
ptree17: 2017-08-17 20:03:20.808 - pid=93216: read  6 from 'pt-next.dat'
I'm process  7 with pid 93216 and ppid 93212
ptree17: 2017-08-17 20:03:20.808 - pid=93222: read  6 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.808 - pid=93222: dozing
ptree17: 2017-08-17 20:03:20.808 - pid=93216: wrote  7 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.808 - pid=93217: read  7 from 'pt-next.dat'
I'm process  8 with pid 93217 and ppid 93213
ptree17: 2017-08-17 20:03:20.809 - pid=93217: wrote  8 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.809 - pid=93218: read  8 from 'pt-next.dat'
I'm process  9 with pid 93218 and ppid 93213
ptree17: 2017-08-17 20:03:20.809 - pid=93223: Process = 14
ptree17: 2017-08-17 20:03:20.809 - pid=93218: wrote  9 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.809 - pid=93223: read -1 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.809 - pid=93219: read  8 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.809 - pid=93221: read  9 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.809 - pid=93224: Process = 15
ptree17: 2017-08-17 20:03:20.809 - pid=93223: dozing
ptree17: 2017-08-17 20:03:20.809 - pid=93219: dozing
ptree17: 2017-08-17 20:03:20.809 - pid=93213: child 93217 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.809 - pid=93222: read  9 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.809 - pid=93224: read  9 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.809 - pid=93220: read  9 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.809 - pid=93221: dozing
ptree17: 2017-08-17 20:03:20.809 - pid=93224: dozing
ptree17: 2017-08-17 20:03:20.809 - pid=93222: dozing
ptree17: 2017-08-17 20:03:20.810 - pid=93220: dozing
ptree17: 2017-08-17 20:03:20.810 - pid=93213: child 93218 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.810 - pid=93211: child 93213 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.810 - pid=93223: read  9 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.810 - pid=93219: read  9 from 'pt-next.dat'
I'm process 10 with pid 93219 and ppid 93215
ptree17: 2017-08-17 20:03:20.811 - pid=93223: dozing
ptree17: 2017-08-17 20:03:20.811 - pid=93219: wrote 10 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.811 - pid=93224: read 10 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.811 - pid=93222: read 10 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.811 - pid=93220: read 10 from 'pt-next.dat'
I'm process 11 with pid 93220 and ppid 93215
ptree17: 2017-08-17 20:03:20.811 - pid=93221: read 10 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.811 - pid=93224: dozing
ptree17: 2017-08-17 20:03:20.811 - pid=93221: dozing
ptree17: 2017-08-17 20:03:20.811 - pid=93222: dozing
ptree17: 2017-08-17 20:03:20.812 - pid=93220: wrote 11 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.812 - pid=93215: child 93219 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.812 - pid=93223: read 11 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.812 - pid=93223: dozing
ptree17: 2017-08-17 20:03:20.812 - pid=93215: child 93220 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.812 - pid=93211: child 93215 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.813 - pid=93210: child 93211 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.813 - pid=93222: read 11 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.813 - pid=93224: read 11 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.813 - pid=93222: dozing
ptree17: 2017-08-17 20:03:20.813 - pid=93224: dozing
ptree17: 2017-08-17 20:03:20.813 - pid=93221: read 11 from 'pt-next.dat'
I'm process 12 with pid 93221 and ppid 93214
ptree17: 2017-08-17 20:03:20.813 - pid=93221: wrote 12 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.813 - pid=93223: read 12 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.813 - pid=93223: dozing
ptree17: 2017-08-17 20:03:20.814 - pid=93214: child 93221 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.814 - pid=93222: read 12 from 'pt-next.dat'
I'm process 13 with pid 93222 and ppid 93214
ptree17: 2017-08-17 20:03:20.815 - pid=93222: wrote 13 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.815 - pid=93224: read 13 from 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.815 - pid=93223: read 13 from 'pt-next.dat'
I'm process 14 with pid 93223 and ppid 93216
ptree17: 2017-08-17 20:03:20.815 - pid=93224: dozing
ptree17: 2017-08-17 20:03:20.815 - pid=93214: child 93222 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.815 - pid=93212: child 93214 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.816 - pid=93223: wrote 14 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.816 - pid=93224: read 14 from 'pt-next.dat'
I'm process 15 with pid 93224 and ppid 93216
ptree17: 2017-08-17 20:03:20.816 - pid=93216: child 93223 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.816 - pid=93224: wrote 15 to 'pt-next.dat'
ptree17: 2017-08-17 20:03:20.817 - pid=93216: child 93224 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.817 - pid=93212: child 93216 exited with status 0x0000
ptree17: 2017-08-17 20:03:20.817 - pid=93210: child 93212 exited with status 0x0000
$

如您所见，“I'm the process”消息严格按顺序打印。整个程序的运行时间并不长——从第一条消息到最后一条打印消息总共大约需要 19 毫秒。

ptree17 5 的标准错误日志对于 SO 的答案来说太大了。

关于c - 使用 fork 在进程的二叉树中进行广度优先搜索，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45745483/

25 4 0
文章推荐： javascript - 使用外部脚本动态添加的 javascript 不会被执行
文章推荐： android - Unity3D ETC预览不会显示ETC1格式
文章推荐： android - 异步或在 Android 上的不同线程中编译 GLSL 着色器
文章推荐： linux - 在 morty : backtrace-supported. h 中构建 libgfortran_6.2.bb 配方时出错:没有这样的文件或目录
太空狗
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com