Lab 1. Profiling shell


You are a programmer for Big Data Systems, Inc., a company that specializes in large backend systems that analyze big data. Much of BDS's computation occurs in a cloud or a grid. Computational nodes are cheap SMP hosts with a relatively small number of processors. Nodes typically run simple shell scripts as part of the larger computation, and you've been assigned the job of speeding up these scripts.

Many of the shell scripts have command sequences that look like the following (though the actual commands tend to be more proprietary):

  sort < a | cat b - | tr A-Z a-z > c
  sort -k2 d - < a | uniq -c > e
  diff a c > f

  until cmp -s a b; do
    recalc a b | sort -u -o a
    recalc b a | sort -u -o b

Some of these individual commands run quickly, and some slowly, and it's not easy for your developers (who are not shell experts) to debug where the slownesses are. They can modify their scripts to use the time command, but that's a pain and they'd rather have a method that doesn't require modifying their scripts.

Your goal is to write a prototype for a shell that runs scripts like the above, without modification, while providing performance information that does not unduly interfere with ordinary execution. If this prototype works well, the idea is that you'll later (i.e., after CS 111 is over...) improve the prototype until it is production quality.

Your company's shell scripts all follow some simple rules which should make the prototype easier to write:

Your implementation will take three phases:

Lab 1c details

In Lab 1c, every process started by the shell or by one of its descendant subshells should generate one line of output in the profile when the process exits. Also, one line of output should be generated for the shell process itself, when it exits. Each line of the profile should look like the following:

1414117272.94 0.159 0.020 0.003 sleep 0.1547825513s

In this example, "1414117272.94" is the time when the command finished (in seconds since 1970-01-01 00:00:00 UTC, not counting leap seconds), "0.159" is the command's real time in seconds, "0.020" is the command's user CPU time in seconds, "0.003" is the command's system CPU time in seconds, and "sleep 0.1547825513s" is the command name (here, "sleep") followed by a space and then by its arguments separated by spaces (here just one argument, "0.1547825513s"). If a name or argument contains a newline, display the newline as a space; if the entire log line (not counting the trailing newline) would contain more than 1023 bytes, output just the first 1023 bytes.

If the process did not exec a command or is the shell process itself, log the process's numeric ID in square brackets instead, e.g., for process 1321:

1414117272.98 0.199 0.023 0.004 [1321]

When logging user and system CPU time for a process, include the CPU time consumed by children of the process.

When logging absolute times such as 1414117272.94, use the CLOCK_REALTIME clock; see the clock_gettime system call. When logging real time, use the clock supported by the SEASnet GNU/Linux servers that is most appropriate for measuring real time in a profiling shell; this is not necessarily the CLOCK_REALTIME clock. Your README file should justify your choice of clock.

If you can log times to more precision than shown in the examples above, do so; include trailing zeros in the times only if they are significant. See the clock_getres system call for information about how to get clock resolution.

If the log file cannot be written to for some reason, the shell should continue without further attempts at logging but should eventually exit with nonzero status. For example, the command "profsh -p /dev/full script" should exit with nonzero status after running the script.

Make sure that log lines are not interleaved when two processes finish at about the same time.

Your README file should answer the following questions. In these questions, assume that the log file could always be written to successfully.


A skeleton implementation will be given to you on CCLE. It comes with a makefile that supports the following actions. Your solution should have similar actions in its makefile.

Your solution should be written in the C programming language. Stick with the programming style used in the skeleton, which uses standard GNU style for C. Your code should be robust, for example, it should not impose an arbitrary limit like 216 bytes on the length of a token. You may use the features of C11 as implemented on the SEASnet GNU/Linux servers. Please prepend the directory /usr/local/cs/bin to your PATH, to get the versions of the tools that we will use to test your solution. Your solution should stick to the standard GNU C library that is installed on SEASnet, and should not rely on other libraries.

You can run your program directly by invoking, for example, ./profsh -t foo. Eventually, you should put your own test cases into a file so that it is automatically run as part of 'make check'.

More details on syntax and semantics of the shell subset

The "time travel" feature of your shell is feasible partly because of the restricted subset of the shell that you need to implement. Also, for this assignment, the shell has been simplified further so as to avoid some work that can be deferred until a production version.

Shell syntax subset

Your implementation of the shell needs to support only the following small subset of the standard POSIX shell grammar:

If your shell's input does not fall within the above subset, your implementation should output to stderr a syntax error message that starts with the line number and a colon, and should then exit.

Your implementation can have undefined behavior if any of the following features are used. In other words, our test cases won't use these features and your program need not diagnose an error if these features are used.

Don't care behaviors

Similarly, in some cases, your company's scripts don't care how your implementation behaves, and it's OK for it to depart from established semantics when it is run in time-travel mode.

You can simplify your shell in one other way, regardless of whether it is run in time-travel mode:


After you implement Lab 1a, submit via CCLE the .tar.gz file that is built by 'make dist'. Similarly for 1b and 1c. Your submission should contain a README file that briefly describes known limitations of your code and any extra features you'd like to call our attention to.

We will check your work on each lab part by running it on the SEASnet GNU/Linux servers, so make sure they work on there. Lab 1 parts are due at different times, but we will not grade each part separately; the lab grade is determined by your overall work on all three parts.

Design problem ideas

Here are some suggestions for design problems, if you have been assigned a design problem for Lab 1. You may implement one of them, or design your own. If you design your own, get approval from us before committing significant work to it. Your implementations should include test cases.

For Lab 1a:

For Lab 1b:

For Lab 1c:

© 2012–2014 Paul Eggert. See copying rules.
$Id: lab1.html,v 1.10 2014/10/24 05:53:34 eggert Exp $