**Assignment 10: Synchronization** # Learning Goals - Learn how to use synchronization primitives. - Learn how to interact with operating system functionality. # Grading Walk-Throughs This assignment will be graded as "Nailed It" / "Not Yet" by a TA. To pass ("Nailed It") the assignment, you must 1. Complete the assignment and submit your work to gradescope. + You should start this assignment in class on the day shown on the calendar. + *Complete the assignment as early as possible*. 1. Schedule a time to meet with a TA. You can meet with them after the submission deadline. + You must book a time to meet with a TA + Sign-up on the Google Sheet *with at least 36 hours of notice*. + Contact your TA on Slack after signing up. + All partners must meet with the TA. If you cannot all make it at the same time, then each of you needs to schedule a time to meet with the TAs. 1. Walk the TA through your solutions prior to the deadline. + Walk-throughs should take no more than 20 minutes. + You should be well prepared to walk a TA through your answers. + You may not make any significant corrections during the walk-through. You should plan on making corrections afterward and scheduling a new walk-through time. Mistakes are expected---nobody is perfect. + You must be prepared to explain your answers and justify your assumptions. TAs do not need to lead you to the correct answer during a walk-through---this is best left to a mentor session. 1. The TA will then either + mark your assignment as "Nailed It" on gradescope, or + mark your assignment as "Not Yet" and inform you that you have some corrections to make. 1. If corrections are needed, then you will need to complete them and then schedule a new time to meet with the TA. + You will ideally complete any needed revisions by the end of the day the following Monday. If you have concerns about the grading walk-through, you can meet with me after you have first met with a TA. # Overview In this assignment, you will synchronize a multi-threaded program. As usual, you should complete this assignment with a partner; you may choose your partner for this assignment. Starter code is available on the course server, and you should complete the assignment on the course VM. You can copy and unpack the tar file with: ~~~bash tar xvf /data/A10-Synchronization.tar ~~~ You will find two files inside the newly created directory: `sync.c` and `Makefile`. The source file contains code implementing a club patronized by two types of people: CS majors and math majors (no double majors allowed!). CS majors and math majors are both implemented as threads; each category of thread enters the club, hangs out for a couple of seconds, and then leaves the club. Your job will be to add synchronization to these programs to enforce various constraints using **locks** (mutexes) and **condition variables**. # Testing The simulation will run continuously. You will need to signal your process with `SIGINT` to kill it. You can do this by typing `ctrl-c` (the "control" key pressed simultaneously with the "c" key) at the prompt. While running your program, you will occasionally see some strange output. For example ~~~text CS Major #00 arrives ( 0/10 CS and 0/10 Math Majors in the club) CS Major #02 arrives ( 0/10 CS and 0/10 Math Majors in the club) CS Major #02 enters ( 2/10 CS and 0/10 Math Majors in the club) CS Major #00 enters ( 1/10 CS and 0/10 Math Majors in the club) CS Major #01 arrives ( 0/10 CS and 0/10 Math Majors in the club) CS Major #01 enters ( 3/10 CS and 0/10 Math Majors in the club) CS Major #03 arrives ( 3/10 CS and 0/10 Math Majors in the club) CS Major #03 enters ( 4/10 CS and 0/10 Math Majors in the club) CS Major #04 arrives ( 4/10 CS and 0/10 Math Majors in the club) CS Major #04 enters ( 5/10 CS and 0/10 Math Majors in the club) Math Major #00 arrives ( 5/10 CS and 0/10 Math Majors in the club) Sync error: bad social mixup! CS Majors=5, Math Majors=1 Math Major #01 arrives ( 5/10 CS and 1/10 Math Majors in the club) Math Major #01 arrives ( 5/10 CS and 1/10 Math Majors in the club) Sync error: bad social mixup! CS Majors=5, Math Majors=2 Math Major #02 arrives ( 5/10 CS and 1/10 Math Majors in the club) Math Major #02 arrives ( 5/10 CS and 1/10 Math Majors in the club) Math Major #03 arrives ( 5/10 CS and 2/10 Math Majors in the club) ~~~ Notice that we have an error report, and then several additional lines of output---even though we have an `exit(1)` after any such error reporting (check for `exit` in the given file)! Your first question on gradescope is to provide an explanation of such a phenomenon. Testing and debugging synchronization code is notoriously difficult. My best advice is to leave your code running for a while and see whether the `sanitycheck` function detects any problems. I would also recommend that you try varying the number of CS majors and the number of math majors (but make sure the club capacity is always big enough to accommodate all the people if you have not yet implemented Task 3). # Your Tasks For this assignment, you should complete the following three tasks. (Here is some [great information on the POSIX Threads API (pthreads)](https://www.cs.fsu.edu/~baker/realtime/restricted/notes/pthreads.html); I highly recommend having this open while coding up your solution.) ## Task 1 The provided starter code will compile and run. You should notice that shared memory is accessed by many threads. What could go wrong (**answer this question on gradescope**)? Your first task is to add synchronization ensuring that: 1. The CS and math major threads are accessing `daclub299` safely. You'll need to use a lock, `pthread_mutex_t`. 2. The club is always (mutually)-exclusively CS majors **or** math majors, i.e., no CS majors should enter as long as there are math majors in the club, and vice versa. This step will require a condition variable, `pthread_cond_t`, for CS majors and another one for math majors. You will need to modify - the `struct club` definition (add one lock and two condition variables) - `club_init` (initialize the lock and condition variables), - `comp_enter` (use the lock to safely access `daclub299` memory and the condition variables to limit "entrance" into the club), - `comp_exit` (use the lock to safely access `daclub299` memory and the condition variables to notify other threads about the change), - `math_enter` (use the lock to safely access `daclub299` memory and the condition variables to limit "entrance" into the club), and - `math_exit` (use the lock to safely access `daclub299` memory and the condition variables to notify other threads about the change). Look for "`TODO(Task 1): ...`". Once implemented, you should notice something sad about your program's output. **Answer the next question on gradescope.** ## Task 2 Once you have successfully solved the first task, you might observe that your solution suffers from a problem known as *starvation*: there is no guarantee that a thread waiting to enter the club will ever gain entrance. For example, the club might admit a few CS majors at the start, and then remain exclusively CS majors for all time, leaving the waiting math majors to wait at the door, talking about how cool the club was when it was still underground. Prior to implementing a fix for starvation, you should **draw the diagram described on gradescope.** Modify your synchronization so that it is *starvation-free*, that is all threads are guaranteed to eventually make progress. To do so, you will need to add another lock, `pthread_mutex_t`. You will need to modify - the `struct club` definition (add another lock) - `club_init` (initialize the new lock) - `comp_enter` (use the new lock), and - `math_enter` (use the new lock). Look for "`TODO(Task 2): ...`". ## Task 3 As requested on gradescope, **draw a starvation-free diagram of your code.** You might also observe that your code doesn't enforce any capacity constraints for the club. In the starter code, the capacity of the club is set equal to the total number of people (CS majors plus math majors), so this isn't a problem, but you could run into trouble if you increase the number of people (i.e., threads) without increasing the capacity of the club. Modify your synchronization to explicitly enforce the restriction that the number of people in the club cannot be greater than the capacity of the club. You will need to make three VERY minor changes - change `CLUB_CAPACITY`, - modify usage of your condition variable in `comp_enter`, and - modify usage of your condition variable in `math_enter`. Look for "`TODO(Task 3): ...`". Note: due to your starvation-prevention mechanism, you might need to set the capacity quite low to test it out. Try it first at something like `6` and see what your program does. # Submitting Your Assignment You will submit your code and/or responses on gradescope. **Only one partner should submit.** The submitter will add the other partner through the gradescope interface. To pass the autograder (if one exists for this assignment), your output must exactly match the expected output. Your program output should be similar to the example execution above, and the autograder on gradescope will show you the correct output if yours is not formatted properly. You can use [text-compare](https://text-compare.com/) to compare your output to the expected output and that should give you an idea if you have a misspelled word or extra space (or if I do). Additional details for using gradescope can be found here: - [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work) - [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members) - [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)