Software Systems
Spring 2005

For today, you should have:

1) Prepared for the exam.

2) read Tanenbaum pages 132 to 142, and answered the reading questions.

Outline:

1) Homework 2 comments

2) Tanenbaum reading

3) Intro to CPU scheduling

4) Exam 1 

For next time you should:

1) read Tanenbaum pages 142--151

   (no reading questions this time)

2) start Homework 3, including the reading from The Cow Book
   and Stevens.


Homework 2
----------

Homeworks were pretty good, despite my panic in class!

One warning -- be careful about "confirming" what you
think you know, and waving your hands at anomalies.

Sometimes you have to give a range of possible values
rather than one value you are sure of.

Assignments for Homework 3:

 jonathan.pollack        jesus.fernandez
 alexander.davis         sarah.leavitt
 matthew.colyer		 douglas.ellwanger
 william.clayton	 steven.shannon
 sharon.talbot		 nicholas.zola
 grant.hutchins		 jonathan.tse
 kathleen.king		 aleksander.lorenc
 christopher.stone       kathryn.rivard
 kevin.tostado		 brendan.doms
 anthony.roldan


Scheduling
----------

Processes arrive in the ready state from three sources

1) new submissions, whose arrival times are unpredictable

2) a running process that has been interrupted

3) a blocked process that has been serviced

In the latter two cases, we have some historical information
about the process.

In the first case we _might_ have some information about the
program.


The CPU scheduler makes decisions at the following times

1) whenever an interrupt occurs (including timer expirations),
   we have to decide which process to run next (possibly
   including the current one)

2) whenever a process arrives in the ready state, we might
   choose to preempt the running procees

3) when the running process terminates

4) when the running process blocks   


Other schedulers are also involved and affect the overall
performance of the system.  For example, the disk scheduler
controls the order in which disk requests are handled.


Goals
-----

What would we like the scheduler to do?

1) minimize the average turnaround time for all processes

   (turnaround time = wall clock time from beginning to completion)

2) satisfy real-time constraints, like requirements for
   interactive behavior

3) maintain high utilization of the CPU and the other hardware
   by overlapping the CPU of one process with the I/O of
   another

   (this last is more like a heuristic than a goal -- we have
   a vague notion that doing this is generally a good idea, 
   although it is not necessarily something users care about)

4) behave predictably and fairly

   predictability is good for programmers who need to have
   a model of program behavior

   fairness is hard to define, but one aspect of it is that
   every process should have _some_ access to the CPU; none
   should "starve"

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

FIFO:  first in first out

       processes are moved from ready into running in the
       order they arrived, and they run until they complete
       or block

       pro: simple, and meets some definition of fairness

       con: bad average turnaround when short waits for long

	    bad utilization when I/O bound wait for CPU bound

            no priority mechanism: hard to meet real-time constraints

       example: a 1 ms process and a 10 ms process






SJF:   shortest (time to completion or blocking) first

       this has some intuitive appeal, if you think about
       relative costs:

       a 1 ms delay isn't bad for a 30 ms process, but it is
       catastrophic for a 0.1 ms process

       SJF meets a different definition of fairness

       pro: provably optimal (minimal) average turnaround time
            for a set of processes all available at t0

       con: we generally don't know the duration of each process's
            next CPU burst, and also the model assumed in the 
	    proof does not consider the dependency of successive
	    bursts