W4118 OPERATING SYSTEMS I

1/27: Homework 1 is updated. All updates are marked with the label "UPDATE".

Homework 1 is due Thu 2/5 at 4:09pm EST

All written and programming problems in this assignment are to be done alone. We do not allow group collaboration for this assignment. You should submit your solutions electronically via CourseWorks. Refer to the homework submission page on the class web site for additional submission instructions.

The total points of this assignment is 110 (not a mistake).

Written Assignment (40 pts)

Exercise numbers refer to the course textbook, Operating System Concepts. Each problem is worth 5 points.

1. (1.13) In a multiprogramming and time-sharing environment, several users share the system simultaneously. This situation can result in various security problems. a. What are two such problems? b. Can we ensure the same degree of security in a time-shared machine as in a dedicated machine? Explain your answer.
2. (1.14) The issue of resource utilization shows up in different forms in different types of operating systems. List what resources must be managed carefully in the following settings: a. Mainframe or minicomputer systems. b. Workstations connected to servers. c. Handheld computers
3. (1.22) What is the purpose of interrupts? What are the differences between a trap and an interrupt? Can traps be generated intentionally by a user program? If so, for what purpose?
4. (1.24) Some computer systems do not provide a privileged mode of operation in hardware. Is it possible to construct a secure operating system for these computer systems? Give arguments both that it is and that it is not possible.
5. What are the main requirements for an Interrupt Handler in Linux? Why?
6. List the main differences between a system call and a regular function call.
7. (2.13) Describe three general methods for passing parameters to the operating system.
8. (2.23) What is the main advantage for an operating-system designer of using a virtual-machine architecture?What is the main advantage for a user?

Programming Assignment: Shell (70 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. Refer to the homework submission page on the class web site for additional submission instructions.

Description

A shell provides a command line interface for users. It interprets user commands and executes them. Some shells provide simple scripting terms such as if or while, and allow users to make a program which facilitates their computing life. There are two categories of shells: command line and graphical. Intuitively, command line shells provide command line user interface commonly used in Unix/Linux environments, while graphical shells provide graphic user interface(GUI) such as MS Windows. In this assignment, we will focus on command line shells.

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.

A shell in Unix-like systems often supports two interesting features:

• input/out redirection. When you start a command, there are always three default file streams open, stdin(usually maps to input from the keyboard), stdout(usually maps to the normal output to the screen), and stderr (usually maps to error messages output to the screen). These, and any other open files, can be redirected, i.e., they can be mapped to files or devices users specify. Below are some redirection examples:

  $ cmd1 < in.txt 

  executes cmd1, using in.txt as the source of input, instead of the keyboard.

  $ cmd2 > out.txt 

  executes cmd2 and places the output to file out.txt.

  $ cmd3 >out.txt 2> err.txt 

  executes cmd3 and places the normal output to file out.txt and the error messages output to file err.txt. Here the 2 in 2> actually refers to the file descriptor 2.
• pipeline. The command below connects the standard output of cmd1 to the standard input of cmd2, and again connects the standard output of cmd2 to the standard input of cmd3, using the pipeline operator '|'

  $ cmd1 | cmd2 | cmd3 

  An example usage is:

  $ sort < file.txt | uniq | wc

  which counts the number of unique lines in file.txt. Without pipes, you would have to use three commands and two intermediate files to count the unique lines in a file.

You can learn more about I/O redirection at this wiki page.

In this assignment, you will implement your own shell.

1. (10 points) Write a simple shell. Basically 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 /bin/sh shell to do all the work. You are not allowed to use execlp() or execvp() in the standard library, because our shell has its own path variable, explained in part 2.
   • You may 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 (|).
   • You can assume that the command line a user types is no longer than 4096 bytes. However, you should not assume that there is a restriction on the number of arguments to a given command.
   • The executable file for your shell should be named myshell, for the TAs' grading pleasure.


2. (20 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.


3. (20 points) Extend your shell with I/O redirection (<, >, and 2>), as described above.
   • You'll need to understand Unix file descriptors. stdin maps to file descriptor 0, stdout to 1, and stderr to 2.
   • You'll need the open(), close(), and dup2() system calls.
   • You can assume that there is no space inside the stderr redirection operator "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).
   • You don't need to handle other forms of redirections. For example, you don't need to handle the following redirections : cmd 1> filename (another way to redirect standard output)), cmd 2>&1 (redirect standard error to standard output). (Most other shells do handle the above cases.)
   • UPDATE: Your shell do not need to handle I/O redirection for built-in commands (cd, exit, path).


4. (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.
   • UPDATE: Your shell do not need to handle built-in commands (cd, exit, path) in pipeline.
   • UPDATE: Your shell should not accept new user commands while the pipeline is still running.

Additional Requirements

• All code must be written in C; you'll receive 0 if you use other programming languages such as C++ or Java.
• Use 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. Do not be satisfied with code that merely compiles; it should compile with no warnings. You will lose points if your code produces warnings when compiled.
• 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.

Tips

• For this assignment, your primary reference will be Programming in C. You might also find the Glibc Manual useful.
• Many questions about functions and system behaviour can be found in the system manual pages; type in man function to get more information about function. If function is a system call, man 2 function can ensure that you receive the correct man page, rather than one for a system utility of the same name.
• If you are having trouble with basic Unix/Linux behavior, you might want to check out the resources section of the class webpage.
• A lot of your problems have happened to other people. If you have a strange error message, you might want to try searching for the message on Google.