[2022] CS3214 Computer Systems - Project 1: Customizable Shell
CS3214 Spring 2022 Project 1 - “Customizable Shell”
This project must be done in groups of 2 students. Self-selected groups must have registered using the grouper app (URL). Otherwise, a partner will be assigned to you.
1 Introduction
This assignment introduces you to the principles of process management and job control in a Unix-like operating system. In this project, you will develop a simple job control shell.
This is an open-ended assignment. In addition to implementing the required functional- ity, we encourage you to define the scope of this project yourself.
2 Base Functionality
A shell receives line-by-line input from a terminal. If the user inputs a built-in command, the shell will execute this command. Otherwise, the shell will interpret the input as the name of a program to be executed, along with arguments to be passed to it. In this case, the shell will fork a new child process and execute the program in the context of the child. Normally, the shell will wait for a command to complete before reading the next command from the user. However, if the user appends an ampersand ‘&’ to a command, the command is started and the shell will return to the prompt immediately. In this case, we refer to the running command as a “background job,” whereas commands the shell waits for before processing new input are called “foreground jobs.”
The shell provides job control. A user may interrupt foreground jobs, send foreground jobs into the background, and vice versa. Thus at a given point in time, a shell may run zero or more background jobs and zero or one foreground jobs. If there is a foreground job, the shell waits for it to complete before printing another prompt and reading the next command. In addition, the shell informs the user about status changes of the jobs it manages. For instance, jobs may exit, or terminate due to a signal, or be stopped for several reasons.
At a minimum, we expect that your shell has the ability to start foreground and back- ground jobs and implements the built-in commands ‘jobs,’ ‘fg,’ ‘bg,’ ‘kill,’ ’exit,’ and ‘stop.’ The semantics of these commands should match the semantics of the same-named commands in bash. The ability to correctly respond to ˆC (SIGINT) and ˆZ (SIGTSTP) is expected, as are informative messages about the status of the children managed. Like bash, you should use consecutively numbered small integers to enumerate your jobs.
For the minimum functionality, the shell need not support pipes (|), I/O redirection (< > >>), nor the ability to run programs that require exclusive access to the terminal (e.g., vim).
We expect most students to implement pipes, I/O redirection, and managing the control- ling terminal to ensure that jobs that require exclusive access to the terminal obtain such access (see Section 3.3). Beyond that, cush’s customizability, described in Section 5 should allow for plenty of creative freedom.
3 Strategy
3.1 Handling SIGCHLD To Process Status Changes
At a given point in time, a user may have multiple jobs running, each executing arbitrary programs chosen by the user. Because the shell cannot and does not know what these programs do, it has to rely on a notification facility from the OS to be informed when these jobs encounter events the shell needs to know about. We refer to such events as “changing status,” where “status” means whether the job is running, has been stopped, has exited, or has been terminated with a signal (for instance, crashed).
This notification facility involves a protocol in which the OS kernel sends an asynchronous signal (SIGCHLD) to the shell, and in which the shell then follows up by executing a system call (a variant of wait(), specifically waitpid(), as shown in the provided starter
Thus, you will need to catch the SIGCHLD signal to learn about when the shell’s child processes change status. Since child processes execute concurrently with respect to the parent shell, and since the shell has no knowledge of what these processes are doing, it is impossible to predict when a child will exit (or terminate with a signal), and thus it is impossible to predict when this signal will arrive. In the worst case, a child may have terminated by the time the parent returns from fork()! You also should not make any assumptions about how a child process might change state: for instance, even if the user issues a kill built-in command to terminate a process, the processes might not immediately terminate (or may not terminate at all), so the shell should not assume that a status change occurred unless and until it has first-hand information from the OS that it did.
Because of the asynchronous nature of signal delivery, you will need to block handling of the signal in those sections of your code where you access data structures that are also needed by the handler that is executed when this signal arrives. For example, consider the data structure used to maintain the current set of jobs. A new job is added after a child process has been forked; a job may need to be removed when SIGCHLD is received. To avoid a situation where the job has not yet been added when SIGCHLD arrives, or - worse - a situation in which SIGCHLD arrives while the shell is adding the job, the parent should block SIGCHLD until after it completed adding the job to the list. If the SIGCHLD signal is delivered to the shell while the shell blocks this signal, it is marked pending and will be received as soon as the shell unblocks this signal.
Use the provided helper functions in signal support.c to block and unblock sig- nals, which in turn rely on sigprocmask(2). To set up signal handlers, they use the sigaction(2) system call with sa flags set to SA RESTART. The mask of blocked signals is inherited when fork() is called. Consequently, the child will need to unblock any signals the parent had blocked before calling fork().
3.2 Process Groups
User jobs may involve multiple processes. For instance, the command line input ls | grep filename requires that the shell start two processes, one to execute the ls and the other to execute the grep command. To help manage this scenario, Unix introduced a way to group processes that makes it simpler for the shell and for the user to address them as one unit.
Each process in Unix is part of a group. Process groups are treated as an ensemble for the purpose of signal delivery and when waiting for processes. Specifically, the kill(2), killpg(2), and waitpid(2) system calls support the naming of process groups as 3
possible targets . In this way, if a user wants to terminate a job, it is possible for the shell to send a termination signal to a process group that contains all processes that are part of this job. To facilitate this mechanism the shell must arrange for process groups to be created and for processes to be assigned to these groups.
Each process group has a designated leader, which is one of the processes in the group. To create a new group with itself as the leader, a process simply calls setpgid(0, 0). The process group id of a process group is equal to the process id of the leader. Child processes inherit the process group of their parent process initially. They can then form their own group if desired, or their parent process can place them into a different process group via setpgid(). The shell must create a new process group for each job and make sure that all processes that will be created for this job become members of this group.
In addition to signals and waitpid, process groups are used to manage access to the ter- minal, as described next.
3.3 Managing Access To The Terminal
Running multiple processes on the same terminal creates a sharing issue: if multiple processes attempt to read from the terminal, which process should receive the input? Similarly, some programs - such as vi - output to the terminal in a way that does not allow them to share the terminal with others.
To solve this problem, Unix introduced the concept of a foreground process group. Each terminal maintains such a group. If a process in a process group that is not the foreground process group attempts to perform an operation that would require exclusive access to a terminal, it is sent a signal: SIGTTOU or SIGTTIN, depending on whether the use was for output or input. The default action taken in response to these signals is to suspend the process. If that happens, the process’s parent (i.e., your shell) can learn about this status change by calling waitpid(). WIFSTOPPED(status) will be true in this case. To allow this process to continue, its process group must be made the foreground process group of the controlling terminal via a call to tcsetpgrp(), and then the process must be sent a SIGCONT signal. The shell will typically take this action in response to a ’fg’ command issued by the user.
Signals that are sent as a result of user input, such as SIGINT or SIGTSTP, are also sent to a terminal’s foreground process group. Note that this sending of signals occurs auto- matically by the operating system, it is not an action the shell takes. Delivering this signal to an entire process group makes it so that when a user hits ctrl-c to terminate a job such as ls | grep filename both the process running ls and the process running grep will receive the SIGINT signal, informing them of the user’s desire to terminate them. To ensure that such signals are delivered to the correct process group, the shell must arrange for these process groups to exist and be populated with the correct processes, and it must inform the OS which process group the user intends to run in the foreground at a given point in time.
3.4 Managing The Terminal’s State
Many years ago, most Unix terminals were actual devices that had a console and a key- board and that were connected to the main computer with some kind of serial interface such as RS-232. To control those devices, the OS device drivers would need to control a set of input and output flags collectively known as the terminal state. In modern systems, the most commonly used terminal type is a pseudo-terminal (pty) connected to an ssh network connection, yet this model still exists. You can type stty -a to see what those flags are, though you probably won’t care about their details.
Some processes change the state of the terminal in a certain way. For instance, vim puts the terminal in so-called “raw” mode where it receives keystrokes as they are typed (as opposed to “cooked” which requires the user to end a line with the enter key before it is received by a program). So does bash and in fact, your shell, which uses the readline library, does this too while reading user input.
This raises a management issue when the user switches between the shell’s command line and foreground process jobs. For instance, a user may start vim, then use ctrl-z to stop it, run some other job in the foreground, then stop it, resume vim, exit vim, and resume the second job.
In this case, it is necessary to restore the terminal state whenever the vim process is re- sumed to what it was before vim was stopped. Interestingly, it is possible for a process to perform such restoration itself (in fact, vim does this by handling the SIGCONT signal).
However, if the shell performed such saving and restoration transparently, then any pro- gram that manipulates its terminal state could be run under a job control regime. Specifically, your shell should save the state of the terminal when a job process is suspended
When the shell returns to the prompt, it must make itself the foreground process group of the terminal. In this case, it should also restore a known good terminal state. Your shell should sample this known good terminal state when it starts. You may find the functions provided in termstate management.c useful, which already handle most of the logic.
This known good state is also the state that the terminal will be in if a new job is started by the user. Therefore, programs that are agnostic with respect to the state of the terminal will continue to work. However, if the shell always restored the same good terminal state it sampled when the shell itself was started, then the stty command would not work - while it could change the terminal state, any such changes would be undone once the shell learns that the stty command has exited and returns to the prompt. To avoid that, shells sample the terminal state when a job has exited and replace their known good state with the sampled state. Your shell should do the same.
3.5 Pipes and I/O Redirection
A pipeline of commands is considered one job. All processes that form part of a pipeline should thus be part of the same process group, as already discussed in Section 3.3. Note that all processes that are part of a pipeline are children of the shell, e.g., if a user runs a | b then the process executing b is not a child process of the process executing the program a.
To implement the pipes itself, use the pipe(2) system call, or alternatively the pipe2(2) GNU extension. The latter allows you to set flags on the returned file descriptors such as O CLOEXEC. A pipe must be set up by the parent shell process before a child is forked. Forking a child will inherit the file descriptors that are part of the pipe. The child must then redirect its standard file descriptors to the pipe’s input or output end as needed using the dup2(2) system call. If the user used the |& instead of the | symbol, both standard output and standard error should be redirected to the pipe.
Although the parent shell process creates pipes for each pair of communicating children before they are forked, it will not itself write to the pipes or read from the pipes it creates. Therefore, you must make sure that the parent shell process closes the file descriptors referring to the pipe’s ends after each child was forked. This is necessary for two reasons: first, in order to avoid leaking file descriptors. Second, to ensure the proper behavior of programs such as /bin/cat if the user asks the shell to execute them. To see why, we must first discuss what happens to file descriptors on fork(), close(), and exit().
Each file descriptor represents a reference to an underlying kernel object. fork() makes and restore it when the job is continued in the foreground by the user. a shallow copy of these descriptors. After fork(), both the child and the parent process have access to any object the parent process may have created (i.e., open files or other kernel objects). Closing a file descriptor in the (parent) shell process affects only the cur- rent process’s access to the underlying object. Hence when the parent shell closes the file descriptor referring to the pipe it created, the child processes will still be able to access the pipe’s ends, allowing it to communicate with the other commands in the pipeline.
The actual object (such as a pipe or file) is closed only when the last process that has an open file descriptor referring to the object closes that file descriptor. If you fail to close the pipe’s file descriptors in the parent process (your shell), you compromise the correct func- tioning of programs that rely on taking action when their standard input stream signals the end of file condition. For instance, the /bin/cat program will exit if its standard in- put stream reaches EOF, which in the case of a pipe happens if and only if all descriptors pointing to the pipe’s output end are closed. So if cat’s standard input stream is connected to a pipe for which the shell still has an open file descriptor, cat will never “see” EOF for its standard input stream and appear stuck.
Lastly, note that when a process terminates for whatever reason, via exit or via a signal, all file descriptors it had open are closed by the kernel as if the process had called close() before terminating. This means that you do not need to worry about making sure that file descriptors you open for the shell’s child processes are closed after these child pro- cesses exit. However, since the shell is a long running program that does not exit between user commands, the shell must close its copies of these file descriptors to avoid above- mentioned leakage. If it did not, it would eventually run out of file descriptors because the OS imposes a per-process limit on their number.
Although the processes that are part of pipeline typically interact with each other through the pipe that connects their standard streams, they are still independent processes. This means they can exit, or terminate abnormally, independently and separately. When your shell calls waitpid() to learn about these processes’ status changes, it will learn about each one separately. You will need to map the information you learn about one process to the job to which it belongs, using a suitable data structure you define in your shell.
Here is a brief table summarizing facts about the status changes and the corresponding macros you can apply to the status returned by waitpid:
3.6 Use of posix spawn
In a 2019 paper published at the HotOS workshop, Baumann et al [1] criticized the use and teaching of the Unix style of creating a new process by first creating a clone via fork(), then customizing the new process’s environment through actions the clone performs on itself before executing a new program. A key weakness of this approach is that it is incom- patible with multithreaded programs. They propose the use of an existing alternative API instead, i.e., posix spawn(3). This call combines fork() and exec() into one, and it also can be customized so that the child process will perform the necessary operations to set up or join a process group and to redirect inherited file descriptors as desired.
However, posix spawn as defined by POSIX lacks one important feature, which is to provide the child process with ownership of its terminal. This action cannot be per- formed in the parent since doing so would create a race condition: the child may reach a point where it assumes it had terminal ownership before the parent assigns ownership to it. For this project, you have access to a version of posix spawn that includes a non- portable extension posix spawnattr tcsetpgrp np(posix spawnattr t *attr, int fd) that allows you to provide a file descriptor referring to the terminal for which the child process should acquire ownership.
For your implementation, you are encouraged to use posix spawn in lieu of fork +exec. If you choose to do so, your implementation will avoid the potential sources of bugs that the use of fork() introduces, such as inadvertently attempting to update par- ent data structures in the child process, and in general will exhibit to easier-to-understand control flow and memory access semantics. Control flow will be traditional and linear: posix spawn will be called once, and return once, like any ordinary function. It will spawn a new program in a new process as a side effect. This child process will never directly access data structures inherited from the parent, though it relies on inheriting open file descriptors like in the fork case. posix spawn also does not change the fact that the created process will immediately run concurrently with the parent process when it returns. In other words, you may think of it as a combination of fork and exec, not of fork, exec, and wait.
However, it is difficult to use posix spawn successfully if you do not understand how fork and exec interact with file descriptors and process groups, so the explanation in the preceding sections still applies and must be thoroughly understood. Everything related to job management applies equally as it is independent of the method used to start the child processes.
When using posix spawn, you must observe all of the following hints
- Use the posix spawnp variant to be able to find programs in the user’s path.
- Use posix spawn file actions adddup2 to wire up pipe file descriptors and handle the redirection of standard error.
- Use posix spawn file actions addopen to wire up I/O redirection from/to files.
- Use posix spawnattr setpgroup along with the POSIX SPAWN SETPGROUP flag to establish or join a new process group.
- Use posix spawnattr tcsetpgrp np along with the POSIX SPAWN TCSETPGROUP flag to give the child’s process group terminal ownership.
- Use posix spawnattr setflags to set the desired flags. You may include POSIX SPAWN USEVFORK to make use of the specialized (and slightly faster) vfork() system call. Note that you may call this function only once since later calls will replace the flags set in earlier ones.
- You do not need to perform a setpgid() call in the parent since the race condition necessitating this call no longer exists: the call to spawn won’t return until after the child has been placed into its process group.
- You will need to pass the current environment as the last argument. Add an external declarationlikesoextern char **environ;.
- Lastly, note that the resulting code won’t necessarily be shorter (my version is 94 vs. 67 lines for the fork/exec variant), but very likely less confusing.
- The Makefile will set the correct include path and library flags to link with the re- quired version of posix spawnp, which overrides the version in the installed GNU
