cs341 Lecture Notes
Spring 2002
Week 7, Thursday

For today you should have

1) solved the producer-consumer semaphore problem.

2) read the cow book and the Anderson handout.

3) Started hw5

For next time you should:

1) Write answers to Quiz 4b and read Nutt page 370 and the
   handout from Silberschatz and Galvin.

2) Read the next section of the semaphores book and think about
   the puzzle on page 52 before you read page 53.

   Attempt the puzzle on page 53.  I will give you a hint on
   Monday (after break) and ask for a solution for Thursday.

3) Continue work on hw5.  You should do Experiment 1 and maybe
   2 before Monday so that we can discuss preliminary results.

4) Prepare for a quiz on page replacement algorithms.


Topics for today:

1) page replacement strategies (notes11.txt)

2) producer/consumer solution

3) a little bit of C


Producer-consumer solution
--------------------------

Basic mechanism is simple:

use length semaphore to count the
number of items available for the consumer, 
or the number of consumers in queue (if negative).

One small wrinkle: consider "event" a local variable
(local to a thread, that is).

One small performance issue: generally, don't signal
until the signalee will be able to proceed.

In this case, it's best to release the mutex before
signalling the consumer.

On the other hand, correctness is more important than
performance (up to a point).

Next puzzle: what if the size of the buffer is finite?

In that case, if the buffer is full, the producer has
to queue.

Remember: you're not allowed to read the current value of
a semaphore.

  (Why not?)



Objects in C
------------

C is not an object-oriented language, but it is still possible
to write in a somewhat object-oriented style.

Here's how I implemented a "Lock" object in C:

The public interface goes in the header file lock.h:

#include <pthread.h>

typedef struct {
  int value;
} Lock;

Lock *make_lock ();
void acquire (Lock *lock);
void release (Lock *lock);


1) sometimes header files include other header files

2) the typedef creates a new type called Lock that is
   a structure with one instance variables

3) the other lines declare the public methods in lock.c


The implementation of the methods is in lock.c

#include <stdio.h>
#include "lock.h"

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

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

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

Notice that lock.c includes the header file.

#include <stdio.h>
#include "lock.h"

<> means "look for header files in the usual places"
"" means "look for header files in the current directory"


make_lock
---------

This is the constructor.

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

1) allocate space (ugly idiom)

2) initialize instance variables

3) return a pointer to the new object


acquire and release
-------------------

always pass objects by pointer.

always use the -> operator to access instance variables.


Suggestion for pthread_mutex implementation
-------------------------------------------

typedef struct {
  pthread_mutex_t mutex[1];
} Lock;

The instance variable is an array of pthread_mutex objects.

It contains one element.

Now the expression

    lock->mutex

has type "pointer to pthread_mutex_t"

which can be used as a parameter to pthread procedures:

    pthread_mutex_init (lock->mutex, NULL);
    pthread_mutex_lock (lock->mutex);
    pthread_mutex_unlock (lock->mutex);


Libraries
---------

When you compile a program (actually, when you link it)
you have to specify what libraries are needed with the
-l option, usually the last thing on the line:

   gcc -o cpuloop cpuloop.c -lm             (math library)

   gcc mutex.c -o mutex -lpthread           (pthread library)


Makefiles
---------

Handy way to store compilation commands (and much much more):

badlock: lock.c main.c lock.h
        gcc -g main.c lock.c -o badlock

Badlock depends on (lock.c main.c lock.h)

If one of those is more recent than badlock, execute the
command.

$ make badlock
gcc -g main.c lock.c -o badlock

$ make badlock
make: `badlock' is up to date.


How did I implement lock.x86.s?
-------------------------------

BTS = bit test and set

test and set atomically (reads a bit and sets it to one)

acquire
   while (bts(location) == 1) ;

If the lock is locked, the value is 1
   BTS reads 1 and writes 1
       loop continues, lock stays locked

If the lock us unlocked, the value is 0
   BTS reads 0 and writes 1
       loop breaks, lock gets locked