Pre-lab 5 – CSCI 315 Operating Systems Design

Thread Synchronization

Goals

Learn to work with Unix and Pthread synchronization mechanisms. The Pthread library offers the pthread_mutex_t data type, which is much like a binary semaphore and therefore somewhat of limited utility in the solution of synchronization problems. Fortunately, POSIX gives you the more general-purpose semaphore in the sem_t data data type. In this lab, you will learn to work with these two mechanisms for thread synchronization as you implement a solution to the bounded-buffer problem.

Credits

This lab was developed by Prof. L. Felipe Perrone. Permission to reuse this material in parts or in its entirety is granted provided that this credits note is not removed. Additional students files associated with this lab, as well as any existing solutions can be provided upon request by e-mail to: perrone[at]bucknell[dot]edu

Set Up

In your git repo, create a working directory for this lab:

~/csci315/Labs/Lab5/

Copy the following directory recursively to your git repository; this will be your working directory for this lab:

~cs315/Labs/Lab5/

If you’re working on becoming a Unix hotshot, you should copy these files using only shell commands – for instance, there’s a way to make a copy of an entire directory subtree to another location in the file system. (Hint: look at the cp command and the -R flag.) This will create a directory structure in which you will develop your work. This directory structure has all header files in an include/ directory and all C source files in an src/ directory. You are also being given a Makefile to build this week’s programs which will make gcc put object files in an obj/ directory and executables in a bin/ directory. You might be puzzled by the existence of a file called Doxyfile in this bundle; this is a a configuration file that guides a program called Doxygen, which extracts documentation comments from your code and builds web pages with them. What Doxygen does is similar to javadoc.

Now, in your top level directory for Lab5, create a file called pre-lab.txt.

Problem 1 [20 points]

Review your knowledge of data structures and algorithms to remember what are:

an abstract-data type (ADT)
a circular list

You will use the C programming language to create two files called circular-list.h and circular-list.c, the first is a header file where you will list function prototypes of an ADT that other programs will use, the second is the corresponding implementation of the ADT’s functionality. When you did the recursive copy of files from the ~cs315 account, you got skeletons of these files. Actually, the header file should be in shape for you to use directly; the implementation file is where you will do most of your work.

The code in circular-list.h makes use of the C preprocessor’s conditional compilation functionality to avoid the multiple definition of symbols. The #ifndef, #define, #endif are directives laid out in a common pattern that is worth learning for future use. We will talk more about this in lab; for now, you can just use the file as given.

#ifndef _CIRCULAR_LIST_H_
#define _CIRCULAR_LIST_H_

typedef double item;

/** Circular list ADT. This circular list is implemented as a
 * bounded buffer for use in multi-threaded applications.
 */
struct circular_list {
  int start; /// index of the first occupied position in buffer
  int end; /// index of the last occupied position in buffer
  int elems; /// number of elements currently held in buffer
  int size; /// capacity of the buffer
  item *buffer; /// array of buffer items
}; 

...
#endif

In circular-list.c, flesh out the implementation of the functions for insertion and removal in the ADT. Create program src/adt-test.c, where you will write tests to call all the three functions in the ADT. The goal of this program is to exercise your implementation so that you can discover any bugs and, subsequently, correct them. Modify the Makefile given to you so that it compiles src/adt-test.c and places the executable in directory bin/.

When you are done with this, you need to:

cd ~/csci315/Labs/Lab5
git add include
git add src
git add Makefile
git commit -m “Pre-lab 5.1 completed”
git push

Problem 2 [10 points]

In this lab, you will use two different types of synchronization mechanisms: Pthreads mutex locks and POSIX unnamed semaphores. Use your best resources to investigate how to work with both these mechanisms. You might want to refer to the manual pages of the following library calls:

pthread_mutex_init
pthread_mutex_lock
pthread_mutex_unlock
sem_init(3)
sem_wait(3)
sem_post(3)

Write the answers to the following questions in your pre-lab.txt file.

(1) Describe succinctly the difference between mutex and semaphore.

(2) Write a couple of sentences to describe each of the six calls listed above.