代码之家 › 专栏 › 技术社区 › negar14

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

binary-tree fork unix linux c

negar14 · 技术社区 · 8 年前

我正在尝试使用在里面 c .

类似于:

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

所以我写了这段代码:

#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 13
Im the procces 15
Im the procces 4
Im the procces 8
Im the procces 14
Im the procces 12
Im the procces 11
Im the procces 10
Im the procces 9

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

我的输出一点也不正确。我以为是的,但我错了。

1 回复 | 直到 8 年前

Jonathan Leffler 8 年前

在我的首选选项下,您的原始代码几乎编译得很干净,这是一种赞扬。我将其修改为初始化 n 到 4 并进行测试 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() 也不会成为一个阻碍,然后你可以创建一个文件,其中包含最后一个进程的编号,以打印其“我是进程”消息。每个进程将等待,直到轮到它,它通过检查文件中的数字是否为其数字减1来知道。其他进程也可以读取该文件。当进程写入其“我就是进程”消息时,它会启动其两个子进程,然后等待它们完成。

我选择使用我的 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
$

$ 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
$

如你所见,“我就是过程”消息严格按顺序打印。整个程序从第一条打印消息到最后一条打印消息总共运行约19毫秒并不需要太长时间。

具有标准错误的日志 ptree17 5 太大了,无法回答。