Software Systems
Spring 2005

Homework 5

The purpose of this assignment is to experiment with three implementations of locks, and to measure the frequency of errors caused by incorrect synchronization primitives.

Break the lock

Pick up the code by running 

wget http://wb/ss/code/lock.tgz
tar -xzf lock.tgz
cd lock

The file lock.c contains an incorrect implementation of a lock written in C. The file lock.x86.s contains a correct (I think) implementation of a lock written in Intel x86 assembler code. I will explain the latter in class. The Makefile shows how to make programs called goodlock and badlock based on the two versions of a lock. Compile and run both programs.

The file example.c contains the skeleton of a multi-threaded program with shared state. The shared state is encapsulated in an object called Environment. Compile and run example.

Experiment 1

  1. Starting with a copy of example.c, write a program that uses at least two threads and that accesses a shared variable concurrently. Make the shared variable a counter that hands out unique identifiers in sequence. Create a big array and count the number of times each identifier gets handed out. If there are no synchronization errors, every identifier should get handed out exactly once, so each array element should be 1. Run the program and see how frequently synchronization errors occur.

  2. Now use the broken lock implementation to enforce exclusive access to the shared variable. Test whether your program is in fact achieving mutual exclusion. What is the frequency of synchronization errors now?

  3. Finally, replace the broken lock implementation with the `correct' one. What is the frequency of synchronization errors now? Can we prove that the `correct' implementation is correct?

Experiment 2

  1. Read the handout from Programming with POSIX threads that describes pthread mutexes. Print the documentation of the relevant library functions.

  2. Make a copy of lock.c and call it mutex.c. Change the implementation of make_lock, acquire and release so that they use pthread mutexes. This should be a trivial implementation, since mutexes are the same thing as locks. All you are doing is creating a veneer that changes the interface.

  3. What is the frequency of synchronization errors using the pthread lock implementation?

  4. Time your program to compare the efficiency of my lock implementation with pthread mutexes. Which is faster? Where is the extra time spent, in user code, system code, or operating system overhead?