Process Section 2: Process control exercises

In today’s section, we’ll walk through a selection of our process control exercises, which are problems taken from prior exams. Also take the opportunity to ask questions about the problem set and class material.

Simultaneously enrolled students are responsible for attending section and self-reporting their attendance at www.tinyurl.com/cs61sections.

The main subjects of these exercises are:

• PROC-9: Process control explanations.
• PROC-2: Semantics of pipes and system calls.
• PROC-10: Command lines and strace.
• PROC-8: Emulating inter-process communication.

PROC-9. Process control explanations

QUESTION PROC-9A. Match each system call with the shell feature that requires that system call for implementation. You will use each system call once.

If you’re unfamiliar with a system call, remember you can read its manual page!

1. chdir: This system call changes the current process’s current working directory. It’s only used by cd (d).
2. fork: This system call creates a new process. Most command lines use this (e); any command is executed in a child process of the current shell. (An exception is that some simple commands, such as echo, might be provided by the shell itself.)
3. open: This system call opens a named file. The shell only needs to explicitly open files to handle redirections, such as > (b).
4. pipe: This system call creates a pipe and returns the two file descriptors that comprise it. It’s required by | (c).
5. waitpid: Many command lines use this, but given the constraint that each system call is used once, the best choice is ; (a). The shell must wait for the conditional chain on the left of ; before proceeding to the conditional chain on the right, which requires a blocking call to waitpid; some command lines, such as background commands, don’t use a blocking call to waitpid.

QUESTION PROC-9B. What is the best explanation for the function of zombie processes in Unix? Select one.

1. Zombie processes automatically kill other processes that leak too much memory, keeping the OS as a whole more stable.
2. Zombie processes ensure that process IDs are never reused.
3. Zombie processes allow parent processes to reliably collect the statuses of their exited children.
4. Zombie processes cannot be killed by most signals.
5. None of the above.

3 is the best answer. Recall that a zombie process in Unix is a process that has terminated, but whose status has not been collected by its parent process.

1. False. Zombie processes are entirely passive and have already terminated—they don’t take action on their own—and zombie processes are created whenever processes terminate, whether or not memory was leaked. (Though some OSes do have features to kill processes that leak memory, such as Linux’s “OOM Killer”.)
2. False. Process IDs are reused eventually!
3. True—this is the best answer. The zombie process effectively reserves the terminated process’s ID and holds its status until the parent collects that status.
4. This is true—zombie processes are already terminated, so they can’t be killed—but it’s a property of zombie processes, not their function.

QUESTION PROC-9C. What is the best explanation for why signal handlers in Unix should be kept simple? Select one.

1. Signal handlers run with interrupts disabled, so a complex signal handler could violate process isolation.
2. Signal handlers can be invoked at any moment, including in the middle of another function, so a complex signal handler is likely to violate assumptions on which the program and/or C++ libraries depend.
3. The kernel ensures that signal handlers have no effect on primary memory.
4. Signal handlers are called by the kernel rather than being called explicitly by other parts of the program.
5. None of the above.

2 is the best answer.

1. False. This is one way that signal handlers are different from OS interrupts. In WeensyOS, interrupts are disabled whenever the kernel runs; but as you may remember from the kernel unit, it’s unsafe to leave interrupts disabled when an unprivileged process is running! Process isolation requires that the kernel always recover control eventually, even if a signal handler enters an infinite loop.
2. True! Signal handlers can be invoked between any two instructions.
3. False. Signal handlers can set variables that are observed in the main flow of control.
4. This is true, but it doesn’t really address why signals would need to be kept simple.

QUESTION PROC-9D. What is the best explanation for why the pipe system call precedes the fork system call when setting up a pipeline in a shell? Select one.

1. The fork system call creates a new, isolated process whose file descriptor table cannot be influenced by other processes.
2. In the shell grammar, a command is part of a pipeline, so the pipe is encountered first, before the command is forked.
3. Pipe hygiene requires that all extraneous ends of a pipe are closed in all processes, including the parent shell.
4. The read end of a pipe is created after the write end.
5. None of the above.

1 is the best answer.

1. This is in fact what fork does, and it explains why the pipe system call can’t follow the fork (a pipe created after a fork cannot be accessed from the forked child).
2. This one’s word salad—the grammar describes the syntax of pipelines, not their semantics.
3. This is true, but doesn’t concern ordering.
4. False. The read and write ends are created simultaneously by the pipe system call.

QUESTION PROC-9E. What is the best explanation for the difference between foreground conditional chains and background conditional chains? Select one.

1. In a foreground conditional chain, the shell waits for each pipeline in sequence, while in a background conditional chain, all commands in the pipelines run in parallel.
2. Foreground conditional chains never create zombie processes.
3. Background conditional chains do not write to the shell’s standard output.
4. Foreground conditional chains do not need to create subshells.
5. None of the above.

4 is the best answer. However, some students implement subshells even for foreground conditional chains (although normal shells do not do this), so they might put 5.

1. False. If a background conditional chain contains more than one pipeline, then the pipelines run in sequence—a subshell process must wait for the first pipeline’s status to determine whether to continue to the next. (For instance, in cat foo | wc && cat bar | wc &, cat bar | wc will execute only if cat foo | wc exits successfully).
2. False. Every process becomes a zombie process after terminating, although if the parent is already waiting, the zombie process exists only for a moment.
3. False. We’ve often seen how background commands can write to the terminal, often interrupting the shell prompt.
4. True. A subshell is a forked copy of the parent shell process responsible for handling some part of a command line. (We distinguish a subshell from the child processes that handle single commands.) Subshells may be required to handle background conditional chains, but foreground conditional chains can be handled by the parent shell.

PROC-2. Process management

Here’s the skeleton of a shell function implementing a simple two-command pipeline.

// Create the pipeline `cmd1 [argv1] | cmd2 [argv2]`, and wait for both processes
// to complete before returning.
void simple_pipe(const char* cmd1, char* const* argv1, const char* cmd2, char* const* argv2) {
    int pipefd[2], r, status;

    [A]

    pid_t child1 = fork();
    if (child1 == 0) {
        [B]
        execvp(cmd1, argv1);
    }
    assert(child1 > 0);

    [C]

    pid_t child2 = fork();
    if (child2 == 0) {
        [D]
        execvp(cmd2, argv2);
    }
    assert(child2 > 0);

    [E]
}

And here is a grab bag of system calls with arguments.

1. close(pipefd[0]);
2. close(pipefd[1]);
3. dup2(pipefd[0], STDIN_FILENO);
4. dup2(pipefd[0], STDOUT_FILENO);
5. dup2(pipefd[1], STDIN_FILENO);
6. dup2(pipefd[1], STDOUT_FILENO);
7. pipe(pipefd);
8. r = waitpid(child1, &status, 0);
9. r = waitpid(child2, &status, 0);

Your task is to assign system call IDs, such as “1”, to slots, such as “A”, to achieve several behaviors, including a correct pipeline and several incorrect pipelines. For each question:

• You may use each system call ID once, more than once, or not at all.
• You may use zero or more system call IDs per slot. Write them in the order they should appear in the code.
• You may assume that no signals are delivered to the shell process (so no system call ever returns an EINTR error).
• The simple_pipe function should wait for both commands in the pipeline to complete before returning.

QUESTION PROC-2A. Implement a correct foreground pipeline.

A correct pipeline will have the following characteristics:

• The pipe (7) must be created before any child.
• Since cmd1 is on the left-hand side of the pipe, slot [B] will handle its write end via dup2(pipefd[1], STDOUT_FILENO) (6). It must also handle pipe hygiene (1 and 2).
• Since cmd2 is on the right-hand side of the pipe, slot [D] will handle its read end via dup2(pipefd[0], STDIN_FILENO) (3) and pipe hygiene (1 and maybe 2).
• The parent shell must handle pipe hygiene by closing both ends of the pipe. The ends can’t be closed in [A], since an end must remain open until the child handling that end has been forked. The write end may be closed in [C] or [E]; the read end must be closed in [E].
• The parent must wait for both children (8 and 9). Since pipeline commands run in parallel, both waitpid calls belong in [E].

Putting it all together:

[A]	[B]	[C]	[D]	[E]
7	6, 1, 2 or 6, 2, 1 or 1, 6, 2		3, 1, 2	1, 2, 8, 9 or 2, 1, 8, 9 or others (1, 2 come first)

or

[A]	[B]	[C]	[D]	[E]
7	6, 1, 2 or 6, 2, 1 or 1, 6, 2	2	3, 1	1, 8, 9

QUESTION PROC-2B. Implement a pipeline so that, given arguments corresponding to “echo foo | wc -c”, the wc process reads “foo” from its standard input but does not exit thereafter. For partial credit describe in words how this might happen.

This is a pipe hygiene problem. Some process has an open file descriptor to the write end of the pipe, which means the wc process (the right-hand side of the pipe) never detects end-of-file on the read end. Anything that doesn’t close the pipe’s write end will have this behavior. This leaves both ends of the pipe open in the shell:

[A]	[B]	[C]	[D]	[E]
7	6, 1, 2		3, 1, 2	8, 9

This closes both ends in the shell, but leaves the write end open in wc itself:

[A]	[B]	[C]	[D]	[E]
7	6, 1, 2		3, 1	1, 2, 8, 9

QUESTION PROC-2C. Implement a pipeline so that, given arguments corresponding to “echo foo | wc -c”, “foo” is printed to the shell’s standard output and the wc process prints “0”. (In a correctly implemented pipeline, “wc” would print 4, which is the number of characters in “foo\n”.) For partial credit describe in words how this might happen.

Anything that doesn’t redirect the left-hand process’s standard output will do it. It is important that the read end of the pipe be properly redirected, or wc would block reading from the shell’s standard input.

[A]	[B]	[C]	[D]	[E]
7	1, 2 (anything without 6)		3, 1, 2	1, 2, 8, 9

QUESTION PROC-2D. Implement a pipeline that appears to work correctly on “echo foo | wc -c”, but always blocks forever if the left-hand command outputs more than 65536 characters. For partial credit describe in words how this might happen.

This happens when we execute the two sides of the pipe in series: first the left-hand side, then the right-hand side. Since the pipe contains 64KiB of buffering, this will often appear to work for left-hand sides that emit relatively few characters; but if the left-hand side blocks while writing to the pipe (because the pipe buffer runs out of room), the shell will wait for it forever.

[A]	[B]	[C]	[D]	[E]
7	6, 1, 2	8	3, 1, 2	1, 2, 9

QUESTION PROC-2E. Implement a pipeline so that, given arguments corresponding to “echo foo | wc -c”, both echo and wc report a “Bad file descriptor” error. (This error, which corresponds to EBADF, is returned when a file descriptor is not valid or does not support the requested operation.) For partial credit describe in words how this might happen.

Given these system calls, the only way to make this happen is to redirect the wrong ends of the pipe into stdin/stdout: it is illegal to read from a write end or to write to a read end. If we were given close(0) and close(1) system calls, it would suffice to close the left-hand command’s standard output and the right-hand command’s standard input; but we were not given those system calls. It doesn’t work to close and then dup2 (e.g., close(pipefd[0]); dup2(pipefd[0], STDIN_FILENO), because such a dup2 will fail without affecting the new file descriptor.

[A]	[B]	[C]	[D]	[E]
7	4, 1, 2		5, 1, 2	1, 2, 8, 9

PROC-10. Piping hot

QUESTION PROC-10A. Fill in the blanks so that each command line prints 61, and only 61, to the shell’s standard output. The resulting command lines should be valid according to the shell grammar. At most one of your fragments may contain the string 61.

1. _________
2. _________ || echo 61
3. false && _________ && echo 61
4. echo ab | tr _________
5. yes _________ echo 61

There are many, many possible answers; try to come up with a few!

Here are some!

1. echo 61 or echo -n 6 ; echo 1 or expr 60 + 1
2. false or echo 61 && true
3. true || true or true ; true
4. ba 16 or a-z a-z > /dev/null && echo 61
5. | echo > /dev/null ; or 61 | head -n 1 && false &&

Note that for #5, > /dev/null ; does not work. Why not? (Try it!)

In the remaining questions, we provide strace output for attempts at a shell running a two-process pipeline, echo foo | wc -c. For each question, you are to characterize the shell. This is Shell X1.

58797 pipe([3, 4])                      = 0
58797 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f892b19ea10) = 58798
58797 close(4)                          = 0
58798 close(3)                          = 0
58797 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f892b19ea10) = 58799
58798 dup2(4, 1)                        = 1
58798 close(4)                          = 0
58798 execve("/bin/echo", ["/bin/echo", "foo"], 0x7ffdea26fe98 /* 57 vars */ <... detached ...>
58797 close(3)                          = 0
58797 wait4(58798,  <... unfinished ...>
58799 dup2(3, 0)                        = 0
58799 close(3)                          = 0
58799 execve("/usr/bin/wc", ["/usr/bin/wc", "-c"], 0x7ffdea26fe98 /* 57 vars */ <... detached ...>
58797 <... wait4 resumed> NULL, 0, NULL) = 58798
58797 --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=58798, si_uid=1000, si_status=0, si_utime=0, si_stime=0} ---
58797 wait4(58799, NULL, 0, NULL)       = 58799
58797 --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=58799, si_uid=1000, si_status=0, si_utime=0, si_stime=0} ---
58797 exit_group(0)                     = ?
58797 +++ exited with 0 +++

QUESTION PROC-10B. What is the process ID of the parent shell?

58797.

QUESTION PROC-10C. Does Shell X1 wait for the right-hand process, the left-hand process, or both?

Both (there are wait4 lines for each child).

QUESTION PROC-10D. Does Shell X1 appear to implement two-process pipelines correctly?

Yes it does. The shell creates the pipe before cloning; the left-hand child dup2s the write end of the pipe, file descriptor 4, onto standard input, fd 1, then closes both ends of the pipe. Meanwhile, the parent shell closes the write end of the pipe and clones again; the right-hand child dup2s the read end of the pipe onto stdin, then closes the read end. Finally, the parent closes the read end before waiting for both children. The children run in parallel and there are no extraneous pipe ends open in any process (the history of each process does both close(3) and close(4)).

QUESTION PROC-10E. This is Shell X2. It is incorrect.

58969 pipe([3, 4])                      = 0
58969 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f6d566b0a10) = 58970
58970 close(3)                          = 0
58970 dup2(4, 1)                        = 1
58970 close(4)                          = 0
58970 execve("/bin/echo", ["/bin/echo", "foo"], 0x7ffcc0a30220 /* 57 vars */ <... detached ...>
58969 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f6d566b0a10) = 58971
58971 dup2(3, 0)                        = 0
58971 close(3)                          = 0
58971 execve("/usr/bin/wc", ["/usr/bin/wc", "-c"], 0x7ffcc0a30220 /* 57 vars */ <... detached ...>
58969 close(3)                          = 0
58969 close(4)                          = 0
58969 wait4(58970,  <... unfinished ...>
58969 <... wait4 resumed> NULL, 0, NULL) = 58970
58969 --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=58970, si_uid=1000, si_status=0, si_utime=0, si_stime=0} ---
58969 wait4(58971, NULL, 0, NULL)       = ? ERESTARTSYS (To be restarted if SA_RESTART is set)
58969 --- SIGINT {si_signo=SIGINT, si_code=SI_KERNEL} ---
58969 +++ killed by SIGINT +++

Give an strace line, including process ID, that, if added in the right place, would make Shell X2 appear to implement two-process pipelines correctly.

58971 close(4) = 0, which would go somewhere after 58971 is created and before execve.

QUESTION PROC-10F. This is Shell X3. It is incorrect, though it appears to run correctly on this specific pipeline.

59026 pipe([3, 4])                      = 0
59026 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f0dfa757a10) = 59027
59026 close(4)                          = 0
59027 close(3)                          = 0
59026 wait4(59027,  <... unfinished ...>
59027 dup2(4, 1)                        = 1
59027 close(4)                          = 0
59027 execve("/bin/echo", ["/bin/echo", "foo"], 0x7ffe0672b1b0 /* 57 vars */ <... detached ...>
59026 <... wait4 resumed> NULL, 0, NULL) = 59027
59026 --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=59027, si_uid=1000, si_status=0, si_utime=0, si_stime=0} ---
59026 clone(child_stack=NULL, flags=CLONE_CHILD_CLEARTID|CLONE_CHILD_SETTID|SIGCHLD, child_tidptr=0x7f0dfa757a10) = 59028
59026 close(3)                          = 0
59026 wait4(59028,  <... unfinished ...>
59028 dup2(3, 0)                        = 0
59028 close(3)                          = 0
59028 execve("/usr/bin/wc", ["/usr/bin/wc", "-c"], 0x7ffe0672b1b0 /* 57 vars */ <... detached ...>
59026 <... wait4 resumed> NULL, 0, NULL) = 59028
59026 --- SIGCHLD {si_signo=SIGCHLD, si_code=CLD_EXITED, si_pid=59028, si_uid=1000, si_status=0, si_utime=0, si_stime=0} ---
59026 exit_group(0)                     = ?
59026 +++ exited with 0 +++

Give a two-process Unix pipeline that Shell X3 will not appear to run correctly, and/or briefly describe problem with Shell X3.

The parent shell waits for the left-hand command to finish before starting the right-hand command, so yes | echo foo would fail.

PROC-8. Tripe

This question concerns a new pipe-like feature called a tripe. A tripe has one write end and two read ends. Any data written on the write end is duplicated onto both read ends. Each end observes the same stream of characters.

QUESTION PROC-8A. A tripe can be emulated using regular pipes and a helper process, where the helper process runs the following code:

     void run_tripe(int fd1, int fd2, int fd3) {
/*1*/    while (true) {
/*2*/        char ch;
/*3*/        ssize_t n = read(fd1, &ch, 1);
/*4*/        assert(n == 1);
/*5*/        n = write(fd2, &ch, 1);
/*6*/        assert(n == 1);
/*7*/        n = write(fd3, &ch, 1);
/*8*/        assert(n == 1);
/*9*/    }
     }

How many regular pipes are required to make this design work?

3.

This helper process reads from one file descriptor (which must therefore be a pipe read end) and writes to two other file descriptors (two write ends). Outside the helper process, the emulated tripe has one write end and two read ends. It doesn’t make sense for any of these ends to be shared, so there are six ends, and three pipes, total.

Here’s a sketch of this design. First, the semantics users expect of a tripe:

And here’s the three-pipe emulation with helper process:

If you try to use fewer than three pipes, then the tripe semantics will be broken—for instance, characters written to the tripe’s write end would get split among the read ends.

QUESTION PROC-8B. If the run_tripe helper process encounters end of file on fd1, it will assert-fail. It should instead close the write ends and exit. Change the code so it does this, using line numbers to indicate where your code goes. You may assume that read and write never return an error.

Line 4 should be changed to this:

        if (n == 0) {
            _exit(0);
        }

Exiting the helper process automatically closes the write ends.

QUESTION PROC-8C. “Pipe hygiene” refers to closing unneeded file descriptors. What could go wrong with the tripe if its helper process had bad pipe hygiene (open file descriptors referring to unneeded pipe ends)? List all that apply.

1. Undefined behavior.
2. read from either read end of the emulated tripe would never return end-of-file.
3. write to the write end of the emulated tripe would never block.
4. write to the write end of the emulated tripe would never detect the closing of a read end.
5. None of the above.

The best answers are 2 and 4.

1. Open pipe ends don’t cause undefined behavior.
2. A read from a tripe read end will return end-of-file only if the helper process closes its write ends, fd2 and fd3. The helper closes these only when exiting. And that happens only if a read from fd1 returns 0 or -1, rather than blocking or returning a character. When will a read from a pipe read end, such as fd1, return end-of-file? Only when there are no copies of the corresponding write end open. So if the helper process had bad hygiene and kept the write end of fd1 open, disaster.
3. A write to a write end can block even before any ends are closed—this is describing normal pipe (and tripe) behavior, not a problem.
4. A write detects the closing of a read end only once all file descriptors corresponding to the read end are closed. Similarly to #2, this will happen only if the helper process exits, which bad pipe hygiene can prevent.