Software Systems
Spring 2008

For today, you should have:

1) had a good break!


Outline:

1) the Internet, bottom up.

2) heap implementation (notes14)

3) lock implementation

4) Homework 5 warmup


For next time you should:

1) prepare a project progress report (see the handout)

2) read the first half of Chapter 18 of the Cow book

3) start Homework 5 (due Monday 7 April)

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


4) Read Tanenbaum pages 379-399.  Might seem like a lot, but
   much of it is familiar.


Lock implementation
-------------------

We have been taking for granted that we can implement a mutex,
but we haven't talked about how.

It is possible to do in software; Tanenbaum presents several
algorithms in Section 2.3.3

1) disable interrupts

   con: vulnerable to programmer error

2) simple lock variable
   
   con: pure software version doesn't work

3) strict alternation

void enter_region(int self, int other) {
    while (turn != self);  // loop
}

void leave_region(int self, int other) {
    turn = other;
}

   con: requires strict alternation


4) Peterson's algorithm

void enter_region(int self, int other) {
    interested[self] = TRUE;
    turn = self;
    while (turn == self && interested[other]);  // loop
}

void leave_region(int self, int other) {
    interested[self] = FALSE;
}

    con: hard to generalize to n>2

5) a little help from the hardware

One version is called BTS (bit test and set) in
some instruction sets and TSL (test and set lock) in others.

How does it work?  It performs two operations atomically:

1) read the value of the mutex to a register

2) write a 1 to the same mutex

Initially, the value of the mutex is 0, indicating that the
lock is open or available.

If two threads run TSL concurrently, only one of them will read
0 before the other writes 1.

So how do you unlock the lock?


Homework 5 warmup
-----------------

Follow the instructions in the first section.

Read Experiment 1 and let's talk about how to measure the rate
of sync errors.