cs341 Lecture Notes
Spring 2002
Week 4, Monday which is Tuesday

For today you should have

1) Solved the next semaphore puzzle.

2) Met with your partner and made a plan for Homework 3.

   Any problems?

3) Read 7.3 and 7.4 and the paper by Waldspurger and Weihl.
   Preparation questions follow.

4) Prepared for a quiz.


For next time you should:

1) solve the last semaphore puzzle before the exam.

2) Work on hw03.

3) reread the lottery scheduling paper after we discuss it

4) Read Sections 8.1 and 8.2 and answer the preparation
   questions below.


Strategies (heuristics)
-----------------------

When is SJF optimal?

1) all jobs arrive at the same time

2) all run times are known

3) average turnaround time is the only metric

If we relax the second assumption, we don't know which is
the shortest job any more.

We can approximate using Round Robin

       usually: almost as good as SJF, and much better than FIFO

       pathology: can be even worse than FIFO (actually pessimal!)

       example: two 10 ms processes, quantum = 1 ms

       pro: generally good when there is large variability in duration

       con: overhead becomes signficant as quantum gets smaller

            pessimal when jobs are the same length


If we relax the first assumption, then jobs can arrive at
any time.

In that case we need a PREEMPTIVE strategy.

Example: 10 ms job arrives at t=0 and starts

	  1 ms job arrives at t=1 and waits 9ms!

Again, if we know the run times, there is an optimal strategy:

       shortest remaining lifetime next.

And again, if we don't know the runtimes, then we have to
approximate them.

Here's where the rocket science comes in.

The distribution of run times is long-tailed, which means
that the expected remaining lifetime _increases_ as the
job runs.

The longer it's been running, the longer we expect it to run!


Multi-level feedback queue:
     
     use past behavior to predict future behavior

     two kinds of learning:

     1) predict the duration of the next burst based on
        past bursts

     2) classify process based on long-term behavior

     Adjust quantum length automatically to reduce overhead
     for long-running computationally-intensive processes
     (but why bother?)

     Tradeoff against the expense of keeping track of
     accounting information.


Non-deterministic scheduling:

     Example: lottery scheduling.

     Problem: for any deterministic system you can contruct
              pathological cases that yield bad performance

     Solution: a little randomness goes a long way

     Con: unpredictable execution model for programmers


Real-time scheduling
--------------------

When processes arrive, we generally need to know

1) their resource requirements

2) their deadlines

3) sometimes a cost function (how bad would it be if
   we missed the deadline)

The goal of the real time scheduler is either

1) find any schedule that misses no deadlines

   (or maybe the best such schedule)

2) if not possible, minimize the total cost of all misses


In the case where there is guaranteed to be a schedule that
misses no deadlines, and the cost of a context switch is zero,
there is a simple algorithm that is guaranteed to find a
successful schedule:

   Work on the Process with the Nearest Deadline First

Sound familiar?

Problem: if the schedule is untenable, this algorithm is
often pessimal.


Reading preparation
-------------------

Section 8.1

What is the fundamental goal of interacting processes?










What are the fundamental problems with interacting processes?









What is a race condition?




What is wrong with the disableInterrupts solution to the
mutex problem?




What is the implementation difficulty of the lock solution
to the mutex problem?



Section 8.2

What problem that we have been working on is Nutt trying to
solve in Section 8.2?