CS376: Operating Systems - Threaded Programming (100 Points)

Assignment Goals

The goals of this assignment are:

Design and implement a C program to simulate multiple threads
Use mutex locks to protect shared variables
Investigate the implications of race conditions in concurrent programming
Evaluate the performance impact of different synchronization techniques
Implement correct concurrent programs that coordinate using semaphores and condition variables

Background Reading and References

Please refer to the following readings and examples offering templates to help get you started:

Makefile Tutorial

The Assignment

Part 1: Introduction to Concurrent Programming

Write a program in C to simulate 100 people (threads) that enter a stadium. They get up a few times, let’s say 1000 times (for food, etc.), and return to their seats. They pass through a counter each time they return to their seat. Write a program that consists of one threaded function that you invoke via 100 pthreads. That threaded function should increment a shared variable (initialized to 0, and declared as a volatile variable), 1000 times each. Note - if your system does not allow you to spawn so many threads, you may use fewer threads and/or a larger number of “times they get up.”

Be sure to declare this variable volatile, and describe in your writeup why this is important. Also, when you increment a variable that is a pointer to an integer (or a long integer, etc.), do not do:

*value++; // BROKEN!!

This is because the ++ operator takes precedence over the dereference * operator, so it will execute first! Do one of these instead:

(*value)++;

*value = *value + 1;

Run this program 10 times, and time the runs. What is the average runtime of these runs? Also, record the final output of the counter. It should be 100000, but it likely will not be. What was it on each run?

Correcting the Race Condition with Mutex Locks

What is the problem with this program? Use the valgrind thread checker to identify the program’s thread failures, and provide the report showing the problems it identified.

Now, create a new version of your program, and using mutex locks (lock inside the loop), fix the code, and re-run it 10 times. Again, time the runs, and give the average runtime. As before, give the final output of the counter (this time, it really should be 100000). How much slower was this program than the one without mutex locks?

Now, in a new version of the program, move the locks so that they lock and unlock only once per thread (outside the loop). Verify the correct value is still obtained, and find the average runtime over 10 runs again. What do you observe as compared to the other two versions?

Part 2: The Office Hours Problem

Consider the following problem: your professor has a small office that can seat three students simultaneously. During office hours, students arrive after a random duration (perhaps after “sleeping” for a random amount of time!) to the professor’s office to ask questions and have disucssion. Professors do no other work during their office hours, so they simply block if no students are there and until one arrives. Once the professor is working with three students simultaneously, additional students will queue up outside by blocking; they are awoken when a student leaves the office.

Using mutex locks, implement a solution to this problem. To do this, create a shared int variable representing a counter of the number of students waiting for office hours. This variable is initially 0 and should be protected by a mutex lock (also accessible to all threads, just like the shared counter).

The threaded function should check the value of this counter. If it is less than 3, increment the variable and enter the office (by proceeding through the function). Decrement the variable right before you return, simulating leaving the office. Don’t forget to lock your mutex when accessing this variable!

If the shared counter is greater than or equal to 3, malloc a new lock and insert it at the head of a linked list. Increment a new shared variable representing the number of students in the waiting room (also known as the size of the linked list!). Again, don’t forget to protect this access with a mutex! Lock the lock twice (once to lock it, and once more to block on it – since you want to wait outside the office for a seat to open up!). Hint: protect adding the node to the linked list with your mutex, but be sure to unlock the mutex right before locking your new waiting room lock the second time (why?).

When a student leaves the office, check the size of the waiting room queue. If it is greater than 0, remove the tail of the linked list (the student who was waiting the longest), and decrement the waiting room size (again, all protected by a mutex!). Unlock the lock you just popped off of the linked list to “wake up” the student in the waiting room. Be sure to destroy this lock so that you free the resources it was using. If you wake up a student, leave the shared counter at its current value (since you left and another student entered, the count stays the same!). If the waiting queue is empty and you do not wake up a student, decrement the shared counter (to reflect that you have left). Be sure to protect this shared counter with a shared mutex lock, and to declare the shared counter as volatile!

Run your program using the valgrind thread checker; specifically, by running valgrind --tool=helgrind ./a.out, and provide the report. Be sure to destroy all your mutexes at the end of your program and free your dynamically allocated memory. Use the valgrind leak check to verify you have no memory leaks, and include this report in your submission.

What to Do

To solve this problem, it is not necessary to implement a professor thread (only a student thread). If a student arrives and sees that numstudents < 3, increment numstudents and enter the office without blocking (other than to lock the mutex to protect numstudents, of course). When a student needs to wait for the professor (i.e., numstudents >= 3), you can create a lock for the student thread to block on. To do this, when it is time for a thread to block and wait, you’ll:

malloc a pthread_mutex_t and call pthread_mutex_init(theMutex, NULL) to initialize it (assuming you called the pthread_mutex_t* variable theMutex).
Lock the mutex once (so it’s locked)
Add that mutex to the linked list
Lock it again (so your thread blocks on it).

When a student leaves the office, they can check if the linked list is not NULL. If it’s not NULL, then remove a lock off of the linked list, and unlock it (which releases the next student waiting outside to come in). If it is NULL, decrement the shared counter (again, in a mutex lock to protect the variable).

By the end of your program, loop over the linked list of mutex locks (or once you unlock the mutex for the final time), and call pthread_mutex_destroy(theMutex) followed by a free of the linked list item or mutex you malloc‘ed.

Causing a Thread to Sleep

It may be helpful to have your threads sleep occasionally in their loops so that the print statements are easier to read. You can use the sleep and rand functions to do this. An example is given below that will sleep for a minimum period of 1 to 5 seconds. I recommend incorporating this into a function that you can call on-demand.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

int main() {
    // Initialize the random number generator with the current time
    srand(time(NULL));

    // Generate a random number between 1 and 5
    int sleepTime = rand() % 5 + 1;

    // Inform the user about the sleep time
    printf("The program will sleep for %d seconds.\n", sleepTime);

    // Sleep for the determined number of seconds
    sleep(sleepTime);

    // Inform the user that the program has finished sleeping
    printf("The program has woken up.\n");

    return 0;
}

Avoding Deadlocks

Be sure you lock the shared mutex lock before checking the value of things like the number of students waiting outside, or in the office! If you do not, you might observe a certain value in that variable, and then proceed, but before you finish, that value could change. This could be problematic if, for example, you observe that 3 students are in the office, and create a mutex to add to the waiting room linked list (to wait on). But one of the threads “in the office” could finish before you create and add this lock to the linked list! If that happens, you’ll block on it, but that other thread will not unlock you when it leaves (because it will think the linked list is empty, or doesn’t have your lock on it). Acquire that mutex, and be sure to release it just before you block on any other locks.

Avoiding Race Conditions

Similarly, be sure to lock the mutex any time you update a shared variable. That includes the linked list! You can lock and unlock before and after calling push or remove from your linked list, using the shared mutex you had used previously.

Logging

It’s a good idea to put print statements in your program to log what your threads do. I like to add them before and after my mutex lock and unlock calls. I suggest adding an int id to your ThreadData structure, and set threadData[i].id = i when you create your threads. That way, you can printf the data->id field in your log messages inside your thread function!

Part 3: Makefile

Write a makefile to compile and run your programs. You may write separate makefiles for each program, if you prefer, but each should have a target to build the program, and one to run/test the program.

Submission

In your submission, please include answers to any questions asked on the assignment page in your README file. If you wrote code as part of this assignment, please describe your design, approach, and implementation in your README file as well. Finally, include answers to the following questions:

Describe what you did, how you did it, what challenges you encountered, and how you solved them.
Please answer any questions found throughout the narrative of this assignment.
If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).

Assignment Rubric

Description	Pre-Emerging (< 50%)	Beginning (50%)	Progressing (85%)	Proficient (100%)
Program Correctness (20%)	The program does not compile or runs with significant errors.	The program compiles but does not function as expected, showing incorrect behavior or outputs.	The program runs with minor issues; some elements of thread coordination or synchronization are not implemented correctly.	The program runs correctly, handling thread synchronization effectively and producing accurate outputs as per the assignment requirements.
Proper Thread Coordination (20%)	Thread coordination is absent or implemented incorrectly, leading to severe race conditions or deadlocks.	Basic thread coordination is implemented, but it's prone to occasional race conditions or inefficiencies.	Thread coordination is mostly correct, with minor issues in handling synchronization or resource sharing.	Excellent implementation of thread coordination, demonstrating a strong understanding of synchronization mechanisms, preventing race conditions and deadlocks.
Answering Assignment Questions (20%)	Responses to the assignment questions are missing or largely incorrect.	Partially correct responses to the assignment questions, but lacking in detail or accuracy.	Responses address most of the assignment questions accurately, with some gaps in thoroughness or detail.	Comprehensive and accurate responses to all assignment questions, demonstrating deep understanding and analysis.
Inclusion of Valgrind Report (10%)	No Valgrind report is included in the submission.	A Valgrind report is included but is incomplete or shows significant memory leaks or errors.	The Valgrind report is complete, showing minor memory issues or warnings.	A comprehensive Valgrind report is included, demonstrating effective memory management with no leaks or errors.
Writing a README (15%)	README is absent or lacks basic instructions on how to run the program.	README includes some instructions, but they are unclear or incomplete.	README is well-written with clear instructions on running the program, but lacks some details or explanations.	A comprehensive README is provided, with detailed, clear instructions on how to run the program and explanations of its functionality.
Providing a Makefile (15%)	No Makefile is provided, or it fails to compile the program.	Makefile is provided but has errors or lacks functionality for easy compilation.	Makefile compiles the program correctly but lacks advanced features or is not fully optimized.	An excellent Makefile is provided, facilitating easy compilation and offering features such as clean, build, and test options.

Please refer to the Style Guide for code quality examples and guidelines.