Reading 05: Condition Variables

Everyone:

Last week, we have studied two different forms of concurrency: event-based programming via select/poll and threads (ala pthreads). While the former allowed us to overlap I/O and computation, it did not allow us to take advantage of parallelism. To do harness multiple hardware resources, we will need to utilize threads. Unfortunately, using threads also means we need to employ locks and condition variables to ensure correct concurrent access to shared resources.

The readings this week focus on how locks and condition variables work together and how we can use them to implement concurrent data structures.

TL;DR¶

For this reading assignment, you are to read about using locks and condition variables to synchronize pthreads, submit your responses to the Reading 05 Quiz, and modify your program to use a thread pool and the producer consumer model.

Reading¶

The readings for this week are:

Operating Systems: Three Easy Pieces
1. Lock-based Concurrent Data Structures
2. Condition Variables

Optional Readings¶

The following are optional related readings:

Quiz¶

Once you have done the readings, answer the following Reading 05 Quiz questions:

Program¶

In Reading 04, you created a [thread] to compute the sha1sum of each argument. This provides concurrency and parallelism, but it is possible to overwhelm the system and waste time if there are a lot of arguments (and thus a lot of threads). Instead of creating threads on-demand, we will instead use a thread pool to create 2 workers then feed them work via the concurrent queue discussed in Lecture 10.

In summary, you are to modify the program in Reading 04 to use the producer consumer model where there are 2 consumers threads (ie. sha1sum_thread) and 1 producer thread (ie. main).

Note: You will want to copy the queue.h, queue.c, and thread.h files from the Lecture 10 example. Additionally, you will need to modify the Queue to support storing c-strings (ie. char *) instead of ints.

You may choose between either queue2.c or queue3.c.

Example¶

The usage and output of your program should be the same as sha1sum:

$ ./program Makefile  # Compute SHA1 of Makefile
50bb7f7ccf1ca089f3c5eaff5fe95e56ddbe53a5  Makefile

$ echo $?             # Check exit status
0

$ ./program asdf      # Handle invalid files

$ echo $?             # Check exit status
1

Requirements¶

Your code must compile cleanly with no warnings.
Your program may only use I/O system calls such as open, read, and close to access the contents of each file.
Your program must use stat to get the size of any files.
Your program must use the SHA1() function provided by OpenSSL.
Your program must not have any resource leaks or memory errors as detected by valgrind.
Your program must use Thread, thread_create, thread_join from thread.h discussed in Lecture 10.
Your program must use Queue, queue_create, queue_push, queue_pop, and queue_delete from queue.h discussed in Lecture 10.
Each thread must run concurrently (ie. without waiting for another thread to complete first).

Note: To link properly to the SHA1 functions, you will need to add -lcrypto to the LIBS variable in your Makefile. You will also need to add the -pthread flag to your CFLAGS.

Make sure your program links with queue.c in addition to program.c.

Hints¶

You can define the following constants to make your life easier:

#define MAX_THREADS 2                 /* Number of threads in thread pool */
#define QSIZE       4                 /* Maximum size of Queue structure */
#define SENTINEL    (const char *)-1  /* Sentinel to mark end of Queue */

You will need to modify your sha1sum_thread from [Reading 05] into the following structure:

void *sha1sum_thread(void *arg) {
    Queue *q = (Queue *)arg;
    ...
    while (...) {
        path = queue_pop(q);
        ...

        if (sha1sum_file(path, cksum)) {
            ...
        } else {
            ...
        }
    }
    ...
    return (void *)failures;
}

This [thread] function will repeatedly pop from the Queue until it reaches a SENTINEL value. For each value popped from the Queue, the [thread] should compute the sha1sum of the path and track if there are any failures. At the end, the [thread] should return the number of failed sha1sum computations.

To implement the thread pool pattern, you will need to modify your main function to look like the following:

function main():
    Thread thread[MAX_THREAD]  # Thread array
    Queue *q = queue_create(SENTINEL, QSIZE)

    # Start thread pool
    For each thread:
        Create a thread stored in thread[i] that runs sha1sum_thread on q.

    # Producer: send work to queue
    For each argument:
        Push argument into q

    Push SENTINEL into q

    # Clean up thread pool
    For each thread:
        Join thread[i] and aggregate failures.

Submission¶

To submit you work, follow the same process outlined in Reading 01:

$ git switch master                   # Make sure we are in master branch
$ git pull --rebase                   # Make sure we are up-to-date with GitLab

$ git checkout -b reading05           # Create reading05 branch and check it out

$ cd reading05                        # Go into reading05 folder
$ $EDITOR answers.json                # Edit your answers.json file

$ ../.scripts/check.py                # Check reading05 quiz
Checking reading05 quiz ...
      Q1 0.30
      Q2 0.20
      Q3 0.30
      Q4 0.40
      Q5 0.20
      Q6 0.60
   Score 2.00 / 2.00
  Status Success

$ git add answers.json                # Add answers.json to staging area
$ git commit -m "Reading 05: Quiz"    # Commit work

$ $EDITOR program.c                   # Edit your program.c file

$ make test-program                   # Check reading05 program
Testing reading05 program...
 I/O System Calls                                             ... Success
 I/O Functions                                                ... Success
 Memory Functions                                             ... Success
 SHA1 Functions                                               ... Success
 Process System Calls                                         ... Success
 Thread Functions                                             ... Success
 Queue Functions                                              ... Success
 program                                                      ... Success
 program (valgrind)                                           ... Success
 program (strace)                                             ... Success
 program Makefile                                             ... Success
 program Makefile (valgrind)                                  ... Success
 program Makefile (strace)                                    ... Success
 program Makefile README.md                                   ... Success
 program Makefile README.md (valgrind)                        ... Success
 program Makefile README.md (strace)                          ... Success
 program Makefile README.md program.c                         ... Success
 program Makefile README.md program.c (valgrind)              ... Success
 program Makefile README.md program.c (strace)                ... Success
 program Makefile README.md program.c asdf                    ... Success
 program Makefile README.md program.c asdf (valgrind)         ... Success
 program Makefile README.md program.c asdf (strace)           ... Success
 program Makefile README.md /bin/ls /bin/bash                 ... Success
 program Makefile README.md /bin/ls /bin/bash (valgrind)      ... Success
 program Makefile README.md /bin/ls /bin/bash (strace)        ... Success
 program Makefile fdsa README.md program.c asdf               ... Success
 program Makefile fdsa README.md program.c asdf (valgrind)    ... Success
 program Makefile fdsa README.md program.c asdf (strace)      ... Success
   Score 2.00 / 2.00
  Status Success

$ git add program.c                   # Add program.c to staging area
$ git add Makefile                    # Add Makefile to staging area
$ git commit -m "Reading 05: Code"    # Commit work

$ git push -u origin reading05        # Push branch to GitHub

Pull Request¶

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the appropriate teaching assistant from the Reading 05 TA List.