Semaphores Lab

Overview

In this lab you will get hands-on practice with POSIX semaphores by solving three classic synchronization problems. The lab has three parts:

1. Producer / Consumer (Bounded Buffer) – the running example from lecture and from the assigned reading.
2. Thread-safe Ordered Logging – forcing N threads to print in a fixed sequence using only semaphores.
3. Chemical Reaction – the H2O assembly-line problem from the earlier threading lab, but reimplemented with semaphores instead of locks and condition variables.

Across all three parts you may use only POSIX semaphores (sem_init, sem_wait, sem_post, sem_destroy) for synchronization. No pthread_mutex_*, no condition variables, and, no busy-waiting.

The total assignment is worth 100 points: 30 for Part 1, 30 for Part 2, and 40 for Part 3.

Getting the starter code

Download and untar the starter code with the commands below

cd ~/cs224
wget https://cs224.cs.vassar.edu/labs/semaphores.tar
tar xvf semaphores.tar
cd semaphore_lab

The starter code is laid out as follows:

semaphore_lab/
  Makefile                    # builds everything; "make run" runs all tests
  part1/
    producer_consumer.c       # YOU EDIT THIS
    test_producer_consumer.c  # provided test harness
    Makefile
  part2/
    logger.c                  # YOU EDIT THIS
    test_logger.c             # provided test harness
    Makefile
  part3/
    reaction.h                # do not modify
    reaction.c                # YOU EDIT THIS
    test_reaction.c           # provided test harness
    Makefile

From inside semaphore_lab/ directory, make builds every part and make run runs every test suite. You can also cd partN && make run to focus on a single part.

Part 1: Producer / Consumer (30 points)

Implement the bounded-buffer producer/consumer solution from the lecture and the reading. The starter file part1/producer_consumer.c already takes care of:

• parsing command-line arguments,
• spawning producer and consumer threads,
• joining them and printing a summary line,
• sending one “poison-pill” -1 per consumer so consumers exit cleanly when production is finished.

What’s left for you is the synchronization logic: declare and initialize the semaphores, fill in put() and get(), and destroy the semaphores at the end. The exact spots are marked with TODO (Part 1) comments in the starter.

You will need three semaphores:

• one to count empty buffer slots,
• one to count full buffer slots,
• one mutex (binary semaphore) to protect the body of put() and get().

Building and running

cd part1
make            # builds producer_consumer and test_producer_consumer
make run        # runs the test suite

The harness exercises your code with several producer/consumer counts and item counts. It checks that the right total number of items is produced and consumed, that no item is dropped or duplicated (the sum of all consumed values has to match the expected mathematical sum), and that the program does not deadlock.

Deliverable for Part 1

part1/producer_consumer.c with your edits.

Part 2: Thread-safe Ordered Logging (30 points)

You have N threads, each representing a process that generates a log message. Each thread has an assigned sequence number from 0 to N-1. Your job is to:

• ensure only one thread writes to the log at a time, and
• enforce that threads log in strict sequence order (0, 1, 2, …, N-1).

The starter file part2/logger.c already declares an array sem_t sems[NUM_THREADS], creates the threads (in reverse order, on purpose, so that out-of-order printing is exposed quickly), and joins them. Your job is to:

1. initialize the semaphores in main(),
2. fill in logger_thread() so each thread waits its turn before printing, then hands off to the next thread,
3. destroy the semaphores at the end.

Hints for Part 2

Read these one at a time – only peek at the next hint if you’re truly stuck.

• Hint 1. Section 31.3 (“Semaphores For Ordering”) of the reading shows how one thread can wait until another has signaled. Generalize that idea to a chain: thread k should wait until thread k-1 has signaled.

• Hint 2. It’s natural to associate one semaphore per thread. Define what each one means. A useful interpretation: sems[i] is “permission for thread i to print”.

• Hint 3. If every semaphore starts at 0, every thread waits forever and you have a deadlock. Exactly one semaphore should start at 1; the rest at 0. Which one?

• Hint 4. Each thread’s body should look roughly like:

  sem_wait(  permission to print  );
  print the message;
  sem_post(  permission for the NEXT thread  );
  

• Hint 5 (last resort). Revisit the parent/child example with sem_init(&s, 0, 0) and sem_post/sem_wait in the reading. Ordered logging is just that pattern, repeated.

Building and running

cd part2
make
make run        # runs ./logger 20 times, verifying ordering each run

Because a buggy solution can sometimes get lucky, the test harness runs your program many times; any single bad run fails the suite.

Deliverable for Part 2

part2/logger.c with your edits.

Part 3: Chemical Reaction (40 points)

Mother Nature is back. She still wants water, but she has switched synchronization libraries: she now wants the H2O assembly line implemented purely with POSIX semaphores. The setup is the same as in Problem 2 of the earlier threading lab:

• Each H atom is a thread that calls reaction_h(struct reaction *r).
• Each O atom is a thread that calls reaction_o(struct reaction *r).
• The functions must delay until at least two H atoms and one O atom are present; then exactly one of them must call the provided make_water() function.
• After each make_water() call, exactly two reaction_h() and one reaction_o() should return.

You will edit part3/reaction.c. The header part3/reaction.h declares struct reaction (which already has slots for a mutex, two queue semaphores, and the H/O counters; you may add more fields if you want) and the prototypes you must implement:

void reaction_init(struct reaction *r);
void reaction_destroy(struct reaction *r);
void reaction_h(struct reaction *r);
void reaction_o(struct reaction *r);

make_water() is provided by the test harness and must be called exactly once per (2H + 1O) group, while those calls are still active.

Hints for Part 3

• Use the binary-semaphore-as-lock pattern around the counters nH and nO. That mutex protects every read/write of those fields.

• Use one “queue” semaphore for hydrogen atoms (initial value 0) and one for oxygen atoms (initial value 0). When a thread realizes it is not the one that completes the trio, it should sem_wait on its own queue. When some other thread does complete the trio, it should sem_post the right number of times on each queue to wake up the partners.

• Whichever thread completes the trio (the one that, holding the mutex, sees that nH >= 2 and nO >= 1) is the natural choice to call make_water(). That thread also wakes its partners.

• Holding the mutex across make_water() is a clean way to guarantee that make_water() runs serialized and that no overlapping group forms. Don’t forget to release the mutex before returning.

• Keep your solution short. A clean reference solution is well under 50 lines of synchronization code.

Building and running

cd part3
make
make run

The test harness creates many H and O threads and verifies that:

• make_water() is called exactly the right number of times,
• at every make_water() call, at least 2 H and 1 O atom are actively inside their reaction functions,
• every atom thread eventually returns,
• the program completes within a wall-clock timeout (no deadlock, no busy-wait).

Deliverable for Part 3

part3/reaction.c. (You may also submit reaction.h if you added fields, but you must not change the public interface.)

Submitting the lab

From the lab/ directory, run:

make submit

This produces semaphores-submit.tar containing your edited source files. Upload that tarfile to Gradescope. The autograder there runs the same test suites as make run, plus additional stress and correctness tests, and will assign 30 / 30 / 40 points across the three parts.

Grading

Each part is graded by the test harness for that part. Within a part, points are awarded proportionally to the test cases your solution passes. As with prior threading labs, simplicity counts: a clean, short, correct solution is much more valuable than a long, fragile one. Spend the time to get the synchronization right rather than trying to paper over a race with extra sem_post or sem_wait calls.