You are required to submit your work through
Blackboard.
No e-mail submissions or late work will be accepted, so please check the deadlines accurately.
Create a directory called assign4 for this assignment under cs3733 in your course directory.
Write all your programs under this assign4 directory.
Overview: Dining Philosophers (100 points + 20 bonus points)
In this assignment, we will practice thread synchronization. The principle idea for this assignment was borrowed from MIT's Dr. Shene's webpage (https://www.cs.mtu.edu/~shene/NSF-3/e-Book/MUTEX/TM-example-philos-1.html). You may refer to this webpage to obtain a better understanding of the problem, however, you cannot copy the implementation/code from this page. You have to implement the assignment and write all code yourself. [Note: for this reason, please do not use C++ for this assignment, as the solution given in the above referenced webpage utilizes C++.]
This assignment requires you to implement a solution to the famous Dining Philosophers problem using multithreading and concurrent programming techniques. The problem was the brainchild of Dr. E. W. Dijkstra, in which five philosophers spend their lives simply thinking and eating, to the exclusion of all of activities. They sit together on a circular table featuring five chairs. The table contains a single plate of spaghetti from which they apportion their servings from. However, there are only five chopsticks available, as shown in the figure.
Initially, each philosopher first starts from the "thinking" state. When a philosopher feels hungry, the philosopher will sit down and try to pick up the two closest chopsticks (i.e., the ones to the immediate left and right sides of this philosopher). If a philosopher successfully picks up both chopsticks, the philosopher eats for some period of time, and puts down the chopsticks.
To simulate the behaviors of the philosophers, you must write a multithreaded program with proper synchronization for this assignment. The assignment is divided into several components as described below.
Part 1 (20 points): Creation of Simple Threads
In this part, you will create a main program that takes a single command line parameter (an integer) to indicate the number of threads to be created. You can finish this part by following these steps:
(1) Process the command line parameter to retrive the value of nthreads.
(2) Print your name, followed by "Assignment 4: # of threads = " along with the value of nthreads.
(3) Your main function should invoke the function
void creatPhilosophers(int nthreads)
where nthreads is the parameter indicating the number of threads to be created. To create each thread, the function philosopherThread(void * pVoid) will be called, and passed a pointer to an integer containing the index of the thread.
(4) For each philosopher thread, the function philosopherThread() should simply output the statement: "This is philosopher X", where X is the index of the current thread. Afterward, the thread function can simply return NULL.
(5) In the function creatPhilosophers(), the main thread must wait for the completion of all philosopher threads using the function pthread_join(). Once all created threads join successfully, the function creatPhilosophers() will print out a message consisting of: "N threads have been completed/joined successfully!", then return.
Please name the source code for this part as assign4-part1.c. Please test with values 5 and 20 for the value of nthread. The output should be included in the REPORT.txt file within your submission, detailed under the title "Section: Part I". Moreover, please briefly explain how you have utilized the function pthread_join() in the report.
Part 2 (30 points): Use Multiple Mutexes to Manage Chopsticks
In this part, you will simulate the activities of the philosophers, whereby each philosopher is in a "thinking"-"picking up chopsticks"-"eating"-"putting down chopsticks" cycle, as shown below. That is, you need to creat four different functions to implement these four corresponding steps, where these functions have deterministic prototypes as follows:
void thinking();
void pickUpChopsticks(int threadIndex);
void eating();
void putDownChopsticks(int threadIndex);
The function pickUpChopsticks(), which simulates the activity of the "pick up chopsticks" stage, is the key function of this assignment. Note that each chopstick is shared by two neighboring philosophers and hence is a shared resource. We certainly cannot allow a philosopher to pick up a chopstick that is already being held by their neighbor, which would be a race condition. To address this problem, we can implement each chopstick as a mutex lock. Each philosopher, prior to eating, needs to lock the left chopstick as well as the right chopstick. Only after the acquisitions of both locks (representing the two chopsticks) are successful, may this philosopher begin to eat. After finishing eating by calling the function eating(), the philosopher will invoke the function putDownChopsticks() to release both locks (i.e., chopsticks), and exit the program (that is, for Part 2, each philosopher only goes through the above cycle once).
Both functions eating() and thinking() can be easily simulated by invoking a sleep function, such as usleep(), placed between two output statements "Philosopher #X: starts eating/thinking", and "Philosopher #X: ends eating/thinking", respectively. However, we should not use a fixed value for every invocation of the sleep function to emulate the different length of activites of the philosophers. Instead, we need to utilize a random number between 1 to 500. You can use function random() to obtain a random value, which could be initilized using the srandom() function using a proper seed value for the random value generator. Please utilize Google or use the man pages of these functions if you are not already familiar with their usage.
In general, two problems may arise in a carelessly designed synchronization solution: starvation and deadlock (see Dr. Shene's webpage for more descriptions of these two problems). For the above simple solution, where each philosopher only eats once and exits, there will be no starvation issue. However, the solution may still lead to deadlock. In particular, when every philosopher sits down and picks up his left chopstick at the same time, a deadlock will occur. In this case, all chopsticks are locked and none of the philosophers can successfully lock the right chopstick, which leads to a circular waiting situation (i.e., every philosopher waits for the right chopstick that is currently being locked by their right neighbor).
Note 1: Name your program for this part as assign4-part2.c; Again, you need to test your program with both 5 threads and 20 threads, and add the output in the REPORT.txt labeled under "Section: Part 2."
Note 2: Moreover, please run the program 100 times, and report the number of deadlocks encountered in your REPORT.txt
Part 3 (50 points): Ordered Eating
In this part, the deadlock problem in the solution for Part 2 will be addressed by using only one global mutex object for synchronization. In addition, the solution for this part needs to enforce the order of eating, where the philosopher with index 0 should eat first, followed by the one with index 1, and so on. The ordered eating can be achived with a conditional variable, which works together with nextIndex to indicate which philosopher should eat next. Initially, before creating all philosopher threads, nextIndex is initialized to 0.
Here, when the ith philosopher thread completes "thinking," the thread should check whether it is the ith philosopher's turn to eat or not prior to obtaining the chopsticks. If nextIndex==i, the ith philosopher will grab both chopsticks and begin eating. Otherwise, if nextIndex!=i, the thread should wait on the shared conditional variable. When a philosopher thread completes "eating," it will increment the value of nextIndex and release the lock to wake up all threads that are waiting on the conditional variable. Depending on the value of nextIndex, only one of the threads can move forward based on the determined order, where other threads will have to go back to waiting again.
Note: Name your program for this part as assign4-part3.c. Again, test the program with 5 and 20 threads. Run this program 10 times and confirm that there is no deadlock. Please include the output for one running of the case of 5 threads in the REPORT.txt under "Section: Part 3". Moreover, please explain how you design your conditional variables to enforce the order of eating. You can copy the key part of your code to help your explanation.
Part 4 [Extra credit] (20 points): Utilize pthread_mutex_trylock to solve the deadlock problem
This part is for extra credit. For this part, the same as in Part 2, you will use multiple mutex objects to represent the chopsticks. Here, you need to utilize the function pthread_mutex_trylock() (instead of lock) where it may not acquire the lock successfully and can be discovered by checking the return value of pthread_mutex_trylock. Note that, the eating order of philosophers is NOT fixed in this part. To get proper synchronization among the threads, you can utilize any number of conditional variables if necessary.
Note: Name your program for this part as assign4-part4.c. You should confirm whether you have solved the deadlock problem by running the program for 20 times with 5 threads. You need to include the idea of how you solve the deadlock problem into the REPORT.txt under "Section: Part 4". The output of one running should also be included in REPORT.txt.
Report and Submission Guidelines
REPORT:
At the end of REPORT.txt, answer the following questions:
1. List all of the people that you have collaborated with on this assignment. For each person indicate the level of collaboration (small, medium, large). Also write a few sentences describing what was discussed. Indicate whether you were mainly giving help or receiving help.
2. Do you think everything you did is correct?
3. If not, give a brief description of what is working and what progress was made on the part that is not working.
There will be a severe penalty if you do not include this REPORT.txt or the REPORT.txt is not aligned with your code.
SUBMISSION:
Zip the entire contents of, and including, the directory of assign4 as a single file a4-abc123.zip, where abc123 should be replaced with your myUTSA ID. It is very important for the TA to receive all files as a single archive.
You need to submit this single zip file through Blackboard – no e-mail submissions will be accepted.