Software Systems
Spring 2008

For today you should have

1) read the next section of the LBoS


Today:

1) Queueing theory

2) Project shopping

3) the Thrasher!!!


For Monday you should:

1) read Chapter 13 of the Cow book

2) write the replace function as described on the exam

3) write a project proposal

4) read http://en.wikipedia.org/wiki/Queueing_theory

   and  http://wb/ss/handouts/taylor84queueing.pdf


Queueing Theory
---------------

We have talked about analysis a few times, but haven't seen many
examples.

Three step process:

1) abstraction: building a mathematical model of the system of
   interest

2) derivation: proving something about the model

3) interpretation: applying the result to the original system


Systems of interest: queueing systems.  Examples?

Abstraction:   

queue = arrival process + discipline + server(s) + service process

"arrival process" =  statistical model of a sequence of arrivals

discipline = the rules for choosing which element from the queue
	     moves into service when a server is idle

"service process" =  statistical model of service times



The "Poisson arrival process" is characterized by

1) equal chance of an arrival during any infinitesimal interval

2) exponential distribution of interarrival times

3) number of arrivals in an interval is distributed Poisson

4) can be described with one parameter, the arrival rate, lambda,
   which does not vary in time.

5) the expected time between arrivals is 1/lambda

6) the time until the next arrival does not depend on history,
   so this process is called "memoryless"

Property 6 turns out to be enormously useful for analysis.

(See also http://en.wikipedia.org/wiki/Poisson_process)


How general is this queueing model?

How easy is it to generalize?

Are there queueing systems or features we can't describe?

What kind of questions can we use it to answer?



The Thrasher
------------

Open a window and run 'top'.

By default it shows the processes that are using the most CPU.

Press Capital-M to sort the list by memory use.

Watch the output for a while, until you understand what it is.

Notice the Mem: and Swap: lines in particular.

In another window, download and compile thrasher.c

wget http://wb/ss/code/thrasher.c
gcc -o thrasher thrasher.c

Now run it, and keep an eye on top!