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 10th Ed., by Silberschatz, Galvin, and Gagne, discusses the bounded-buffer problem in the context of the classical synchronization problem of producers and consumers (Section 7.1). The solution to the problem is presented in structures that delineate the code for the two types of process as shows below.

Producer process

do {
  ...
  // produce an item i
  ...
  wait(empty);
  wait(mutex);
  // add item i to buffer
  signal(mutex);
  signal(full);
} while (TRUE);

Consumer process

do {
  ...
  // consume an item i
  ...
  wait(full);
  wait(mutex);
  // remove item i from buffer
  signal(mutex);
  signal(empty);
} while (TRUE);

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):

/**
 * Create a circular list with a pre-defined buffer size.
 * @param l pointer to a circular list ADT
 * @param size number of items to allocate in circular list
 * @return 0 if successful, -1 if any error condition is found
 */
int circular_list_create(struct circular_list *l, int size);

/**
 * Insert item into the circular list.
 * @param l pointer to a circular list ADT
 * @param i item to copy into a position of the circular list
 * @return 0 if successful, -1 if any error condition is found
 */
int circular_list_insert(struct circular_list *l, item i);

/**
 * Remove item from the circular list.
 * @param l pointer to a circular list ADT
 * @param i pointer to an item onto which the removed item is copied
 * @return 0 if successful, -1 if any error condition is found
 */
int circular_list_remove(struct circular_list *l, item *i);

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.

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 (9th edition SGG, Chapter 5, Project 3, which is reproduced at the bottom of this lab).

Problem

  1. 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. Note that the given code to compute the amount of time to sleep is incorrect, you must fix the potential problems. Read the code segment for additional information.  Please be sure to not delete the printf statements that you will find in the skeleton code – they are used for evaluating your solution. [10 points]
  2. 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]
  3. 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]
  4. 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.

The following notes may help you debug your program and verify if your program works properly.

  • While the completed program requires you run an infinite loop, consider a finite loop when developing the program, e.g., while (n < 100) instead of while(1).
  • It would help if you keep and print a unique ID for each thread of both consumers and producers so that you can see exactly which thread produced or consumed which item.
  • You may consider to use the “pipe” feature of Linux command line to extract relevant information from the output. See the illustration below. Each of the following is a command, with # representing a comment that you shouldn’t type.
    • ./bin/prodcons 3 4 1000 > output.txt # save the program output to a file named ‘output.txt’
    • cat output.txt | grep CONSU > consumed-items.txt; cat output.txt | grep PROD > produced-items.txt # two commands extract info about CONSUMER and PRODUCER
  • Both text files “consumed-items.txt” and “produced-items.txt” contain the lines such as “CONSUMER (4) consumed 0.045678” or “PRODUCER (1) produced 0.045678”. Now you can use the Linux command “colrm” to remove the preceeding columns until the item such as “0.045678.” The two most important parameters for “colrm” is the starting column and ending column. So for this example, the “CONS…” has 22 columns (positions) before the item 0.04567, so the Linux command

    colrm 1 22 < consumed-items.txt > items-consumed.txt

    will produce list of items consumed in the file item-consumed.txt. You can do the same to generate the list of items produced from the file produced-items.txt.

    colrm 1 22 < produced-items.txt > items-produced.txt
  • If your program works correctly, the order and the number of the items produced and consumed should be identical. The Linux command

    diff items-produced.txt items-consumed.txt

    should result in nothing at the terminal. Occasionally the producers have generated more items than the consumers have consumed at the time of program completion, so there may be extra items left in the buffer. If this is the case, you should see extra items at the end of the produced list.

When you are done with this, you need to:

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

Grading Rubric

Problem 1 [10 points total]

  • [10 points] Correctly restructure the call to rand_r so the random numbers can be correctly used in the usleep() call.

Problem 2 [10 points total]

  • [10 points] Explain why rand_r is thread-safe.

Problem 3 [30 points total]

  • [10 points] Put and initialize synchronization calls properly in the function circular_list_create();
  • [10 points] Put and use synchronization calls properly in the function circular_list_insert();
  • [10 points] Put and use synchronization calls properly in the function circular_list_remove().

Problem 4 [20 points total]

  • [3 points] Read and use commend line arguments correctly;
  • [5 points] Define, initialize, and pass the parameters for the threads correctly;
  • [12 points] Create the consumer and producer threads based on the commend line arguments correctly so that the program works correctly.

Reproduced from 9th edition SGG, chapter 5, Project 3 for your reference.

Citations are to content in SGG 5, some of which is translated to 10th in brackets [].

Project 3 —Producer – Consumer Problem
In Section 5.7.1 [7.1.1], we presented a semaphore-based solution to the producer– consumer problem using a bounded buffer. In this project, you will design a programming solution to the bounded-buffer problem using the producer and consumer processes shown in Figures 5.9 [7.1] and 5.10 [7.2]. The solution presented in Section 5.7.1 [7.1.1] uses three semaphores: empty and full, which count the number of empty and full slots in the buffer, and mutex , which is a binary (or mutual-exclusion) semaphore that protects the actual insertion or removal of items in the buffer. For this project, you will use standard counting semaphores for empty and full and a mutex lock, rather than a binary semaphore, to represent mutex . The producer and consumer—running as separate threads—will move items to and from a buffer that is synchronized with the empty , full , and mutex structures. You can solve this problem using either Pthreads or the Windows API.

#include "buffer.h"
/* the buffer */
buffer_item buffer[BUFFER_SIZE];
int insert_item(buffer_item item) {
/* insert item into buffer
return 0 if successful, otherwise
return -1 indicating an error condition */
}
int remove_item(buffer_item *item) {
/* remove an object from
placing it in item
return 0 if successful,
return -1 otherwise indicating an error condition */
}

Figure 5.24 Outline of buffer operations.

The Buffer
Internally, the buffer will consist of a fixed-size array of type buffer item
(which will be defined using a typedef ). The array of buffer item objects
will be manipulated as a circular queue. The definition of buffer item , along
with the size of the buffer, can be stored in a header file such as the following:

/* buffer.h */
typedef int buffer_item;
#define BUFFER_SIZE 5

The buffer will be manipulated with two functions, insert item() and
remove item() , which are called by the producer and consumer threads,
respectively. A skeleton outlining these functions appears in Figure 5.24.

The insert item() and remove item() functions will synchronize the
producer and consumer using the algorithms outlined in Figures 5.9 [7.1] and 5.10 [7.2]. The buffer will also require an initialization function that initializes the mutual-exclusion object mutex along with the empty and full semaphores.

The main() function will initialize the buffer and create the separate
producer and consumer threads. Once it has created the producer and
consumer threads, the main() function will sleep for a period of time and,
upon awakening, will terminate the application. The main() function will be
passed three parameters on the command line:
1. How long to sleep before terminating
2. The number of producer threads
3. The number of consumer threads

#include "buffer.h"
int main(int argc, char *argv[]) {
1. Get command line arguments argv[1],argv[2],argv[3] */
2. Initialize buffer */
3. Create producer thread(s) */
4. Create consumer thread(s) */
5. Sleep */
6. Exit */
}

Figure 5.25 Outline of skeleton program.
A skeleton for this function appears in Figure 5.25.

The Producer and Consumer Threads
The producer thread will alternate between sleeping for a random period of
time and inserting a random integer into the buffer. Random numbers will
be produced using the rand() function, which produces random integers
between 0 and RAND MAX . The consumer will also sleep for a random period of time and, upon awakening, will attempt to remove an item from the buffer. An outline of the producer and consumer threads appears in Figure 5.26.

As noted earlier, you can solve this problem using either Pthreads or the
Windows API . In the following sections, we supply more information on each of these choices.

Pthreads Thread Creation and Synchronization
Creating threads using the Pthreads API is discussed in Section 4.4.1. Coverage of mutex locks and semaphores using Pthreads is provided in Section 5.9.4 [7.3.2]. Refer to those sections for specific instructions on Pthreads thread creation and synchronization.

Print Friendly, PDF & Email

Want to learn more about Bucknell?

Request information