COMP 3430 - Operating Systems
Winter 2021
Description
General submission requirements
Question 1: The Marginal At Best Shell ?
Description
Task
System calls
Running your program
Script files
Assumptions
Checking your output
Testing
Evaluation
Code quality and design
Implementation
Submitting your assignment
Advice
Debugging
Description
In assignment 2, you’re going to be working with processes, pipes, and FIFOs.
Assignment 2 is due Friday, March 11th, 2022 at 11:59pm CDT (Winnipeg time).
General submission requirements
- Operating Systems
2/11
Submissions that violate any of the following will not be evaluated (i.e., you will
receive a score of 0 for the assignment):
All solutions must be written in C. No other languages are accepted.
All solutions must include a working Makefile.
Forget how to make a Makefile? Never knew how to make a Makefile?
Thankfully, you can go to https://makefiletutorial.com and find some
very easy to use basic examples.
Your Makefile should contain a clean rule. When
is run in your directory, all the temporary files, including the executable
should be removed (e.g., rm -f my_prog).
All solutions must be compiled by issuing the command make in the directory
containing the Makefile. No other build commands are acceptable, even if
documented in the README.md.
All solutions must include a Markdown-formatted README.md file that
minimally describes how to run your submission.
Forget how to make a README.md? Never knew how to make README.md?
Thankfully, you can go to https://readme.so/ and build a nice,
Markdown-formatted README.md with a nice preview and some handy
buttons to help you build it.
All solutions must run to successful completion. Premature termination for
any reason (no obvious output, Segmentation Fault, Bus Error, etc.) is
considered to be a solution implementation that does not run.
Code that runs for an unreasonably long time (e.g., > 30 seconds) without
terminating is also considered to be a solution implementation that does not
run.
All solutions must compile. Code that does not compile will not be evaluated.
Programs must produce no errors when compiled with the flags
Note that -Werror prevents your code from being compiled when warnings
are present.
make clean
-Wall -Wpedantic -Wextra -Werror
- Operating Systems
3/11
If these flags are not in your Makefile, your submission will be treated as
though it does not compile.
Your code must compile and run on a machine on aviary.cs.umanitoba.ca.
No late submissions will be accepted. The assignment deadline is enforced
electronically. Submissions will not be accepted by e-mail.
Reminder: All submitted code will be evaluated using an automated similarity
testing tool, alongside commonly available online solutions for problems.
Question 1: The Marginal At Best
Shell ?
Description
“I am very proud of this shell.” Look at him, he’s beaming with
pride. (Public Domain)
- Operating Systems
4/11
Operating systems generally come with a shell, some kind of an interface for
interacting with the operating system. We’re using command-line shells
extensively in this course. When you’re connected to aviary, you’re almost
certainly using TCSH (“tee-see-shell”). If you’re using WSL, you’re almost
certainly using GNU Bash. If you’re using any recent version of macOS, you’re
almost certainly using Zsh (“zee-shell”, but I can’t bring myself to say it, so I
always refer to it as “zed-shell”).
Almost universally, you can figure out what command-line shell you’re using by
running a command:
These shells are all interactive, meaning that there’s a “prompt”, where the shell
is waiting for you (the user) to type something in (a command). The shell
interprets that command, then does the normal fork(), exec(), wait() dance.
When the process it fork()ed finishes, the shell prints out that prompt again,
patiently waiting for you to enter another command.
All of these shells also have the ability to execute scripts — you write a sequence
of commands into a text file, and run the shell as a program with that file as an
argument:
While there still may be some interactivity when running these scripts
(prompting you to enter a value), generally these kinds of scripts are non-
interactive. A non-interactive invocation of a shell script will just run to
completion without ever asking you for input.
Task
Your job is to implement a non-interactive shell with pipe, redirection, and
process substitution support. Your program will be provided with a script, where
each line is a sequence of commands that may have pipes (|), redirection
operators (< redirect file to standard input and > redirect standard output to file),
or process substitution sequences (<(program)). Your program has the
responsibility of doing the fork(), pipe(), exec(), wait() dance for all of the
commands in the line of the script.
So, for example, the command
echo $SHELL
bash my-script.sh
sort -R <(cat /usr/share/dict/words) | head -5 > random.txt
- Operating Systems
5/11
will invoke the sort command with the arguments -R and a “file-like-thing”?
that contains the contents of /usr/share/dict/words, pipe its standard output to
the head command (which was invoked with the argument -5), and the head
command will have its standard output written to a file named random.txt. The
contents of random.txt in this pipeline will be a random selection of 5 words
from /usr/share/dict/words.
You must implement this pipeline from scratch using the appropriate system
calls (e.g., pipe(), mkfifo(), fork(), dup2(), the exec family, and wait()).
When working with files in a command pipeline (i.e., redirection operators < and
>), you should use the open() and close() system calls. You should not use the
I/O functions from the standard library, you’d just be making your life harder.
When working with files (reading the script), you can safely use the I/O functions
from the standard C library (e.g., fopen, fgets, fclose). You’re also permitted to
use the standard string processing functions for deconstructing the command
into its components (e.g., strtok, strdup, strchr, etc), though you may consider
building a lower-level state machine for parsing the command pipelines.
You are permitted to use mktemp (see man 3 mktemp) for implementing process
substitution, however process substitution should not actually create a real file,
but should be implemented using a FIFO.
You are explicitly not permitted to pass your script to another shell and have
the other shell do the work.
System calls
You’ve used fork(), and wait() in assignment 1. You also used execvp(), pipe(),
and dup2() in lab 2.
Our textbook describes using the exec family of system calls in Chapter 5, and the
pipe() and dup2() system calls are described in APUE. Both of these families of
system calls are also well documented in the manual pages.
In terms of the exec family of system calls, you’re going to want to use either
execve() or execvp(), since they both allow you to pass command-line
arguments to the program that you’re exec-ing.
In terms of pipe() and dup2(): you should read the manual page for dup2() but,
in summary, you can use this system call to effectively replace a file descriptor.
For the purposes of this assignment, you’re going to need to repeatedly replace
STDIN_FILENO and STDOUT_FILENO in the child processes that you create using
pipes and the dup2() system call (STDIN_FILENO and STDOUT_FILENO are in
unistd.h).
- Operating Systems
6/11
The strategy here is: create a pipe in the parent, create the processes on either
side of the pipe in the command sequence, then replace the STD{IN,OUT}_FILENO
file descriptors on both sides just before running exec*().
Running your program
Your program should take one argument as input, which is the name of the script
script it should evaluate.
Script files
Here is a sample script file that you can use to test your implementation. The
sequence of commands increase in complexity as you get further down in the file.
The commands above depend on each other (e.g., ln -sf has to be run before
head -5 words), so the sequence of execution is important.
Assumptions
You can make the following assumptions about script files:
Each a line in a script file will never have more than 100 characters, each
sequence of commands will fit completely on one line (i.e., you don’t have to
handle commands that continue onto the next line).
Each individual command will be a valid command (e.g., you will never have
an individual command that has multiple redirect file to standard in <
operators, the name of the program will be an actual program).
If a command within a pipeline has redirection operators (>, <), it will only
have one of those kinds of operators. In other words, a command won’t have
a file redirected to its standard input and redirect its standard output to a file.
The only command with the redirect standard input operator < will be the
first command, and the only command with the redirect standard output
operator > will be the last command.
./tmabsh script.sh
touch touched.txt
ln -sf /usr/share/dict/words
head -5 words > first5words.txt
cat /proc/self/status | grep nonvol > nonvoluntaryswitches.txt
sort -R < words | head -5 > rand5words.txt
sort -R < words | head -5 | sort -d > randsort5words.txt
head -5 <(sort -R words) | sort -d > randsort5wordsprocsub.txt
- Operating Systems
7/11
Program names will be separated from their arguments using single
whitespace characters.
All commands within the script will execute successfully. While I encourage
you to check the status code of the child process with wait, you’re explicitly
not required to handle a command failing in the middle of the pipeline.
Commands within process substitution are simple (i.e., no embedded pipes
or redirection, no pipes, no recursive process substitution).
Output substitution (e.g., >(cat)) is possible in POSIX shells, but you can
safely assume that we will only evaluate your code using input substitution.
Checking your output
Since these are just regular commands, you can just run each of them in your
actual shell and see what the output is.
NOTE: Not all shells are created equally, and tcsh does not support process
substitution. When you try to do output substitution on tcsh, you’ll get output
similar to:
You should use bash or zsh instead of tcsh on aviary when you get to the point of
testing your implementation of process substitution. Starting bash or zsh on
aviary is easy: just type in bash or zsh and press Enter. You can quit bash or zsh
and get back to tcsh by typing exit and hitting Enter.
Testing
Please note that the graders will be using different scripts than the example
shown above, but the scripts they are using will be limited to the features
described above (e.g., redirection in and out, pipes, and process substitution).
With that in mind, we strongly recommend that you write your own test
scripts.
Some ideas for what to use in your test scripts:
Use other programs that redirect I/O (e.g., tee).
Read contents from the /proc file system (as in lab 0) and pass them through
pipelines in your script.
Use other programs that filter I/O (e.g., grep).
Whatever you choose to use, you should not be using interactive commands for
testing, since none of the scripts the graders will run will be interactive in any
way (remember: this is a non-interactive shell).
Missing name for redirect.
- Operating Systems
8/11
Evaluation
Code quality and design
5 points are awarded for code quality and design. “High quality” is defined as
code that follows the standards and best practices that you can find in the
“Standards and Best Practices” folder at the root of the Assignments section on
UM Learn:
Level Description
The code is very poor quality (e.g., no comments at all, no functions,
poor naming conventions for variables, etc).
–
The code is low quality, while some coding standards are applied, their
use is inconsistent (e.g., inconsistent use of comments, some functions
but functions might do too much, code is repeated that should be in a
function, etc).
This is the maximum level you can earn if the implementation of your
program is substantially incomplete.
–
the code is high quality, coding standards are applied consistently
throughout the code base.
Implementation
The implementation for this assignment is worth a total of 20 points (10 points ×
2), and is separated into 3 parts:
1. Command-line parsing and redirection.
2. Piping.
3. Process substitution.
Command-line parsing and redirection
This part represents the basic implementation of your shell and is worth a total of
5 points.
Level Description
Parsing and redirection is not implemented at all.