Concurrent Access to Data Structures in C++

• Students should be able to define what a thread-safe data structure object is
• Given a definition of an object, students should be able to distinguish whether it is properly thread-safe or not and why
• Students should be able to describe how locking may be used to ensure proper concurrent access to data structures and how deadlock is avoided
• Given a problem that can be improved using parallel access to shared data, students should be able to use built-in thread-safe classes to implement parallel solutions and determine the speedup of their solution

This module is typically implemented in an introductory (2nd course) or intermediate-level Java-based course. It may be taught while introducing the concepts of threads and thread-safe data structures. An instructor could present the materials (handout, slideshow presentation) in class and assign exercises as a lab or homework.

You can visit the module in your browser:
Concurrent Access to Data Structures in C++

or you can download the module in either PDF format or latex format.
PDF Format: Concurrent Access to Data Structures in C++.pdf.
Latex Format: Concurrent Access to Data Structures in C++.tar.gz.
Word Format: Concurrent Access to Data Structures in C++.docx.

This is the code you can use to get students started on a lab or homework assignment:
CDS C++ student code 20120301 (gzip Archive 5kB Mar1 12)

Instructors: If you want example completed code, please contact Dick Brown, rab at stolaf dot edu.

This module utilizes the Boost package, a library of enhanced capabilities for C++. Several of these capabilities have become incorporated in the new C++11 standard, including the Boost support for programming with threads (which we will use). The module also uses a TBB Container data structure in order to obtain a thread-safe implementation, and the CURL library for conveniently accessing web information.

In the code archive:

• Two versions of web-crawler code are provided, named serial (a mostly complete sequential implementation) and parallel (a mostly complete multithreaded implementation, omitting two key code segments for students to fill in). These implementations each contain multiple source files, located in subdirectories src and include, and a Makefile for building the application (using separate directories for object files, and resulting binary).
• main() is within src/spider_driver.cpp (in each implementation).
   
• Two additional versions, serial_all and parallel_all, contain the complete code (please request).

The concept of the lab/homework is that students should have worked out a sequential version of the Spider already. You could do this by explaining it to them, or by having them work on that first. We have used this in the past by staging assignments so that they get some parts of the code and then must complete to make a working spider. What is provided here is the already working sequential version.

You may feel like using different data structures for parts of this assignment- we realize there are other ways to hold the information kept by the crawler. However, the TBB Containers data structures we chose for the threaded version fit the problem well. (Feedback/suggestions? Please enter below.)

The lecture/class materials present the concepts of using multiple threads that share data structures in memory. Since the intended audience is introductory to intermediate students, we include a rather gentle introduction to the issue of "data race condition" errors, and explain how the designers of the data structures in the TBB Containers library avoided such errors.

Boost threads documentation

TBB documentation

CURL documentation