CSE 451
Assignment 1 : Callout Structures
Spring 1998
Assignment Handed Out: 4/1/98 (Wednesday)
Assignment Due Date: 4/10/98 (Friday)
This assignment should be done individually.
Manifest:
Files required for the project
main.c callout.c
callout.h Makefile
Tared version which contains all the above files.
Assignment1.tar
Download the file and use the following command to extract all the
files.
This will create a directory called Assignment1 in the current directory
and extract all the files into it.
Introduction:
The first assignment is designed to refresh some of your C programming
skills as well as get you familiar with some systems programming tasks.
In this assignment, you will be modifying an existing block of code to
implement a callout data structure and experiment a bit with measuring
the time it takes to perform some operations. The idea of a callout structure
is simple, but common in operating systems. Often, some low level piece
of the system needs to take some action when a particular event occurs,
for example a network interrupt. But, the low level piece of the system
doesn't know what precisely should happen on such an event, so it goes
looking for a callout. A callout is a function that has been registered
by some higher level piece of software to run when the particular event
occurs. This allows high level software to control the policies (eg, what
should happen when the network interrupt fires) while leaving to lower
levels the mechanism of handling and dispatching the network interrupt.
Task:
We have provided you with a partial implementation of a simple callout
management service in the context of a file called callout.h. This
file provides most of the services that we would expect to find in a callout
system that you might find in most operating systems. However, it has a
terrible (as well as incomplete) implementation (well, not terrible, but
just excessively simple, and in lots of need for optimization).
Your assignment has several parts:
-
To improve the implementation of callout.c so that it uses one queue per
event type, rather than a single global queue that needs to be searched
for each event. In addition, you should modify callout.c so that it exports
true handles rather than pointers to internal data structures.
-
To complete the implementation of callout.c so that it implements all of
the functions declared in callout.h. NOTE: YOU MUST NOT CHANGE callout.h:
This is an API that tens of millions of lines of code might depend on.
-
To test your new implementation using the skeleton framework provided in
main.c. You should declare a set of new arguments to ct (the program built
by the makefile) so that it can be invoked as
ct -t test_name
where test_name is
simple
complex
stress
and each of these test_names is supported by a function in main.c
that tests various characteristics of your implemention.
Example: the simple test ensures that simple operations
(make a few events, get them running) works. The complex test
ensures that a complicated series of callout register/unregister requests
work, as well as the map function. The stress test should cause
the system to be be stressed to its breaking point (eg, create a potentially
unbounded number of callouts -- what happens; unregister an event twice,
what happens?).
-
To time the implementation of your callout code. We would like to know
how long it takes to dispatch an event to a simple event handler that just
returns without doing any work. To do this, you will need to access the
UNIX clock to take a a timestamp delta (man gettimeofday) before and after
running some benchmark (example: generate 10000 callouts). Remember to
subtract the time to generate 10000 callout events from your computer delta.
What to turn in:
-
A new version of main.c and callout.c. Note: Do not turn in a version of
callout.h. We will be testing your code with our distributed version. So,
if you change callout.h, you run a pretty good risk of not even being able
to compile when being graded. Your code should be well commented.
-
A README file that contains
-
a description of what the three testing scenarios actually test.
-
a description of the performance of your callout system. How long does
it take to perform a single callout (you won't be able to measure this
directly since it's too fast; you'll need to run it many times and do some
division).
How to turnin:
You have to use the turnin program on orcas or
sanjuan to turn in your project.
To turn in your solution, use the following
turnin -c cse451 -p callout <all the files>
You could use
turnin -c cse451 -p callout *
to submit all the files in the current directory.
Remember to use only orcas or sanjuan to turnin files.
Have fun!
cse451-webmaster@cs.washington.edu