Software Systems
Spring 2008

For today, you should have:

1) read Chapter 13 of the Cow book

2) written the replace function as described on the exam

3) written a project proposal

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

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


Outline

1) OOP in C

2) Queueing Theory

3) random variates

4) producer-consumer


For next time you should:

1) Do the next semaphore puzzle (readers-writers)

2) Start on Homework 4.  Here are your partners:

jeffrey.dezso     kent.munson
allison.weis      Mary.Germino
Ilari.Shafer      andrew.tsang
Jonathan.Inman    Benjamin.Fisher
James.Switzer     Christina.Nguyen
samuel.freilich   kiuk.gwak

3) Skim Chapters 14 and 15 of the Cow Book.

4) reading questions below

5) prepare for a quiz


Object-oriented programming in C
--------------------------------

Not really an OOP language, but you can write in an OO style.

My solution to problem 12-2 demonstrates:

1) declaring the instance variables

typedef struct {
  int hour, minute, second;
  int day, month, year;
} DateTime;


2) the constructor

DateTime *make_datetime(int hour, int minute, int second)
{
  DateTime *dt = (DateTime *) mymalloc (sizeof(DateTime));

  dt->hour = hour;
  dt->minute = minute;
  dt->second = second;

  dt->day = 14;
  dt->month = 10;
  dt->year = 1066;          // Battle of Hastings 
}

3) a couple of methods

void print_datetime(DateTime *dt)
{
  printf("%0.2d:%0.2d:%0.2d, %d/%d/%d", dt->hour, dt->minute, dt->second,
	 dt->day, dt->month, dt->year);
}

double diff_datetime(DateTime *d1, DateTime *d2)
{
	...
}

4) instantiating a few objects

  DateTime *currenttime = make_datetime(10, 12, 20);
  DateTime *lunchtime = make_datetime(11, 59, 59);

  printf ("The current time is ");
  print_datetime(currenttime);

  printf ("\nLunch time is ");
  print_datetime(lunchtime);

  double minutes = diff_datetime(lunchtime, currenttime);
  printf ("\nThere are %g minutes until lunchtime.\n", minutes);

If you squint at it just right, it looks like Java!

Notice:

1) all instances are instantiated dynamically (using malloc)

2) objects are _always_ manipulated by pointer, so you _always_
   use the -> syntax for accessing instance variables

3) method names include the name of the "class" they operate on

4) "class" names begin with capital letters


The differences between a style and a programming language feature:

1) no syntactic help; in effect, you compile by hand

2) the rules are not enforced by the compiler/run time system


Queueing theory, part two
-------------------------

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
--------------------

Also known as Little's Law

Please read
http://en.wikipedia.org/wiki/Little's_law

L = lambda W

lambda = average arrival rate (customers/time)
L      = average # customers in the system (queue + in service)
W      = average time in the system (waiting + service)

The "proof" in the book is bogus, but here is a way
to convince yourself:

Think of yourself as a customer entering the system.

You wait in queue, then move into the service bay, then
exit.

Let's say your total time in the system is w.

As you leave, how many people, on average, do you expect
to see in the system?


M/M/1
-----

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

Thus, at all times, the probability of an arrival during a
_small_ interval, h, is lambda h.

And the chance of a departure (if there is a customer in service)
is mu h.

Thus, the state of the system is completely described by the
number of customers in the system, X(t)!

So we can:

1) describe the system with a state-transition diagram

2) write a difference equation for the Pr{X(t) = k}

3) write a limit for the time rate of change of Pr{X(t) = k}

4) when the system is in steady state, that time rate of
   change is zero, so

5) that gives us a recurrence relation for Pr{X = k}

6) solve the recurrence relation to get

   Pr{X = k} = (lambda/mu)^k Pr{X = 0}

   which is a geometric series.

7) If lambda < mu, we can normalize this series to get

   Pr{X = 0} = 1 - lambda / mu

   Pr{X = k} = (lambda/mu)^k Pr{X = 0}

   which is an honest-to-goodness probability mass function.

8) Compute the mean of that pmf:

   L = lambda / (mu - lambda)

9) apply Little's Law

   W = 1 / (mu - lambda)


In Homework 4, you are using a simulation to validate these
analytic results.


Homework 4
----------

Generating random numbers.

Most systems provide a random-number generator that generated
integers from 0 to RAND_MAX (inclusive).

To get a uniform number on [0, 1)

double rand_uniform ()
{
  return (double) random() / ((double) RAND_MAX + 1);
}

To generate exponential numbers, we use the inverse-CDF
method.

double rand_exp (double param)
{
  return -log(1.0 - rand_uniform()) / param;
}

Generating normal values is non-trivial.  The algorithm in
random.c is from Numerical Recipes in C.

Read the explanation at http://www.nrbook.com/a/bookcpdf/c7-2.pdf

Exercise: how do you generate a Pareto variate?

The cdf is at http://en.wikipedia.org/wiki/Pareto_distribution


How do you test empirical data for family membership?


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

Standish pages 224 -- 237.

http://wb/ss/handouts/standish98memory.pdf

1) In general (not just in Java) what kind of variables get
   allocated in the static segment, the stack, and the heap?






The mark and gather algorithm on page 227 is one of the
two basic garbage collection algorithms.  The other, reference
counting, is coming up on page 235.

The example on page 228 is more specific than we care about.
Don't spend too much time on it.

2) On page 230, you might wonder why the available blocks are
   kept in a two-way linked list, but at this point you probably
   don't know.  At the end of the chapter, come back and write
   the reason below...







3) What is the primary benefit of the First-Fit strategy?






4) What is the primary benefit of the Best-Fit strategy?





5) What is the difference between coalescing and compacting?





6) Why is compacting hard to implement?





7) What is double-dereferencing?





8) What is the primary advantage of reference counting over
   mark and collect?





9) What is the primary disadvantage?






10) Please answer question 2 in section 7.6 on page 237.