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.
The main subjects of these exercises are:
- PROC-9: Process control explanations.
- PROC-10: Command lines and strace.
- PROC-2: Semantics of pipes and system calls.
- 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.
|
|
QUESTION PROC-9B. What is the best explanation for the function of zombie processes in Unix? Select one.
- Zombie processes automatically kill other processes that leak too much memory, keeping the OS as a whole more stable.
- Zombie processes ensure that process IDs are never reused.
- Zombie processes allow parent processes to reliably collect the statuses of their exited children.
- Zombie processes cannot be killed by most signals.
- None of the above.
QUESTION PROC-9C. What is the best explanation for why signal handlers in Unix should be kept simple? Select one.
- Signal handlers run with interrupts disabled, so a complex signal handler could violate process isolation.
- 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.
- The kernel ensures that signal handlers have no effect on primary memory.
- Signal handlers are called by the kernel rather than being called explicitly by other parts of the program.
- None of the above.
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.
- The
fork
system call creates a new, isolated process whose file descriptor table cannot be influenced by other processes. - In the shell grammar, a
command
is part of apipeline
, so the pipe is encountered first, before the command is forked. - Pipe hygiene requires that all extraneous ends of a pipe are closed in all processes, including the parent shell.
- The read end of a pipe is created after the write end.
- None of the above.
QUESTION PROC-9E. What is the best explanation for the difference between foreground conditional chains and background conditional chains? Select one.
- 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.
- Foreground conditional chains never create zombie processes.
- Background conditional chains do not write to the shell’s standard output.
- Foreground conditional chains do not need to create subshells.
- None of the above.
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
.
_________
_________ || echo 61
false && _________ && echo 61
echo ab | tr _________
yes _________ echo 61
There are many, many possible answers; try to come up with a few!
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?
QUESTION PROC-10C. Does Shell X1 wait for the right-hand process, the left-hand process, or both?
QUESTION PROC-10D. Does Shell X1 appear to implement two-process pipelines correctly?
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.
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.
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.
close(pipefd[0]);
close(pipefd[1]);
dup2(pipefd[0], STDIN_FILENO);
dup2(pipefd[0], STDOUT_FILENO);
dup2(pipefd[1], STDIN_FILENO);
dup2(pipefd[1], STDOUT_FILENO);
pipe(pipefd);
r = waitpid(child1, &status, 0);
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] |
[B] (child1) |
[C] |
[D] (child2) |
[E] |
---|---|---|---|---|
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.
[A] |
[B] (child1) |
[C] |
[D] (child2) |
[E] |
---|---|---|---|---|
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.
[A] |
[B] (child1) |
[C] |
[D] (child2) |
[E] |
---|---|---|---|---|
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.
[A] |
[B] (child1) |
[C] |
[D] (child2) |
[E] |
---|---|---|---|---|
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.
[A] |
[B] (child1) |
[C] |
[D] (child2) |
[E] |
---|---|---|---|---|
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?
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.
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.
- Undefined behavior.
read
from either read end of the emulated tripe would never return end-of-file.write
to the write end of the emulated tripe would never block.write
to the write end of the emulated tripe would never detect the closing of a read end.- None of the above.