Lab 5

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


The Bounded-Buffer Problem

Assume that you have a circular-list (a.k.a. circular-queue) with n buffers, each capable of holding a single value of data type double. If this list is to be shared by multiple threads, you need to be careful with how you implement functionality to remove and to return a buffer to the data structure. By virtue of their scheduling, threads might interrupt each other in the middle of one of these operations leaving the data structure in an inconsistent state.

Your textbook, Operating Systems Concepts 9th Ed., by Silberschatz, Galvin, and Gagne, discusses the bounded-buffer problem in the context of the classical synchronization problem of producers and consumers. The solution to the problem is presented in structures that delineate the code for the two types of process as shows below.

Producer process

Consumer process

Looking at the structure of code given above, you will realize that having the producers and the consumer processes deal directly with synchronization is not ideal. Primarily, there is an issue of applying the concept of abstraction: the code would be substantially easier to manage if you had an ADT for the circular-list. The work you did for the pre-lab implements the following application programming interface (API):

Now that you have a single-thread implementation for these functions, you can work to build synchronization into them. Once you have that, the producer and consumer can safely call circular_list_insert and circular_list_remove in a multi-threaded context because the synchronized ADT takes proper care of things. By now, you must have completed the implementation of the ADT and of a program that exercises that implementation (which we called adt-test.c in the pre-lab). If you haven’t fully tested and debugged your circular list, do not move on to the remainder of this lab.

Problem

  1. Once your ADT works well for a single-threaded program, spend some time identifying which synchronization mechanisms you can hide behind the API of your circular list. Your goal is to modify the ADT so that it works safely in a multi-threaded program. Your textbook gives you a nearly complete solution to implement (SGG, Chapter 5, Project 3).
  1. Next, work in the skeleton given to you in file prodcons.c to flesh out the functions that model producer and consumer threads. Work with the code to verify that the numbers being generated to pass into usleep do look random – you will have to restructure calls to rand_r so that you can print the values to standard out for inspection. [10 points]
  1. The skeleton code you were given makes calls to rand_r(3) to generate random times for threads to sleep. Note that rand_r is the thread safe version of rand – you should be curious why a random number generator needs a thread safe function. Create a file called answers.txt in which you explain why rand_r is thread safe.   [10 points]
  1. At this point, you should be ready to go back to your circular_list_insert and circular_list_remove functions and build the required synchronization into them. When you modify your circular list ADT to work in a multithreaded context, what you have is almost a special purpose monitor. Almost.

    The solution in the textbook uses counting semaphores to represent the number of slots that are empty or full and a binary semaphore to provide mutually exclusive access to fields in struct circular_list, which are accessed in insertions and removals.

    Note that in order to receive full credit in this problem, your solution must use mutex for any locks and semaphore for any counting semaphores. Read the solution outlined in the textbook and think carefully so that you can identify when each type of synchronization mechanism is needed.  [30 points]

  1. Finally, flesh out the main() function in prodcons.c to bring everything together. Your main() will read three command line parameters, all integers, provided as in the example below. If the user tries to invoke your program without these three parameters, your program should: (a) display a help message indicating the correct usage (hint: use the structure in the example below) and (b) exit with (-1) termination status[20 points]

prodcons [num_prod] [num_cons] [sleep_time]
where:

  • [num_prod] is the number of producer threads
  • [num_cons] is the number of consumer threads
  • [sleep_time] is the number of seconds to sleep before the process terminates

It should go with saying that you should experiment with your code extensively to convince yourself that there are no obvious bugs, that your implementation works as expected.

IMPORTANT: In order to shake this program around to expose bugs, you will need to ensure that every producer thread has a different seed for random number generation. Think about how you can pass into each thread an integer value and use that value to seed the thread’s random number generator.

When you are done with this, you need to:

  • cd ~/csci315/Labs/Lab5
  • make clean
  • git add include
  • git add src
  • git add Makefile
  • git commit -m “Lab 5 completed”
  • git push

 

Print Friendly