Software Systems
Spring 2005

For today, you should have:

1) Finished your project proposal.
 
2) Continued work on Homework 4.


Outline:

1) Virtual memory.

2) Queueing theory.


For next time you should:

1) Finish Homework 4.

2) Read Tanenbaum pages 234-242, and answer the reading questions below

3) Prepare for a quiz on virtual memory.



Queueing theory
---------------

Concepts and vocabulary:

queue, queueing system

arrival process, interarrival time, service time, wait time

arrival rate, service rate, load, utilization

steady state (see page 342)

The Queueing Formula:  L = lambda W



M/M/1
-----

Exponential distribution with parameter x has mean 1/x.

If the arrival rate is x per unit time, then the average time
between arrivals is 1/x.

Exponential distribution is memoryless: the time until the next
arrival does not depend on how long you have been waiting.

Thus, the state of the system is completely described by the
number of customers in the system!

So we can describe the system with a state-transition diagram:

Which makes it possible to derive the relationships:

L = l / (m-l)

and

W = 1 / (m-l)

Which you are testing in Homework 4.


M/G/1
-----

In an M/G/1 system, we relax the assumption that the distribution
of service times is exponential.

In the homework, we make it Pareto.

What is the coefficient of variation of the Pareto distribution?

Qualitatively, what effect does this have?



Reading questions
-----------------

Tanenbaum pages 232-234

1) What's the difference between global and local page frame
   allocation?







2) What experiment could you run to try to tell whether your
   system uses global or local allocation?






3) What is thrashing?






4) Under what circumstance is thrashing expected to happen?






5) Does a large page size increase or decrease internal fragmentation?






6) Name one drawback of a small page size.






7) On a machine with 64-bit addresses, do you think it will be useful
   to have separate instruction and data address spaces?






8) Why is it easier to share text (program) pages than to share
   data pages?







9) What does the paging daemon do?