Principles of Operating Systems

CMSC 421-02 - Spring 2017

Homework 2

50 points total

Due by 11:59PM EDT on Wednesday, April 19, 2017

Part I

15 points

Please provide written responses to the following questions. Each response should be at least 5-7 sentences in length. Each question is worth 5 points.

1. Describe how each of the following CPU scheduling algorithms work, including how each determines what thread to run next and for what reasons a thread may be swapped out: First come First served, Round Robin, Shortest Remaining Time First.
2. Describe the four conditions that must hold simultaneously in order for a deadlock to arise.
3. Describe the following types of directory structures for a filesystem, including listing pros and cons of each type: Tree-Structured, Acyclic Graph-Based, and General Graph-Based.

Part II

35 points

Complete the following programming assigment and submit your code using the GitHub repository that you will have created for this assignment. This assignment must be completed in the C programming language (you can choose to use C89/C90/ANSI-C, C99, or C11 as you see fit).

In this assignment, you will be augmenting your shell from Homework 1 with a few new features:

• A built-in exit command that can take zero or one arguments that exits your shell. If an argument is specified, it must be an integer, which should be used as the exit code for the program. If a non-integer argument or multiple arguments is given, you must simply print out an error message and not exit. If no argument is given, assume that the exit code should be 0.
• A built-in chdir command that changes the current working directory of the shell. If no argument to this command is specified, then the directory shall be changed to the user's home directory (assuming HOME is set in the user's environment — if it is not set, then you shall print out an error). You must also be sure to also update the PWD environment variable. You may assume that no paths given will ever exceed the value of PATH_MAX which is defined in <limits.h>. You may ignore anything after the first fully unescaped argument to the command (so chdir /long/"space filled"/path/name abc should just ignore the abc part).
• A built-in cd command that shall do the same thing as the chdir command specified above.
• A built-in getenv command that looks up the specified environment variable (a string) and prints out the contents of it, followed by a newline character. If the specified environment variable does not exist in the user's environment, then you shall simply print out the newline character specified above. You should report an error if more than one argument is given to this command.
• A built-in setenv command that sets the specified environment variable name to a given value. The value shall be unescaped prior to storing it in the environment variable. The command shall be structured so that setenv key=value will set the environment variable key to the value. Anything after the full unescaped value may be ignored (so if you had setenv k="v 123" abc , the abc part would simply be ignored).
• A built-in echo command that shall unescape the given string and print it out, followed by a newline on the user's standard output.
• All built-in commands shall have priority over identically named programs that are in the user's PATH. That is to say, if the user has an echo program in his or her path (say in /bin), unless they specifically call that program by a full path, you should run your own internal implementation and not the one provided by the program. If the user specifies a full path, like /bin/echo (in this example), then you'd run the program and not your implementation.
• All built-in commands shall unescape commands where appropriate. That is to say that the argument to chdir, echo, and the value to store in the environment variable for setenv shall be unescaped before use. Environment variable names for getenv and setenv shall not be unescaped and must not contain any space characters (as defined by the isspace C library function) nor any = characters. In addition, all program paths shall be unescaped and all arguments to non-built-in programs should also be unescaped properly.

To aid in your development of this new version of the shell, I've provided some useful utility functions. You can find the code to these functions here and a header file for them here. In particular, the unescape function in there should be quite useful (i.e, this will do the hard work of the last requirement up there). You do not have to use these source files if you don't want to, but it would be kinda silly not to. If you choose to not use them, you must still unescape strings as specified above in the same manner as my unescape function. It will be up to you to ensure that your implementation is functionally equivalent if you do not use mine.

As a hint, many (but not all) of the commands that you are to implement boil down to parsing out arguments, checking for error conditions, and running one function from the C library. I'm pretty deliberate about how I name things, so you might use that as a good starting point for searching in the Open Group Base Definitions.

Your shell program is not allowed to use any external libraries other than the system's C library and the files provided in this assignment. Do not try to use libraries like Readline. You will lose points for using external libraries to implement shell functionality! In addition, the C library functions specifically outlawed in Homework 1 are still outlawed in this assignment, as is using another shell to do the work of parsing arguments and running commands. Please refer back to Homework 1 if you have any questions on this.

Here is an example shell session demonstrating some of the new functionality in this assignment:

$ getenv HOME
/Users/lj
$ getenv PWD
/Users/lj/421-sp2017/shell
$ cd ..
$ getenv PWD
/Users/lj/421-sp2017
$ ls -l
total 24
drwxr-xr-x  14 lj  staff   476 Mar  3 16:44 shell
-rwxr-xr-x   1 lj  staff  9420 Feb 18 11:42 simple_shell
$ cd shell
$ /bin/ls -la
total 184
drwxr-xr-x  14 lj  staff    476 Mar  3 16:44 .
drwxr-xr-x   5 lj  staff    170 Feb 19 14:59 ..
drwxr-xr-x  13 lj  staff    442 Feb 19 12:53 .git
-rw-r--r--   1 lj  staff    304 Mar  3 11:02 Makefile
-rw-r--r--   1 lj  staff   5103 Mar  3 16:44 builtin.c
-rw-r--r--   1 lj  staff    228 Mar  3 10:58 builtin.h
-rw-r--r--   1 lj  staff  10808 Mar  3 16:44 builtin.o
-rwxr-xr-x   1 lj  staff  20048 Mar  3 16:44 simple_shell
-rw-r--r--   1 lj  staff   2674 Mar  3 16:27 simple_shell.c
-rw-r--r--   1 lj  staff   8272 Mar  3 16:27 simple_shell.o
-rw-r--r--   1 lj  staff   3568 Feb 23 11:34 test.o
-rw-r--r--   1 lj  staff   7558 Mar  3 16:10 utils.c
-rw-r--r--   1 lj  staff   2330 Mar  3 16:19 utils.h
-rw-r--r--   1 lj  staff   9368 Mar  3 16:10 utils.o
$ setenv MESSAGE="Hello, world"
$ getenv MESSAGE
Hello, world
$ setenv MESSAGE="Hello, 'Lawrence'"
$ getenv MESSAGE
Hello, 'Lawrence'
$ setenv MESSAGE=Hello,\ \"Lawrence\".\ How" are you today?"
$ getenv MESSAGE
Hello, "Lawrence". How are you today?
$ chdir /
$ getenv PWD
/
$ chdir
$ getenv PWD
/Users/lj
$ echo \x48\151\x20\157\165\164\040\x74\x68\x65\x72\x65\041
Hi out there!
$ echo Goodbye, \'World\'\a
Goodbye, 'World'
$ /bin/echo \x48\151\x20\157\165\164\040\x74\x68\x65\x72\x65\041
Hi out there!
$ exit

When submitting your shell program, please be sure to include the source code of the shell program (in one or more C source code files), as well as a Makefile that can be used to build the shell. Your shell must be able to be built and run on a VM as has been set up for this course in your projects. If you use my utility functions, make sure to include those files as well.

As this should be an extension of your earlier homework 1 shell, you should be using the same directory and git repository for it. To submit your code, you should do the following:

git add your_updated_and_added_files_go_here
git commit
git push -u origin master

git tag hw2
git push origin --tags

Last modified