Reading 06: Semaphores, Concurrency Bugs

Everyone:

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

The readings this week focus on another synchronization primitive called a semaphore and on how to use to different various concurrency patterns. The readings will also explore various concurrency bugs like deadlock and the various ways we can use the synchronization primitives studied in this course to avoid such issues.

TL;DR¶

For this reading assignment, you are to read about semaphores and concurrency bugs, submit your responses to the Reading 06 Quiz, and modify your program to implement throttling.

Reading¶

The readings for this week are:

Operating Systems: Three Easy Pieces

Optional Resources¶

Quiz¶

Once you have done the readings, answer the following Reading 06 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 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 04 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 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 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 04 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 switch master                   # Make sure we are in master branch
$ git pull --rebase                   # Make sure we are up-to-date with GitLab

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

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

$ ../.scripts/check.py                # Check reading06 quiz
Checking reading06 quiz ...
     Q01 0.20
     Q02 0.10
     Q03 0.10
     Q04 0.10
     Q05 0.10
     Q06 0.20
     Q07 0.05
     Q08 0.15
     Q09 0.70
     Q10 0.30
   Score 2.00 / 2.00
  Status Success

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

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

$ make test-program                   # Check reading06 program
Testing reading06 program...
 I/O System Calls                                             ... Success
 I/O Functions                                                ... Success
 Memory 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 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
 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
   Score 2.00 / 2.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 06: Code"    # Commit work

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