Software Systems
Spring 2008

For today, you should have:

1) worked on your project -- progress report due today

2) done the take-home part of the exam

3) optional: Hiltzer's barbershop problem


Outline:

1) exam solutions

2) homework 5 solutions

3) OOP in C


For next time you should:

0) work on your project

1) read the sync in C handout from LBoS and answer the puzzle
   at the end of these notes.

2) read the handout from Raskin, "The Humane Interface"

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

and the Wikipedia pages on Raskin and Archy

http://en.wikipedia.org/wiki/Jef_Raskin
http://en.wikipedia.org/wiki/Archy

and follow the instructions below for installing Archy.


Archy
-----

To install Archy:

1) install pygame by running the following as root

yum install pygame

2) download my slightly fixed up version of Archy

wget http://wb/ss/code/archy-build115.tgz
tar -xzf archy-build115.tgz
cd archy-build115
python archy.py

Follow the instructions you (should) see in the document.

You might want to read

http://rchi.raskincenter.org/index.php?title=Using_Archy

first.

Homework 5 debrief
------------------

I continue to be amazed that my x86 lock works.

In some cases, the pthread implementation was faster than my x86
lock, which makes perfect sense because mine is a spin lock and the
pthread implementation blocks.

In some cases, my x86 implementation was faster, which makes perfect
sense, because mine is lean assembly language code, and the pthread
implementation has more overhead.

Some factors that affect lock performance:

1) spinning versus blocking

2) kernel versus user code

3) contention for the lock

4) single or multiple processors

     multiple processors are good for low contention locks,
     but in high contention, performance might be worse on
     multiple processors because of cache effects.


To go deeper, read http://en.wikipedia.org/wiki/Futex


OOP in C
--------

In OOP it is common to have multiple implementations of an
interface.

1) One file specifies the interface.

2) Any number of clients can be written using only the
   public parts of the interface.

3) Any number of implementations can be written.

When do you specify which impementation you actually want to use?

1) Compile time: in Java, for example, you cannot instantiate an
   object without specifying which implementation you want.

2) Link time: alternatively, we can write client code that is
   completely implementation independent, and provide the
   implementation at link time or run time.

In my solution to Homework 5, I demonstrate a way to do (2) in C.


Step 1
------

First, I put the interface definition in lock.h

typedef struct lock Lock;

Lock *make_lock ();
void lock_acquire (Lock *lock);
void lock_release (Lock *lock);

Notice that the type definition only says that Lock is a structure;
it doesn't say what's in it.

This is an anonymous structure.  The client code is not allowed to
access the elements.


Step 2
------

Then I put an implementation in lock.c:

#include "lock.h"

struct lock {
  int value;    % here is the actual specification of the lock structure
};

Lock *make_lock ()
{
  Lock *lock = (Lock *) malloc (sizeof(Lock));
  lock->value = 0;
  return lock;
}

void lock_acquire (Lock *lock)
{
  while (lock->value == 1);
  lock->value = 1;
}

void lock_release (Lock *lock)
{
  lock->value = 0;
}


Step 3
------

And I can put another implementation in pmutex.c:

#include "lock.h"

struct lock {
  pthread_mutex_t mutex[1];    % a completely different structure
};

Lock *make_lock ()
{
  Lock *lock = (Lock *) malloc (sizeof(Lock));
  pthread_mutex_init (lock->mutex, NULL);
  return lock;
}

void lock_acquire (Lock *lock)
{
  pthread_mutex_lock (lock->mutex);
}

void lock_release (Lock *lock)
{
  pthread_mutex_unlock (lock->mutex);
}

Notice that the structure definition contains an array with
a single pthread_mutex_t in it.

This is a quick and dirty way of allocating space and getting
a pointer to it.


Step 4
------

Then I can write array.c using _only_ the interface:

#include "lock.h"

typedef struct {
  int next_id;
  int array[SIZE];
  Lock *lock;
} Environment;

Environment *make_environment ()
{
  int i;

  Environment *env = (Environment *) malloc (sizeof (Environment));
  if (env == NULL) {
    perror ("malloc failed");
    exit (-1);
  }
  env->next_id = 0;

  for (i=0; i<SIZE; i++) {
    env->array[i] = 0;
  }

  env->lock = make_lock ();
  return env;
}

void loop_and_count (pthread_t self, Environment *env)
{
  int id;

  while (1) {
    lock_acquire (env->lock);
    id = get_next_id (env);
    lock_release (env->lock);

    // printf ("%d got %d\n", self, id);

    if (id >= SIZE) return;
    env->array[id]++;
  }
}


Step 5
------

Then I can specify at link time which implementation I want.
Here's the Makefile:

array1:
	gcc -g array.c lock.c -o array1 -lpthread

array2:
	gcc -g array.c lock.s -o array2 -lpthread

array3:
	gcc -g array.c pmutex.c -o array3 -lpthread

array4:
	gcc -g array.c semlock.c semaphore.c cond.c -o array4 -lpthread


The last one uses 3 files:

cond.c:       a wrapper for pthread_cond_t

semaphore.c:  an implementation of semaphores using pthread condition
	      variables and mutexes

semlock.c:    an adapter that implements the lock.h interface using
              a semaphore.


See the handout from LBoS for details about my implementation of
semaphores.

Puzzle: what are the two problems with this implementation of
semaphores?

void semaphore_wait (Semaphore *semaphore)
{
  acquire (semaphore->lock);
  semaphore->value--;
  if (semaphore->value < 0) {
    cond_wait (semaphore->cond, semaphore->lock);
  }
  release (semaphore->lock);
}

void semaphore_signal (Semaphore *semaphore)
{
  acquire (semaphore->lock);
  semaphore->value++;
  if (semaphore->value <= 0) {
    cond_signal (semaphore->cond);
  }
  release (semaphore->lock);
}


What is a spurious wakeup?  
See http://en.wikipedia.org/wiki/Spurious_wakeup