Assignment 8: Synchronization

Due by: Friday, April 25, 2025 at 11:59 p.m.

The goal of this project is to practice using locks and semaphores to protect access to critical sections. For Stage 1, you'll use a lock in a nested loop to observe the timing that results from different granularities of locking. For Stage 2, you'll implement a Producer-Consumer queue to simulate the arrival and processing of concurrent network requests.

As with all the assignments and projects in this course, it's recommended that you do the stages in the order given. Try to get the MIN unit tests passing before moving on to the FULL ones. Likewise, try to get the MIN integration tests passing before moving on to the FULL ones.

First, download the archive given below and unzip it into an appropriate directory.

Stage 1: Protecting Critical Sections

In this stage, your goal is to protect a critical section created by a nested loop. The inner loop adds 1 to and then subtracts 1 from a shared variable. The end result should be 0 if this critical section is protected. Your task is to use a lock as needed. You will also need to set up two threads to run concurrently and perform this calculation.

  1. Edit the main.c file to initialize and later destroy the lock you will pass to run() and fifo_queue(). Note that both of these functions might run, and they can share the same lock.
  2. Edit the run() function in mutex.c to create and then join two threads, each of which runs the runner() function implemented in the same file.
  3. Use the lock to synchronize access to the shared variable in runner(). Note that you can place the locking and unlocking function calls in multiple places. One of the unit tests includes a timing constraint that you must pass: Correct placement of the lock will result in parallel execution that is at least three times slower than sequential execution but no more than six times slower. (Slower parallel execution is in general not ideal, but it is sometimes a necessary by-product of using a lock to share a resource and avoid race conditions.)

Stage 2: Synchronized Request Queue

For this stage, you will implement a Producer-Consumer request queue that simulates a queue containing server requests. One thread (running listen()) will pretend to listen for incoming network connections. When it "receives" an incoming socket connection (in actuality, a generated integer), it will (safely) put this integer (a "file descriptor") into the request queue. The listener thread will always simulate a total of 25 incoming requests. However, the queue size will vary between a capacity of 1 and a capacity of 30.

You will also create five threads (running worker()) responsible for "handling" each request. In this case, we'll simulate this behavior by pulling a "file descriptor" from the queue and printing it out. If you synchronize the access correctly, these messages will print out in order (0, 1, 2, 3, ...). You'll also need to make sure you're accessing the queue safely, using semaphores and locks. Note that the queue is implemented as a fixed-size circular queue, meaning that pulling values from a queue of size 10 will access indexes 0, 1, 2, ..., 9 and then return to index 0.

Note: Virtually all of the book's examples show named semaphores. However, unnamed semaphores are slightly easier (since you don't have to come up with a name for them) and work fine with threads in Linux. Feel free to use either named or unnamed semaphores.

  1. Edit the fifo_queue() function in queue.c to create one listener thread and five worker threads. Properly initialize the semaphores required, using the approach discussed in Section 8.3 of the book. You will also need to dynamically allocate a queue based on the requested size and set up the other variables in the prodcons_t struct to pass to the threads. Note that all threads (including the listener and all the workers) should have a pointer to the same instance of the struct so that they are sharing the same queue, lock, semaphores, and so on.
  2. Implement the worker() thread so that it correctly pulls int values from the fixed-size queue and prints out a message to simulate processing the request. Each worker should process exactly five requests.
  3. Implement the listen() thread so that it will enqueue 25 int values for the workers to process.

Turn In

First, run make clean to remove all of the executable and object files from your directory structure. Then, zip up the contents of your project directory in either a .zip or a .tar.xz file. Upload this archive to Brightspace. Your assignment must be submitted by Friday, April 25, 2025 at 11:59 p.m. Grace days are not available for assignments.

All work must be done within assigned teams, though you may discuss general concepts with your classmates. Please refer to the course policies if you have any questions about academic integrity. If you have trouble with the assignment, I am always available for assistance.

Under no circumstances should any member of one team look at the code written by another team. Tools will be used to detect code similarity automatically.

Code that does not compile will automatically score zero points.

Grading

Your grade will be determined by the following categories.

Category Description Weight
Unit Tests Your solution passes the seven unit tests. 70%
Integration Tests Your solution passes the three integration tests. 30%

Credits

This assignment is based on material from CS 361 by Michael S. Kirkpatrick. This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.