COMS 3157 Advanced Programming

Recitation NN: forkherd

forkherd is based on a final exam problem from Fall 2019.

You can find the solutions for this recitation on CLAC:

git clone ~j-hui/cs3157-pub/examples/forkherd

Consider the following program, forkherd.c:

int main(int argc, char **argv) {
    while (1) {
        if (*++argv == NULL) {
            exit(0);
        } else if (fork() == 0) {
            // Child process
            break;
        } else {
            // Parent process
            continue;
        }
    }

    sleep(2);  // Sleep for 2 seconds

    char buf[4];
    int pos = 0;
    int r;
    while (1) {
        FILE *f = fopen(*argv, "rb");
        assert(f);

        fseek(f, pos, SEEK_SET);
        r = fread(buf, 1, sizeof(buf), f);
        fclose(f);

        if (r == 0) {
            exit(0);
        } else if (fork() == 0) {
            break;
        } else {
            pos += r;
        }
    }

    sleep(2);  // Sleep for 2 seconds

    char name[128];
    sprintf(name, "%s.%d", *argv, pos);

    while (1) {
        if (r == 0) {
            exit(0);
        } else if (fork() == 0) {
            break;
        } else {
            r--;
        }
    }

    sleep(r * 2);  // Sleep for r * 2 seconds

    FILE *f = fopen(name, "ab");  // Open in append mode
    fwrite(buf + (r - 1), 1, 1, f);
    fclose(f);  // Also flushes f before closing

    return 0;
}

We built forkherd.c in the following directory:

$ ls
A   B   forkherd.c

$ gcc -Wall forkherd.c -o forkherd

$ cat A
0123456789

$ cat B
0123456789abcdef0123456789


$ ls -l
total 16
-rw-r--r-- 1 jae faculty   11 Dec 16 15:03 A
-rw-r--r-- 1 jae faculty   27 Dec 16 16:08 B
-rwxr-xr-x 1 jae faculty 9240 Dec 17 00:28 forkherd
-rw-r--r-- 1 jae faculty 1208 Dec 16 16:49 forkherd.c

Note that the sizes of A and B are 11 and 27 bytes, respectively, because they contain a newline at the end.

We execute forkherd on a lightly loaded Linux system; it runs without any errors or memory leaks:

$ ./forkherd A B

1. Execution time

forkherd calls fork() to create child processes during the execution; those processes may start and terminate at different times. forkherd is considered terminated when all its processes terminate. Note that it is okay for a parent process to terminate before its child process, in which case the child process will continue executing normally.

A process is considered sleeping if it is blocked on the sleep() function. Upon running forkherd, how many processes are sleeping at the following points in time:

Specify 0 if all processes (i.e. the whole program) have terminated at that point in time.

2. Directory contents

During its execution, forkherd may create some files in the current directory.

While forkherd was running, we logged on to the same machine in a different terminal window, changed the current directory to the directory where we ran forkherd, and ran the following command at different times during the execution of the forkherd program:

$ ls A.*

Note that this command lists the files whose names start with A. and it will NOT include the file A which we saw in the directory earlier.

What is the output of ls A.*:

Now consider file names starting with B.. What is the output of ls B.*:

For 2.1 to 2.6, write NONE if there are no such files in the directory. If the directory contents reported by ls A.* and ls B.* are unpredictable at a particular time, write UNPREDICTABLE.

3. File contents

We also examined the content of various files during the execution of forkherd, using the cat command.

What is the output of cat A.0:

What is the output of cat B.8:

For 3.1 to 2.6, write NONE if the file does not exist, and EMPTY if the file exists but does not contain anything. If the file contents are unpredictable, write UNPREDICTABLE.