COMS W4118: Operating Systems I

Homework 1

Homework 1 is due Monday 2/11 at 12:01 AM ET.

All written and programming problems in this assignment are to be done alone. Submit the homework using the instructions on the homeworks page. Your homework directory should contain all files related to the written and programming assignments together. Periodically check back on the course page for any errata or updates to submission instructions.

Written Assignment (40 pts)

Exercise numbers X.Y refer to the exercise problem Y in Chapter X in the course textbook, Operating Systems Concepts 9e. Each problem is worth 5 points. Make your answers concise. You'll lose points for verbosity.

Programming Assignment: Shell (60 pts)

For this programming assignment you will be required to submit source code, a README file documenting your files and code, and a test run of your programs. The README should explain any way in which your solution differs from what was assigned, and any assumptions you made.

Description

Download and read the original UNIX paper The UNIX Time-Sharing System by Ritchie and Thompson. Our object of interest for this homework is found in Section 6, The Shell. Although most modern OSes provide a graphical shell, power users (if you aren't one already, you'll soon be one by the end of the semester) often still prefer the command line shell. In this assignment, we're going to implement one.

Under the hood, a shell is just another user program. The files /bin/sh, /bin/bash, and /bin/tcsh are all executable files for shells. The only thing special about your login shell is that it is listed in your login record so that /bin/login (the program that prompts you for your password) knows what program to start when you log in. If you run ``cat /etc/passwd'', you'll see the login records of the machine and the login shell program listed as the last field.

In addition to basic command execution, we are also going to implement the two shell features described in Sections 6.1 and 6.2 of the UNIX paper, viz. I/O redirection and pipelining (called Filters in the paper). You can read more about them at this wiki page.

Deliverables

All code must be written in C. The executable file for your shell should be named myshell. You also need to supply a makefile to control the compilation of your code. The makefile should have at least a default target that builds your shell. Google "makefile tutorial" for how to write makefiles. When using gcc to compile your code, use the -Wall switch to ensure that all warnings are displayed. You will lose points if your code produces warnings when compiled. Before submitting, make sure you remove any files produced during compilation (.o files, executable).

(10 points) Write a simple shell. Your shell should read the line from standard input, parse the line with command and arguments, and execute the command with arguments. You'll need the fork() and exec*() system calls.

• The shell should find the command in your current working directory first. If not found, it should search the directories in the shell's pathname list which will be explained in the part 2.
• You are not allowed to use system(), as it just invokes the system's shell to do all the work. You can't use execlp() or execvp() — our shell has its own path variable, explained in part 2.
• Assume that arguments are separated by white spaces. You do not have to deal with special characters such as ', ", \, etc; however, you need to handle the redirection operators (<, >, and 2>) and the pipeline operator (|).
• Assume that the command line a user types is no longer than 4096 bytes. However, don't assume that there is a restriction on the number of arguments to a given command.
• You do not need to handle the background operator &

(10 points) Implement the following built-in commands.

• exit: users can exit from the shell with the exit command.
• cd: cd is a command to change directories. You will need to invoke the chdir system call.
• path: path is a command not only to show the current pathname list, but also to append or remove several pathnames. In your shell implementation, you may keep an variable or data structure to deal with pathname list (referred to as "path" variable below). This list helps searching for executables when users enter specific commands.
  • path (without arguments) displays the pathnames currently set. It should show pathnames separated by colons. ex) "/bin:/usr/bin"
  • path + /foo/bar appends the pathname to the "path" variable. Only one pathname will be given to each invocation of the path command. It's okay to add a pathname to the "path" variable even if it already contains the same pathname, i.e., duplicates in the "path" variable are fine.
  • path - /foo/bar removes the pathname from the "path" variable. It should remove all duplicates of the given pathname. Only one pathname will be given to each invocation of the path command.

(20 points) Extend your shell with I/O redirection (<, >, and 2>).

• You'll need the open, close, and dup2 system calls and understand Unix file descriptors. stdin maps to file descriptor 0, stdout to 1, and stderr to 2.
• You should handle cases when all three streams are redirected, such as cmd < in.txt > out.txt 2> err.txt (not necessarily in this order). Assume that there isn't any space in the stderr redirection operator "2>".
• You don't need to handle I/O redirection for built-in commands (cd, exit, path) or other forms of redirections. For example, you don't need to handle: cmd 1> filename (another way to redirect standard output)), cmd 2>&1 (redirect standard error to standard output).

(20 points) Extend your shell with pipeline (|), as described above.

• You'll need the pipe system call.
• There is no restriction on the depth of a pipeline. That is, your solution should handle arbitrary number of commands chained together with operator |
• You should handle combinations of redirection and pipeline when they can be combined. An example is: sort < file.txt | uniq. However, if there is a conflict between redirection and pipeline, i.e. one file descriptor gets associated with two things, you should report a syntax error. An example is: ls > 1.txt | grep FOO; we cannot redirect the stdout of ls to both 1.txt and grep at the same time.
• You do not need to handle built-in commands (cd, exit, path) in the pipeline.
• Your shell should not accept new user commands while the pipeline is still running.

Error Handling

Check the return values of all functions utilizing system resources. Do not blithely assume all requests for memory will succeed and all writes to a file will occur correctly. Your code should handle errors properly. Many failed function calls should not be fatal to a program. Typically, a system call will return -1 in the case of an error (malloc will return NULL). If a function call sets the errno variable (see the function's man page to find out if it does), you should use the result of strerror(errno) as part of your error message. As far as system calls are concerned, you will want to use one of the mechanisms described in Reporting Errors or Error Reporting.