Working with Threads
As noted earlier, you will need to read and follow Coding Standards for Programming with Threads, by Mike
Dahlin. If you’re shaky on monitors (we covered them in class, but you might want reinforcement), see this
chapter from OSTEP.
To simplify your task, we supply a simple thread package (written by Mike Dahlin) on top of the standard
POSIX thread library (which is known as pthreads). The idea is to shield you from irrelevant detail. This way,
you use the standard package but you also focus on the project at hand. However, you are not required to use
the wrapper; you may instead use pthreads if you so choose. The code for the simple thread package (which
we will refer to hereafter as sthreads) we provide is in sthread.cpp and sthread.h.
The package provides threads (sthread_ts), mutex locks (smutex_ts), and condition variables (scond_ts) as
well as some other utility functions that you may need. We suggest that you read over these functions to see
how they are used. It may be helpful to write a couple of example programs using sthreads before starting this
project. For more information, see the man pages for the pthreads library functions used in the sthread.cpp
code.
You should keep the following in mind as you code these labs:
If you find that the problem is underspecified, please make reasonable assumptions and document them
in the documentation file.
You are required to adhere to the multi-threaded coding standards/rules discussed in class and above.
Code that fails to conform to these rules is incorrect and will receive little credit when this lab is
graded.
Code will be evaluated based on its correctness, clarity, and elegance. Strive for simplicity. Think
before you code.
One of the most common mistakes we see on projects year after year is using sthread_sleep when
you should be using scond_wait. The standards document above discusses this issue in more detail.
This year, we don’t want anyone to make this mistake, so be warned: seeing an sthread_sleep in your
code in the wrong place is an easy way for a TA to conclude that you don’t know how to write
multithreaded programs, and the TAs will be instructed to deduct a large number of points from any
project that uses sleep when it should wait on a condition variable. If you find yourself writing sleep,
treat that as a red flag that you might be making a mistake. If you don’t know when to use one and
when to use the other, come to office hours, but don’t start writing code!
Before writing any code, think of different types of simple generic data structures (e.g., bounded buffer,
readers/writers, …). These particular data structures may (or may not) be directly useful for this project,
but this flavor of data structure will be extremely useful.
Part A: Task Queue and Coarse-Grained Store Synchronization
For our model, we will simulate a fixed number of customers and suppliers. For each customer and each
supplier, there will be a unique thread representing that customer or supplier. We will often refer to these
threads throughout this document as worker threads. These worker threads will get jobs to work on from a
task queue, which you will implement. There will be one queue for all customer threads and one queue for all
supplier threads. This task queue must allow for multiple worker threads to simultaneously attempt to add or
remove jobs while still maintaining the integrity of the queue’s internal data structures by using locks (i.e.,
your task queue must be thread-safe).
It is a common pattern in multi-threaded programming to have a single (or small number of) task queue(s) for
a large number of threads. A thread-safe task queue makes the job of allocating work to threads (and having
threads allocate work to other threads, should the case arise) easy to do and (relatively) easy to reason about.
Exercise 1. Look through the queue interface in TaskQueue.h and the documentation for its methods in
TaskQueue.cpp. Fill out the rest of the members in class TaskQueue in TaskQueue.h to finish the definition
of your task queue class, then implement the rest of the queue methods in TaskQueue.cpp. You are welcome
to use any standard C++ container to help build the functionality of your queue (such as a std::queue or
std::deque), or you can create your own data structures (like a linked list) and add any needed helper
structures to do the same.
A task in the task queue is represented by a struct Task (also found in TaskQueue.h), which consists of a
pointer to a function and an argument to be passed to that function. When a worker thread removes a task
from the task queue, it should call the function given in the struct Task with the argument given in the
Task.
Run make to make sure your queue code compiles. For now, there’s no executable to run.
A task queue is little good to worker threads if there is no work available to be put on it. We have provided
some code to generate work requests to be put on your task queues in RequestGenerator.h and
RequestGenerator.cpp. Become familiar with this code. Specifically, there are two subclasses of the main
class RequestGenerator that you should know the purpose of: class CustomerRequestGenerator and
class SupplierRequestGenerator. The former CustomerRequestGenerator, as its name would suggest,
generates requests for customer threads to perform (such as buying items). The latter
SupplierRequestGenerator generates requests for supplier threads to perform (such as adding or removing
items from inventory, or putting items on sale). You will use these generator classes to implement task
generator threads, which will produce work for customer and supplier threads.
Before you start implementing any thread functions, however, you should actually have some threads
running. In the main source file for our simulator, estoresim.cpp, is a function called startSimulation.
This function kicks off all threads in the simulator (generators, customers, and suppliers) and then, after
starting all threads, waits for them to finish. When all threads have finished working, the simulation is
complete.
Exercise 2. Read the documentation for, and then implement, the startSimulation function in
estoresim.cpp. Use sthread_create to create threads. The worker thread functions supplierGenerator,
supplier, customerGenerator and customer all reside in estoresim.cpp. Use the provided class
Simulation to keep track of task queues and the number of customers and suppliers. When you have finished
writing your code, run make run-sim to run the simulator. You may want to have the threads produce some
output to make sure that you are starting them correctly.
Don’t worry about the meaning of the fineMode variable in Simulation for now, just make sure it is set to the
value passed in the parameter useFineMode.
You may also find it useful in this exercise, and in others throughout this lab, to call printf in some choice
places (where worker threads start, for instance). The code we provide you doesn’t print anything to the
terminal, and so when you run the simulator with make run-sim, you won’t see any output unless you put the
printfs in yourself.
At the moment, all of the threads you have created start and then immediately stop, as none of their
associated functions are implemented (they just return when called). However, since you have actual threads
running, you can proceed to implement the generator, customer, and supplier thread functions. If you put
printfs in these functions as suggested, you should see all the threads print to the terminal.
Exercise 3. Implement the customer, supplier, supplierGenerator, and customerGenerator functions in
estoresim.cpp. Read the code referred to above (e.g. RequestGenerator.cpp) and the comments for these
functions to get an idea of what they should be doing. The generator functions should look similar to each
other, as should the supplier and customer functions to each other. Produce some output from these threads to
make sure they’re running and that jobs are being pushed between them properly.
For the supplierGenerator and customerGenerator functions, you will also have to implement the
enqueueStops method in RequestGenerator.cpp.
Run make run-sim to run the simulator. You should see the output of your worker threads. You can stop the
simulator by pressing Control-C.
Now you have many customers and suppliers working on jobs generated by the generator threads. But there
is no inventory for items in the store, nor are any of the work functions produced by the request generators
implemented. So, for the moment, our simulator spawns many workers in parallel to do very little. For the
workers to have anything to work on, there should be an inventory of items to purchase from and add to. To
this end, we have provided the skeleton of this inventory for you as class EStore, in the files EStore.h and
EStore.cpp.
Exercise 4.
Design and implement the EStore class, filling in all the method skeletons we provide and adding
any new methods you may find necessary. Read through all the provided comments in the files related to the
EStore class (but don’t worry about the buyManyItems method for now). The EStore will have to keep track
of many Items and ensure that all modifications to Items in the EStore are synchronized.
You should implement the EStore as a monitor; that is, there should be a single lock on the entire store,
which is acquired upon entering any of the store’s methods and released upon exit.
As a reminder, the buyItem method in EStore should wait for an item to become available or on discount if
necessary. So, if a customer comes in looking to buy an item outside of the given budget, the customer should
wait until the item is being sold at a sufficiently high discount and then buy, instead of just immediately
returning.
Run make run-sim to make sure your code compiles and doesn’t have any segfault-inducing bugs in the
constructor for class EStore. For the moment, no threads are actually interacting with the EStore, so if you
put any printfs in its methods, you won’t see them output anything just yet.
There is only one piece remaining to make the simulator work now: the handlers for the jobs created by the
request generators and pushed to the worker threads. These jobs consist of adding and removing items from
the EStore inventory or setting discounts on items (for suppliers) and of purchasing items (for customers).
We’ve provided skeletons for these handlers in RequestHandlers.cpp. Before you implement these handlers,
you may find it helpful to read through all the different kinds of requests that exist in Request.h.
Exercise 5.
Go through and implement each handler in RequestHandlers.cpp one-by-one. Print a message at
the beginning of each handler which contains the name of the handler and the fields of the request struct
passed to it (you don’t need to print the value of the store pointer). This will produce a trace of the work
done by your threads as they process jobs.
Your handler functions should largely make use of the methods you implemented previously in EStore.
After implementing all the handlers (including stop_handler), your simulator may not terminate on its own.
This will happen in the case where a customer is blocked on buying an item, but the item never gets
discounted enough for the customer to buy, which will happen sometimes and should be expected. In this
case, you will still need to kill the simulator with Control-C.
Run make run-sim after you implement each handler and make sure that requests are being dispatched to
your new handlers.
Here’s some example output from the staff solution to part A of the lab to give you an idea of what running
your simulator should look like. You don’t have to worry about matching our output format exactly.
Handling AddItemReq: item_id – 77, quantity – 94, price – $6370.15, discount – 0.00
Handling BuyItemReq: item_id – 83, budget – $14308.86
Handling BuyItemReq: item_id – 35, budget – $33853.86
Handling AddItemReq: item_id – 92, quantity – 22, price – $5167.49, discount – 0.00
Handling BuyItemReq: item_id – 62, budget – $9900.27
Handling AddItemReq: item_id – 90, quantity – 64, price – $5201.59, discount – 0.00
Handling BuyItemReq: item_id – 26, budget – $6805.40
Handling AddItemReq: item_id – 26, quantity – 37, price – $892.72, discount – 0.00
…
Handling ChangeItemPriceReq: item_id – 96, new_price – $7007.23
Handling BuyItemReq: item_id – 46, budget – $19934.51
Handling ShippingCostReq: new shipping cost – $29.21
Handling BuyItemReq: item_id – 79, budget – $30974.88
Handling AddItemReq: item_id – 64, quantity – 42, price – $8883.28, discount – 0.00
…
Handling StopHandlerReq: Quitting.
Handling StopHandlerReq: Quitting.
Handling StopHandlerReq: Quitting.
You should now have a working store simulator. Run make run-sim a few times and watch the output of your
workers as they process jobs. If you notice anything suspicious in the output, go back and check to make sure
you did your synchronization correctly and that you are following the multi-threaded coding guidelines
0 comments