CS 336: Project #5

Project 5: Dynamic Assignment of Work

On NSCC, create a proj05 directory.

In this project, you will be exploring the wonders of dynamic work assignment. The first programming assignment requires mutex locks only. The second programming assignment requires mutex locks and condition variables.

  1. Producer - Consumer

    In class, we wrote a program that uses condition variables to produce and consume work. There are many opportunities for deadlock if it isn't implemented properly. Instead of writing code, this part of the assignment asks you to explain why our code must be written the way it is. You may use any on-line resource you can find to answer these questions. Just make sure you understand the answer. And please don't cut and paste!

    1. Read up on condition variables. Why does cond_wait require both a condition variable and a mutex? Describe a scenario in which the consumer could end up waiting forever if it released the lock before executing the wait.
    2. Why does the cond_wait statement need to be in a while loop?
    3. Which variables in our code are protected by the mutex?
    4. What happens if you move the pthread_mutex_lock call from above the while loop to just below it (in either producer or consumer)? Why (hint: what happens when a thread calls lock twice in a row without unlocking?)
    5. sleep is a proxy for actually doing something. Why is the call to sleep after the call to pthread_mutex_unlock?
  2. Searching for Prime Numbers

    Consider a program that will count all the prime numbers between 0 and N. You can do so sequentially by looping from 0 to N, and checking to see if the number is prime. This is what I do in prime_search_seq.c

    Your job is to write two parallel versions, each of which assigns subsequences of numbers to a particular thread.

    1. Write a static version, in which you predetermine which subsequences are assigned. The simplest example of this is assigning i*(N/NUM_THREADS) to (i+1)*N*/NUM_THREADS-1 to thread i.
    2. Write a dynamic version. This will a assign smaller sequence to each each thread. When a thread has finished with one small sequence, it requests another.

      You should also time the work, from after the array creation to before the print statement. Print out how long it took to run.

      To help you out, here are some hints:

      • Define a macro named WORK_CHUNK with a value of 100.
      • Each thread works on WORK_CHUNK sequential numbers at a time. It does so in a loop, that exits once it is sure there are no WORK_CHUNKS remaining.
      • A global variable keeps track of the starting index of the next WORK_CHUNK that must be done. When a thread is ready to begin a new chunk, it updates the global starting index, and gets going. Note that this global starting index must be protected by a mutex.

Extensions

Invent your own extension. Find some aspect of one this week's work that interests you and expand on it. For example, you could try your best to speed up the prime search. Or get the producers/consumers problem working for multiple producers and consumers and then perform an additional analysis. Under what scenarios is this set-up the most efficient? When would this model perform badly?

Writeup and Handin

To hand in your project, you will gather all of the necessary files into a proj05 directory in your "turnin" directory:

  1. Create a file named README.txt for your project write-up. This week, I want you to collect timing information from all of your runs and then analyze the results. The analysis is a significant part of the project, so don't leave it until the last minute, when you are too tired to think clearly.
    1. Run the prime search program for several values of WORK_CHUNK and examine its effect on performance. What happens when it is too small? What makes it slow? What happens when it is too large? What makes it slow?
    2. Analyze the producer-consumer problem by answering the questions above.
  2. You should hand in all code necessary to run your solutions. Place all necessary .h, .c, and Makefile files in the proj05 directory. Stephanie will probably want to compile and run the code. It should be possible to do so without looking for any more files.

Email Stephanie to let her know your project is ready for grading.