CS 414 Fall
2003: Homework 1 (due Sept. 18)
Please type your solutions. Grading for each
question will be on a simple “check-/check/check+” basis (later this will be
translated into points: 0 if you don’t do the problem, 3 for check-, 4 for
check, 5 for check+). You
can discuss problems with other people, but your actual solution must be your
own work, not joint work.
All of these questions
have short answers, a sentence or two at most. If you think a question is asking for
a half a page… you probably don’t understand the problem!
1. Modern devices are more and
more sophisticated, and in some cases this means that things an application
used to do are now done by the hardware.
For example, a high-performance display subsystem of the sort used to
“accelerate” graphics in a computer game basically takes what used to be software
procedures for doing things like shading and projective displays and implements
those functions in hardware. One problem
that now arises involves handling exceptions.
In software, it isn’t uncommon to catch exceptions and perhaps even
ignore them (for example, zero-divide exceptions). In hardware, any exception will always cause
an interrupt.
Suppose that you are writing
a device driver for a graphics accelerator, and you need to handle a
“zero-divide interrupt”. You’ll either
tell the device to ignore the event and continue with the next graphics
instruction, or you’ll terminate the application. Now, suppose that figuring out which action
to take involves executing code in the application itself.
a. The device interrupt handler
runs in the kernel. But the application
runs in user mode. Can the device
driver “call” a function within a user-address space application? Why or why not?
b. Suppose that the application
is waiting for an I/O operation to complete when the interrupt occurs. Can you suggest a way to accomplish both of
the following goals: (a) find out how the application wants to handle this
event as soon as possible, (b) tell the device something sensible right now?
c. In what ways is the
situation in part (1.b) similar to a “priority inversion”? In what ways is it different?
2. A computer game contains
three threads, each of which accesses three lists of objects: the asteroid list, the weapons inventory and the alien
spacecraft. The
threads do different things: one keeps the display current, one updates each of
these objects as time advances, and one handles user inputs, some of which
affect one or more objects.
The code chunks that touch these lists are in critical sections,
but you are finding that the application is running incredibly slowly. On investigation,
you discover that the first and second thread are almost always trying to run “in”
the critical section. Once
of them gets in, the other two freeze up.
a. In general, would it be
possible to modify the code so that each thread goes in and out of the critical
section once for each object?
E.g. perhaps thread1 used to enter, update the asteroid pictures,
then exit. With
such a change, it might enter on an asteroid-by-asteroid basis, each time
calling CSEnter, then accessing one asteroid,
then calling CSExit. How might you be forced to change the old code for
thread1 if you adopted this approach? (Note: Assume that each list is a
double-linked queue, and that the threads can add or delete objects from one or
another list while the application is running.)
b. In class, we talked about
how one could have more than one “flavor” of critical section. Would it make sense to have 3 or more
flavors here, one for each class of objects? Can you describe conditions under
which this would be safe, and contrast those with conditions under which it
might cause problems?
3. In class, we saw that an
atomic test_and_set operation can be used to
implement critical sections on a machine supporting parallelism (with multiple
physical CPUs). We
also saw that the test_and_set operation behaves similarly
to the following procedure, coded here in C#:
public boolean test_and_set(out boolean flag)
{
boolean v = flag;
flag = true;
return(v);
}
Now, suppose that someone
who is maintaining a program that uses this method doesn’t understand the code,
and he actually puts the above code into the program and recompiles it. That is, the CSEnter and CSExit procedures are unchanged
(you can see them in problem 3, below), but test_and_set is now the function shown
above, with no special atomicity properties.
Recall that safety of a critical section algorithm
is the property that no more than one process can enter the critical section at
a time. Could safety now be violated?
4. Here’s the code for CSEnter and CSExit that we used to implement
critical sections with test_and_set, just as we saw it in class:
boolean flag = false;
// initial value
CSEnter()
{
boolean v;
do
{
v
= test_and_set(flag);
}
while(v == true);
}
CSExit()
{
flag = false;
}
Recall that one problem with
this code is its potential for unfair behavior.
It is possible to imagine a situation in which processes P0 and P1
compete to enter the same critical section, and one of them enters an unlimited
number of times while the other one gets stuck and never enters even once. Under the assumption that we are only dealing
with 2 processes, modify CSEnter and CSExit so that if the two
processes try to enter simultaneously, each will “win” half the time. You code should still work correctly even if
one or both processes never tries to enter at all, or enters very rarely.
5. Suppose that you are writing
an application to run on an operating system that employs a round-robin
scheduler using multi-level feedback queues. Your application is a CPU-bound,
long-running, “data cruncher”, and it will run on systems shared with other
kinds of applications.
Each run takes about one hour if nobody else is using the machine
– but as just mentioned, other people are often on the same machine. Being a nasty kind
of person, you’ve decided to trick the system into giving you a larger share of
CPU time, and you’ve noticed that applications on the “interactive” job queue
are scheduled as soon as they become runnable.
a. What could you do to trick
the system into putting your data cruncher onto the interactive jobs queue, and
keeping it there?
b. During periods when nothing
else is runnable, what costs (overheads) will be
incurred in your approach?
c. Would it be possible to
design a mechanism so that your application switches modes, using the “trick”
proposed in part (a) only when other applications are sharing the machine, and
switching to its original crunching mode (and not using that trick) if nobody
else is running? How
would you do it?