Principles of Operating Systems

CMSC 421-04 - Spring 2016

Homework 2

Chapter 6

50 points total

Due by 11:59PM EST on Tuesday, March 15, 2016

Due by 11:59PM EDT on Friday, March 18, 2016

Part I

10 points

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

1. Describe why it is very important for a scheduler to distinguish between I/O-bound tasks and CPU-bound tasks. Be sure to include how the scheduler can use the knowledge of whether a task is I/O- or CPU-bound to aid in its scheduling decisions.
2. Consider the folowing scheduler (which I'll call the RRLTR scheduler). The scheduler works as follows... The scheduler consists of a queue that operates in a pseudo-round robin fashion. That is to say, that as a process is granted the CPU, it is given a time quantum q with which to run. When that process is removed from the CPU (either by q expiring without completing its CPU burst or by it requesting I/O), another process from the queue is selected, assuming that there are any other processes ready to be executed. The process removed from the CPU is placed back into the queue based on how much time is estimated to be remaining in its CPU burst (with longer times given priority over those with less time remaining). Assuming that no new processes enter the system in the time period we consider, can this scheduler result in indefinite starvation? Why or why not? If new processes are allowed to enter the system, can this scheduler result in indefinite starvation? Why or why not?

You must submit a PDF file of the answers to these questions on the Homework 2 assignment on Blackboard. You may prepare your responses in any word processing application of your choosing, but you must submit a PDF file. Do not submit Microsoft Word/Apple Pages/LibreOffice/OpenOffice.org documents with your responses. You must convert to a PDF file before submitting or you will lose points.

Part II

40 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:

• Program path names may be provided either as absolute paths (/bin/ls) or without the path, provided that the program specified is in a directory specified in the user's PATH environment variable. This should be a one-line change from your original Homework 1 shell!
• 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 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.
• 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 exit 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/exit (in this example), then you'd run the program and not your implementation.

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!

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

$ getenv HOME
/Users/lj
$ getenv PWD
/Users/lj/421-sp2016/shell
$ cd ..
$ getenv PWD
/Users/lj/421-sp2016
$ 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'
$ 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