Reading 06: Semaphores

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 a new synchronization primitive called a semaphore and on how to use it build concurrent data structures.

TL;DR¶

For this reading assignment, you are to read about semaphores and submit your responses to the Reading 06 Quiz.

Reading¶

The readings for this week are:

Operating Systems: Three Easy Pieces
1. Semaphores

Optional Resources¶

Quiz¶

Once you have done the readings, answer the following Reading 06 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 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 05 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 checkout 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.80
     Q02 0.40
     Q03 0.40
     Q04 1.40
   Score 3.00 / 3.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
 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 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 add queue.c                     # Add queue.c to staging area
$ git add queue.h                     # Add queue.h to staging area
$ git add thread.h                    # Add thread.h 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.