In this lab, you will implement a model of an online store. Your model will support safe parallel updates to a central inventory database, which maintains stock of all items available for sale from the online store. Updates to this inventory database will come from both suppliers (who add goods to the inventory and enable or disable deals on items, such as discounts and free shipping) and customers (who, by purchasing items from the online store, remove them from the inventory). In the model, customers and suppliers will be represented by different threads, all executing in parallel.
Though your store is only a model, the concepts you will learn and use throughout this lab could be applied similarly in a real-world setting. Suppliers and customers would be on different computers, talking to a central inventory database over the Internet. Requests sent over the Internet from suppliers and customers would be handled by different threads on the central inventory computer, and any operations on the database would have to be done with proper synchronization, just as in your model.
Coding style. In this and subsequent labs, you will be graded for style. We will deduct up to 20% of total lab points for poor style based on our subjective evaluation. You will have to pay attention to things like indentation and spacing (which need to be consistent), variable names (which need to be clear and consistent), repeated code (which needs to be avoided), spaghetti code (which needs to not happen), etc.
Follow this style guide.
Concurrency commandments. You will need to read Coding Standards for Programming with Threads,by Mike Dahlin. You are required to follow these standards for this project. In the real world, unclear multi-threaded code is particularly dangerous – because it is difficult or impossible to test. Moreover, if it’s not clear, then the programmer who comes after you cannot debug it, maintain it, or add new features.
Because it is impossible to determine the correctness of a multithreaded programming via testing, grading on this project will primarily be based on reading your code. If your code is difficult to understand, then you will lose points (potentially lots of them), even if the program seems to work. Feel free to sit down with the TAs or instructor during office hours for code inspections before you turn in your project (note: to take advantage of this, start on time! [which is probably earlier than you think]).
Obtain and update the lab files as follows. We assume that you have set up the upstream as described in the lab setup. Then run the following on your local machine (Mac users can do this on their local machine or within the Docker container; Windows and CIMS users should do this from outside the container):
$ cd ~/cs202
$ git fetch upstream
$ git merge upstream/main
…. # output omitted
cs202-run-docker docker lab1 lab2 lab3 learn-ctags README.md
This labʼs files are located in the lab3 subdirectory.
If you have any “conflicts” from lab 2, resolve them before continuing further. Run git push to save your work back to your personal repository.
Letʼs begin by ensuring that you can build the code you just pulled. Enter the Docker environment:
cs202-user@172b6e333e91:~/cs202-labs$ cd lab3/
EStore.cpp RequestGenerator.cpp TaskQueue.cpp estoresim.cpp
EStore.h RequestGenerator.h TaskQueue.h sthread.cpp
Makefile RequestHandlers.cpp answers.txt sthread.h
Request.h RequestHandlers.h check-lab.sh
The rest of these instructions presume that you are in the Docker environment. We omit the cs202-user@af8b1be95427:~/cs202-labs part of the prompt.
You should see output similar to the following:
g++ -pipe -MD -I. -Wall -g -c estoresim.cpp -o build/estoresim.o
estoresim.cpp:116:1: warning: ‘void* customer(void*)’ defined but not used [-Wunused-function]
estoresim.cpp:95:1: warning: ‘void* supplier(void*)’ defined but not used [-Wunused-function]
estoresim.cpp:74:1: warning: ‘void* customerGenerator(void*)’ defined but not used [-Wunused-functio]
estoresim.cpp:43:1: warning: ‘void* supplierGenerator(void*)’ defined but not used [-Wunused-functio]
g++ -pipe -MD -I. -Wall -g -c TaskQueue.cpp -o build/TaskQueue.o
g++ -pipe -MD -I. -Wall -g -c EStore.cpp -o build/EStore.o
g++ -pipe -MD -I. -Wall -g -c RequestGenerator.cpp -o build/RequestGenerator.o
g++ -pipe -MD -I. -Wall -g -c RequestHandlers.cpp -o build/RequestHandlers.o
g++ -pipe -MD -I. -Wall -g -c sthread.cpp -o build/sthread.o
g++ -pipe -o build/estoresim build/estoresim.o build/TaskQueue.o build/EStore.o
build/RequestGenerator.o build/RequestHandlers.o build/sthread.o -lpthread -lrt
A Quick Introduction to C++
A very helpful way to think of shared state is as shared objects. We’re therefore going to use C++, C’s object oriented descendant, for this project.
If you haven’t used C++ before, don’t worry. For the subset of C++ relevant to this project, the learning curve will be gentle (especially assuming you already know Java). Furthermore, we will provide template code to which you will add the details; this should largely insulate you from having to learn much C++ syntax.
Read A Quick Introduction to C++, and you should be good to go. Note that this document was written over a decade ago, so a few of the comments on the state of standards and tools are a bit out of date (for example,the document warns against using C++ templates because debuggers didn’t understand them well back then;this warning is much less applicable today.) Nonetheless, it provides a good, quick overview of the key ideas to use (and some issues/pitfalls to avoid.)
C++ References. See our references page for some tutorials and futher references on C++.
Working with Threads
As noted earlier, you will need to read and follow Coding Standards for Programming with Threads, by Mike Dahlin. Also note that we covered monitors in class, and assigned 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: Navigating code: grep
Before we get into the meat of the lab, we will cover a useful tool: grep.
grep can be used to search for a text string or regular expression in files. It is commonly called with the following pattern:
$ grep [flags] [expression-to-search-for] [files-to-search]
To see a concrete example, run the following command:
$ grep “void” sthread.h
grep scans the file sthread.h and prints out each line that contains the term void. You should get the following output:
void smutex_init(smutex_t *mutex);
void smutex_destroy(smutex_t *mutex);
void smutex_lock(smutex_t *mutex);
void smutex_unlock(smutex_t *mutex);