Reading 07: Concurrency Bugs

Everyone:

Last week, we discussed how to utilize semaphores to synchronize multiple threads and to construct concurrent data structures. As with locks and condition variables, we saw that there were some common programming patterns that allow us to implement monitor style mutual exclusion.

The readings this week focus on concurrency bugs such as deadlock and ways we can avoid them by while carefully using all the synchronization primitives we have discussed thus far.

TL;DR¶

For this reading assignment, you are to read about concurrency bugs such as deadlock, and submit your responses to the Reading 07 Quiz.

Reading¶

The readings for this week are:

Operating Systems: Three Easy Pieces
1. Concurrency Bugs
2. Summary

Optional Resources¶

The Dining Philosophers Problem With Ron Swanson

Quiz¶

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

Program¶

In Reading 05, 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 allowing all threads to run concurrently, we can use a semaphore to implement throttling and thus provide admission control. Likewise, we can also use a semaphore to provide synchronized access to a global Failures counter that records the number of failed sha1sum computations and serves as our program's exit status.

In summary, you are to modify the program in Reading 05 to use one semaphore to implement throttling and another semaphore to synchronize access to a global variable.

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 the SHA1_Init, SHA1_Update, and SHA1_Final functions provided by OpenSSL.
Your program must not have any resource leaks or memory errors as detected by valgrind.
Your program must use sem_init, sem_wait, and sem_post to manipulate your semaphores.
Each thread must run concurrently (ie. without waiting for another thread to complete first) up to the MAX_THREADS limit.

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.

Hints¶

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

#define MAX_THREADS 2                 /* Maximum number of active threads */

You will also want to define the following global variables:

sem_t  Lock;                          /* Semaphore for synchronizing access to Failures */
sem_t  Running;                       /* Semaphore for throttling number of active threads to MAX_THREADS */
size_t Failures = 0;                  /* Records number of failed sha1sum computations */

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

void *sha1sum_thread(void *arg) {
    ... // Semaphore operation

    char cksum[SHA_DIGEST_LENGTH*2 + 1];
    char *path = (char *)arg;

    if (!sha1sum_file(path, cksum)) {
        ... // Semaphore operation
        Failures++;
        ... // Semaphore operation
    } else {
        printf("%s  %s\n", cksum, path);
    }

    ... // Semaphore operation
    return 0;
}

This thread function will perform the sha1sum_file function on the argument given to the thread. It will use one semaphore to throttle the total number of threads, while using another semaphore to guard the updating of the Failures global variable.

To use the semaphores, you will need to modify your main to initialize them to the appropriate values:

function main():
    # Initialize semaphores
    sem_init(&Lock, 0, ...)
    sem_init(&Running, 0, ...)

    # For each argument, create thread to compute sha1sum
    pthread_t thread[argc - 1]  # Thread array
    For each argument:
        Create a thread stored in thread[i] that runs sha1sum_thread

    # For each argument, join thread
    For each thread in thread array:
        Join thread[i]

    return Failures

Submission¶

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

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

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

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

$ ../.scripts/check.py                # Check reading07 quiz
Checking reading07 quiz ...
     Q01 0.10
     Q02 0.40
     Q03 0.80
     Q04 0.20
     Q05 0.30
     Q06 1.20
   Score 3.00 / 3.00
  Status Success

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

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

$ make test-program                   # Check reading07 program
Testing reading07 program...
 I/O System Calls                                             ... Success
 I/O Functions                                                ... Success
 SHA1 Functions                                               ... Success
 Process System Calls                                         ... Success
 Thread Functions                                             ... Success
 Semaphore Functions                                          ... Success
 program                                                      ... Success
 program (valgrind)                                           ... 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 README.md a /bin/ls /bin/bash b             ... Success
 program Makefile README.md a /bin/ls /bin/bash b (valgrind)  ... Success
 program Makefile README.md a /bin/ls /bin/bash b (strace)    ... Success
   Score 3.00 / 3.00
  Status Success

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

$ git push -u origin reading07        # 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 07 TA List.