---------------------------
TECHNICAL NOTE 1  (9/22/01)
---------------------------



Here is a summary of troublespots for Assignments A2 and A3,
which will be returned to you this week.

ASSIGMENT A2

(1) Processes and threads are different objects.  A process is
a virtual machine containing one or more threads, an address space,
executable code, parameters, I/O connections, an environment
variables.  A thread is a sequence of statewords of a CPU.
Starting a new process is expensive compared to starting a new
thread because the system has to make a copy of all the components
of a process's virtual machine.  Threads have their own stacks
but share the process address space.  This facilitates information
sharing and complicates protection.  NOTE: context-switching
does not apply to processes; only to threads.

(2) and (3).  The important point is that the interrupt handler
gets its own frame pushed on the stack of the current thread;
when that handler is done, and executes its return instruction,
the current thread will continue from the point of interruption,
unaffected.  A subtle, but important point is that with certain
interrupts (notably clock) there is a context switch; when the
ready process returns to the front of the RL and is resumed, it
returns from the SAME handler invocation that interrupted it
before; when that handler returns, the frame is popped off the
stack and the process continues as if it had not been
interrupted.  See the previous technical note about the way
interrupts push and pop frames from the stack.

(4) and (5).  R(SJF) = 22 sec.  R(LJF) = 38.5 sec.  R(RR) = 34
sec.  No schedule can have shorter R than SJF because moving any
longer job ahead of a shorter one will increase the waiting
times of the displaced jobs and because SJF can be converted to
any other schedule by a series of these simple interchanges.  No
non-preemptive schedule can do worse than LJF for a similar
reason.  However, a preemptive schedule can do worse: run every
job for 1 microsecond less than its execution time, then
preempt, then all the jobs complete within a few microseconds of
55 sec, causing R = 55 sec.  It is not possible to do better
than SJF with preemption because putting any part of a job
earlier in the schedule will increase the response times of all
the intervening jobs by that amount.  RR is a preemptive
schedule that is useful when you don't know the job lengths in
advance; it prevents a long job from hogging the CPU.  The
reponse time of RR depends on its quantum.  If you made the
quantum larger than 10 sec, the system would run an SJF schedule
with R=22 sec; and it you made the quantum very small (processor
sharing with 0 switching overhead) it would give response time
R=38.5 sec, the same as LJF.  (Check this for yourself.)



ASSIGNMENT A3

(1) Directories are different objects from files.  Directories
map user-assigned strings to object handles.  The objects may be
other directories, files, devices, pipes, virtual machines.
Because the object handles are not limited to files, the
directory manager cannot be part of the file system.  While it is
true that directories are usually implemented as files, they
could also be implemented as tables in RAM.

(2) The given command is syntactically valid.  It may not be
semantically valid (i.e., it may not be meaningful or
executable).  The initial segment of the command,
outfile<cat, follows the syntax; it says there must be a command
named "outfile" and a data file named "cat" and that shell must
create a VM running "outfile" with file "cat" opened for reading
at its input port.  If your Unix system does not have an
executable named "outfile", the shell will complain that it
cannot find a file "outfile" -- but that is a semantic complaint,
not a syntactical one.  Similarly, if there is no datafile named
"cat" the shell will complain that it can't find the file.  Also,
if the Unix sort command does not accept the flag "-a", the error
message will come from the sort program, not the shell, and it
will be about an invalid flag, not invalid syntax.

(3) File handle points to a file.  Open file handle points to an
open-file control block, which contains a copy of the index for
the file, buffers, and other information, all designed to speed
up read and write accesses to the file.  Files are different
objects from open-file control blocks.

(4) Handles are stored in a user's workspace.  User has a portion
of the directory system as part of that workspace.  The
directories protect the handles from manipulation.  If you could
alter a handle, you could present it to the wrong object manager
or you could access the wrong object.

(5) DOS executes pipeline components sequentially to completion.
UNIX executes all the components in parallel and uses the pipes
to synchronize them.  (Pipes prevent the downstream VM from
reading if they are empty.)  If the pipeline is called on to
process a large dataset, the parallelism will enable it to start
producing its final outputs much sooner in UNIX than in DOS.
Because pipes may be implemented as files, it is hard to say that
the DOS files are a significant disadvantage.

---------------------------
TECHNICAL NOTE 2  (9/27/01)
---------------------------



The programming assignment you are working on has three aspects
to it:

1.  Understanding the operation of a synchronization mechanism
    (monitors) in a realistic, and complex, situation.

2.  Getting the synchronization mechanism to work in a real
    program.

3.  Designing a simulator of the situation controlled by the
    synchronizer and taking measurements of the effects of the
    synchronization.

As you do these parts, you will find, especially in 2 and 3,
that the problem statements are not fully specified.  You
will therefore have to take responsibility for some key
design decisions and for your own creativity.  In your
report, document and defend your design decisions.  This
is standard engineering practice.

  For example, if you choose Java as your implementation
  language, you will find the synchronized statement along
  with the operations wait(), notify(), and notifyall()
  as the nearest equivalent to monitors.  Java, however,
  has no direct support for condition variables.  You need
  to simulate the effect of condition variables (see previous
  technical note).

  If you choose the Sun OS with multithreading as your
  implementation platform, you will find that there is no
  monitor structure available.  Thus you will have to
  define and use semaphores to accomplish the job.

You will also find plenty of opportunities to be creative
in designing the simulator.  The simulator consists of
a set of N threads each simulating one car, a representation
of the bridge and its queues, the controller, and data
collection steps.  I suggest that you allocate the N
threads at the beginning of the simulation and let each
one cycle, representing the car returning to the bridge
again and again for repeated crossings.  The largest number
of cars you can therefore observe on the bridge is N.
What value of N to use?  That's a design decision.  You
can perform experiments with a few different values of N
to see what the effect of N is on the results.  For
example, N = 5, 10, 20, 40.

Each car thread has a cycle with a random delay of mean
duration R away from the bridge and a fixed crossing time C
of the bridge.  You can explore the effects of large, medium,
and small values of the ratio R/C.  Large R would mean low
contention for the bridge and small R high contention.

You can collect various data as your run the simulator through
its time steps.  You can measure the queue lengths at the ends
of the bridge, the mean time in the queue, the mean number on
the bridge at once, the max number observed in a given
direction.  You can plot graphs showing how variations in
the parameters (especially R/C) affect the results.

You can investigate improvements on the controller program.
For example, under heavy load (low R/C) the intensity of
cars in a given direction (say eastbound) may seize
the bridge, preventing the opposite cars from crossing.
This is a form of starvation.  You can experiment
with policies that prevent it -- for example, allow
at most five cars in one direction before switching directions.
If you switch directions, remember that time C must pass
for the cars to empty from the bridge before the waiting
cars in the opposite direction can start.



----------------------------
TECHNICAL NOTE 3  (10/30/01)
----------------------------

This note concerns trouble spots in the questions of midterm Q1.

(1b) To prove that LJF has longest response time among
nonpreemptive schedules, you must show that LJF is the worst
among all possible orderings of the jobs.  Suppose that the jobs
are indexed 1,2,...,n with execution times e1,e2,...,en.  The
completion time of the first job is e1; of the second e1+e2; of
the third e1+e2+e3; and so forth.  The sum of the completion
times is

   S  = n*e1 + (n-1)*e2 + (n-2)*e3 + ... + (1)*en

and the response time is R = S/n.  Since n is fixed for a given
job set, S is maximum when the largest coefficient (n) has the
largest job (e1), the next largest coefficient (n-1) has the next
largest job (e2), etc.

(1c) The worst possible response time is achieved when every job
is preempted a moment just before its completion and these tiny
residuals are all finished at the end of the schedule.  This
makes the mean response time nearly 55 sec (the completion time
of the job set).  See Technical Note 1.

(1d) Preemption cannot improve over SJF.  If you try to move any
slice of a job earlier in the schedule, you would increase the
completion times of the intervening jobs by the size of the slice
and would decrease none of the other completion times.  Since any
preemptive schedule can be constructed by a series of such
transformations from an SJF, none can shorten the response time.

(1f) In PS, the set of 10 jobs runs at 1/10 speed until one of
them completes.  That's the one with execution time 1 and it
completes at time 10.  Now the 9 remaining jobs are have 1 sec
less to complete.  This set runs at speed 1/9 until one of them
completes at time 19.  The remaining jobs run at speed 1/8 until
one of them completes at time 27.  Continue this and you find
that the mean response time is 38.5 sec, the same as for LJF.

(1h) The ideal is to run SJF to minimize the average response
time.  Unfortunately, we don't usually know job execution times
in advance.  The preemptive schedules give us a way of pushing
back a long job when it becomes apparent from watching it that it
is long.  RR does this by giving all jobs equal time slices in
rotation; no long job can hog the CPU.  MLQ improves on this by
"learning" which jobs are long and putting them at lowest
priority.  NOTE 1: there is a cost to minimizing response time: the
response time for short jobs is less than the mean response time
of FIFO and the response time for long jobs is greater.  Somebody
has to "pay" to give the short jobs good response time.  If you
judge that the cost to long jobs is too high, FIFO would be a
better choice because it's less discrimatory against long jobs.
NOTE 2: There is a cost of each preemption.  Too many preemptions
can accumulate these costs and cancel the gains in response time.

(1j) When job arrivals are scattered at random over time, the MLQ
is the best way to "learn from experience" which jobs are long
and demote them to the lower priority queues.  New jobs always
start at level 0 and long ones soon migrate to the levels
1,2,3,... .  As noted, this helps give short jobs good response
time at the expense of the response time for long jobs.  In many
time-sharing systems, most jobs are short and interactive, and
this is the best strategy to keep the response times short for
the large majority of users.

(2a) The protocol A is safe because TSL is a hardware instruction
that completes in one memory cycle; if two CPUs try TSL at the
same time, they will be sequenced into two separate memory
cycles.  Therefore only one CPU can observe lock=0.

(2b) Protocol B is unsafe because two CPUs can observe lock=0
before either acts on that by setting lock=1.

(2c) Protocol C is unsafe because two CPUs can observe mutex=0
and then proceed to observe lock=0 at the same time.  The mutex
did not achieve mutual exclusion.

(2d) Clock interruptions do not affect safety and liveness.
The interruption cannot occur in the middle of a TSL, but only at
the end of a memory cycle.  An interruption in a critical section
can cause another process to spin-wait, but it cannot get into
the critical section until the process therein is resumed and
exits.

(2e) Other interruptions won't affect safety either (same reason)
but they could affect liveness -- e.g., an error occurs in a
critical section and the process is aborted by the OS after the
ensuing interrupt.

(2f) Turning off all interrupts does not affect safety but may
affect liveness -- e.g., there would be no way to respond to
an error occurring in a critical section, so hardware could
hang up.

(3a) A critical section is a segment of code that performs
an operation on a shared resource.  There are two shared
resources: the work queue and the disk.  The segment "insert task into
work queue" is a critical section because there would otherwise
be a conflict between two user processes making a disk request at
the same time.  The segment "remove task from work queue" is also a
critical section because it should not conflict with the user
processes inserting requests.  These two sections can be
protected by surrounding them with the pattern "wait(mutex), CS,
signal(mutex)".  The segment "STARTIO, wait(DiskDaemon)" is also
a critical section but does not need its own protective semaphore
because the DiskDaemon process serves only one request at a
time.

(3c) The semaphores shown explicitly in the protocol do not make
a deadlock.  To show this, you need to examine each wait
operation and show that there is always a corresponding signal.
For example, the wait(DiskDaemon) always gets a signal because
the disk will interrupt and cause the IH to send the signal.
You also need to check for hidden deadlocks.  For example, the
memory space allocated to the work queue can get used up and a
process trying to insert a request is blocked; however, this is
not a deadlock because the DiskDaemon will eventually remove
a task from queue.

(3d) To make DiskDaemon into a driver, you can simply call it
from the user process P.  P does not need to put anything in a
work queue; it simply calls DiskDaemon and waits for the return.
However, the entry to DiskDaemon procedure needs to be protected
by a semaphore, whose queue will stack up processes seeking
access to the disk and cause them to be served one at a time.  At
start of DiskDaemon there is a wait(mutex) and at the end a
signal(mutex).  In this case, the disk driver cannot inspect the
wait queue (it's hidden in the semaphore) and thus cannot do
optimizations like the one considered next.

(3f) SSTF scheduling is handled very simply.  Just before
the "remove item from work queue" in DiskDaemon, read the
current disk position.  Implement remove to search the queue
looking for the request closest to that position.